top page > computer > haskell > web_lecture > for_programmer > fold_right.html
更新日:
文責: 重城良国

たたみこみ(右)

はじめに

リストの総和、総積、長さを求める関数はすべて2引数関数でリストをひとつの値へ変換している。これを「たたみこみ」と呼ぶ。左右2種類ある「たたみこみ」のうち「右たたみこみ」から学ぶ。

それぞれの関数

mySum [] = 0
mySum (x : xs) = x + mySum xs

myProduct [] = 1
myProduct (x : xs) = x * myProduct xs

myLength [] = 0
myLength (_ : xs) = 1 + myLength xs

関数mySumとmyProductのちがいは0が1に(+)が(*)になっていることだ。関数mySumとmyLengthのちがいはxが1になっていることだ。どれも同じ枠組みを共有している。

右たたみこみ

mySum [3, 7, 8, 4]を展開してみよう。

mySum [3, 7, 8, 4]
-> mySum (3 : [7, 8, 4])
-> 3 + mySum [7, 8, 4]
-> 3 + mySum (7 : [8, 4])
-> 3 + (7 + mySum [8, 4])
-> 3 + (7 + mySum (8 : [4]))
-> 3 + (7 + (8 + mySum [4]))
-> 3 + (7 + (8 + mySum (4 : [])))
-> 3 + (7 + (8 + (4 + mySum [])))
-> 3 + (7 + (8 + (4 + 0)))

同様にmyProduct [3, 7, 8, 4]は以下のように展開できる。

3 * (7 * (8 * (4 * 1)))

myLength [3, 7, 8, 4]は以下のようになる。

1 + (1 + (1 + (1 + 0)))

関数mySumやmyProductはリストの要素に右結合で演算子を次々と適用している。この枠組みが「右たたみこみ」だ。

おきかえ

リスト[3, 7, 8, 4]の本当の姿は

3 : (7 : (8 : (4 : [])))

だ。mySumでは[]を0に(:)を(+)におきかえている。myProductでは[]を1に(:)を(*)におきかえている。[]と(:)のおきかえでそれぞれの「右たたみこみ」関数になる。

関数myLength

関数myLengthでは(:)をおきかえる演算子が自明ではない。関数lenを考える。

len :: a -> Int -> Int
len _ l = 1 + l

するとmyLength [3, 7, 8, 4]は以下のようになる。

3 `len` (7 `len` (8 `len` (4 `len` 0)))

myLength関数は[]を0に(:)をlenにおきかえる。

右たたみこみを抽象化する

関数foldrは[]をおきかえる値と(:)をおきかえる関数とを引数として右たたみこみ関数を作る。

関数foldrの使いかた

関数mySumをfoldrで書きなおす。関数foldrの第1引数は(:)をおきかえる関数であり第2引数は[]をおきかえる値だ。mySumでは(+)と0だ。

mySum = foldr (+) 0

関数myProductでは(*)と1を指定する。

myProduct = foldr (*) 1

関数myLength

関数myLengthは関数lenを使って

myLength = foldr len 0

のように書ける。lenを書きかえていく。

len _ l = 1 + l

演算子の部分適用で

len _ = (1 +)

となる。引数をとわずいつも(1 +)を返す関数だ。

len = const (1 +)

関数myLengthは

myLength = foldr (const (1 +)) 0

と書きなおせる。

関数foldrの定義

mySumやmyProductの定義を見る。

mySum [] = 0
mySum (x : xs) = x + mySum xs

myProduct [] = 1
myProduct (x : xs) = x * mySum xs

mySumの0や(+)、myProductの1や(*)をmyFoldrの第1引数と第2引数におきかえる。

myFoldr _ v [] = v
myFoldr op v (x : xs) = x `op` myFoldr op v xs

関数foldrの型

第1引数はそれぞれの要素を結合する演算子だ。第2引数は1番右に来る値、初期値だ。第3引数はたたみこみの対象となるリストだ。返り値はたたみこみの結果得られる値だ。

関数mySumからの一般化

mySumではそれぞれ以下のような型になる。

(+) :: Integer -> Integer -> Integer
0 :: Integer
xs :: [Integer]
返り値 :: Integer

foldr :: (Integer -> Integer > Integer) -> Integer -> [Integer] -> Integer

一般化すると

foldr :: (a -> a -> a) -> a -> [a] -> a

となる。「2つのa型の値からa型の値を作る演算子」とa型の値と「a型の値のリスト」をとりa型の値を作る関数だ。この型はまだ十分に一般的ではない。foldrはもっと広い範囲に使える。

関数myLengthからの一般化

myLengthではそれぞれ以下のような型になる。

(const (1 +)) :: a -> Int -> Int
0 :: Int
xs :: [a]
返り値 :: Int

foldr :: (a -> Int -> Int) -> Int -> [a] -> Int

一般化する。

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr op v [x1, x2]はx1 `op` (x2 `op` v)に展開される。opの第1引数の型はx1の型と等しく、第2引数の型はopの返り値の型と等しく、さらにその型は値vの型と等しい。全体の返り値の型はopの返り値の型と等しい。

まとめ

関数foldrは関数mySum、myProduct、myLengthの「たたみこみ」という枠組みを表現している。Haskellの「抽象化」の力だ。学習を進めると抽象化の層構造あるいは網目構造について実感できる。

「リストの長さ」へもどる 「たたみこみ(左)」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics