Warum ist es manchmal möglich, eine unendliche Liste von rechts zu falten?

Question

Ich habe den hervorragenden CIS 194-Kurs durchlaufen, als ich bei Teil 5 von Hausaufgabe 6 feststeckte. Es geht darum, die Linealfunktion ohne Teilbarkeitstests zu implementieren .

Ich fand heraus, dass es möglich ist, die Linealfunktion zu erstellen, indem ein Akkumulator kontinuierlich mit Werten aus einer unendlichen Liste durchsetzt wird.

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]

Dann habe ich versucht, diesen Algorithmus für den StreamDatentyp zu implementieren, der eine Liste ohne istnil

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

Wie erwartet wurde ein Stackoverflow-Fehler angezeigt, da ich versucht habe, von rechts zu folden. Ich war jedoch überrascht zu sehen, dass der gleiche Algorithmus für normale unendliche Listen funktioniert.

import Data.List

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

Was vermisse ich? Warum funktioniert eine Implementierung, die andere nicht?

Answer 1

Ihr interleaveist nicht ausreichend faul. Die magische Sache, die richtige Falten tun müssen, um an unendlichen Strukturen zu arbeiten, besteht darin, das Ergebnis des gefalteten Werts nicht zu genau zu untersuchen, bevor sie die erste Berechnung durchführen. So:

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

Dies erzeugt Cons x _vor der Inspektion stream; Im Gegensatz dazu muss Ihre Version streamein wenig ausgewertet werden, bevor sie auf die rechte Seite der Gleichung übertragen werden kann. Dies erzwingt im Wesentlichen die gesamte Falte, bevor ein Konstruktor erstellt wird.

Sie können dies auch in Ihrer Listenversion von sehen interleave:

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

Das erste Element der zurückgegebenen Liste ( x) ist bekannt, bevor intersperseder Mustervergleich gestartet wird list.

Answer 2

Wir können den Quellcode von foldr[src] überprüfen . Eine weniger laute Version sieht aus wie:

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

Haskell bewertet nicht eifrig. Dies bedeutet, dass der Akku nicht ausgewertet wird, es sei denn, Sie benötigen (foldr f z xs) ihn. Dies bedeutet also, fdass der zweite Parameter nicht benötigt wird, beispielsweise weil das erste Element xeinen bestimmten Wert hat, wird der Akkumulator nicht ausgewertet.

Zum Beispiel, wenn wir implementieren takeWhileNeq:

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

Wenn wir also diese auf einer Liste laufen takeWhileNeq 2 [1,4,2,5], dann wird es nicht beurteilen nichts . Wenn wir das Ergebnis jedoch drucken möchten, wird dies wie folgt bewertet:

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

und fprüft, ob es 1 == 2, da dies nicht der Fall ist, zurückkehrt (x:xs), also:

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

Jetzt wird es ausgewertet 4 == 2, und da dies falsch ist, wird es ausgewertet, um:

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

Jetzt werten wir aus 2 == 2, und da dies Trueder Fall ist , gibt die Funktion die leere Liste zurück und speichert den Akkumulator, sodass sie niemals Folgendes betrachtet foldr f [5]:

-> 1 : (4 : [])

Bei einer unendlichen Liste wird daher auch eine leere Liste erstellt und das Falten des Restes der Liste ignoriert.