List To Tree 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" []]]