Pourquoi est-il parfois possible de plier une liste infinie à partir de la droite?
J'ai suivi l'excellent cours CIS 194 lorsque je suis resté coincé sur la partie 5 de Devoirs 6. Il tourne autour de l'implémentation de la fonction règle sans aucun test de divisibilité.
J'ai trouvé qu'il est possible de construire la fonction de règle en intercalant continuellement un accumulateur avec des valeurs d'une liste infinie.
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]
Ensuite, j'ai essayé d'implémenter cet algorithme pour le Stream
type de données qui est une liste sansnil
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
Comme prévu, j'ai eu une erreur de stackoverflow car j'essayais de me plier par la droite. Cependant, j'ai été surpris de voir le même algorithme fonctionner pour des listes infinies normales.
import Data.List
interleave x list = [x] ++ (intersperse x list) ++ [x]
ruler = take 20 (foldr interleave [] [0..])
Qu'est-ce que je rate? Pourquoi une mise en œuvre fonctionne alors que l'autre ne fonctionne pas?
Réponses
Vous n'êtes interleave
pas suffisamment paresseux. La chose magique que les plis droits doivent faire pour travailler sur des structures infinies est de ne pas inspecter le résultat de la valeur pliée de trop près avant de faire le premier bit de calcul. Donc:
interleave x stream = Cons x $ case stream of
Cons y ys -> Cons y (interleave x ys)
Cela produit Cons x _
avant l'inspection stream
; en revanche, votre version doit stream
être évaluée un peu avant de pouvoir passer au côté droit de l'équation, ce qui oblige essentiellement le pli entier à se produire avant qu'un constructeur ne soit produit.
Vous pouvez également le voir dans votre version de liste de interleave
:
interleave x list = [x] ++ intersperse x list ++ [x]
Le premier élément de la liste renvoyée ( x
) est connu avant de intersperse
commencer la recherche de motifs list
.
Nous pouvons inspecter le code source de foldr[src] . Une version moins bruyante ressemble à:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Haskell n'évalue pas avec empressement. Cela signifie donc que, sauf si vous en avez besoin (foldr f z xs)
, il n'évaluera pas l'accumulateur. Cela signifie donc que f
n'a pas besoin du deuxième paramètre, par exemple parce que le premier élément x
a une certaine valeur, il n'évaluera pas l'accumulateur.
Par exemple si nous implémentons takeWhileNeq
:
takeWhileNeq a = foldr f []
where f x xs -> if x == a then [] else (x:xs)
si nous exécutons donc ceci sur une liste takeWhileNeq 2 [1,4,2,5]
, alors il n'évaluera rien . Si nous voulons cependant imprimer le résultat, il évaluera ceci comme:
f 1 (foldr f [4,2,5])
et f
inspectera si 1 == 2
, puisque ce n'est pas le cas, il reviendra (x:xs)
, donc:
-> 1 : foldr f [4,2,5]
alors maintenant, il évaluera 4 == 2
, et comme c'est faux, il évaluera ceci à:
-> 1 : (4 : foldr f [2,5])
maintenant nous évaluons 2 == 2
, et puisque c'est le cas True
, la fonction retourne la liste vide et ingère l'accumulateur, donc elle ne regardera jamais foldr f [5]
:
-> 1 : (4 : [])
Pour une liste infinie, il en résultera donc également une liste vide et ignorera le pliage du reste de la liste.