Haskell vs Ruby

(2008.9.25 新規作成)

刺激的なタイトルにしてみましたが、どちらがいいとか悪いとか、という話ではありません。あしからず。

Haskell の特徴を調べるために、手続き型言語のRubyと比較してみようと思います。

ループ

変数の再代入やオブジェクトの破壊的な変更ができない Haskell ではループが書けません。

はるか昔、goto文が悪とされ、構造化プログラミングとしてgotoを使わないようになりました。goto文があればどのようなフローでも書けましたが、それに代わってwhileやforでループを書くようになりました。不自由ですが、ソースコードが明瞭になり、他人が書いたものでも読みやすくなりました。

変数への再代入が禁止されることで、ある変数が参照する値が勝手に変わることもなく、よりプログラムが読みやすくなります。ちょっと私はまだその境地には達していませんが。

ループのようなことは再帰で書きます。Haskell (に限らずたいていの最近の言語) では、再帰は可能であれば、gotoと同じ動作に変換されるので、効率も悪くありません。

Haskell
[RAW]
  1. fn x = if x == 1 then 1
  2. else x * fn (x - 1)
  4. main = print $ fn 10

Rubyでループを使って書くとこうでしょうか。

Ruby
[RAW]
  1. def fn x
  2. r = 1
  3. for i in 2..x do
  4. r *= i
  5. end
  6. r
  7. end
  9. puts fn(10)

こんなに短いとどちらが読みやすいも何もないですが、規模が大きくなると、変数の値が一つに決まるというのは安心感がある、かもしれません。

高階関数

関数型プログラミングでは高階関数を使いまくります。

リストの各要素に対して関数を適用してその結果のリストを作る、リストの要素に関数を適用して真になったものだけでリストを作る、リストを畳み込む、などなど、様々なパターンがあらかじめ組み込み関数などで用意されていて、その引数として自分で書いた関数を与えます。

例えば filter 関数は、最初の引数として関数を取り、その関数が真を返すリストを返します。

Haskell
[RAW]
  1. fn x
  2. | x `mod` 3 == 0 = True
  3. | otherwise = False
  5. main = print $ take 5 $ filter fn [1..]

実行結果: 

[3,6,9,12,15]

Rubyではブロックを使います。Rubyのブロックは、メソッドの引数として関数（クロージャ）を渡すためのシンタックスシュガーです。

Ruby
[RAW]
  1. p (1..15).select {|x|
  2. x % 3 == 0
  3. }

Rubyでもブロックを使いまくりますし、この辺は差が出ません。ただ、打ち切り条件の書き方に違いがあります。

内側と外側の逆転

Haskell は遅延評価 (lazy evaluation) で式を評価（実行）します。遅延評価は、データのうち、実際に必要になった部分しか使われません。

ループというかコードの内側で無限リストを使い、ループの外側に打ち切り条件を書く、ということができます。

例えばリストの最初の5つを得るときは、次のように書きます。

Haskell
[RAW]
  1. main = print $ take 5 [1..]

take によって必要とされる最初の5要素だけが評価されます。lazyでない、引数を先に評価する言語ではこれは完了しません。

Rubyだとこうです。

Ruby
[RAW]
  1. r = []
  2. i = 0
  3. while true
  4. r << (i += 1)
  5. break if i >= 5
  6. end
  7. p r

あまりにも短いので作為的ですが、とにかく、ループの内側に脱出条件を書く、というのがポイント。

私が Haskell を練習していたとき、このような逆転で、腸が捩れるような感覚になりました。

例題：素因数分解

少しだけ大きな題材として、大きな数の素因数分解をしてみます。

問題文は Project Euler から持ってきました (Problem 3)。

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

正の整数nを素因数分解するごく簡単な方法は、2から√n までの素数で割り切れるかどうか試すものです。

素数は、エラトステネスの篩（ふるい）で生成できます。

Rubyで書いた1回目。これはダメすぎな例です。

Ruby
[RAW]
  1. number = 600851475143
  3. # エラトステネスの篩 (ふるい) で素数リストを作成
  4. def prime_while max
  5. rest = Array.new(max - 1) {|i| i + 2}
  6. max_s = Math.sqrt(max).floor
  7. while (prime = rest.shift)
  8. return if !(yield prime)
  9. rest.delete_if {|i| (i % prime) == 0}
  10. break if prime > max_s
  11. end
  12. rest.each {|x|
  13. return if !(yield x)
  14. }
  15. end
  17. puts Time.now
  19. x = number
  20. prime_while (Math.sqrt(number).floor) {|pn|
  21. break if x == 1
  22. while x % pn == 0
  23. print "#{pn} "
  24. x /= pn
  25. end
  26. true
  27. }
  28. print "\n"
  30. puts Time.now

私の機械で、ちょうど1分ぐらい掛かりました。

次は Haskellで書いたもの。

Haskell
[RAW]
  1. number = 600851475143
  2. -- number = 34
  4. {- (1) 素数を求める
  5. 無限リストを用意し、2 を取り除いて、
  6. 2で割り切れないのだけ残したリストを作って、
  7. 再帰的に呼び出す。
  8. -}
  9. primes' (p:xs) = p : (primes' $ filter (\x -> x `mod` p /= 0) xs)
  11. primes :: [Integer]
  12. primes = primes' [2..]
  14. {- (2) 素因数分解する
  15. 単に、割って、再帰呼び出しする
  16. -}
  17. facto :: Integer -> [Integer] -> [Integer]
  18. facto n (pn:pns)
  19. | n == 1 = []
  20. | floor (sqrt (fromInteger number)) < pn = [n]
  21. | n `mod` pn == 0 = pn : (facto (n `div` pn) (pn:pns))
  22. | otherwise = facto n pns
  24. main = do
  25. print $ facto number $ primes

非常に短くなりました。

Haskell が遅延評価する、というところが重要で、素数を求める部分は無限リストを返しますが、効率が悪くなることがありません。primes' にも無限リストを与えていますが、これも大丈夫です。

実行すると一瞬で答えが出ます。

ただし、これをもってHaskellのほうが速い、というのは早計です。Ruby版は、篩（ふるい）のために 775,000 の要素を持つ配列を作っています。しかも素数を求める過程で詰めたりしています。

次のようにプロファイルを取ってみると、Array#initialize がほとんどの時間を占めています。アホです。 

$ ruby -rprofile 003.rb

では、どうするのがいいでしょうか。

素数かどうか不明な配列をあらかじめ用意するのではなく、素数かどうか調べたい数値について、素数の倍数でないか試し、当たらなかったら新しい素数です。効率化のために、素数の次の倍数にマークを付けるのがよさそうです（テストしたときにマークする先を替えていく）。

クロージャを使って面白い書き方をされている方がいましたので、貼り付けます（少し修正しました）。

Ruby
[RAW]
  1. class MyPrime
  2. include Enumerable
  4. def initialize
  5. @hash = {}
  6. @n = 1 # 直前の素数
  7. end
  9. # 次の素数を返す
  10. def succ
  11. n = @n
  12. while true
  13. n += 1
  14. if (s = @hash[n])
  15. s.call()
  16. @hash.delete(n)
  17. else
  18. # n は素数
  19. i,j = n,n
  20. f = Proc.new {
  21. k = i + j
  22. if (g = @hash[k])
  23. g.call()
  24. end
  25. @hash[k] = f
  26. j += n
  27. }
  28. f.call()
  29. @n = n
  30. return n
  31. end
  32. end
  33. end
  34. alias next succ
  36. def each
  37. g = MyPrime.new
  38. while true
  39. yield g.succ
  40. end
  41. end
  42. end
  44. x = 600851475143
  45. p Time.now
  47. gen = MyPrime.new
  48. while pn = gen.next
  49. break if x == 1
  50. while x % pn == 0
  51. print "#{pn} "
  52. x /= pn
  53. end
  54. end
  55. print "\n"
  57. p Time.now

今度は一瞬です。

比べてみると、

  • Haskell のほうがずいぶん短いコードになった。
  • Rubyではパフォーマンスを考えて作り込まなければならない。もちろん作り込めばRubyのほうが速いコードが書けるが、このぐらいの問題だとHaskellでは何も考えなくてもコンパイラがそこそこのコードを出力する。

問題の種類にもよるのでしょうけど、Haskell のほうが効率よく書ける可能性がありそうです。