Adjacency list of a tree data structure in Haskell

haskell

Solution

I came up with this solution:

import Data.List (foldl')

enum :: Int -> Trie -> ([(Int,Int,Char)],Int)
enum x Leaf = ([],x+1)
enum x (Node pairs)
  = let go (acc,y) (c,t) = (acc',y')
          where acc' = [(x,y,c)] ++ edges ++ acc
                (edges,y') = enum y t
    in foldl' go ([],x+1) pairs

`enum` takes a starting id and a `Trie` and returns a list of edges and the next available id.

-- some examples:

leafs xs = [ (c,Leaf) | c <- xs ]
t1 = Node $ leafs "XYZ"
t2 = Node [('W', t1)]
t3 = Node $ [('A',t2)] ++ leafs "BC"

enum 1 t1 -- ([(1,4,'Z'),(1,3,'Y'),(1,2,'X')],5)
enum 1 t2 -- ([(1,2,'W'),(2,5,'Z'),(2,4,'Y'),(2,3,'X')],6)
enum 1 t3 -- ([(1,8,'C'),(1,7,'B'),(1,2,'A'),(2,3,'W'),(3,6,'Z'),(3,5,'Y'),(3,4,'X')],9)

Problem

I have the following abstract data type defined in Haskell: ``` data Trie = Leaf | Node [(Char, Trie)] deriving (Eq) ``` The `Node` type is a list of elements `(c, t)` where `c` is the label for the edge from the current node to `t`. Now I want to print out the adjacency list of the tree. Specifically, I need to print one edge per row, where an edge is in the format: n1 n2 c with `n1` the source, `n2` the target, and `c` the label for the edge. I can print the edges from my root node with ``` instance Show Trie where show = show' 2 1 where show' _ _ Leaf = "" show' next n1 (Node ts) = unlines $ zipWith (\n2 (c, _) -> show n1 ++ " " ++ show n2 ++ " " ++ show c) [next..] ts ``` but now I'm stuck how to recursively print the children. In particular, how do I number the children nodes?

Original source