Adjacency list of a tree data structure in Haskell

Question

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?

Answer 1

Labeling nodes is quite trivial since GHC will do all the heavy lifting for you:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

import qualified Data.Traversable as T
import qualified Data.Foldable as F 
import Control.Monad.State 

data Trie a = Leaf a | Node a [(Char, Trie a)] 
  deriving (Eq, Functor, F.Foldable, T.Traversable)

number :: Trie a -> Trie (a, Int)
number = flip evalState 1 . T.mapM (\x -> state $ \n -> ((x,n),n+1))

As for printing the trie, I'm afraid that I don't quite understand the desired output.