2011/09/27

「よりClojureらしい素数列」をGaucheで

よりClojureらしい素数列 - OGINO Masanori@はてな

(defn prime?
  "Returns true if x is prime number, false otherwise."
  [x]
  (not-any? zero?
            (map #(rem x %)
                 (range 2 (inc (/ x 2))))))

(defn prime-numbers
  "Returns a lazy seq of prime numbers."
  []
  (filter prime? (drop 2 (range))))

効率的にベストではないけどとてもわかりやすいコードと解説だと思った。

で、無限素数列を生成して呼び出し側が必要なとこだけ取れるようにできるのが lazy sequenceの良いところなんだけど、現在のGaucheの開発版HEADでも これができるようになっている。

まだ試しにいろいろ書いてみて実装を調整してる段階なので、 APIとか揃ってないし確定もしてないんだけど。 上のコードをそのまま移植すると今のところはこんな感じで書ける:

(use srfi-1)
(use gauche.lazy)

(define (prime? n)
  (not (any zero? (lmap (pa$ mod n) (lrange 2 (+ 1 (/ n 2)))))))

(define (prime-numbers)
  (lfilter prime? (lrange 2)))

prime-numbersの戻り値は無限リストなのでREPLで表示させようとすると終わらなくなる。 *print-length*みたいのをそのうちつけるつもりだけど。 結果を表示するには、srfi-1のtakeで頭から必要なだけ取るとか (clojureのtakeと 引数の順序が違うことに注意):

gosh> (take (prime-numbers) 10)
(2 3 5 7 11 13 17 19 23 29)

100以下の素数だけ取るとか:

gosh> (take-while (pa$ > 100) (prime-numbers))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

100番目の素数だけ取るとか:

gosh> (~ (prime-numbers) 99)
541

ストリームライブラリ (refj:util.stream) との違いは、 リストを期待している関数にlazy sequenceをそのまま渡せるところ。 なのでeagerに結果が欲しくなった時点で普通のリスト処理関数を使える。 carやcdrももちろん使える。というより Schemeレベルではlazyなシーケンスか普通のペアかという区別はつかない (副作用や停止しないことを以って観測可能ではあるけれど)。

現在の実装はちょっと注意が必要で、 「必要とされる要素のひとつ先まで計算する」って性質がある。 これは性能上の要件としてわりとクリティカルで、今回の実装の肝でもあるんだけれど、 lazyなアルゴリズムを実装するのにshow stopperにならないかどうか、 まだ確信が持てない。 もし何らかのshow stopperが見つかったら、このlazy sequenceの機能を すぱっと諦めるかもしれない。

Tags: Gauche, Clojure