[Haskell途中下車の旅] fold村散策（その３）

まずは foldl の弟分 foldl1 からです。
foldl は

    foldl f z [x1,x2,x3,...x_n]
が
    (...(((z `f` x1) `f` x2) `f` x3) `f` ...) `f` x_n

となる計算でしたが foldl1 はこれの初期値 z に関する部分がない

    foldl1 f [x1,x2,x3,...x_n]
が
    (...((x1 `f` x2) `f` x3) `f` ...) `f` x_n

となる計算です。リストが１要素だけの場合と空リストの場合はそれぞれ

    foldl1 f [x1] = x1
    foldl1 f [] = error "Prelude.foldl1: empty list" -- エラー

となります。
foldl1 を使っている典型的な例はリスト中の要素の最大値を求める maximum と最小値を求める minimum です。

maximum xs = foldl1 max xs
minimum xs = foldl1 min xs

foldl に弟分 foldl1 がいるように foldr にも弟分 foldr1 がいます。

    foldr1 f [x1,x2,x3,...x_n]
が
    x1 `f` (x2 `f` (x3 `f` (... `f` x_n)))

となる計算です。

次に紹介するのは foldl より年上格の scanl です。
foldl は計算の最終結果だけを返しましたが scanl は計算途中のすべての値をリストにまとめて返します。初期値もこのリストの先頭に入るので要素数 n個のリストに対して scanl が作るリストの要素数は (n+1)個になります。

scanl で (+) を使った例を見てみましょう。

> scanl (+) 0 [1..5]
[0,1,3,6,10,15]     -- [0, 0+1, (0+1)+2, ((0+1)+2)+3, (((0+1)+2)+3)+4, ((((0+1)+2)+3)+4)+5]

scanl にも弟分 scanl1 がいます。scanl の初期値に関する部分がないバージョンです。

> scanl1 (+) [1..5]
[1,3,6,10,15]    -- [1, 1+2, (1+2)+3, ((1+2)+3)+4, (((1+2)+3)+4)+5]

scanl と scanl1 がいるなら scanr と scanr1 もいます。

> scanr (+) 0 [1..5]
[15,14,12,9,5,0]    -- [1+(2+(3+(4+(5+0)))), 2+(3+(4+(5+0))), 3+(4+(5+0)), 4+(5+0), 5+0] 
> scanr1 (+) [1..5]
[15,14,12,9,5]    -- [1+(2+(3+(4+5))), 2+(3+(4+5)), 3+(4+5), 4+5, 5] 

最後に紹介するのは長老格の mapAccumL です。
（mapAccumL と次に紹介する mapAccumR は Preludeモジュールに入っていないので使うときには Data.Listモジュールを import しておく必要があります）
scanl は計算途中の値をリストにまとめましたが mapAccumL は計算していく値とは別の値をリストにまとめることができます。実際に返す値はそのリストと計算の最終結果をタプルにしたものです。
foldl,scanlに比べてインタフェースが複雑なので例を見て確認してみましょう。
初期値 0 に [1..5] を順に加えていきリストとしてまとめるのは計算する値の２倍という例です。

> mapAccumL (\b a -> (b+a,2*b)) 0 [1..5]
(15,[0,2,6,12,20])

(\b a -> (b+a,2*b)) の部分の意味は
・ b が一つ前の計算ステップで計算されてきた値
・ a がリストの現ステップで使う要素の値
・ b+a の部分が次の計算ステップに渡す値
・ 2*b の部分がリストにまとめる値
です。
要素数 n個のリストに対して scanl が作るリストの要素数は (n+1)個でしたが mapAccumL が作るリストの要素数は n個です。

mapAccumL がいるなら mapAccumR もいます。

> mapAccumR (\b a -> (b+a,2*b)) 0 [1..5]
(15,[28,24,18,10,0])

最後に fold系高階関数に与える関数の引数についてまとめておきましょう。

・foldl,foldl1,scanl,scanl1 に渡す関数の引数は
　　第１引数が一つ前の計算ステップで計算されてきた値
　　第２引数がリストの現ステップで使う要素の値
・foldr,foldr1,scanr,scanr1 に渡す関数の引数は
　　第１引数がリストの現ステップで使う要素の値
　　第２引数が一つ前の計算ステップで計算されてきた値
です。
「一つ前の計算ステップから渡ってくる値は
　left系ならleft側（第１引数）、
　right系ならright側（第２引数）」
という覚え方だと思い出しやすいでしょう。
ただし mapAccumL と mapAccumR は両方とも
　　第１引数が一つ前の計算ステップで計算されてきた値
　　第２引数がリストの現ステップで使う要素の値
という left系順番なので気をつけてください。

次回は fold,scan,mapAccum のパワー比較と高階関数の効能について説明します。