CODEWITHSUNDEEP
haskelltree
luispauloml
luispauloml

Reputation: 1010

How to create a tree hierarchy in Haskell?

How do I achieve the same result shown in this question using Haskell and non-binary trees, such as Data.Tree? Considering the record NodeData { nodeID :: String , parentID :: String, value :: a } to store data, and Data.Tree for the tree type, a tree would be:

Node $ NodeData "id" "parent" (value :: a) (children :: Forest (NodeData a)) :: Tree (NodeData a)

Now how could I update value based on the node's children's value and its own? The input table would be a list [NodeData]. NodeData and the ids could be made an instance of Eq, but not Ord.

Upvotes: 1

Views: 484

Answers (1)

amalloy
amalloy

Reputation: 91857

I see no particularly clever single-pass solution to this. You simply have to bite the bullet and do two passes: one pass creates an index of the form Map Id [Node], listing all the children of each node. Then a second pass consumes this index and reconstitutes it into a Forest a. Note it's not a Tree a, because there's no value to put at the root, and also because for all we know there are multiple roots.

import qualified Data.Map.Lazy as M
import qualified Data.Tree as T

newtype Id = Id Int deriving (Eq, Show, Ord)
data Node a = Node {id, parent :: Id, value :: a} deriving Show

input :: [Node String]
input = [ Node (Id 1) (Id 0) "1"
        , Node (Id 2) (Id 1) "1.1"
        , Node (Id 3) (Id 0) "2"
        , Node (Id 4) (Id 2) "1.1.1"
        , Node (Id 5) (Id 3) "2.1"
        , Node (Id 6) (Id 1) "1.2"
        ]

index :: [Node a] -> M.Map Id [Node a]
index m = M.fromListWith (++) $ do
  n@(Node this parent v) <- m
  pure (parent, [n])

recombine :: M.Map Id [Node a] -> T.Forest a
recombine m = go (Id 0) -- Implied root, but a more thorough solution would be explicit
  where go root = [ T.Node v (go idx)
                  | Node idx p v <- M.findWithDefault [] root m
                  ]

After this, we have the tree we wanted:

> putStr . T.drawForest . recombine . index $ input
2
|
`- 2.1

1
|
+- 1.2
|
`- 1.1
   |
   `- 1.1.1

Upvotes: 3

Related Questions