無限リスト

エラトステネスの篩のGauche版を書いてみる。

(use util.stream)
(define (mod? x y) (not (zero? (modulo x y))))

(define (sieve l)
  (stream-cons (stream-car l)
    (sieve (stream-filter (cut mod? <> (stream-car l)) (stream-cdr l)))))

実行結果

gosh> (stream->list (stream-take (sieve (stream-iota -1 2)) 9))
(2 3 5 7 11 13 17 19 23)

各関数のstream-が邪魔なのでジェネリック関数等を使って以下のような定義を加えてみる。

(use srfi-1)
(define-method car ((x <promise>)) (stream-car x))
(define-method cdr ((x <promise>)) (stream-cdr x))
(define-method filter (f (x <promise>)) (stream-filter f x))
(define-method take ((x <promise>) i) (stream->list (stream-take x i)))
(define list-iota iota)
(define (iota . x) (apply (if (negative? (car x)) stream-iota list-iota) x))

それを使って書いたバージョン

(use mystream)
(define (mod? x y) (not (zero? (modulo x y))))

(define (sieve l)
  (stream-cons (car l) (sieve (filter (cut mod? <> (car l)) (cdr l)))))

実行結果

gosh> (take (sieve (iota -1 2)) 9)
(2 3 5 7 11 13 17 19 23)

stream-consだけは引数の評価を遅延するので事前に引数のクラスが調べられないのが残念。