途中脱出のある反復計算

Haskell

そのまえに

もとネタは[id:Dekosuke:20100810]「breakのあるfor文をHaskellで書きなおす」という記事です．

この記事に対して，直感的に[id:nobsun:20100118]の双方向畳み込みfoldで汎用的に表現できる」と思って，コメントを付けました．ところが，その後が波瀾万丈 < 大袈裟なやつ

  • 途中脱出の例題を考えてみた．
  • ちゃちゃっと書いたサンプルコードが途中脱出してくれない．
  • あわてて取り消しのコメントを．
  • どうも原因がよくわからない，上手くいくはずなのに．
  • foldの定義の所為だと思い込む．
  • 何人かにfoldを説明してみた．
  • coolじゃないfoldの代替定義をでっちあげた．
  • 代替foldリファクタリング．
  • 代替foldを何人かに説明してみた．
  • 代替foldでよいことは納得できる．
  • でもやっぱり，元のfoldで上手くいかなり理由がわからない．
  • よくよく考えたら，そもそものfoldの使い方がわるかった．

ふう．（というわけで，以前，私に fold のデタラメ話を聞かされた方，すみません．）

もうひとつ

ちょっと言い訳．

命令プログラムと関数プログラムとはコンピュータ上での計算のためのものであるという点では共通のものなのです．しかし，そもそもプログラムとは何か，プログラムの実行とは何か，という根本的なよりどころが全然違うのです．これでは，一貫性のある対応をとって一貫性のある説明を正確に行うのは無理だろう．下手に不正確な説明をすると，後でワケワカメになる人がいるからよくない．というのが正直なところでした．

「...というのが正直なところでした．」と過去形なのは，いまはすこし考えを改めたようかと思っているのです．一貫性を保って説明すればよいので，すくなくともそういう説明努力は自分にとって大事なことだから．

反復計算

反復計算ってなんだろか．

  • 「同じ処理」が
  • 「異なるデータ」に対して
  • 「連続して」適用されている

ということだよね．反復の1つのパターンは，なにかの「集合の要素をなんらかの順に辿って」同じ処理をするというものです．まずは，このパターンの反復を考えることにします．また，「なんらかの順に辿る」ということなので，集合の表現はリストに固定しても，汎用性は失われないものとしてもよいはず（その範囲で議論するつもり）です．（unfold タイプの反復については，別の機会に．）

map f で表現する反復計算

最もシンプルなのは，1つずつのデータに適用する処理がそれぞれ独立している場合です．どういうことかというと，反復計算で1つのステップの計算が前のステップの計算結果には依存しないような場合です．たとえば，与えられた整数のリストに対して，それぞれの要素を二乗するような計算を考えます．

 squares []     = []
 squares (x:xs) = x^2 : squares xs

これは，以下の再帰パターン

 foo []     = []
 foo (x:xs) = f x : foo xs

のように一般化できます．2行目は「foo を，先頭が x，のこりの部分が xs であるようなリストに適用したものは，x^2 を，のこりの部分 xs に squares を適用して構成されるリストの先頭に追加したものである．」と読めます．
これは良くあるパターンなので標準プレリュードで高階関数が定義されています．

 map :: (a -> b) -> [a] -> [b]
 map f []     = []
 map f (x:xs) = f x : map f xs

したがって，

 squares = map (^2)

foldr f a で表現する反復計算

map f は反復計算の一表現であることを見ましたが，命令プログラミングでは反復計算の結果を一つのデータにまとめることが多いでしょう．たとえば，単に二乗する計算だけではなく，和にまとめることを考えることにします．このような関数 sumSquare は，単純に再帰で考えれば簡単に定義できて，

sumSquares :: [Int] -> Int
sumSquares []     = 0
sumSquares (x:xs) = x ^ 2 + sumSquares xs

となります．これは，

foo :: [a] -> b
foo []     = e
foo (x:xs) = f x `o` foo xs

というよく現れる再帰パターンになっています．このパターンはほんとうによく現れるので標準プレリュードの高階関数 foldr として抽象化されています．定義は以下のとおりです．

 foldr :: (a -> b -> b) -> b -> [a] -> b
 foldr g z []     = z
 foldr g z (x:xs) = g x (foldr g z xs)

先ほどの二乗和の関数をリスト[1..5]に適用する場合を展開して考えてみると，以下のような計算になっています．

 1   : (2   : (3   : (4   : (5   : []))))

               ↓ 

 1^2 + (2^2 + (3^2 + (4^2 + (5^2 + 0 ))))

foldr の第一引数 g は以下のように 2つの関数 f, ⊕ を組み合わせたものと考えると

 g = \ x y -> f x ⊕ y 
   = \ x y -> (⊕) (f x) y
   = \ x -> (⊕) (f x)
   = (⊕) . f

です．g の第一引数 x は今見ている要素，第二引数 y は後の計算全体です．すなわち，この関数は

（今見ている要素に対する計算）⊕（残りの計算全体に対する計算）

というわけです．そうすると反復計算 foldr (\ x y -> f x ⊕ y) z [1..5] は

  1   :  (2   :  (3   : (4   :  (5  :  []))))

を

  f 1 ⊕ (f 2 ⊕ (f 3 ⊕ (f 4 ⊕ (f 5 ⊕ z))))

に変換しているわけです．命令プログラミングでの反復計算がリスト構造と対応するのが判ります．
したがって，sumSquares は

 sumSquares = foldr ((+).(^2)) 0

また，map は実は foldr の特別な場合であることも判りますよね．map f が g = f，(⊕) = (:) としたときの，foldr g すなわち foldr ((:).f) に対応しています．

 map f = foldr ((:).f) []

foldl f a で表現する反復計算

命令プログラミングにおいては反復計算があらわれるときに，ある周回の計算がそれまでの周回の計算に依存することがよくあります．たとえば，上で定義た sumSquare にしても

int s = 0;
for (int i = 1; i <= 5; i++) {
  s = s + i * i;
}

のような for ループになるでしょう．この反復計算をHaskellで表現すると

 sumSquare = ss 0
   where 
     ss s []     = s
     ss s (x:xs) = ss (s+x^2) xs

この反復計算パターンは

 foo = iter z
   where
     iter a []     = a
     iter a (x:xs) = iter (f a x) xs

（これは，いわゆる末尾再帰として知られる再帰パターンです．）ここにある反復を表現しているローカル関数 iter の第一引数 a がそれまでの周回計算の結果をためています．このような引数のことをアキュムレータあるいは蓄積パラメータといいます．
このようなパターンの計算もよくあるので，プレリュードに foldl として定義されています．

 foldl :: (a -> b -> a) -> a -> [b] -> a
 foldl f z []     = z
 foldl f z (x:xs) = foldl f (f z x) xs

foldl の第二引数 z がアキュムレータになっていることがわかりますよね．
これを使って，二乗和 sumSquares を定義すると

 sumSquare = fold (\ x y -> x + y^2) 0

となります．sumSquare [1..5] を展開してみると，

 ((((0 + 1^2) + 2^2) + 3^2) + 4^2) + 5^2

となるわけです．一般化して，foldl (\ x y -> x ⊗ f y) z を [1..5]に適用して展開すると

  ((((z ⊗ f 1) ⊗ f 2) ⊗ f 3) ⊗ f 4) ⊗ f 5

となるわけです．foldl はアキュムレータを使って後ろの計算にそれまでの計算の結果を伝えています．どちらかというと命令プログラミングのループ計算のニュアンスはことらだと思われます．

foldr の構造と foldl の構造との相違

foldr の反復計算パターンは

  結果 ＝ 最初の計算 ⊕ 残りの計算

です．「最初の計算」部分はfoldrの第三引数であるリストの最初の要素に対する計算に対応します．この計算パターンの面白いところは，二項演算子⊕が第二オペランドについて非正格である場合には，残りの計算が必要ないときには行われないということです．例えば，⊕が論理積&&である場合，「最初の計算」がFalseになったら，残りの計算は必要ないので計算されない．これが，命令プログラミングでのループからの途中脱出ということになります．

foldl の反復計算パターンは

  結果 ＝ 手前の計算 ⊗ 最後の計算

です．「最後の計算」部分はfoldlの第三引数であるリストの最後の要素に対する計算に対応します．こちらの方は結果を得るのに最後の計算のところまで辿り着く必要があることがわかる．つまり，途中脱出は構造的に困難です．

scanl

foldl では途中脱出は困難です．以下のような問題を考えましょう．

整数のリストの先頭から要素の二乗和を計算し，その自乗和が指定した数を超える手前までの先頭部分リストと残りの部分リストとの対を返す関数 splitBySumSquares :: Int -> [Int] -> ([Int],[Int])を定義せよ．

再帰でナイーブに考えれば，いくつめまでの二乗和が制限以内におさまるかがわかればよいので，

 splitBySumSquares b xs = splitAt (iter 0 0 xs) xs
   where
     iter s c []     = c
     iter s c (x:xs) = if s' > b then c else iter s' (c+1) xs
                       where s' = s+x^2

というわけです．アキュムレータを使っても，簡単に途中脱出が表現できています．foldlで上手く表現できないのは，後の計算が保留できないからです．周回毎にアキュムレータの値をリストにはきだすことで，後の計算を保留できるようにしたのが，プレリューで定義されている関数 scanl です．

scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl f a bs = a : case bs of
                     []   -> []
                     x:xs -> scanl f (f a x) xs

これを使えば，splitBySumSquares は

 splitBySumSquares b xs = splitAt (length.tail.takeWhile (b>).scanl f 0 $ xs) xs
   where f a x = a + x^2

mapAccumL

scanl はアキュムレータで後ろの計算にそれまでの計算結果を伝えつつ，アキュムレータの足跡をリストに書きだしています．これで後ろに送るアキュムレータと足跡として残すものを分けたものが，Data.List モジュールで定義されている mapAccumL です．

mapAccumL :: (acc -> x -> (acc,y)) -> acc -> [x] -> (acc,[y])
mapAccumL f s [] = (s,[])
mapAccuml f s (x:xs) = (s'', y:ys)
  where (s' ,y ) = f s x
        (s'',ys) = mapAccumL f s' xs

途中脱出（リストのトラバースの短絡）をしたいのなら，足跡リストのトラバースを短絡すればよいわけです．ただし，mapAccumL を使う場合にはちょっとした注意が必要です．mapAccumL は結果として，アキュムレータと足跡とのペアを返すのですが，アキュムレータは左畳み込みの構造のなかで計算されるので，結果として返されるアキュムレータに触れてると短絡できなくなります．（scanlは足跡リストしか残さないのでその心配はいらない）．

双方向 fold

mapAccumL の足跡リストはいわば，足跡を (:) で畳み込んだものに見える．この (:) 部分を一般化したのが 双方向畳み込み - HaHaHa!です．模式図を再掲しておきましょう．

　　　 x0　　　　　x1　　　　　　　　xn
　　　　↓　　　　　↓　　　　　　　　↓
 a  ┏━━┓ a' ┏━━┓          ┏━━┓ a''
 → ┃    ┃ → ┃    ┃ → … → ┃    ┃ →
 ← ┃    ┃ ← ┃    ┃ ← … ← ┃    ┃ ←
 c''┗━━┛ c' ┗━━┛          ┗━━┛ c

定義は以下のとおり，

fold :: ((a,c) -> b -> (a,c)) -> (a,c) -> [b] -> (a,c)
fold f (a,c) (b:bs) = (a'',c'')
  where 
    (a',c'') = f (a,c') b
    (a'',c') = fold f (a',c) bs
fold _ z _ = z

foldは左からアキュムレータ（型 a）に畳み込んだ結果と，右からアキュムレータ（型 c）に畳み込んだ結果を返します．
これで splitBySumSquares を定義すると以下のようになる．

splitBySumSquares :: Int -> [Int] -> ([Int],[Int])
splitBySumSquares l xs = snd $ fold f ((0,xs),([],[])) xs
  where f ((s,bs),c) x = if s' > l then (undefined,([],bs))
                         else ((s',tail bs),(x:fst c,snd c))
                           where s' = s+x^2

これで上手く動くのであるが，実は，この fold は mapAccumL のときと同じで，短絡させたいときの扱いがむずかしい．短絡させたいときには，

  • fold が返す結果のタプルの第一要素を評価しようとしてはいけない．
  • fold にわたす蓄積関数 f を定義するさい蓄積関数の第一引数のタプルの第二要素を無条件で評価してはいけない（構成子でパターンマッチしようとしてはいけない）．

という制限があります．この制限は型で保証されないので，プログラマが注意しなければなりません．
この点を改善するには，短絡するかどうかの情報を同時に返す蓄積関数を使うように fold を修正します．

data Control a = Break { val :: a } 
               | Continue { val :: a }

fold :: ((a,c) -> b -> Control (a,c)) -> (a,c) -> [b] -> (a,c)
fold f (a,c) (b:bs) = (a'',c'')
  where
    x          = f (a,c') b
    y@(a',c'') = val x
    (a'',c')   = case x of
                   Continue _ -> fold f (a',c) bs
                   _          -> y

こうすると，蓄積関数 f は明示的に短絡情報を返すようにする必要がありますが，上の制限は気にしなくてよくなります．

splitBySumSquares :: Int -> [Int] -> ([Int],[Int])
splitBySumSquares l xs = (ps,qs)
  where
    ((_,qs),ps) = fold f ((0,xs),[]) xs
    f ((s,bs),fs) x = if s' > l then Break ((s,bs),[])
                      else Continue ((s',tail bs),x:fs)
                      where s'=s+x^2