ListToTree Haskell Module

> {-# 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" []]]