2009年1月1日木曜日

Haskell で関数の抽象化 - sum, product から foldl1 → foldl へ

高階関数のメリットって何だろう?

最近、少しずつ

を読んでいる。しかし、なかなか理解できない。(+_+) せめて、最初の節、

「3. 関数の貼り合せ」

を読み切りるのが、今の目標。

ところで、「なぜ関数...」を読まなければ、

  • 関数の抽象化 (パラメータ化、モジュール化、部品と合成) の流れ
  • Haskell で言う fold 系の関数 (reduce) が導かれるまでの過程が重要

ということがわからなかった。

fold 系の関数 については、

「リスト全体に対して、何か演算を施したいときには、何だかよくわからないけれど、`foldl’ という関数を使う」

という程度の認識だった。 ^^;

 

Ruby の inject メソッドを見たのが最初

fold 系の関数と言えば、最初に見たのが Ruby の inject メソッド。

「なんてわかりにくい動作のメソッドなんだ」 (@_@;)

という印象だったのを覚えている。

「やってることは、コンテナの責務じゃないの?」

と正直思っていた。 (cf.Enumerable の inject)

そもそも、なぜこんな類の関数が定義されているのか、理由がわからなかった。しかし、 Python にも、Haskell にも同類の関数があると知って、「あれ?なぜ、ここにも定義されているのだろう?」と疑問を感じはじめ、今になってやっと、「fold 系の関数が導かれる過程」が重要だったと理解した。

 

抽象化についての固定観念

それまで、「抽象化」というと、「クラスやオブジェクトの単位でするもの」という固定観念があった。だから、

「高階関数って便利だけれど、それ以上何か意味があるんだろうか?」

「それって、抽象化に対して何かの役に立つの?」

という疑問を持っていた。なぜなら、

「関数が、どのようにして抽象化されていくのか」

という、一番基本的なところを理解してなかったため。

なぜ関数プログラミングは重要か」 には、次のように書かれている。

… 従来のプログラミング言語では分割できない関数を、部品 (汎用の高階関数といくつかの特定の特殊化関数) の合成として表現できる関数型言語 …

  1. 関数を、
  2. 部品として、
  3. 合成して表現できる

という意味が、最近になって、少しわかりはじめてきた気がする。

これでやっと Haskell の入口付近に来ただろうか。まだ玄関の扉を開けることができないけれど…。

 

リストを足し上げる関数 sum を定義してみる

なぜ関数...」には、冒頭で Haskell の foldr に相当する reduce 関数が、sum から導かれる様子が述べられている。

(`foldl’ ではなくて `foldr’ であることに注意。foldr 相当の関数で説明されている理由は、リストのデータコンストラクタである cons と foldr の構造の対応が良いことによる。)

理解するには、写経するのが一番ということで、「なぜ関数...」を真似て sum から foldl を導いてみることにした。

 

右から左へと足し合わせる関数 sum

なぜ関数...」の関数 sum は、以下のように定義されていた。

sum (x:xs) = x + sum xs

関数 sum は、再帰的に定義されている。この sum における再帰的な定義は、以下のように、リストを

  • 先頭
  • 2 番目の要素以降

に分けて考えていると考えれば納得できる。

081231-010

なぜ関数...」におけるリストの定義は、以下の通りだった。

listof X  ::= nil |  cons X (listof X)

リストの要素である X は、リストの先頭に追加されるように見える。

cons – Wikipedia を参考にしても、

リストに要素を追加するとき、その先頭につなげていく

という形になっている。

そのため、( )の内側が先に計算が行われるというモデルで考えた場合、リストの要素が計算されていく順序は、リストの右側の要素から、左側へと計算が行われる。。

はじめ foldr を見たとき、「なぜ、リストの末尾から先頭に向かって計算をするのだろう?」と思っていた。しかし、リストを生成・生長させていくときの構造、つまり、データコンストラクタと対応付けて考えれば、その計算方法が極めて自然であることがわかる。

 

左から足し合わせる関数 sum

上記に対して、関数 sum を、下図のように「左の要素から右へと足し合わせる」定義を考えてみる。

081231-011

定義を考える方法は、まず予め sum が

「リストの要素を合計する関数」

であると想定しておく。

sum の対象リストが、空でない場合を考えると、

  1. リストの先頭の要素 X と、残りの要素 XS の先頭要素を足す。
  2. 上記の結果と、リスト XS の 2 番目以降のリストを合わせて、新たにリストを生成。
  3. 上記のリストを sum 。

定義するときに注意する点は、sum は既に Prelude に定義されているので、これを読み込まないように、以下を記述しておく。

import Prelude hiding(sum)

これで準備 OK 。

sum (x:xs) = ... として定義する場合、上記の順に計算を考えると、

  1. x + head xs
  2. (x + head xs) : (tail xs)
  3. sum $ (x + head xs) : (tail xs)

となる。まとめると、

sum (x:xs) = sum $ (x + head xs) : (tail xs) 

sum を sum で再帰的に定義している。計算が行われていく過程で、

対象のリストは徐々に小さくなっていく

ことがいめーじできる。

そして、最後に、対象のリストが空のときは 0 を返すとすると、

sum [] = 0

「これで計算できるかな?」と思い 1 ~ 10 までの合計を計算させてみた。しかし、残念ながら、途中で止まってしまった。 (@_@;)

上記の定義だけだと、リストの要素が一つのとき問題かな? しかし、head xs でエラーが表示されるかと思いきや、何も表示がされずに止まってしまう。うーん、この辺まだよくわからない… ^^; しかし、以下のようにしたら、とりあえず動いてくれたので、よしとしておこう。

sum [] = 0
sum [x] = x
sum (x:xs) = sum $ (x + head xs) : (tail xs) 

 

リストのデータコンストラクタの使い方を変える

そういえば、以前に逆ポーランド法で見たリストのデータコンストラクタの使い方を見た。これを真似すれば、上記の定義より、head, tail を使わなくて済むようだ。

sum (x:y:xs) = sum $ (x + y) : xs

この方がシンプルでええわ~。^^

 

左から掛け合わせる関数 product を定義

ついでなので、リストの要素をすべて掛け合わせる関数 product を同じように定義してみる。

product [] = 1
product [x] = x
product (x:y:xs) = product $ (x * y) : xs

product も Prelude に定義されているので import で hiding しておくことに注意。

こうやって、上記関数 sum, product を見ると、定義がそっくりなことがわかる。

違うのは、

  • 空のときの値
  • 二項演算子の種類

よって、この2つの計算から、共通の構造を取り出した関数を定義し、そこから、関数 sum, product 導けば経済的だし、バグの混入を防ぎやすくなる。

そういえば、以前、オブジェクト指向なプログラミング環境で、コンテナの役割を持つクラスで、子要素に対して何らかの処理を書くとき、

「いつも同じような for ループがうっとうしいなぁ」

と感じていたことを思い出した。そういった処理も、このように抽象化したメソッドを定義しておけばよかった…。まぁ、それが Ruby の inject メソッド周りにあることに気がつけが良かったんだけれど。。 (+_+)

 

foldl1 を定義

では、上記関数 sum, product よりも、抽象度の高い関数 foldl1 を定義する。foldl1 も Prelude にあるので、定義する前に import で hiding するのを忘れずに。

ところで、関数 sum, product における独自な部分は、二項演算子 + , * だった。よって、sum, product の定義では、引数として、リストのみを与えればよかったが、fold1 の定義では、それに加えて、二項演算子も与えることになる。

予め型宣言を書いておくと、

foldl1 :: (a -> a -> a) -> [a] –> a

先ほどの sum の図における `+’ の部分を、一般的な関数である `f’ として考えていく。

090101-012

sum の定義を見ながら、

sum (x:y:xs) = sum $ (x + y) : xs

foldl1 を考えればいいので

  1. `+’ の部分を `f’ で置き換える
  2. 引数を増やす
foldl1 f (x:y:xs) = foldl1 f $ (x `f` y) : xs

リストの要素数が 1 のときはそのまま返す。これをまとめると、

foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 _ [x] = x
foldl1 f (x:y:xs) = foldl1 f $ (x `f` y) : xs

 

foldl1 から sum , product を定義

次に、この foldl1 を使って、sum, product を定義してみる。

sum = foldl1 (+) 
product = foldl1 (*)

シンプルな形で定義できた。

 

foldl1 から foldl へ

foldl1 では、リストの要素に対して、引数である関数 f を適用した。ただし、空のリストに対してどのような動作をするのかは定義しなかった。

これに対し、foldl では、foldl1 の引数に加え、初期値 z を与える。計算は、最初に初期値 z と、リストの先頭要素に関数 f を適用する。その後、順次、要素間に対して、関数 f を適用する。

このように考えれば、「foldl1 は foldl の特殊な形」と想定できる。

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

次に、fold1 から sum, producet を定義したときと同じように考え、関数 fold から foldl1 を定義する。 foldl1 に与えられたリストの先頭要素を初期値と考えればいいので、

foldl1 f (x:xs) = foldl f x xs

空のリストが与えられたら error 関数でエラー表示をするなら、

foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 _ [] = error "empty list"
foldl1 f (x:xs) = foldl f x xs

では、最後に、Prelude に定義してある foldl のソースを見る。

foldl        :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

考えてみたら、以下のような例の場合、二項演算子により、型が異なるから、二項演算子の型を間違えていた~。(+_+)

 foldl (\x y -> x++[y*2]) [] [1..10]