読者です 読者をやめる 読者になる 読者になる

foldlに無限リスト?

無限リストに foldl を適用すると停止しないと言うのを前に書いたが、なぜ停止しないのだろうか。

なぜ停止しないのか

foldl の定義はこうなっている。

foldl f z0 xs0 = lgo z0 xs0
  where
    lgo z []     =  z
    lgo z (x:xs) = lgo (f z x) xs

f を(&&) とした場合。lgo (f z x) xs で z が False の場合 x の評価はされないが、xs は評価する必要がある。無限リストであれば xs は当然無限に続くので、lgo の基底部に達することはない。

じゃあ

こういう無限リストがあった場合に、

(…((True && True) && True)… && False)

こんな関数を使えば

(&&&) :: Bool -> Bool -> Bool
_ &&& False = False
x &&& True  = x

停止できるんじゃないかと思った。

が、無限リストの末尾の要素を取り出せないのでダメだよね。