[Haskell-cafe] Re: Construct all possible trees

Jon Fairbairn jon.fairbairn at cl.cam.ac.uk
Thu Jun 14 05:58:10 EDT 2007

Mirko Rahn <rahn at ira.uka.de> writes:

> Jon Fairbairn wrote:
> > Trees with all the elements of a list in that order:
> >>the_trees [x] = [Leaf x]
> >>the_trees l = zipWith Branch (concat (map the_trees (tail $ inits l)))
> >>                             (concat (map the_trees (tail $ tails l)))
> Sorry, but this problem seems to trigger incorrect codes, somehow.

I don't think it's the problem in this case -- it's writing
code when half asleep.  The network connexion had been down
for hours, so it was past my bedtime when I started...

> splits xs = zip (tail . inits $ xs) (tail . tails $ xs)

I should have defined this (though I might have called it
partitions), probably like this:

> partitions l = inits l `zip` tails l

and used (with appropriate discarding) it in both the_trees
and combinations, and I should have written a proper
combinations rather than writing "nonempty_combinations" and
calling it "combinations".

Jón Fairbairn                                 Jon.Fairbairn at cl.cam.ac.uk

More information about the Haskell-Cafe mailing list