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