「なぜ関数プログラミングは重要か」解読(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, 2, 1]

###

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 でも関数型プログラミングが出来るものだな。

Linux Mint には Ruby がデフォルトで入っている

Linux Mint 18.2 で確認。

$ ruby -v
ruby 2.3.1p112 (2016-04-26) [x86_64-linux-gnu]

 
Ubuntu 17.04 にはまだデフォルトでは入っていないようだ。

Ruby の型注釈のオレオレ記法

Ruby が型を明示的に書かないのはすごくラクだし気に入っているのだけれど、複雑な処理をするメソッドなどでは型注釈があった方がわかりやすい場合もあります。なので、コメントで型注釈をする仕方を自分で決めてみました。
 

●引数(self も含む) -> メソッド内の変数 >> 返り値

メソッド内に出現するすべての変数を登場順に書きます。引数と返り値は自明ならば省略します。

def hoge(a, b, c)
  #a, b, c -> x, .. >> String
  x = a.each {}
  ...
  return result
end

 

●型

型としてクラス名を指定します。下みたいな感じ。型が自明な場合は省略します。

def hoge
  #Integer{i, j}, Array{ar}, a, b, ...
end

 
ダッグタイピングで型が複数あるばあいは、Integer or Float{num, r, ..} のように書きます。

配列の場合は、中身の型を書いてもよい。

  #Integer{a[], matrix[][]}, ...

あるいは

  #Array[Integer]{a1, a2, ..}

あるいは

  #a[Integer, String], ...

 
ハッシュの場合は、

  #Hash{h[Object]: Integer, ...}

あるいは

  #(Hash[Symbol]: Integer){h1, h2, ...}

みたいに書いてもよい。

●ユーザー定義型

同じ Integer でも呼び方を変えたい場合は、「%ユーザー定義型 = クラス名」みたいに宣言して使う。

  #%distance = Integer, %counter = Integer
  #%distance{r, d}, %counter{i, j}

みたいに。

●返り値

配列が返るときだけ、

  # ... >> [String]

みたいな書き方を許す。


こんな感じでどうでしょうか。

例。
基数ソート(Ruby) - Camera Obscura
Ruby で循環小数を扱う - Camera Obscura
ベルマン−フォード・アルゴリズム(Ruby) - Camera Obscura

Ruby で循環小数を扱う

以前にも同様の試みをしたのですが(参照)、コードを始めから書き直しました。以前のは何か自分でもよくわからない、面倒なことをしているので。

作ったのは Rational#to_rec_decimal と String#to_r で、前者は Rational(分数)を(String で表される)循環小数に、後者はその逆で(String で表される)循環小数を Rational(分数)に直します。ともに負数もサポートします。String#to_r は同名の組み込みメソッドをオーバーライドしています。

例。

irb(main):001:0> require './rec_decimal'
=> true
irb(main):002:0> Rational(25, 17).to_rec_decimal
=> "1.(4705882352941176)"
irb(main):003:0> Rational(12, 7).to_rec_decimal
=> "1.(714285)"
irb(main):004:0> Rational(55, 48).to_rec_decimal
=> "1.1458(3)"
irb(main):005:0> "0.23(41)".to_r
=> (1159/4950)
irb(main):006:0> "7.(3)".to_r
=> (22/3)
irb(main):007:0> Rational(-1, 3).to_rec_decimal
=> "-0.(3)"
irb(main):008:0> "-2.45(7)".to_r
=> (-553/225)

 
コード。
rec_decimal.rb

class Rational
  #分数を循環小数に直す
  def to_rec_decimal
    #String{f, result}, Rational{num, ra}
    #Integer{i, remainder, deno, place[], rems[], idx} >> String
    
    f, num = (self < 0) ? ["-", -self] : ["", self]
    
    i = num.to_i
    result = f + i.to_s
    ra = num - i
    return result if ra.zero?
    result += "."
    
    remainder = ra.numerator
    deno      = ra.denominator
    place = []
    rems  = []
    begin
      rems  << remainder
      place << remainder * 10 / deno
      remainder = remainder * 10 % deno
      return result + place.join if remainder.zero?
    end while not (idx = rems.find_index(remainder))
    place.insert(idx, "(")
    result + place.join + ")"
  end
end

class String
  #循環小数を分数に直す
  alias :__to_r__ :to_r
  def to_r
    #String{st}, Rational{result}, m, f, l >> Rational
    st = delete(" ")
    return st.__to_r__ unless (m = /^([^\d]?)(\d+)\.(\d*)\((\d+)\)$/.match(st))
    f = (m[1] == "-") ? -1 : 1
    
    result = (m[2] + "." + m[3]).__to_r__
    l = m[4].length
    result += Rational(m[4].to_i, 10 ** l - 1) * Rational(1, 10) ** m[3].length
    result * f
  end
end

 

Gem 化

いろいろ使っているコードを Gem 化した中に入れておきました。
kaki-utils | RubyGems.org | your community gem host
インストールは $ gem install kaki-utils で。使うときは

require 'kaki/utils/rec_decimal'

でどうぞ。

Ruby で Python の for else みたいなの

繰り返しを実行して break(あるいは return)されなかったら何かを実行するって時々欲しいのですけれど、Ruby では Python の for else みたいな構文がないのですよね。なので throw ~ catch を使って大域脱出したりするのだけれど、どうにかできないかと思って考えてみました。

Enumerator#with_else(f) {..} です。f は Proc オブジェクトです。each などの Enumerator をレシーバーとして、ブロック内で break が実行されなければ、繰り返しを終えたあとに f.call されます。ブロックがなければ Enumerator を返します。
こんな感じ。

f = proc do
  puts "break せずに実行されました!"
end

ar = []
5.times {ar << rand(5)}
ar.each.with_else(f) do |i|
  puts i
  break if i == 4
end

を実行すると

1
0
0
1
3
break せずに実行されました!

みたいな。break されると

0
4

という風に f は実行されません。

また、each_with_index などと組み合わせて

ar = []
5.times {ar << rand(5)}
ar.each_with_index.with_else(f) do |i, j|
  p [i, j]
  break if i == 4
end

で、

[0, 0]
[0, 1]
[1, 2]
[1, 3]
[0, 4]
break せずに実行されました!

なんてのも可能です。


コードはこんな感じ。
with_else.rb

class Enumerator
  def with_else(f, *args)
    if block_given?
      each {|*i| yield(*i)}
      f.call(*args)
    else
      Enumerator.new do |y|
        each do |*i|
          a = (i.size <= 1) ? i[0] : i
          y << a
        end
        f.call(*args)
      end
    end
  end
end

else 節の可変長引数の処理にちょっと悩みました。
 
じつは前にも考えたのだけれど、上のように落ち着きました。

でも、やっぱり throw ~ catch の方が見やすいですかね…。
 

Gem 化

調子にのって Gem にしました。まったく大したものではないですが…。(9/11)
with_else | RubyGems.org | your community gem host

GTK+ で落書き 12(Ruby)

三角形の内心・外心・重心・垂心・傍心
自分で求めた公式を使って、三角形の内接円と外接円を Ruby で描いてみました。
 
20170908123010

描画には自作の Gem 'oekaki' を使っています。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた(Ruby) - Camera Obscura

require 'oekaki'
require 'ostruct'

Width, Height = 400, 300

A = Vector[-0.2,  0.8]
B = Vector[-0.8, -0.3]
C = Vector[ 0.8, -0.3]

incircle     = OpenStruct.new
circumcircle = OpenStruct.new

l, m, n = (B - A).norm, (C - B).norm, (A - C).norm
q = l + m + n

incircle.p = A * (m / q) + B * (n / q) + C * (l / q)
incircle.r = sqrt((q / 2 - l) * (q / 2 - m) * (q / 2 - n) * 2 / q)

a = A[0] * (B[1] - C[1]) + B[0] * (C[1] - A[1]) + C[0] * (A[1] - B[1])

circumcircle.p = Vector[(A.norm ** 2 * (B[1] - C[1]) + B.norm ** 2 * (C[1] - A[1]) +
                            C.norm ** 2 * (A[1] - B[1])) / a,
                        (A.norm ** 2 * (C[0] - B[0]) + B.norm ** 2 * (A[0] - C[0]) +
                            C.norm ** 2 * (B[0] - A[0])) / a] / 2
circumcircle.r = (A - circumcircle.p).norm

class Vector
  def to_w
    l = Height / 2
    Vector[Width / 2 + self[0] * l, l - self[1] * l]
  end
end


Oekaki.app width: Width, height: Height do
  draw do
    clear
    
    color(0, 65535, 0)
    line(A.to_w[0], A.to_w[1], B.to_w[0], B.to_w[1])
    line(C.to_w[0], C.to_w[1], B.to_w[0], B.to_w[1])
    line(A.to_w[0], A.to_w[1], C.to_w[0], C.to_w[1])
    
    color(65535, 65535, 0)
    circle(false, incircle.p.to_w[0], incircle.p.to_w[1], incircle.r * Height / 2)
    
    color(65535, 0, 65535)
    circle(false, circumcircle.p.to_w[0], circumcircle.p.to_w[1],
       circumcircle.r * Height / 2)
  end
end

 
定数 A, B, C が三角形の頂点の座標なので、いろいろ変えて遊んでみて下さい。例えば

A = Vector[-0.7,  0.6]
B = Vector[-0.2, -0.8]
C = Vector[ 0.7, -0.4]

にすると
20170908134541
となります。ちなみに座標はウィンドウのそれではなく、原点がウィンドウの中心となるようなふつうの x-y座標系で、Y方向の最大最小値がそれぞれ 1, -1 になっています。

なお、Gem 'oekaki' のバージョンを 0.1.1 に上げました。変更点はメソッド Tool#clear の引数を省略した場合、黒色で画面クリアが行われるようにしたことです。上のコードはそれを前提に書かれています。
 

追記


こんなのも描いてみました。コードは下。
移動する内接円 · GitHub

OpenGL で正多面体を回転させてみる その2(Ruby)


前回のエントリの隠面消去バージョンです。

5つのウィンドウが同時に立ち上がるのは同じです。

コードは下のリンク先にあります。
OpenGL で正多面体を回転させる · GitHub