4月の振り返り
3 月に続いて scheme をやっていた。練習問題として Project Euler を 20 問まで解いた。今まで Python、 JavaScript などオブジェクト指向の動的型付け言語ばかりをやっていたので一つくらい関数型言語を覚えたいという目標をとりあえず達成した形だ。
この記事は、その時困惑したところなどをまとめる。
プロジェクトオイラーとは？
プログラミングを使って解く数学の問題集。回答者だけが読めるフォーラムでいろいろな人がいろいろな言語を使って解いていて参考になる。
fold 適用順
gauche(scheme の処理系の一つ) には fold 系の手続き fold、 fold-left、 fold-right の三種類がある。
要するに Python, JavaScript に存在する reduce の一種と理解した。
例を挙げると次のように違う。
gosh> (fold cons '() '(1 2 3))
;; (3 2 1)
gosh> (fold-left cons '() '(1 2 3))
;; (((() . 1) . 2) . 3)
gosh> (fold-right cons '() '(1 2 3))
;; (1 2 3)
結果の差異は確認したので、次にその理由を見ていく。
調べて 1 週間もすればどれがどれか絶対にごっちゃなるだろうとか、他の言語ともズレている部分もありそうと思って調べてみるととっくにまとめた記事があった。
この章の記述はリンク先を読んで理解できれば、実のところ読む必要はない。
-
他言語との比較
-
fold 系手続きの比較
fold 系手続きは結果が適用順に依存しない計算ならばすべて同じ結果を返す。ここでは総和を例に適用順を説明する。
総和は fold で (fold + 0 '(1 2 3 4 5)) のように書ける。
適用順を調べるために + の代わりに次のような手続き addxy を作る。
見ての通り引数を表示して足し算するだけの手続きだ。
(define (addxy x y)
(print (format "X:~a Y:~a" x y))
(+ x y))
この手続きを使い 1 から 5 の総和の過程を確認していこう。
(define lst (iota 5 1 1)); '(1 2 3 4 5)
(print "list: " lst)
(newline)
(print "fold")
(print (fold addxy 0 lst))
(newline)
(print "fold-left")
(print (fold-left addxy 0 lst))
(newline)
(print "fold-right")
(print (fold-right addxy 0 lst))
このコードを実行するこのような結果を返す。
fold
X:1 Y:0
X:2 Y:1
X:3 Y:3
X:4 Y:6
X:5 Y:10
15
fold-left
X:0 Y:1
X:1 Y:2
X:3 Y:3
X:6 Y:4
X:10 Y:5
15
fold-right
X:5 Y:0
X:4 Y:5
X:3 Y:9
X:2 Y:12
X:1 Y:14
15
この結果をまとめるとつぎのようになる。
| 関数名 | 結果を蓄積する変数 | リストの読取方向 |
|---|---|---|
fold |
右 | 頭から |
fold-right |
右 | 逆から |
fold-left |
左 | 頭から |
終わりに
プロジェクトオイラーを解きながら書くべきでした。いろいろ気になっていたのにほとんど忘れてしまいました。
この感覚が抜けないうちに、静的型付け言語に挑戦するつもりです。候補は Java, Rust, Haskell のどれかです。