Haskellの評価戦略とfoldl/foldr (2)

プログラミング Haskell

前の記事 d:id:linglang:20110909:1315561320 で、

  foldl (<+>) (z<+>a0) (a1:[a2,a3,a4,a5,a6])

という式を評価するとき、2通りの簡約(計算)順序があることを示しました。

  foldl (<+>) b0 (a1:[a2,a3,a4,a5,a6])           {- 内部簡約 -}
  foldl (<+>) ((z<+>a0)<+>a1) (a2:[a3,a4,a5,a6]) {- 最外最左簡約 -}

Haskellでfoldlを評価する

今度は、Haskellの評価戦略である、最外最左簡約でfoldlを評価してみます。
一番外側から順に展開していくので...

  result =
    foldl (<+>) z (a0:[a1,a2,a3,a4,a5,a6]) =
    foldl (<+>) (z<+>a0) (a1:[a2,a3,a4,a5,a6]) =
    foldl (<+>) ((z<+>a0)<+>a1) (a2:[a3,a4,a5,a6]) =
    foldl (<+>) (((z<+>a0)<+>a1)<+>a2) (a3:[a4,a5,a6]) =
    foldl (<+>) ((((z<+>a0)<+>a1)<+>a2)<+>a3) (a4:[a5,a6]) =
    foldl (<+>) (((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4) (a5:[a6]) =
    foldl (<+>) ((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5) (a6:[]) =
    foldl (<+>) (((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) [] =
    (((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6)

となります。ここまで来ると、あとは一番内側しか簡約できる候補がないので、

  result =
    (((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) =
    ((((((b0<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) =
    (((((b1<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) =
    ((((b2<+>a3)<+>a4)<+>a5)<+>a6) =
    (((b3<+>a4)<+>a5)<+>a6) =
    ((b4<+>a5)<+>a6) =
    (b5<+>a6) = b6

という風に式が消化されていきます。
せっかく末尾再帰で記述したのに、なんだか内部簡約の時のfoldrと同じような感じになってしまいました。

これは、場合によっては嬉しくないので、Haskellの標準仕様(Haskell2010)には、内部簡約と同じ順序で計算を行う foldl' という関数が用意されています。

Haskellの評価戦略とfoldlはあまり相性がよくない

さて、(今更ですが)なんで私がこんな記事を書き出したのかというと、[twitter:@kazu_yamamoto] さんとの以下のような呟きが発端です。

ここで、[twitter:@kazu_yamamoto]さんが例に出されている

  foldl (&&) True [False,(trace "Haha!" True),True,True]

という式を同じように評価してみます。
最外最左簡約ですので、

  foldl (&&) True [False,(trace "Haha!" True),True,True] =
    foldl (&&) True (False:[(trace "Haha!" True),True,True]) =
    foldl (&&) (True&&False) ((trace "Haha!" True):[True,True]) =
    foldl (&&) ((True&&False)&&(trace "Haha!" True)) (True:[True]) =
    foldl (&&) (((True&&False)&&(trace "Haha!" True))&&True) (True:[]) =
    foldl (&&) ((((True&&False)&&(trace "Haha!" True))&&True)&&True) [] =
    ((((True&&False)&&(trace "Haha!" True))&&True)&&True) =
    (((False&&(trace "Haha!" True))&&True)&&True) = {- 注:(trace ...)は評価されない -}
    ((False&&True)&&True) = 
    (False&&True) = False

という簡約順序になります。論理積の途中にFalseが混じっているので、評価を打ち切ってほしいところですが、

  • 最外最左簡約によって畳み込みが全て式に展開されてしまう
  • foldl が演算を左結合で繋げるので、演算を途中で打ち切れない

ために、期待に沿わない結果となってしまいました。

ここでfoldrの出番

実は、上の式でfoldlの代わりにfoldrを使うと、あっけなく計算が終わります。

  foldr (&&) True [False,(trace "Haha!" True),True,True] =
    foldr (&&) True (False:[(trace "Haha!" True),True,True]) =
    False && (foldr (&&) True [(trace "Haha" True),True,True]) =
    False {- False && _ = False なので！ -}

こちらの方が、元々の期待に沿った動作なのではないでしょうか？