Rubyで関数型プログラミングをするための ImmutableList gem を公開

ImmutableList gem とは

Immutable な LinkedList を Ruby で使うためのライブラリです。

C-Extension なので、Rubyで実装したものに比べて動作が高速です。

Ruby の Array は 配列で実装されているため、 長いリストでの先頭への要素を追加(cons)や連結(append)が とても遅いという問題を解決しようと思って作りました。

用途としては、Rubyで再帰を使って関数型言語風にプログラムを組むことを想定しています。

Immutable List Gem (KLab ALM版) from Sho Hosoda

導入方法

RubyGems で公開したので、次のようにターミナルで入力するだけで導入できます。

$ gem install immutable_list

基本的な使い方

基本的には、Ocaml の List のような動作をします。メソッド名も Ocaml を意識しています。

require 'immutable_list'

p ImmutableList.new # => ()

p l1 = ImmutableList.new.cons(1).cons(2).cons(3) # => (3, 2, 1)
p l1.head # => 3
p l1.tail # => (2, 1)

p l2 = ImmutableList[1, 2, 3, "a", "b"] #=> (1, 2, 3, "a", "b")

p l1.rev_append(l2) #=> (1, 2, 3, 1, 2, 3, "a", "b")
p l1.rev #=> (1, 2, 3)
p l3 = l1.append(l2) #=> (3, 2, 1, 1, 2, 3, "a", "b")

p l3.length # => 8
p ImmutableList[].length #=> 0

p l3.nth(0) #=> 3
p l3[7] #=> "b"
p l3[100] #=> nil

Rubyで関数型プログラミングを書きたい

まずここで言う、関数型プログラミングというのは、 一般的な言語がループを使って繰り返しを表現するのに対して、 再帰を使って繰り返しを表現することを指します。

例えば、ImmutableListを使えば、クイックソートを次のように実装することができます。

再帰を使うことで、プログラムの本質に関係ないループと変数が消えて、 とても読みやすく短くプログラムを書くことができます。(読みやすさには個人差があります。)

require 'immutable_list'

def partition(a, l, lt, ge)
  if l.empty?
    [lt, ge]
  elsif l.head < a
    partition(a, l.tail, lt.cons(l.head), ge)
  else
    partition(a, l.tail, lt, ge.cons(l.head))
  end
end

def qsort(l)
  if l.empty?
    ImmutableList.new
  else
    lt, ge = partition(l.head, l.tail, ImmutableList.new, ImmutableList.new)
    qsort(lt) + qsort(ge).cons(l.head)
  end
end

l = ImmutableList[3, 5, 8, 1, 4, 7, 10, -3, 2, 100, 43, 10, 50]
p qsort(l) #=> (-3, 1, 2, 3, 4, 5, 7, 8, 10, 10, 43, 50, 100)

動作速度について

C-Extension なので、動作が高速だと言いますが、どのくらい速いのか気になる人もいるかと思います。

ArrayImmutableListで、先頭に長さ3のリストを 連結する処理にかかった秒数を、 連結した回数ごとにまとめました。

連結回数 Array LinkedList
10 1.5e-05 2.0e-05
1000 0.007251 0.00166
10000 0.727542 0.015206
100000 102.080825 0.414083

この測定には、benchmark.rb を用いました。

リストの長さが長くなるほど、ArrayよりもLinkedList の方が相対的に高速になります。

その他

  • GitHub
  • RubyExtensionProgrammingGuide がとても参考になりました。
  • WBなどはしていないので、RGenGC に対応できてるか不安です。
    • そもそも、どの関数も破壊的ではないので、WBが発生するタイミングが無い?
  • セーフレベルやオブジェクトの汚染など、セキュリティのことは全く考えてません。
  • headtailnth で要素がない場合ですが、すべてnilを返すようにして、例外は発生させないことにしました。
    • 将来的には例外を発生させるように仕様を変更するかもしれません。

これまでのあらすじ

RubyのC-Extentionとして、Immutable な LinkedList を作り、

RubyGems で C-Extention を含んだGemを作る方法を紹介しました。

1つ目の記事と内容がほとんど同じですが、クラス名やインストール方法が変わったので、記事を書き直しました。

comments powered by Disqus

gam0022.net's Tag Cloud

gam0022.net

Qiita