「なぜ関数プログラミングは重要か」解読(Ruby)
メモです。
melborne 氏のブログを参考に lambda のみで実装。
関数合成に関してはここを参考にしたが、これではうまくない。多少改変した。
cons = ->(a, list) do return [a] if !list or list == [] [a] + list end.curry #Ruby にはパターンマッチがないので、パターンマッチには cons1 を使う cons1 = ->(list) do return [list, []] if list.class != Array list.empty? ? [] : [list[0], list[1..-1]] end sum0 = ->(list) do return 0 if !list or list == [] num, l = cons1[list] num + sum0[l] end p sum0[[1, 2, 3, 4, 5]] #=>15 ### add = ->(x, y) {x + y} #高階関数 reduce reduce = ->(f, x, list) do return x if list == [] a, l = cons1[list] f[a, reduce[f, x, l]] end.curry sum = reduce[add, 0] p sum[[1, 2, 3, 4, 5]] #=>15 ### multiply = ->(x, y) {x * y} product = reduce[multiply, 1] p product[[3, 7, 10]] #=>210 #リストの結合 append = ->(list1, list2) {reduce[cons, list2, list1]}.curry p append[[5, 6], [1, 2]] #=>[5, 6, 1, 2] ### double = ->(x) {x * 2} #関数合成 class Proc def *(f) ->(*args) do ar = [] a = f.arity.abs if a < args.size args, ar = args.first(a), args[a..-1] elsif a > args.size b = f.curry[*args] return self.curry * b end self.curry[f.curry[*args], *ar] end.curry end end #高階関数 map map = ->(f, list) {reduce[cons * f, nil, list]}.curry #dlc = ->(num, list) {(cons * double)[num, list]} #doubleall = reduce[dlc, nil] #p doubleall[[3, 4, 6]] doubleall = map[double] p doubleall[[1, 2, 3]] #=>[2, 4, 6] ##### ##### ##### node = cons n4 = node[4, nil] n3 = node[3, cons[n4, nil]] n2 = node[2, nil] n1 = node[1, cons[n2, cons[n3, nil]]] tree = n1 redtree1 = nil redtree = ->(f, g, a, list) do label, subtrees = cons1[list] f[label, redtree1[f, g, a, subtrees]] end.curry redtree1 = ->(f, g, a, list) do return a if !list or list == [] subtree, rest = cons1[list] g[redtree[f, g, a, subtree], redtree1[f, g, a, rest]] end.curry sumtree = redtree[add, add, 0] p sumtree[tree] #=>10 labels = redtree[cons, append, nil] p labels[tree] #=>[1, 2, 3, 4] maptree = ->(f, list) {redtree[node * f, cons, nil, list]}.curry st = ->(x) {x.to_s} p maptree[st, tree] #=>["1", ["2"], ["3", ["4"]]] ##### ##### 遅延評価(Enumerator を使う) ##### ニュートン法による平方根の計算 ##### nxt = ->(n, x) {(x + n / x) / 2}.curry repeat = ->(f, a) do Enumerator.new {|y| loop {y << a; a = f[a]}} end within = ->(eps, enum) do a, b = enum.next, enum.peek return b if (a - b).abs <= eps within[eps, enum] end sqrt = ->(a0, eps, n) {within[eps, repeat[nxt[n], a0]]} p sqrt[1.0, 0.0001, 2.0] #=>1.4142135623746899 relative = ->(eps, enum) do a, b = enum.next, enum.peek return b if (a - b).abs <= eps * b.abs within[eps, enum] end sqrt = ->(a0, eps, n) {relative[eps, repeat[nxt[n], a0]]} p sqrt[1.0, 0.0001, 3] #=>1.7320508100147274
意外と Ruby でも関数型プログラミングが出来るものだな。
しかし思うのだけれど、ブロックを使った Ruby のメソッドチェーンは関数合成や高階関数のいいところ取りという気もする。ちがいますかね。
Ruby で不自由なのはいわゆる「部分適用」。これはカリー化を使って第一引数で(というか前の引数から)しかできない。しかし「部分適用」は、コードにバグがあると対応が面倒そうなので、まあいいかという気もする。