Neden bazen sağdan sonsuz bir listeyi katlamak mümkün?
Ö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ı Stream
veri 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
Sizin interleave
yetersiz 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 stream
denklemin 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, intersperse
desen eşleştirmeye başlamadan önce bilinir list
.
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 x
belirli 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 f
durum 1 == 2
bö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 == 2
ve bu yanlış olduğu için bunu şu şekilde değerlendirecek:
-> 1 : (4 : foldr f [2,5])
şimdi değerlendiriyoruz 2 == 2
ve 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.