Dlaczego czasami można złożyć nieskończoną listę z prawej strony?
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 Stream
typu 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
Twój interleave
jest 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 stream
nieco 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 intersperse
rozpoczęciem dopasowywania wzorców w dniu list
.
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 f
nie potrzebuje drugiego parametru, na przykład ponieważ pierwsza pozycja x
ma 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 f
sprawdzi, czy 1 == 2
skoro 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.