「なぜ関数プログラミングは重要か」解読(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 で不自由なのはいわゆる「部分適用」。これはカリー化を使って第一引数で(というか前の引数から)しかできない。しかし「部分適用」は、コードにバグがあると対応が面倒そうなので、まあいいかという気もする。