flattening a tree

[Damien]

Hi,

Not sure if I should talk about flattening but basically I'm trying to
achieve the following transformation:

user=>(flatten-tree {1 {2 {3 4 5 6} 7 {8 9}}})
((1 2 3 4) (1 2 5 6) (1 7 8 9))

Any suggestion?
Thanks

[Meikel Brandmeyer]

Hi,

On 21 Feb., 08:17, Damien <damienlep...@gmail.com> wrote:

> Not sure if I should talk about flattening but basically I'm trying to
> achieve the following transformation:
>
> user=>(flatten-tree {1 {2 {3 4 5 6} 7 {8 9}}})
> ((1 2 3 4) (1 2 5 6) (1 7 8 9))

Using protocols seems overkill:

(defprotocol TreeFlattener (flatten-tree [this]))

(extend-protocol TreeFlattener
clojure.lang.IPersistentMap
(flatten-tree
[this]
(mapcat (fn [[k v]] (map #(cons k %) (flatten-tree v))) this))
Object
(flatten-tree
[this]
(list (list this)))
nil
(flatten-tree [_] (list (list nil))))

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

... but it also allows to add other data structures later on:

(extend-type clojure.lang.IPersistentVector
TreeFlattener
(flatten-tree
[this]
(mapcat (fn [idx x] (map #(cons idx %) (flatten-tree x))) (range)
this)))

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

Beware structure depths and stack overflows, though.

Hope that helps.

Sincerely
Meikel

[Damien Lepage]

Thanks, I expected something more simple but this protocol works well.
Before I stick to it, I'm just going to give a little bit more context.

I want to write a wrapper for the Java library Hector, client for Cassandra DB.
And this tree structure would be useful in the API.

Hector allows inserting many fields at once using the following syntax:

mutator.addInsertion(”jsmith,” "Identification",HFactory.createStringColumn(“first”, “John”))
   .addInsertion(“jsmith”, “Identification”, HFactory.createStringColumn(“last”, “Smith”))
   .addInsertion(“jsmith”, “Identification”, HFactory.createStringColumn(“middle”, “Q”))
   .execute();

To avoid the repetition of key ("jsmith") and column family (“Identification”), I thought a tree structure would be nice.
Something like:

(insert! {“jsmith”
                 {“Identification”
                      {“first” “John”, “last” “Smith”,  “middle” “Q”}}
                 {“Professional”
                      {“occupation” “programmer”}}})

Does it make sense to use this kind of Map here, along with the protocol proposed by Meikel to flatten it and call the Hector API?
Would I be better with vectors or something else?

Thanks a lot

2011/2/21 Meikel Brandmeyer <m...@kotka.de>

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

--
Damien Lepage
http://damienlepage.com

[James Reeves]

(defn flatten-tree [t]
(if (map? t)
(for [[k v] t, w (flatten-tree v)]
(cons k w))
(list (list t))))

In this case, I think using protocols would be over-engineering. We
can always add protocols in later if we happen to need them. That's
one of the benefits of protocols as compared to Java's interfaces.

- James

[rob levy]

One way to approve the problem is to write a function to convert the nested maps into nested seqs. Once it is in that form you can use flatten on it and partition the flat list as you like:

(defn flatten-maptree [m]

  (letfn [(maptree->seqtree

           [m]

           (lazy-seq

            (cond

             (map? m) (map #(cons

                             (key %)

                             (maptree->seqtree (val %)))

                           m)

             :else [m])))]

    (flatten (maptree->seqtree m))))

user=> (partition 4 (flatten-maptree {1 {2 {3 4 5 6} 7 {8 9}}}))

((1 2 3 4) (5 6 7 8))

[rob levy]

That is, had flattening actually been your goal.  It seem like you didn't really want to throw out that structure, just transform it, so flattening is irrelevant I guess other than the subject line. :)

[Damien Lepage]

Thanks Meikel, James and Rob for your inputs.
I'm gonna use the simple function provided by James and maybe try to come up with a better word than flatten ;o)

2011/2/21 rob levy <r.p....@gmail.com>