 Programming

```> {-# OPTIONS_GHC -fglasgow-exts #-}
> module ListToTree
>     ( Tree ( Tree )
>     , pairListToTreeList
>     , EmptyNode
>     , pairListToTree
>     )
> where
> import Data.Generics
```

There was a thread on haskell-cafe about doing this exact task. The code I wrote was embarassingly complicated compared to their simple answer, which inspired the below code. Thanks to Cale G. and Chris K.

```> data Tree a = Tree a [Tree a]   deriving (Show, Eq, Data, Typeable)
```

Actual exported function

```> pairListToTreeList             ::  [(Int, a)] -> [Tree a]
> pairListToTreeList []          =   []
> pairListToTreeList ((n,a):aa)  =
>     let (kids, sibs) = span (\x-> fst x > n) aa
>     in (Tree a (pairListToTreeList kids)) : pairListToTreeList sibs
```

Or straight to a tree, if an empty node for that tree type has meaning.

```> class EmptyNode a where
>   empty :: a
>
> instance EmptyNode [a] where
>   empty = []
>
> pairListToTree :: EmptyNode a => [(Int, a)] -> Tree a
> pairListToTree list = Tree empty (pairListToTreeList list)
```

Example test code

```> test = do print \$ pairListToTree list
>
> list :: [(Int, String)]
> list = [(1, "topA"),
>             (2, "secondC"),
>             (2, "secondD"),
>                 (3, "thirdG"),
>                 (3, "thirdH"),
>             (2, "secondE"),
>         (1, "topB"),
>             (2, "secondF")]
```

yields

```< Tree "" [Tree "topA" [Tree "secondC" [],
<                       Tree "secondD"
<                                     [Tree "thirdG" [],
<                                      Tree "thirdH" []],
<                       Tree "secondE" []]
<        , Tree "topB" [Tree "secondF" []]]

```
Archive