『Scala 関数型デザイン＆プログラミング』の『Exercise 3.13』のふりかえり
第５回 関数型プログラミング勉強会で
『Scala 関数型デザイン＆プログラミング』の『Exercise 3.13』を解いて実例を試した。
この時、なんとなく解いてしまったので、以下のリンクのような疑問が残った。
http://se-info-tech.hatenablog.com/entry/2015/10/04/124454
もう一度、やってみる。
以下、雑文。
定義は下記となる。
def foldRightViaFoldLeft_1[A,B](l:List[A], z:B)(f:(A,B) => B):B = foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))) (z)
実行例として次を考える。
・z = 0
・l = [1,2,3]
また、関数id = (b => b)を、下で使用する。
foldRightViaFoldLeft_1([1,2,3], 0)(+) => foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))) (0)
ここで、foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))))を簡約していく
foldLeftの初項目のアキュムレータ算出結果
= ( (g,a) => b => g(f(a,b))) )(g = id, a = 1)
= ( b => id(1 + b) )
= ( b => 1 + b )
= <1+>
ただし、<1+> := x => 1 + x とする略記
foldLeftの第二項目のアキュムレータ算出結果
= ( (g,a) => b => g(f(a,b))) )(g = <1+>, a = 2)
= ( b => <1+>(2 + b) )
= <1+><2+>
ただし、<2+> := x => 2 + x とする略記
正確に記述すると
<1+><2+> := (x => (y => 1 + y)(2 + x))
(x => (y => 1 + y)(2 + x)) = (y => 1 + y) (x => 2 + x)
{∵ (y => 1 + y)上では、xは自由変数。
言い換えると、(y => 1 + y)は、xが何になろうと定義(動作仕様)が変わることは無い。}
となる。
foldLeftの第三項目のアキュムレータ算出結果
= ( (g,a) => b => g(f(a,b))) )(g = <1+><2+>, a = 3)
= ( b => <1+><2+>(3 + b) )
= <1+><2+><3+>
ただし、<3+> := x => 3 + x とする略記
正確に記述すると
<1+><2+><3+> := (x => (w => w + 1)(y => 2 + y)(3 + x))
自由変数だから
(x => (y => (w => w + 1)(2 + y))(3 + x)) = (w => w + 1)(y => 2 + y)(x => 3 + x)
となる。
(エレガントさの為に、演算子<n+>を導入したのに自由変数だからの件を書いたのは
本末転倒のような気もするが、記号操作に慣れていない層が
もしかしたらメジャー層とも、思えるので、迎合してみた。でもクドイですね。)
以上より、計算すると
foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))))(0) = <1+><2+><3+>(0) = <1+><2+>(3) = <1+>(5) = 6
略記せずに記述すると
foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))))(0) = (w => w + 1)(y => 2 + y)(x => 3 + x)(0) = (w => w + 1)(y => 2 + y)(0 => 3 + x) = (w => w + 1)(y => 2 + y)(3 + 0) = (w => w + 1)(y => 2 + y)(3) = (w => w + 1)(3 => 2 + y) = (w => w + 1)(2 + 3) = (w => w + 1)(5) = (5 => w + 1) = (5 + 1) = 6
となる。
どうせ、同値なんだから
とっちでも良い気がするけど
階層構造で頑なに記述してみると
foldLeft([1,2,3], id)((g,a) => b => g(f(a,b))))(0) = (x => (y => (w => w + 1)(2 + y))(3 + x))(0) = (0 => (y => (w => w + 1)(2 + y))(3 + x)) = (y => (w => w + 1)(2 + y))(3 + 0) = (y => (w => w + 1)(2 + y))(3) = (3 => (w => w + 1)(2 + y)) = (w => w + 1)(2 + 3) = (w => w + 1)(5) = (5 => w + 1) = (5 + 1) = 6
となる。
『SE情報技術研究会 管理者』さん、今度はどうでしょうか ?
下のページの方も、ここの所を書いていますね。
http://myutaro.blogspot.jp/2015/05/p51.html
http://nijojin.hatenadiary.jp/entry/2015/06/13/163814
作者の回答の訳
/*
The implementation of `foldRight` in terms of `reverse` and `foldLeft` is a common trick for avoiding stack overflows when implementing a strict `foldRight` function as we've done in this chapter.
> reverse と foldLeft の観点での foldRightの実装は、この章で行っている様な、正格評価の
> foldRight関数実装時に起こる、stack overflowを避ける時に、良く使う方法である。
(We'll revisit this in a later chapter, when we discuss laziness).
> (後の章の遅延評価の議論で再度取り上げる)
The other implementations build up a chain of functions which, when called, results in the operations being performed with the correct associativity.
> その他の実装は、関数の連鎖で構築しています。それが呼び出されると、正しい結合規則によって
> 実行される操作を、結果として生じさせます。
We are calling `foldRight` with the `B` type being instantiated to `B => B`, then calling
the built up function with the `z` argument.
> foldRight を呼び、B型(の引数)を、B => B にインスタンス化する。
> そして、z引数で、構築した関数の呼び出している
Try expanding the definitions by substituting equals for equals using a simple example, like `foldLeft(List(1,2,3), 0)(_ + _)` if this isn't clear.
> もし、よくわからないなら、foldLeft(List(1,2,3), 0)(_ + _)の様な簡単な例を用いて
> 同値から同値へ書き換えることによって、定義を展開してみてください
Note these implementations are more of theoretical interest - they aren't stack-safe and won't work for large lists.
> これらの実装は、それらはスタックセーフではなく、大きいリストでは働かないという、
> 理論的な関心のみということではないことに注意してください
*/
def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B =
foldLeft(reverse(l), z)((b,a) => f(a,b))
def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)
def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B =
foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)関数プログラミング(Rバード・Pワドラー)を見るとfoldl、foldrの定義は下記の通り
(なお、引数の順序はscalaとは違し、本とも記述形式を変えて、中高数学っぽくした。
また、<+>は、丸に+の記号で書きたかったが機種依存文字のようなので、代用として使用した。)
右側畳み込み
foldr(f, a, [x1,x2,...,xn]) = f(x1,f(x2, (... f(xn, a) ...)))
左側畳み込み
foldl(f, a, [x1,x2,...,xn]) = f((...f(f(x1, a),x2)...),xn)
読みやすい形式で書くと(f ≡ <+> で、前置記法から中置記法に変更)
foldr(<+>, a, [x1,x2,...,xn]) = x1 <+> (x2 <+> (x3 <+> (... (xn <+> a) ...)))
foldl(<+>, a, [x1,x2,...,xn]) = (... ((a <+> x1) <+> x2) ...) <+> xn
となる。
foldr(<+>, a, []) = a
foldr(<+>, a, [x1]) = x1 <+> a
foldr(<+>, a, [x1,x2]) = x1 <+> (x2 <+> a)
foldr(<+>, a, [x1,x2,x3]) = x1 <+> (x2 <+> (x3 <+> a))
括弧を常に右側にまとめていることから、「右側に畳込む(fold right)」という意味で
この演算をfoldrと呼ぶ。
foldl(<+>, a, []) = a
foldl(<+>, a, [x1]) = a <+> x1
foldr(<+>, a, [x1,x2]) = (a <+> x1) <+> x2
foldr(<+>, a, [x1,x2,x3]) = ((a <+> x1) <+> x2) <+> x3
同様に、「左側に畳込む(fold left)」という意味で
この演算をfoldlと呼ぶ。
後付の理屈でイメージをまとめて書く
(g,a) => b => g(f(a,b))を使用し、特に、g(f(a,b))でfの後にgを実行することによって
たとえば、上記例では、
『「(a <+> x1) <+> x2」の「(a <+> x1)」の演算<+>を「(...) <+> x2」の演算<+>の後に実行する』
となるように、実行順序を組み替えている。
一般化すると
『「(... <+> x[k-1]) <+> xk」の「(... <+> x[k-1])」の演算<+>を「(...) <+> x[k-1]」の
演算<+>の後、に実行する』
となるように、実行順序を組み替えている。
なぜなら、gは、現在処理中のlistのheadである、aの左側にあった、リスト要素の演算を行う様に
構成された関数だからである。
変数名の省略を嫌うオブジェクト志向界隈風にかけば、leftsideOparationsという名前で
def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
foldLeft(l, (b:B) => b)((leftsideOparations,a) => b => leftsideOparations(f(a,b)))(z)
とするかもしれない。
(ただし、leftsideOparationsの意味は、関数チェーン作成中で、リストl:[a,b,c,d,e,f] の要素cを処理している時に、aとbをcの左側にある要素として、leftsideとし、その操作だからOparationsとした。)
『b => g(f(a,b))』となるのは、その型が B => B つまり、初期値の(b:B) => bと
同じ型である必要があるから理解できる。
『(g,a) => 』は、
(1)このgは、演算の途中結果を蓄積するアキュームレータであり、初期値の(b:B) => bを
受取る関数型。
(2)aはふつうのfoldと同じで、Listの要素(head)を受取るものだから
こうなるのは、ふつうに当たり前ですね。
そう考えると、演算の順序を揃えることと、型を合わせることで
『(g,a) => b => g(f(a,b))』に決まってくる様な気がします。
次に
上でやった
<1+><2+><3+> := (x => (w => w + 1)(y => 2 + y)(3 + x))
(x => (w => w + 1)(y => 2 + y)(3 + x)) = (w => w + 1)(y => 2 + y)(x => 3 + x)
のように、階層構造で包まずに
(g,a) => b => g(f(a,b))
を、haskellのcompose演算子を使用して
(g,a) => g . (b =>f(a,b))
と書く。あるいはscalaの関数を使用して
(g,a) => g compose (b =>f(a,b))
(g,a) => (b =>f(a,b)) andThen g
と書けそう。
def foldRightViaFoldLeft_2[A,B](l: List[A], z: B)(f: (A,B) => B): B =
foldLeft(l, (b:B) => b)((g,a) => g compose (b =>f(a,b)))(z) // --- (*)
あるいは、
def foldRightViaFoldLeft_2[A,B](l: List[A], z: B)(f: (A,B) => B): B =
foldLeft(l, (b:B) => b)((g,a) => ((b:B) =>f(a,b)) andThen g)(z) // --- (**)
(*)の様に書けば、leftsideOparationsなどと書かなくても直感的になにをやっているのか
分りやすいのではないか。
冗長に書くと、小学生でもわかる風な、書き方になるかな ?
def foldRightViaFoldLeft_2[A,B](l: List[A], z: B)(f: (A,B) => B): B =
foldLeft(l, (b:B) => b)((leftsideOparations,a) =>
((b:B) =>f(a,b)) andThen leftsideOparations)(z)
なお、(*)と(**)は、手元にscala実行環境が無いので確認していない。
後で確認して、この記述を残すか、削除するか決める。
(=>確認して動いた。ただ、bに型指定を追加する必要があった。)この関数の連鎖で構築する方針の答えは、5章の遅延評価の議論への伏線で上げているのかな ?
reverseでの実装と、操作の回数は同じようだが、優劣はどうか ?
対比
reverseの操作 <=> 関数チェーンの構築
foldの実行 <=> 関数チェーンの簡約操作
個々の処理
reverseの操作 : 結果として操作の対象列ができる
関数チェーンの構築 : 操作の連鎖としての関数列ができる
foldの実行 : 対象列の要素を順次とりながら計算を実行
関数チェーンの簡約操作 : 最後の1引数関数から引数を与えて、得た返却値を
次の1引数関数に引数として与えて行く連鎖を繰返し
最終結果を得る。
『foldの実行』より『関数チェーンの簡約操作』の方がコストは低いかもしれない。
(実験してみれば良いかもしれない。)
ただ、普段の実装で、その微々たるコストを気にするレベルの人ならば
関数型言語は使用せずに、命令型言語のC言語などのコンパイル言語を
使用するべきかもしれない。
そのレベルの人ならば、その方が精神衛生上、楽なのでは ?
関数型が有利と言われている、並列処理もコンパイラやフレームワークの最適化に委ねないで
自ら考えた最適解をハードコーディングした方が、頭の良い人ならば
より良い解が求まるような気がする。
(でも、昔からある格言の、最適化は最後までやるな! とか 最適化は絶対するな!(大体は
物事が見えていない分かっていない人の要らない思い込みで、別の方法が在るはずだから)
とかありますが !"#$%&'?)
自分は頭が悪いし、このレベルの問題に時間を掛けて他のことができなくなるのは
嫌なので、気にせずに「common trick」と言っていたreverseを使う方針を採用するのが
現時点では、良いと思う。
別にみんなに使われる共通基盤を作る訳ではないし
仮にそうでもアルファバージョン位では、カリカリに最適化しなければいけない
理由もない様な ?
皆様は、どう考えるでしょうか ?
