無限のリストを右から折りたたむことができる場合があるのはなぜですか？

Dec 13 2020

宿題6のパート5で立ち往生したとき、私は優れたCIS194コースを受講しました。これは分割可能性テストなしで定規機能を実装することを中心に展開します。

アキュムレータに無限リストの値を連続的に散在させることで、定規関数を構築できることがわかりました。

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]

次にStream、リストのないデータ型にこのアルゴリズムを実装してみました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

予想通り、右から折りたたむとスタックオーバーフローエラーが発生しました。しかし、通常の無限リストに対して同じアルゴリズムが機能するのを見て驚いた。

import Data.List

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

何が足りないのですか？一方の実装が機能するのに、もう一方は機能しないのはなぜですか？

回答

8 DanielWagner Dec 13 2020 at 11:24

あなたinterleaveは十分に怠惰です。無限の構造を処理するために右に折りたたむ必要がある魔法のことは、最初の計算を行う前に、折りたたまれた値の結果をあまり詳しく調べないことです。そう：

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

これはCons x _検査前に生成されstreamます; 対照的に、バージョンはstream、方程式の右辺に渡される前に少し評価する必要があります。これにより、コンストラクターが生成される前に、基本的にフォールド全体が発生します。

これは、リストバージョンのinterleave：でも確認できます。

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

返されたリストの最初の要素（x）は、でintersperseパターンマッチングを開始する前にわかっていlistます。

5 WillemVanOnsem Dec 13 2020 at 07:39

foldr[src]のソースコードを調べることができます。ノイズの少ないバージョンは次のようになります。

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

Haskellは熱心に評価していません。したがって、これは、必要が ない限り(foldr f z xs)、アキュムレータを評価しないことを意味します。したがって、これfは2番目のパラメータを必要としないことを意味します。たとえば、最初の項目xには特定の値があるため、アキュムレータは評価されません。

たとえば、実装する場合takeWhileNeq：

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

したがって、これをリストtakeWhileNeq 2 [1,4,2,5]で実行すると、何も評価されません。ただし、結果を印刷する場合は、次のように評価されます。

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

そして、そうではないので、それが返されるfかどうかを検査します。1 == 2(x:xs)

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

これで、が評価され4 == 2ます。これはfalseであるため、次のように評価されます。

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

ここで、を評価します。2 == 2これはTrueであるため、関数は空のリストを返し、アキュムレータを呼び出します。したがって、次のものは参照されませんfoldr f [5]。