A better flatten

[Krukow]

Hello,
At some point I needed at "flatten" function taking a list of atomic
elements or nested lists, and producting a "flat" list of only atomic
elements (in the same order). It should be lazy.

This is what I came up with. Can anyone see a more elegant solution (I
feel I am working "low-level" somehow).

user> (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)))))))
#'user/flatten
user> (flatten '(1 2 3 4))
(1 2 3 4)
user> (flatten '((1 2) (3) 4))
(1 2 3 4)
user> (flatten '(((1) 2) (3) 4))
(1 2 3 4)
user>

/Karl

[tmountain]

I believe the flatten in contrib is defined as follows. I can't
remember which module I found it in.

(defn flatten
"Takes any nested combination of sequential things (lists, vectors,
etc.) and returns their contents as a single, flat sequence.
(flatten nil) returns nil."
[x]
(filter (complement sequential?)
(rest (tree-seq sequential? seq x))))

-Travis

[Sean Devlin]

It's in c.c.seq-utils

You can look up stuff here:

http://richhickey.github.com/clojure-contrib/api-index.html

[Sudish Joseph]

Hi Karl,

The other solutions seem higher level, but it's worth noting that
destructuring -- (let [[x & xs] lst] ...) -- uses next and is therefore
not fully lazy in that you will peek ahead by one into the lazy
sequence, so to speak. You have to use explicit first / rest to get
that:

;; with destructuring

(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)))))))

;; explicit first / rest
(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)))))))

;; returns a fresh, unevaluated, lazy seq each time
(defn lazy-integers []
(map #(do (print (str "[" % "] ")) %)
(iterate inc 0)))

Then:

user> (take 5 (flatten (lazy-integers)))
([0] [1] [2] 0 [3] 1 [4] 2 [5] 3 4)

user> (take 5 (flatten-2 (lazy-integers)))
([0] [1] 0 [2] 1 [3] 2 [4] 3 4)

So, flatten-2 never looks at the 6th element, 5, when it returns the
first 5. It's fully lazy in that it only evaluates the elements needed
for the result.

Of course, this is not a problem unless the lazy seq contains
computationally intensive or has side effects that need to be accounted
for in other ways.

-Sudish

[Krukow]

On Sep 3, 1:13 am, Sudish Joseph <sud...@gmail.com> wrote:
> The other solutions seem higher level, but it's worth noting that
> destructuring -- (let [[x & xs] lst] ...) -- uses next and is therefore
> not fully lazy in that you will peek ahead by one into the lazy
> sequence, so to speak.  You have to use explicit first / rest to get
> that:

[snip...]

Thanks everyone. I like the contrib version particularly.

Regarding eagerness of let: now that you mention it I recall that from
a recent thread.

http://groups.google.com/group/clojure/browse_frm/thread/32ff3ca7e2649867/ba0aa1edf7cfaeb1?hl=en

I think '&&' would be a nice addition.

/Karl

[Meikel Brandmeyer]

On Sep 3, 1:13 am, Sudish Joseph <sud...@gmail.com> wrote:

> (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)))))))

This version is broken:
user=> (flatten-2 '(:a (:b :c) false :d :e))
(:a :b :c)

Never check with first for nil. Always check explicitely with seq!

(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-3 '(:a (:b :c) false :d :e))
(:a :b :c false :d :e)

Sincerely
Meikel