Dlaczego czasami można złożyć nieskończoną listę z prawej strony?

Dec 13 2020

Przechodziłem przez doskonały kurs CIS 194, kiedy utknąłem na części 5 zadania domowego 6. Obraca się ona wokół implementacji funkcji linijki bez testowania podzielności.

Odkryłem, że jest możliwe zbudowanie funkcji linijki poprzez ciągłe przeplatanie akumulatora wartościami z nieskończonej listy.

nats = [0,1,2,3,..]
[3]
[2,3,2]
[1,2,1,3,1,2,1]
[0,1,0,2,0,1,0,3,0,1,0,2,0]

Następnie próbowałem zaimplementować ten algorytm dla Streamtypu danych, którym jest lista beznil

data Stream a = Cons a (Stream a)

streamToList :: Stream a -> [a]
streamToList (Cons x xs) = x : streamToList xs

instance Show a => Show (Stream a) where
  show = show . take 20 . streamToList

streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f x = Cons x (streamFromSeed f (f x))

nats :: Stream Integer
nats = streamFromSeed succ 0

interleave x (Cons y ys) = Cons x (Cons y (interleave x ys))
foldStream f (Cons x xs) = f x (foldStream f xs)
ruler = foldStream interleave nats

Zgodnie z oczekiwaniami wystąpił błąd przepełnienia stosu, ponieważ próbowałem spasować z prawej strony. Zaskoczyło mnie jednak, że ten sam algorytm działa dla normalnych nieskończonych list.

import Data.List

interleave x list = [x] ++ (intersperse x list) ++ [x]
ruler = take 20 (foldr interleave [] [0..])

czego mi brakuje? Dlaczego jedna implementacja działa, a druga nie?

Odpowiedzi

8 DanielWagner Dec 13 2020 at 11:24

Twój interleavejest niewystarczająco leniwy. Magiczną rzeczą, którą muszą zrobić prawidłowe zawinięcia, aby pracować na nieskończonych strukturach, jest niedokładne sprawdzanie wyniku wartości zawinięcia przed wykonaniem pierwszego bitu obliczenia. Więc:

interleave x stream = Cons x $ case stream of
    Cons y ys -> Cons y (interleave x ys)

To produkuje Cons x _przed inspekcją stream; w przeciwieństwie do tego, twoja wersja wymaga streamnieco oceny, zanim będzie mogła przejść do prawej strony równania, co zasadniczo wymusza wykonanie całego zwinięcia, zanim zostanie utworzony konstruktor.

Możesz to również zobaczyć w swojej wersji listy interleave:

interleave x list = [x] ++ intersperse x list ++ [x]

Pierwszy element zwróconej listy ( x) jest znany przed intersperserozpoczęciem dopasowywania wzorców w dniu list.

5 WillemVanOnsem Dec 13 2020 at 07:39

Możemy sprawdzić kod źródłowy foldr[src] . Mniej hałaśliwa wersja wygląda następująco:

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Haskell nie ocenia chętnie. Oznacza to zatem, że jeśli nie potrzebujesz (foldr f z xs) , nie oceni akumulatora. Oznacza to więc, że fnie potrzebuje drugiego parametru, na przykład ponieważ pierwsza pozycja xma określoną wartość, nie będzie oceniać akumulatora.

Na przykład jeśli wdrażamy takeWhileNeq:

takeWhileNeq a = foldr f []
    where f x xs -> if x == a then [] else (x:xs)

jeśli zatem uruchomić to na liście takeWhileNeq 2 [1,4,2,5], to nie będzie oceniać cokolwiek . Jeśli jednak chcemy wydrukować wynik, oceni to jako:

   f 1 (foldr f [4,2,5])

i fsprawdzi, czy 1 == 2skoro tak nie jest, wróci (x:xs), więc:

-> 1 : foldr f [4,2,5]

więc teraz oceni 4 == 2, a ponieważ to jest fałsz, oceni to w następujący sposób:

-> 1 : (4 : foldr f [2,5])

teraz oceniamy 2 == 2, a ponieważ tak jest True, funkcja zwraca pustą listę i pobiera akumulator, więc nigdy nie będzie patrzeć na foldr f [5]:

-> 1 : (4 : [])

W przypadku nieskończonej listy spowoduje to również utworzenie pustej listy i zignoruje zawinięcie pozostałej części listy.