Mengapa terkadang mungkin untuk melipat daftar tak terbatas dari kanan?

Dec 13 2020

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

8 DanielWagner Dec 13 2020 at 11:24

Anda interleavekurang 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 streamdievaluasi 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 interspersememulai pencocokan pola list.

5 WillemVanOnsem Dec 13 2020 at 07:39

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 ftidak perlu parameter kedua, misalnya karena item pertama xmemiliki 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 fakan 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.