and と or の評価を短絡する仕組み

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