ストリームを使ったアパート問題

これでいいのかな？

ストリームを使ったアパート問題のプログラムは以下のようになった．リスト版の決定性計算版よりはるかに遅いので，てっきり間違っていると考えたが，solveからはすぐに戻っているところをみると，動いているのかな？

しかし，全解探索するより遅いなんて…．効率を何も考えずに書いているからだろうか…．

(define (stream-filter-map f l)
  (stream-delay
   (stream-filter identity (stream-map f l))))

(define solve
  (lambda ()
    (stream-delay
     (stream-filter-map
      (lambda (floor)
        (let* ((floor (stream->list floor))
               (baker (first floor))
               (cooper (second floor))
               (fletcher (third floor))
               (miller (fourth floor))
               (smith (fifth floor)))
          (and (not (= baker 5))
               (not (= cooper 1))
               (and (not (= fletcher 5)) (not (= fletcher 1)))
               (> miller cooper)
               (not (= 1 (abs (- smith fletcher))))
               (not (= 1 (abs (- cooper fletcher))))
               (name-value baker cooper fletcher miller smith))))
      (stream-permutations (stream-iota 5 1))))))

非決定性計算とストリーム

ストリームって，探索木をフラットなリストに変換したようなもので，探索木をトラバースするのとストリームから解を1つずつ取り出すのって，実は等価だったりするのかな？ 任意の非決定性計算はストリームを使って書き直せて，逆も可能なのだろうか？

とりあえず，下のintegers-from-nは等価じゃないかな．

(define (integers-from-n n)
  (stream-delay (stream-cons n (integers-from-n (+ n 1)))))

integers_from_n(N,N) :- integer(N).
integers_from_n(N,N2) :- N1 is N + 1, integers_from_n(N1,N2).

次のprimesも等価な気がするが，本当かな…．

(define (divisible? x y) (zero? (remainder x y)))

(define (sieve stream)
  (stream-delay
   (stream-cons (stream-car stream)
                (sieve (stream-filter
                        (lambda (x) (not (divisible? x (stream-car stream))))
                        (stream-cdr stream))))))

(define primes (sieve (integers-from-n 2)))

:- dynamic prime/1.
non_prime(N) :- prime(P), P < N, N mod P =:= 0.
primes(N) :- integers_from_n(2,N), not(non_prime(N)), assert(prime(N)).

このProlog版エラトステネスのふるいは，assert/1を使うところがいかにもPrologらしくていいな．SiroKuroさんのプログラムをちょっと書き換えさせてもらったものだ．SiroKuroさんのは，ある上限値までの素数を表示するプログラムで，こちらは，?-primes(N)と質問すると，セミコロンを入力する限り，素数を返し続けるというふるまいをする．