I was recently faced with the task of turning a table of database results of the form:

A    B    D
A    B    E
A    C    F
A    C    G

Into an XML structure like this:

<A>
    <B>
        <D/>
        <E/>
    </B>
    <C>
        <F/>
        <G/>
    </C>
</A>

The language I originally used to solve this problem was C# 1.0, which involved a while loop and a lot of conditions to check state. This is a rather inelegant solution; what I’d like to have done is taken a step back, and written a more generic function that converts any arbitrary table of results into its corresponding tree. C# lacks the tools to do this with any ease, but for Haskell, such abstractness is second nature.

import List (groupBy)
 
data Tree a = Tree a [Tree a]
 
instance Show a => Show (Tree a) where
  show (Tree x []) = show x
  show (Tree x ys) = (show x) ++ " -> " ++ (show ys)
 
(.^) :: (a -> a -> b) -> (c -> a) -> (c -> c -> b)
f .^ g = \x y -> f (g x) (g y)
 
empty :: [a] -> Bool
empty xs = (length xs) == 0
 
tableToTree :: Eq a => [[a]] -> [Tree a]
tableToTree = map mkBranch . groupBy ((==) .^ head) . filter (not . empty)
              where
              mkBranch xs = Tree (head . head $ xs) (tableToTree $ map tail xs)

I’ve created a custom tree type for this function, and added to the Show type class so that I could get some visible output from it. The tableToTree function works by recursively grouping columns into tree branches.