Stream in Clojure

(define fibs
  (stream-cons 0
    (stream-cons 1
      (stream-add (stream-cdr fibs) fibs))))

The code above is an excerpt from SICP that generates an infinite Fibonacci sequence. I've tried to migrate it to Clojure.

The following code is the implementations of the stream concept mentioned in SICP and the the Fibonacci function. The essential part is this: (defmacro stream-cons [e s] ...). Because Clojure's cons requires that s to be a ISeq or Seqable, that makes the "(stream-cdr fibs)" part always fails. Because this piece of code is executed before the outer stream-cons ever happened. By the time we execute "(stream-cdr fibs)", we haven't had the value of "fibs" yet.

(defn pair [x y] (cons x [y]))
  
(defn pair-car [p] (first p))

(defn pair-cdr [p] (second p))

(defmacro stream-cons [e s]
  `(pair ~e (delay ~s)))
  
(defn stream-car [s]
  (pair-car s))
  
(defn stream-cdr [s]
  (force (pair-cdr s)))
  
(defn stream-map
  ([f s]
    (stream-cons
      (f (stream-car s))
      (stream-map f (stream-cdr s))))
  ([f s & ss]
    (let [step (fn step [ss]
                  (when (not (empty? ss))
                    (stream-cons (map stream-car ss) (step (map stream-cdr ss)))))]
      (stream-map #(apply f %) (step (cons s ss))))))
    
(defn stream-add [& ss]
  (apply stream-map + ss))
  
(defn take-stream [s count]
  (when (> count 0)
    (stream-cons
      (stream-car s)
      (take-stream (stream-cdr s) (dec count)))))
      
(defn print-stream [s]
  (let [step (fn step [s]
                (when (not (empty? s))
                  (print (stream-car s) "")
                  (recur (stream-cdr s))))]
    (step s)
    (println)))
    
(def fibs
  (stream-cons 0
    (stream-cons 1
      (stream-add (stream-cdr fibs) fibs))))
      
(def ones (stream-cons 1 ones))
(def twos (stream-add ones ones))

(print-stream (take-stream twos 10)) ; => 2 2 2 2 2 2 2 2 2 2
(print-stream (take-stream fibs 10)) ; => 0 1 1 2 3 5 8 13 21 34

Interesting enough that I haven't thought of a way to seamlessly integrate the above stream code into Clojure. If we implement it using (deftype LazyStream [] clojure.lang.Seq ...) that would make cons a function instead of a macro. Therefore I temporarily think that it's impossible to seamlessly integrate the implementation.

评论

2 楼 yangdong 2011-01-10  

谢谢。我只是追求形似，所以找不到对应的写法。

1 楼 jamesqiu 2011-01-10  

Clojure的lazy-cat和Scala的Stream实现fib数列都很清楚明白：
--- Clojure
(defn fib [a b] (lazy-cat [a] (fib b (+ a b))))
(take 10 (fib 0 1))
--- Sclaa
def fib(a:Int,b:Int):Stream[Int] = a #:: fib(b,a+b)
fib(0,1) take 10 toList