Mengapa terkadang mungkin untuk melipat daftar tak terbatas dari kanan?
Saya telah melalui kursus CIS 194 yang sangat baik ketika saya terjebak di Bagian 5 dari Pekerjaan Rumah 6. Ini berkisar pada penerapan fungsi penggaris tanpa pengujian pembagian.
Saya menemukan bahwa adalah mungkin untuk membangun fungsi penggaris dengan terus menerus menyelipkan akumulator dengan nilai dari daftar tak terbatas.
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]
Kemudian saya mencoba menerapkan algoritma ini untuk Stream
tipe data yang merupakan daftar tanpanil
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
Seperti yang diharapkan, saya mendapat kesalahan stackoverflow karena saya mencoba melipat dari kanan. Namun, saya terkejut melihat algoritma yang sama berfungsi untuk daftar normal tak terbatas.
import Data.List
interleave x list = [x] ++ (intersperse x list) ++ [x]
ruler = take 20 (foldr interleave [] [0..])
Apa yang saya lewatkan? Mengapa satu implementasi berhasil sementara yang lainnya tidak?
Jawaban
Anda interleave
kurang malas. Hal ajaib yang harus dilakukan lipatan kanan untuk mengerjakan struktur tak hingga adalah dengan tidak memeriksa hasil nilai terlipat terlalu dekat sebelum mereka melakukan komputasi bit pertama. Begitu:
interleave x stream = Cons x $ case stream of
Cons y ys -> Cons y (interleave x ys)
Ini menghasilkan Cons x _
sebelum memeriksa stream
; sebaliknya, versi Anda perlu stream
dievaluasi sedikit sebelum dapat diteruskan ke sisi kanan persamaan, yang pada dasarnya memaksa seluruh lipatan terjadi sebelum konstruktor apa pun diproduksi.
Anda juga dapat melihat ini di versi daftar Anda dari interleave
:
interleave x list = [x] ++ intersperse x list ++ [x]
Elemen pertama dari daftar yang dikembalikan ( x
) diketahui sebelum intersperse
memulai pencocokan pola list
.
Kita dapat memeriksa kode sumber foldr[src] . Versi yang tidak terlalu berisik terlihat seperti:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Haskell tidak mengevaluasi dengan antusias. Jadi, ini berarti bahwa, kecuali Anda membutuhkannya (foldr f z xs)
, akumulator tidak akan dievaluasi. Artinya f
tidak perlu parameter kedua, misalnya karena item pertama x
memiliki nilai tertentu, maka akumulator tidak akan dievaluasi.
Misalnya jika kita menerapkan takeWhileNeq
:
takeWhileNeq a = foldr f []
where f x xs -> if x == a then [] else (x:xs)
jika kita menjalankan ini pada daftar takeWhileNeq 2 [1,4,2,5]
, maka itu tidak akan mengevaluasi apapun . Namun jika kami ingin mencetak hasilnya, itu akan mengevaluasi ini sebagai:
f 1 (foldr f [4,2,5])
dan f
akan memeriksa jika 1 == 2
, karena bukan itu masalahnya, itu akan kembali (x:xs)
, jadi:
-> 1 : foldr f [4,2,5]
jadi sekarang ini akan mengevaluasi 4 == 2
, dan karena ini salah, itu akan mengevaluasi ini menjadi:
-> 1 : (4 : foldr f [2,5])
sekarang kita mengevaluasi 2 == 2
, dan karena ini True
, fungsi mengembalikan daftar kosong, dan memasukkan akumulator, sehingga tidak akan pernah melihat foldr f [5]
:
-> 1 : (4 : [])
Untuk daftar tak terbatas, itu juga akan menghasilkan daftar kosong dan mengabaikan melipat sisa daftar.