Sequence flatten function?

[Stuart Sierra]

Hello all,
Maybe I'm missing something, but how could I write a flatten function
in Clojure? That is, I want a function that turns [1 2 (3 [4] 5) [6
7]] into (1 2 3 4 5 6 7), for any sequence.

On a related note, is there a way to test if something *could* be a
sequence? (seq? [1]) returns false even though (seq [1]) is allowed.
At the same time, (seq ...) throws an exception if passed an "atomic"
value, like a number.

Thanks,
-Stuart

[jon]

Hi.. I'm new to clojure/lisp.. but I'm having some success with the
following..
It's not lazy and may break the rules (?).
I'm sure Rich will have the _real_ answer :)
--Jon


(defn persistcoll? [x]
(instance? clojure.lang.IPersistentCollection x))

(defn flatten [o]
(if (persistcoll? o)
(apply concat (map flatten o))
(list o)))

user=> (flatten [1 2 '(3 [4] 5) [6 7]])

[jon]

Here's a stab at a (semi) lazy version, which seems to work..
I'd be interested to hear if this is going about things the wrong way.
Thanks, Jon.

--------

(defn persistcoll? [x]
(instance? clojure.lang.IPersistentCollection x))

(defn rec-first-rest [a b]
(if (persistcoll? a)
(rec-first-rest (first a) (cons (rest a) b))
[a (apply concat b)]))

(defn lazy-flatten [o]
(when o
(let [[f r] (rec-first-rest o nil)]
(lazy-cons f (lazy-flatten r)))))

user=> (lazy-flatten ['({1 2} 3) 4 [5 {6 7 8 9}]])
(1 2 3 4 5 6 7 8 9)

[Rich Hickey]

On Mar 8, 10:46 am, Stuart Sierra <the.stuart.sie...@gmail.com> wrote:
> Hello all,
> Maybe I'm missing something, but how could I write a flatten function
> in Clojure? That is, I want a function that turns [1 2 (3 [4] 5) [6
> 7]] into (1 2 3 4 5 6 7), for any sequence.
>

The implementation of tree-seq has all you need to know. Or you could
just use it:

(defn flatten [x]
(let [s? #(instance? clojure.lang.Sequential %)]
(filter (complement s?) (tree-seq s? seq x))))

(flatten '[1 2 (3 [4] 5 "fred") [6 7]])
-> (1 2 3 4 5 "fred" 6 7)

Plus it's lazy.

> On a related note, is there a way to test if something *could* be a
> sequence? (seq? [1]) returns false even though (seq [1]) is allowed.
> At the same time, (seq ...) throws an exception if passed an "atomic"
> value, like a number.
>

It is very important to distinguish seq?, which is a type test, and
seq, which is a function of a collection that returns a sequential
view of that collection. It doesn't turn things into sequences, or
make them inherently sequential, or copy them into another sequential
data structure.

So, 'could be a sequence?', is not really a valid notion, things are
what they are (and some collections, like list, are in fact their own
seqs). A better question might be - 'does the seq function work on
this object?' As discussed before:

http://groups.google.com/group/clojure/msg/fc3cd6e81c9afb8d

I'm not sure of the utility of something like a generic seq-able? For
instance, would you want your flatten function to split apart the
characters in any contained string? Treat maps as sequences?

As above, it's not hard to specify exactly what you want to include/
exclude in the notion of sequence for a particular application. But
the set of things for which seq is supported is open and crosses
types, and thus dangerous to rely upon.

Rich

[Stuart Sierra]

On Mar 8, 4:01 pm, Rich Hickey <richhic...@gmail.com> wrote:
> On Mar 8, 10:46 am, Stuart Sierra <the.stuart.sie...@gmail.com> wrote:
>
> > Hello all,
> > Maybe I'm missing something, but how could I write a flatten function
> > in Clojure? That is, I want a function that turns [1 2 (3 [4] 5) [6
> > 7]] into (1 2 3 4 5 6 7), for any sequence.
>
> The implementation of tree-seq has all you need to know. Or you could
> just use it:
>
> (defn flatten [x]
> (let [s? #(instance? clojure.lang.Sequential %)]
> (filter (complement s?) (tree-seq s? seq x))))
>
> (flatten '[1 2 (3 [4] 5 "fred") [6 7]])
> -> (1 2 3 4 5 "fred" 6 7)
>
> Plus it's lazy.

Thanks, Rich! I hereby nominate this function for inclusion in the
standard library.

> > On a related note, is there a way to test if something *could* be a
> > sequence? (seq? [1]) returns false even though (seq [1]) is allowed.
> > At the same time, (seq ...) throws an exception if passed an "atomic"
> > value, like a number.
>
> It is very important to distinguish seq?, which is a type test, and
> seq, which is a function of a collection that returns a sequential
> view of that collection. It doesn't turn things into sequences, or
> make them inherently sequential, or copy them into another sequential
> data structure.
>
> So, 'could be a sequence?', is not really a valid notion, things are
> what they are (and some collections, like list, are in fact their own
> seqs). A better question might be - 'does the seq function work on
> this object?' As discussed before:
>
> http://groups.google.com/group/clojure/msg/fc3cd6e81c9afb8d
>
> I'm not sure of the utility of something like a generic seq-able? For
> instance, would you want your flatten function to split apart the
> characters in any contained string? Treat maps as sequences?
>
> As above, it's not hard to specify exactly what you want to include/
> exclude in the notion of sequence for a particular application. But
> the set of things for which seq is supported is open and crosses
> types, and thus dangerous to rely upon.

Ok, now I think I understand better. I was thinking of "sequence" as
a generic interface that all collections implement, when it's actually
an independent view over the collection. Thanks for your patience in
explaining this again.

-Stuart

[Arsalan Zaidi]

On Mar 9, 3:22 am, Stuart Sierra <the.stuart.sie...@gmail.com> wrote:
> On Mar 8, 4:01 pm, Rich Hickey <richhic...@gmail.com> wrote:
>
>
>
> > On Mar 8, 10:46 am, Stuart Sierra <the.stuart.sie...@gmail.com> wrote:
>
>
> Thanks, Rich! I hereby nominate this function for inclusion in the
> standard library.
>

+1

--Arsalan