プログラミングHaskellのfoldr, foldlの説明が秀逸だった件
今年はHaskellを勉強しています。
土日などを利用して、すごいH本を3〜4週間かけて読み終えました。時間かかった分、記憶の密度が低くて、まだ理解度は低いです。
新しい概念を学ぶ時は、同じテーマの本を何冊か読んで、本当に読みたかった本を再度読み直すというのが自分の学習の方法として定着しているので、今は、プログラミングHaskellを読み進めています。
すでに「ふつうのHaskellプログラミング」は読み終えていましたが、改めて読むと、本当に普通のプログラミング本に感じたので、すごいH本がかなり刺激的で、よくできた本なんだと思います。読み直す時が楽しみであります。
本題
さて、「プログラミングHaskell」の話に戻りますが、foldrとfoldlの説明の箇所が秀逸だと思ったので内容を紹介してみます。*1
fold関数は、他の言語でreduceとかinjectとか呼ばれている関数ですね。個人的には、かなり表現力が強い関数なので、一番好きな関数かもしれません。*2
プログラミングHaskellでは、冒頭にこんな紹介があります。
引数にリストを取る関数は、リストに対する再帰を使って、以下のような簡単な様式で定義できることが多い。
f [] = v
f (x:xs) = x ⊕ f xs
標準ライブラリで提供される高階関数foldr（fold rightの略称）は、この再帰的な様式を抽出する。演算子⊕と値vは引数となる。
なんのこっちゃという感じですが、確かに、fold関数には引数にリストを除いて、⊕に相当する関数と初期値に相当する値vを渡します。
例にある、sum関数とproduct関数のfoldを使わない定義はこんな感じです。
sum [] = 0 sum (x:xs) = x + sum xs product [] = 1 product (x:xs) = x * product xs
sum関数とproduct関数のfoldを使った定義はこんな感じです。
sum = foldr (+) 0 product = foldr (*) 1
確かに、⊕に相当する部分と、値vに相当する部分がそれぞれ引数になっています。しかも、いつの間にか再帰がなくなりましたね。再帰的な様式を抽出するというのは本当みたいです。
Haskellはすべての関数がカリー化されるので、sumもproductもリストに適用すれば、結果が返ってきます。
わかりやすかった説明
で、前提は以上で、次に以下のような説明が続きます。
すなわち関数foldr f vは、空リストを値vに変換する。空でないリストに対しては、「先頭の要素」と「残りのリストに対し自分自身を呼び出した結果」に関数fを適用する。ただ実際には、foldr f vは再帰的に理解するのではなく、単にcons演算子を関数fに置き換え、末尾の空リストを値vに置き換えると理解する方がいいだろう。
という説明の後に具体例がこのようにきます。
1:(2:(3:[]))
これは、以下のように変換される。
1+(2+(3+0))
こういう説明、今まで見たことなくて、すごくわかりやすい説明だと思いました。
すべての関数を中置記法で使えるHaskellだからこそわかりやすいのかもしれませんが、他の言語でその機能の採用率が低めってだけと考えれば良いだけですし。
まとめるとfoldrのフォーマットは以下のような感じですね。
foldr f v [...]
で、次からは例です。
例: リストの値を合計する
foldr (+) 0 [1,2,3]
関数f = (+)
値v = 0
before:
1:(2:(3:[]))
cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。
after:
1+(2+(3+0))
例: リストで最も大きい数値を求める
foldr max 0 [1,2,3]
関数f = max
値v = 0
before:
1:(2:(3:[]))
cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。
after:
1`max`(2`max`(3`max`0))
例: リストの最初の要素を求める
getLeft :: a -> b -> a getLeft a _ = a foldr getLeft 0 [1,2,3]
関数f = getLeft
値v = 0
この例の場合、値vは即捨てるので、なんでもいいですが。
before:
1:(2:(3:[]))
cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。
after:
1`getLeft`(2`getLeft`(3`getLeft`0))
例: リストの要素数を求める
succRight :: Enum a => a -> a -> a succRight _ n = succ n foldr succRight 0 [1,2,3]
関数f = succRight
値v = 0
before:
1:(2:(3:[]))
cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。
after:
1`succRight`(2`succRight`(3`succRight`0))
例: リストを逆順にする
snoc :: a -> [a] -> [a] snoc x xs = xs ++ [x] foldr snoc [] [1,2,3]
関数f = snoc
値v = []
before:
1:(2:(3:[]))
cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。
after:
1`snoc`(2`snoc`(3`snoc`[]))
例: リストの偶数の要素の合計値を求める
addEven :: Int -> Int -> Int addEven n m = if even n then m + n else m foldr addEven 0 [1,2,3,4]
関数f = addEven
値v = 0
before:
1:(2:(3:(4:[])))
cons演算子を関数fに置き換え、末尾の空リストを値vに置き換えてみる。
after:
1`addEven`(2`addEven`(3`addEven`(4`addEven`0)))
foldr, foldlの要約
foldrの要約として以下の定義が掲載されていました。
foldr (⊕) v [x0, x1, ..., xn] = x0 ⊕ (x1 ⊕ (...(xn ⊕ v)...))
で、foldrは⊕が左結合であることが前提の関数で、foldlは⊕が右結合であることが前提の関数だと。
foldlの定義も以下のように書かれています。
foldl (⊕) v [x0, x1, ..., xn] = (...((v ⊕ x0) ⊕ x1)...) ⊕ xn
foldrかfoldlかでは、個人的には圧倒的にfoldlの方がわかりやすいので、foldl相当（reduceかreduceRightだったらreduce）ばかり使っていましたが、どちらでも実装できる場合は、より効率の良い方を選びましょうという話でした。
例えば、すごいH本には、(++)は(:)に比べると遅いので、リストを使って、リストを構築するようなケースでは、foldrを使う方が良いと書いてありました。後、無限リスト扱う時とか。consは右結合ですもんね。
Perlのリストのおもしろいところ
PerlのリストはPerlらしいというか、結構おもしろいなーと思うことがあります。
Perlのリストの面白いところを紹介してみます。
cons, append
Perlでconsとかappendするいい方法何かなーとか考えてた時に、リストの標準機能でできることに気づきました。
my @one_to_three = (1, 2, 3); # cons my @zero_to_three = (0, @one_to_three); # append my @one_to_four = (@one_to_three, 4);
concat
同じような方法でconcat相当もできます。
my @one_to_three = (1, 2, 3); my @four_five_six = (4, 5, 6); # concat my @one_to_six = (@one_to_three, @four_five_six);
ハッシュ版cons, append, concat
Perlでハッシュを定義する時は、以下のように定義します。
my %foo_bar = (foo => 1, bar => 2);
これはいろんな書籍に書いてあることですが、以下の別記法です。
my %foo_bar = ('foo', 1, 'bar', 2);
ハッシュはkeyとvalueが対になったハッシュをリストコンテキストで評価すれば、ハッシュになるわけですね。
この特徴を利用すれば、ハッシュ版のcons, append, concatも可能になります。
my %foo_bar = (foo => 1, bar => 2); my %baz_qux = (baz => 3, qux => 4); # ハッシュ版cons my %hoge_foo_bar = ('hoge' => 0, %foo_bar); # ハッシュ版append my %foo_bar_hoge = (%foo_bar, hoge => 3); # ハッシュ版concat my %foo_bar_baz_qux = (%foo_bar, %baz_qux);
面白いですね。
car（head）, cdr（tail）
関数型言語でよくあるcar（head）, cdr（tail）などもリストの標準の機能でOKです。これくらいのことをするのに、イチイチ関数なんていらんかったんです。
my ($car, @cdr) = (1, 2, 3, 4);
多値っぽいもの
多値っぽいものもできます。
my $zero = 0; my $one = 1; my $two = 2; # リストの各要素に10足したリストを返す関数 sub map_add_10 { map { $_ + 10 } @_; } my ($ten, $eleven, $twelve) = map_add_10($zero, $one, $two);
便利ですね。
分配束縛っぽいもの
引数を分解するのも簡単です。超単純なheadとtailを関数にしてみましょう。（先ほどいらんかったんですって言ったとこですが...）
sub head { my ($x, @xs) = @_; $x; } sub tail { my ($x, @xs) = @_; @xs; } my $head = head(1, 2, 3); my @tail = tail(1, 2, 3);
4Clojureが楽しい
最近、4Clojureにハマっています。
プログラミング学習サイトには、プログラムの実行環境が必要だと思っていて、ドットインストールのアプローチよりも、Codecademyのアプローチが正解だと思っています。
4ClojureはREPLこそ、別のサイトですが、プログラムの実行環境があるのでとても良いです。
4Clojureの学習の流れ
4Clojureは以下のような流れで学習します。
- 難易度とカテゴリが設定された問題から取り組む問題を選ぶ
- 実装する機能のテストが提示される
- 機能を実装し、入力画面にコードを打ち込んで、打ち込んだ内容を評価する
- テストに通れば、クリア、通らなければ、リトライ
- Golfコンテストに参加していれば、Golf Scoreとともに、コンテスト参加者のScoreのグラフが表示され、評価したコードがどの位置にいるかわかる
ゲーム性があり、リズム良く、効果的な学習ができると思います。
難易度はElementalyからHardまで用意されていて、自分は#1から順番に解いていったのですが、Hardも出てくるし、難易度順でやり直しました。
4Clojureで遊んでみて良かった点
- アルゴリズムを自分で書く経験ができる
- Clojure Docsを隅々まで読むことになる
- コアメソッドを自分で実装することで理解が深まる
など、いろいろあります。
アルゴリズムをまともに勉強したことはないので、Easyでも結構苦戦することもあります。ただ、普段であれば、ライブラリに頼って自分で書かないアルゴリズムを、敢えて自分で書かなければいけないというのはとても頭の刺激になります。
特に最初の方は、Clojureの語彙が自分の中でほとんどないため、ドキュメントを読む機会が増えます。いろいろ解いていく中で、だんだんメソッドに慣れていって、解くまでの時間が短くなっていく実感が湧きます。
また、コアメソッドを自分で実装する問題もあるので、より理解が深まる感じがしました。
パスカルの無限三角形
1例ですが、パスカルの三角形の段を数値で指定すると、その段のシーケンスが返る関数を実装しろという問題がありました。
パスカルの三角形をそもそも知らなかったので、パスカルの三角形とはどういうものかググって、書いてみて、再帰じゃなくて無限シーケンスにしよう、もっと短く書こう、もっとClojureらしく書こう、というようにひとつの問題を取り組むだけでもかなり楽しめます。
上の例は、Clojureらしく書けたけど、Golfスコアはそんなに高くないし、もっと改善したいと思います。もしかしたら、java.lang.Long/MAX_VALUEを超える場合、bigintで出力するといった分岐を書いても、今以上に短く書けるのかもしれませんし。ひとつの関数でここまで考えようと思うのは、やはり4Clojureのゲーム性がなせる技でしょう。
まとめ
プログラミング学習サイトにおけるゲーム性（ゲーミフィケーション）は、学習者にとって、かなり有効に働くものだと思います。
4Clojure楽しいので、1日1問でも進めて、全クリしたいですね！
ということで、今週末のKyoto.lispのスライドをそろそろ準備します...
富豪的プログラミングにおける関数合成の効用
あくまで富豪的プログラミングが許される時という前提付きですが、関数合成がとても有用だと思うので、記事にしてみます。なお、ソースコードはCoffeeScriptで記述しているので*1、JavaScriptはわかるけど、CoffeeScriptはわからないという方は、適宜、CoffeeScript公式サイトのREPL（上部にあるTRY COFFEESCRIPTというリンクより）等で変換しながらご確認ください。また、JavaScriptエンジンはV8を想定しているので、一部のブラウザでは動かないメソッドも入っています。
Lisp脳について
手続き的な発想では、毎回特殊な処理を行いそれを繰り返すという発想でプログラミングしていました。
データからデータへの変換を考えれば良く、出力は後からどうにでもなる、と考えています。
データからデータへの変換は、例えば元データが配列だったりすると、処理のたびに配列を走査する必要があるので、本来なら配列の走査は一度で良いということを考えると、一種の富豪的プログラミングになります。
この富豪的プログラミング時の関数合成の効用を考えます。
関数合成
合成関数という言葉があって、なにやら数学で習うらしいのですが、数学は全然わからないので、習った記憶すらないレベルです。
Wikipediaの写像の合成がそれに該当するのだと思います。
とりあえず、難しいことは置いておいて、(f ∘ g)(x) = f(g(x))が成り立つ関数を作ります。
合成関数を作るための関数を定義する
ex1
これがf(g(x))を実行した結果です。(f ∘ g)(x)な関数を定義できるようにするため、composeという関数を作ります。
ex2
こんな感じです。
引数に関数を3つ以上指定できるようにする
上記の状態では、composeの引数に指定できる関数は2つしかありません。これだと3つ以上関数を合成したい時に少し面倒です。
ex3
引数の入れ替えが面倒だし、composeのネストは少々読みづらいですね。
可変長引数に対応したバージョンのcomposeを定義します。Underscore.jsにあるcomposeも可変長引数を取れます。
ex4
可変長引数版の前は、読みづらかった上に、途中で関数を追加する際に、引数の順番を調整しないといけなかったりして面倒でした。可変長引数版の方が圧倒的に利便性が高いと思います。
関数合成の有用性
では、準備が整ったので、関数合成の有用性を説いてみたいと思います。「Lisp脳」の謎に迫ると同じ、fizzbuzzを例にしてみます。
こんな感じで記述することができますね。
ex5
で、効用の話です。
3の倍数の時と3が付く数字の時はアホにしてほしい、あとアホより優先度低くていいので、Buzzはそのままで*2
こんな依頼が後からやってきた時、関数合成だったら割と修正が容易です。
最後の3行くらいを追加・変更しました。
ex6
compose内で、値の変換に作用する関数のうち、不要になった関数を消して、toAho1とtoAho2を追加して、順序を入れ替えました。一応、仕様が変わったので、関数名も変えていますが。
こんな感じで、関数をくっつけたり、剥がしたりしてプログラミングができる点が、関数合成の強みなのかなと思います。
注意点
このような関数合成を使ってプログラミングをする場合は、前の関数の返り値に強く依存する引数を取る関数を作って当てはめると、順番の入れ替えがしにくくなります。
なので、関数の実行順を入れ替えても問題ないように、関数を書いていく必要があります。そうすることで、ひとつひとつの関数がシンプルな小さな関数になり、組み合わせしやすい関数になるんじゃないかなと思っています。
おまけ
もっと汎用的にしたい場合は、関数合成と組み合わせて、部分適用を使うと便利です。部分適用はCoffeeScriptだと超簡単にできます。
exx
無駄に長くなってる感は否めませんが、汎用的にはなってるような気がします。
CoffeeScriptの場合は(x) -> (y) -> /* 関数本体 */と書くだけで部分適用できるので、活用しやすいです。
まとめ
富豪的プログラミングが許される状況においては、関数合成を使うことで、関数の切り貼り入れ替えがしやすくなり、柔軟性の高いプログラムを作りやすくなると思います。
私は富豪なSchemerになりたい。
