Por que às vezes é possível dobrar uma lista infinita da direita?

Dec 13 2020

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 Streamtipo 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

8 DanielWagner Dec 13 2020 at 11:24

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 streamser 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 intersperseiniciar a correspondência de padrões list.

5 WillemVanOnsem Dec 13 2020 at 07:39

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 fnão precisa do segundo parâmetro, por exemplo, porque o primeiro item xtem 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 fvai 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.