高階関数のメリットって何だろう？
最近、少しずつ
を読んでいる。しかし、なかなか理解できない。(+_+) せめて、最初の節、
「3. 関数の貼り合せ」
を読み切りるのが、今の目標。
ところで、「なぜ関数...」を読まなければ、
- 関数の抽象化 (パラメータ化、モジュール化、部品と合成) の流れ
- Haskell で言う fold 系の関数 (reduce) が導かれるまでの過程が重要
ということがわからなかった。
fold 系の関数 については、
「リスト全体に対して、何か演算を施したいときには、何だかよくわからないけれど、`foldl’ という関数を使う」
という程度の認識だった。 ^^;
Ruby の inject メソッドを見たのが最初
fold 系の関数と言えば、最初に見たのが Ruby の inject メソッド。
「なんてわかりにくい動作のメソッドなんだ」 (@_@;)
という印象だったのを覚えている。
「やってることは、コンテナの責務じゃないの？」
と正直思っていた。 (cf.Enumerable の inject)
そもそも、なぜこんな類の関数が定義されているのか、理由がわからなかった。しかし、 Python にも、Haskell にも同類の関数があると知って、「あれ？なぜ、ここにも定義されているのだろう？」と疑問を感じはじめ、今になってやっと、「fold 系の関数が導かれる過程」が重要だったと理解した。
抽象化についての固定観念
それまで、「抽象化」というと、「クラスやオブジェクトの単位でするもの」という固定観念があった。だから、
「高階関数って便利だけれど、それ以上何か意味があるんだろうか？」
「それって、抽象化に対して何かの役に立つの？」
という疑問を持っていた。なぜなら、
「関数が、どのようにして抽象化されていくのか」
という、一番基本的なところを理解してなかったため。
「なぜ関数プログラミングは重要か」 には、次のように書かれている。
… 従来のプログラミング言語では分割できない関数を、部品 (汎用の高階関数といくつかの特定の特殊化関数) の合成として表現できる関数型言語 …
- 関数を、
- 部品として、
- 合成して表現できる
という意味が、最近になって、少しわかりはじめてきた気がする。
これでやっと Haskell の入口付近に来ただろうか。まだ玄関の扉を開けることができないけれど…。
リストを足し上げる関数 sum を定義してみる
「なぜ関数...」には、冒頭で Haskell の foldr に相当する reduce 関数が、sum から導かれる様子が述べられている。
（`foldl’ ではなくて `foldr’ であることに注意。foldr 相当の関数で説明されている理由は、リストのデータコンストラクタである cons と foldr の構造の対応が良いことによる。）
理解するには、写経するのが一番ということで、「なぜ関数...」を真似て sum から foldl を導いてみることにした。
右から左へと足し合わせる関数 sum
「なぜ関数...」の関数 sum は、以下のように定義されていた。
sum (x:xs) = x + sum xs
関数 sum は、再帰的に定義されている。この sum における再帰的な定義は、以下のように、リストを
- 先頭
- 2 番目の要素以降
に分けて考えていると考えれば納得できる。
「なぜ関数...」におけるリストの定義は、以下の通りだった。
listof X ::= nil | cons X (listof X)
リストの要素である X は、リストの先頭に追加されるように見える。
cons – Wikipedia を参考にしても、
リストに要素を追加するとき、その先頭につなげていく
という形になっている。
そのため、（ ）の内側が先に計算が行われるというモデルで考えた場合、リストの要素が計算されていく順序は、リストの右側の要素から、左側へと計算が行われる。。
はじめ foldr を見たとき、「なぜ、リストの末尾から先頭に向かって計算をするのだろう？」と思っていた。しかし、リストを生成・生長させていくときの構造、つまり、データコンストラクタと対応付けて考えれば、その計算方法が極めて自然であることがわかる。
左から足し合わせる関数 sum
上記に対して、関数 sum を、下図のように「左の要素から右へと足し合わせる」定義を考えてみる。
定義を考える方法は、まず予め sum が
「リストの要素を合計する関数」
であると想定しておく。
sum の対象リストが、空でない場合を考えると、
- リストの先頭の要素 X と、残りの要素 XS の先頭要素を足す。
- 上記の結果と、リスト XS の 2 番目以降のリストを合わせて、新たにリストを生成。
- 上記のリストを sum 。
定義するときに注意する点は、sum は既に Prelude に定義されているので、これを読み込まないように、以下を記述しておく。
import Prelude hiding(sum)
これで準備 OK 。
sum (x:xs) = ... として定義する場合、上記の順に計算を考えると、
- x + head xs
- (x + head xs) : (tail xs)
- 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 を見ると、定義がそっくりなことがわかる。
違うのは、
- 空のときの値
- 二項演算子の種類
よって、この２つの計算から、共通の構造を取り出した関数を定義し、そこから、関数 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’ として考えていく。
sum の定義を見ながら、
sum (x:y:xs) = sum $ (x + y) : xs
foldl1 を考えればいいので
- `+’ の部分を `f’ で置き換える
- 引数を増やす
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]
0コメント:
コメントを投稿