How do I label nodes in a Tree in Haskell?

user_38483 0
Viewed 98

Say that I have a Data.Tree holding characters: Tree Char:

    A
   / \
  B   C
     /|\
    D A F

Note that in the tree there could be duplicates. I want to store this tree in a relational DB by storing edges but I cannot use the content of the node as the key because of the duplicates (note the A at different levels).

Maybe a solution is to traverse de tree and map it with unique ids like:

    (1,A)
    / \
 (2,B) (3,C)
        /|\
  (4,D)(5,A),(6,F)

Now storing the edges hasn't any problem because I use the ids.

(1, null, A)
(2, 1, B)
(3, 1, C)
(4, 3, D)
(5, 3, A)
(6, 3, F)

But I cannot see how to "map" the static tree nodes to an infinite id generator.

What would be your approach from a functional point of view? Note that I cannot make any assumptions on the arity of the branching factor, so I cannot flatten, zip with ids, and reconstruct the tree

tree algorithm functional-programming haskell
1 Answers

You can work with a State that will dispatch ids, so:

import Control.Monad.State.Lazy(State, get, put)

labelNext :: State Int Int
labelNext = do
    val <- get
    put (val+1)
    return val

Then we can label the tree with:

{-# LANGUAGE TupleSections #-}

labelTree :: Tree a -> Tree (Int, a)
labelTree tree = evalState (traverse (\a -> (,a) <$> labelNext) tree) 1

This for example gives us:

ghci> labelTree (Node 'A' [Node 'B' [], Node 'C' [Node 'D' [], Node 'A' [], Node 'F' []]])
Node {rootLabel = (1,'A'), subForest = [Node {rootLabel = (2,'B'), subForest = []},Node {rootLabel = (3,'C'), subForest = [Node {rootLabel = (4,'D'), subForest = []},Node {rootLabel = (5,'A'), subForest = []},Node {rootLabel = (6,'F'), subForest = []}]}]}
user_675790
Related