Neden bazen sağdan sonsuz bir listeyi katlamak mümkün?

Dec 13 2020

Ödev 6'nın 5. Bölümünde takılıp kaldığımda mükemmel CIS 194 kursundan geçiyorum . Herhangi bir bölünebilirlik testi olmadan cetvel işlevini uygulama etrafında dönüyor .

Sonsuz bir listeden değerler içeren bir akümülatörü sürekli olarak serpiştirerek cetvel işlevini oluşturmanın mümkün olduğunu buldum.

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]

Daha sonra bu algoritmayı Streamveri türü için uygulamayı denedim.nil

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

Beklendiği gibi, sağdan katlamaya çalıştığım için stackoverflow hatası aldım. Bununla birlikte, aynı algoritmanın normal sonsuz listeler için çalıştığını görünce şaşırdım.

import Data.List

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

Neyi kaçırıyorum? Neden bir uygulama çalışırken diğeri çalışmıyor?

Yanıtlar

8 DanielWagner Dec 13 2020 at 11:24

Sizin interleaveyetersiz tembeldir. Sağ kıvrımların sonsuz yapılar üzerinde çalışması için yapması gereken sihirli şey, ilk hesaplamayı yapmadan önce katlanmış değerin sonucunu çok yakından incelememektir. Yani:

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

Bu, Cons x _incelemeden önce üretir stream; aksine, sürümünüzün streamdenklemin sağ tarafına geçmeden önce biraz değerlendirilmesi gerekir , bu da esasen tüm katlamayı herhangi bir kurucu üretilmeden önce gerçekleşmeye zorlar.

Bunu aşağıdaki liste sürümünüzde de görebilirsiniz interleave:

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

Döndürülen listenin ( x) ilk öğesi, interspersedesen eşleştirmeye başlamadan önce bilinir list.

5 WillemVanOnsem Dec 13 2020 at 07:39

foldr[Src] kaynak kodunu inceleyebiliriz . Daha az gürültülü bir versiyon şuna benzer:

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

Haskell yok değil hevesle değerlendirir. Bu, ihtiyacınız olmadıkça (foldr f z xs)akümülatörü değerlendirmeyeceği anlamına gelir . Bu f, ikinci parametreye ihtiyaç duymadığı anlamına gelir, örneğin ilk öğe xbelirli bir değere sahip olduğundan , toplayıcıyı değerlendirmeyecektir.

Örneğin şunları uygularsak takeWhileNeq:

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

eğer bunu bir liste üzerinde çalıştırırsak takeWhileNeq 2 [1,4,2,5], o zaman hiçbir şeyi değerlendirmez . Ancak sonucu yazdırmak istersek, bunu şu şekilde değerlendirecektir:

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

ve fdurum 1 == 2böyle olmadığına göre geri dönüp dönmeyeceğini inceleyecek (x:xs), yani:

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

yani şimdi değerlendirecek 4 == 2ve bu yanlış olduğu için bunu şu şekilde değerlendirecek:

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

şimdi değerlendiriyoruz 2 == 2ve bu olduğundan True, işlev boş listeyi döndürür ve toplayıcıyı tamamlar , böylece asla şuna bakmayacaktır foldr f [5]:

-> 1 : (4 : [])

Sonsuz bir liste için, bu nedenle de boş bir liste ortaya çıkar ve listenin geri kalanını katlamayı göz ardı eder.