nested sequences to branching/tree data structure

clojure, f#, haskell, ocaml

Solution

The way I approached this problem was to use a `Forest` to represent your type and then make a `Forest` a `Monoid`, where `mappend`ing two `Forest`s together joins their common ancestors. The rest is just coming up with a suitable `Show` instance:

import Data.List (sort, groupBy)
import Data.Ord (comparing)
import Data.Foldable (foldMap)
import Data.Function (on)
import Data.Monoid

data Tree a = Node
    { value :: a
    , children :: Forest a
    } deriving (Eq, Ord)

instance (Show a) => Show (Tree a) where
    show (Node a f@(Forest ts0)) = case ts0 of
        []  -> show a
        [t] -> show a ++ " -> " ++ show t
        _   -> show a ++ " -> " ++ show f

data Forest a = Forest [Tree a] deriving (Eq, Ord)

instance (Show a) => Show (Forest a) where
    show (Forest ts0) = case ts0 of
        []  -> "[]"
        [t] -> show t
        ts  -> show ts

instance (Ord a) => Monoid (Forest a) where
    mempty = Forest []
    mappend (Forest tsL) (Forest tsR) =
          Forest
        . map (\ts -> Node (value $ head ts) (foldMap children ts))
        . groupBy ((==) `on` value)
        . sort
        $ tsL ++ tsR

fromList :: [a] -> Forest a
fromList = foldr cons nil
  where
    cons a as = Forest [Node a as]
    nil = Forest []

Here's some example usage:

>>> let a = fromList ["foo", "bar", "qux"]
>>> let b = fromList ["foo", "bar", "baz", "quux"]
>>> a
"foo" -> "bar" -> "qux"
>>> b
"foo" -> "bar" -> "baz" -> "quux"
>>> a <> b
"foo" -> "bar" -> ["baz" -> "quux","qux"]
>>> a <> a
"foo" -> "bar" -> "qux"

So your `myFunc` would become:

myFunc :: [[a]] -> Forest a
myFunc = foldMap fromList

Problem

I'm not sure if this is an easy problem to solve and I am just missing something obvious, but I have been banging my head against it for sometime. I am trying to express tree divergence using lists. This is so I can easily specify my dataset easily inline using simple primitives, not worry about order, and build the tree from a disperate set of lists later. So I have some lists like this: ``` a = ["foo", "bar", "qux"] b = ["foo", "bar", "baz"] c = ["qux", "bar", "qux"] ``` I would like to have a function, that would take a sequence of these lists and express a tree like so: ``` myfunc :: [[a]] -> MyTree a (root) -> foo -> bar -> [baz, qux] -> qux -> bar -> qux ``` An ideal solution would be able to take sequences of varying lengths, i.e: ``` a = ["foo"; "bar"; "qux"] b = ["foo"; "bar"; "baz"; "quux"] == (root) -> foo -> bar -> [qux, baz -> quux] ``` Are there any textbook examples or algorithms that can help me with this? seems like it can be solved elegantly, but all my stabs at it look absolutely horrible! Please feel free to post a solution in any functional language, I will translate it as appropriate. Thanks!

Original source