flatten

実装のバリエーションとして、メモ。
http://groups.google.com/group/clojure/browse_thread/thread/4072804251bbad81/15268e2a22418b8e?lnk=gst&q=flatten#15268e2a22418b8e

(defn flatten [lst]
  (lazy-seq
    (if (empty? lst) lst
      (let [[x & xs] lst]
        (if (list? x)
          (concat (flatten x) (flatten xs))
          (cons x (flatten xs)))))))

(defn flatten-2 [lst]
  (lazy-seq
    (if-let [x (first lst)]
      (let [xs (rest lst)]
        (if (seq? x)
          (concat (flatten-2 x) (flatten-2 xs))
          (cons x (flatten-2 xs)))))))

(defn flatten-3 [s]
  (lazy-seq
    (when-let [s (seq s)]
      (let [fst (first s)]
        (if (seq? fst)
          (concat (flatten-3 fst) (flatten-3 (rest s)))
          (cons fst (flatten-3 (rest s))))))))

user=> (flatten '(:a (:b :c) false :d :e))
(:a :b :c false :d :e)
user=> (flatten-2 '(:a (:b :c) false :d :e))
(:a :b :c)
user=> (flatten-3 '(:a (:b :c) false :d :e))
(:a :b :c false :d :e)

flatten-2はこの場合うまくいかない。

もちろんclojure-contribにはflattenがあるのでいちいち実装する必要はない。

user=> (use '[clojure.contrib.seq-utils :only (flatten)])
nil
user=> (flatten '(:a (:b :c) false :d :e))
(:a :b :c false :d :e)

ちなみに、On Lisp版はこうなってるらしい。

(defun flatten (x)
       (labels ((rec (x acc)
                     (cond ((null x) acc)
                       ((atom x) (cons x acc))
                       (t (rec
                            (car x)
                            (rec (cdr x) acc))))))
               (rec x nil)))