2010年2月4日木曜日

Haskell で関数合成 (2)

1 つの引数を取る関数を合成

一つの引数を取る関数を合成する場合、例えば、

*Main> (2*).(3+) $ 4
14

関数合成の定義 は、

(.) f g x = f (g x)

よって、関数合成の部分を定義で置き換えると、

(2*).(3+)
=> \x -> 2 * (3 + x)

これを 4 に適用すると、

(\x -> 2 * (3 + x)) 4
=> 2 * (3 + 4)
=> 14

 

2 つの引数を取る関数と、1 つの引数を取る関数を合成

上記の関数合成 (.) の第 1 引数を、2 つの引数を取る関数 (*) に変更してみる。関数の型を調べると、

*Main> :t (*).(3+)
(*).(3+) :: (Num a) => a -> a -> a

合成された関数が、2 つの引数を取る関数になったことがわかる。

この合成された関数を適当な値に適用してみる。

*Main> ((*).(3+)) 4 5
35

 

関数合成を定義で置き換える

(.) の定義より、上記の関数合成の部分は次のように置き換えられる。

(*).(3+)
=> \x -> (*) (3 + x)

これを 4 に適用すると、

(\x -> (*) (3 + x)) 4
=> (*) (3 + 4)
=> (*) 7

続いて 5 に適用すると、

(*) 7 5
=> 35

 

全体のイメージは、

  1. 3 + 4 で 7
  2. (*) を 7 に適用し、第2引数が与えられるのを待つ
  3. (*) 7 を 5 に適用し => 35

 

2 つの引数を取る関数の引数の型が異なる場合

先ほど関数合成の第1引数に適用したのは (*) だった。(*) が適用する二つの引数の型は同じ。これに対して、リストのデータコンストラクタである

(:)

は、第 1 引数はリストの要素で、第 2 引数はリストを取る。念のため型を確認すると、

*Main> :t (:)
(:) :: a -> [a] -> [a]

これに関数合成を適用する。 (2*) と合成した場合の型を調べると、

*Main> :t (:).(2*)
(:).(2*) :: (Num a) => a -> [a] -> [a]

要素が Num クラスのインスタンスでなければならないという制約が付いた。

これを適当な値で試してみる。

*Main> ((:).(2*)) 3 []
[6]

合成した関数の第 1 引数は要素で、第 2 引数はリストを与える。

 

関数合成を定義で置き換える

関数合成の定義より、合成した関数を置き換える。

(:).(2*)
=> \x -> (:) (2 * x)

これを 3 に適用すると、

(\x -> (:) (2 * x)) 3
=> (:) (2 * 3)
=> (:) 6

そして、空リストに適用したら、

(:) 6 []
=> 6 : []
=> [6]

 

全体のイメージは、

  1. 3 に 2 をかける
  2. (:) を 6 に適用し、第2引数が与えられるのを待つ
  3. (:) 6 を空リストに適用し => [6]

 

map 関数の定義

なぜ関数プログラミングは重要か」の “3. 関数の貼り合せ” では、map 関数がリストに対する高階関数より導かれている。

先ほどのように (:) と関数を合成し、foldr に適用。例えば、リストの要素を 2 倍する関数であるなら、

*Main> foldr ((:).(2*)) [] [0..5]
[0,2,4,6,8,10]

Fold (higher-order function) のイメージを真似ると、

img02-04-2010[1].png
対象のリスト [0..5] を木の左の葉の部分に並べる。
img02-04-2010[2].png
末尾の右の葉に与えられた引数 [] を置く。
img02-04-2010[4].png
合成した関数 (:).(2*) をノードに配置。

img02-04-2010[5].png

最初の関数の適用。
これをルートに向けて繰替えす。

 

map 関数

上記より、関数合成の第2引数に関数を渡せるように変更すると、map 関数が導かれる。 (「なぜ関数プログラミングは重要か」 より)

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

 

関連記事