==== List To Tree module

% ignore

> {-# OPTIONS_GHC -fglasgow-exts #-}

> module ListToTree
>     ( Tree ( Tree )
>     , pairListToTreeList
>     , EmptyNode
>     , pairListToTree
>     )
> where
> import Data.Generics

% end ignore

There was a thread on haskell-cafe about doing this exact task. The
code I wrote is embarassingly complicated compared to their simple
answer. 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" []]]