Por que às vezes é possível dobrar uma lista infinita da direita?
Tenho feito o excelente curso CIS 194 quando fiquei preso na Parte 5 do dever de casa 6. Ele gira em torno da implementação da função de régua sem nenhum teste de divisibilidade.
Descobri que é possível construir a função de régua intercalando continuamente um acumulador com valores de uma lista infinita.
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]
Então tentei implementar este algoritmo para o Stream
tipo de dados, que é uma lista semnil
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
Como esperado, recebi um erro de stackoverflow porque estava tentando fazer fold da direita. No entanto, fiquei surpreso ao ver o mesmo algoritmo funcionar para listas infinitas normais.
import Data.List
interleave x list = [x] ++ (intersperse x list) ++ [x]
ruler = take 20 (foldr interleave [] [0..])
o que estou perdendo? Por que uma implementação funciona enquanto a outra não?
Respostas
Você interleave
é insuficientemente preguiçoso. A coisa mágica que as dobras corretas devem fazer para trabalhar em estruturas infinitas é não inspecionar o resultado do valor dobrado muito de perto antes de fazer o primeiro bit de cálculo. Assim:
interleave x stream = Cons x $ case stream of
Cons y ys -> Cons y (interleave x ys)
Isso produz Cons x _
antes de inspecionar stream
; em contraste, sua versão precisa stream
ser avaliada um pouco antes de poder passar para o lado direito da equação, o que essencialmente força a dobra inteira a acontecer antes que qualquer construtor seja produzido.
Você também pode ver isso em sua versão de lista de interleave
:
interleave x list = [x] ++ intersperse x list ++ [x]
O primeiro elemento da lista retornada ( x
) é conhecido antes de intersperse
iniciar a correspondência de padrões list
.
Podemos inspecionar o código-fonte de foldr[src] . Uma versão menos barulhenta parece:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Haskell não avalia com entusiasmo. Isso significa que, a menos que você precise (foldr f z xs)
, ele não avaliará o acumulador. Isso significa que f
não precisa do segundo parâmetro, por exemplo, porque o primeiro item x
tem um determinado valor, ele não avaliará o acumulador.
Por exemplo, se implementarmos takeWhileNeq
:
takeWhileNeq a = foldr f []
where f x xs -> if x == a then [] else (x:xs)
se executarmos isso em uma lista takeWhileNeq 2 [1,4,2,5]
, então ele não avaliará nada . No entanto, se quisermos imprimir o resultado, ele irá avaliar isso como:
f 1 (foldr f [4,2,5])
e f
vai verificar se 1 == 2
, como não é o caso, ele vai voltar (x:xs)
, então:
-> 1 : foldr f [4,2,5]
então agora ele irá avaliar 4 == 2
, e como isso é falso, ele irá avaliar para:
-> 1 : (4 : foldr f [2,5])
agora avaliamos 2 == 2
, e como isso é True
, a função retorna a lista vazia e ingores o acumulador, de modo que nunca irá olhar para foldr f [5]
:
-> 1 : (4 : [])
Para uma lista infinita, também resultará em uma lista vazia e ignorará a dobragem do resto da lista.