and リストの途中に False の要素が現れたり、or リストを評価している途中にTrue が現れればリストを最後まで評価しなくても結果が確定します。このような仕組みを短絡と言います。
import Debug.Trace myFoldl f z0 xs0 = lgo z0 xs0 where lgo z [] = trace(show z) z lgo z (x:xs) = trace("go (f " ++ show z ++ " " ++ show x ++ ") xs") (lgo (f z x) xs) myFoldr k z xs = go xs where -- リストの要素に出会う度 myFoldr が再帰して呼ばれ、 -- 最後に初期値が返される。 go [] = trace("return:"++show z) z -- y の値がTrueであれば "True `myOr` go ys" となり、 -- "myOr True _" であるから go ys は評価されず捨てられる。 go (y:ys) = trace("call myFoldr: "++show y++" `k` go ys")(y `k` go ys) myOr True _ = trace("myOr True _ -> True " ) True myOr False x = trace("myOr False x -> x " ) x orR = myFoldr myOr False -- 初期値を False にした foldr が使用されている。 orL = myFoldl myOr False
この例は or の場合ですけれども、初期値を False として各要素をチェックして行き、Trueに出会うと上のパターンにマッチするので、それ以降の評価と関係なく True が確定します。
myOr True _ = True myOr False x = x
foldr を使った場合。
ghci> orR [1==3,1==2,False,length [1,2]>0] call myFoldr: False `k` go ys myOr False x -> x -- 値が確定しないので再帰 call myFoldr: False `k` go ys myOr False x -> x -- 値が確定しないので再帰 call myFoldr: False `k` go ys myOr False x -> x -- 値が確定しないので再帰 call myFoldr: True `k` go ys myOr True _ -> True True ghci> orR [1==1,1==2,False,length [1,2]>0] call myFoldr: True `k` go ys myOr True _ -> True -- 最初に確定しているので以下の要素は評価されない。 -- _ 以下の要素にかかわらず True が返される。 True
foldlを使うと最後まで評価してしまう。
ghci> orL [1==3,1==2,False,length [1,2]>0] go (f False False) xs myOr False x -> x go (f False False) xs myOr False x -> x go (f False False) xs myOr False x -> x go (f False True) xs myOr False x -> x True True ghci> orL [1==1,1==2,False,length [1,2]>0] go (f False True) xs myOr False x -> x go (f True False) xs myOr True _ -> True go (f True False) xs myOr True _ -> True go (f True True) xs myOr True _ -> True True True