[Haskell-beginners] [Q] Bulding an Array of Tree Nodes

[Chul-Woong Yang]

Hi, all.

I need to make graph/tree structure,
the nodes of which are contained in _array_
to facilitate random access to that node.

There is no problem in building an array of graph nodes from edge list.

> -- Graphs
> data Graph a = GNode a [Graph a]
> mkGraph :: [(a,[Int])] -> Array Int (Graph a)
> mkGraph table = table'
>   where n      = length table
>         table' = listArray (0,n-1) $
>           map(\(x,adjs) -> GNode x (map (table' !) adjs)) table

However, I cannot build tree from the same input,
if given edge list is undirected one.
The leaf node's edge has a link to parent node
when edge list is undirected, and I cannot find way
to cut that parent edge in building tree.

For example, think of following simple tree:
   A(0)
  / \
B(1) C(2)

It's hard to build tree with following edge list:
[('A',[1,2]),
 ('B',[0]),
 ('C',[0])]
but it's easy when edge list is following:
[('A',[1,2]),
 ('B',[]),
 ('C',[])]

How can I build an array of tree nodes for the former?
In other words, How can I build following mkTree function?

data Tree a =  Node { value :: a
                    , parent :: Tree a
                    , level :: Int
                    , children ::  [Tree a]
                    } deriving Show
mkTree :: [(a,[Int])] -> Array Int (Tree a)

Any comments or helps will be deeply appreciated.

Thank you.

Chul-Woong Yang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20161019/46c188da/attachment.html>