1

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.

luispauloml
  • 1,012
  • 1
  • 8
  • 16
  • I don't understand. How is that a tree at all? I get that conceptually `NodeData` describes a tree but in a CS perspective there are no tree like properties - no log n indexing or search, no links at all. It's just an association list where each lookup key can have multiple values. Did you mean for NodeData to entirely describe the tree's branch node? – Thomas M. DuBuisson May 30 '19 at 09:15
  • Binary search trees support log-time indexing; not all trees have to. – chepner May 30 '19 at 12:27
  • @ThomasM.DuBuisson No, I didn't mean it. `NodeData` should be used with some `Tree a` type to create the structure. I rewrote that part of the question. Perhaps now you understand what I mean. – luispauloml May 30 '19 at 14:41

1 Answers1

3

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
amalloy
  • 89,153
  • 8
  • 140
  • 205
  • What if the ids can't be `Ord`? I just edited the question to make this constraint explicit. And how can I update `value` based on the children's values? – luispauloml May 30 '19 at 14:50
  • If they're hashable, you can use a hashmap instead. If they're not even hashable, just eq, then you probably can't do anything better than the same algorithm but with linear search as your lookup operation. – amalloy May 30 '19 at 16:51
  • And if you can't figure out how to look at the children of a node given a Tree, you are probably asking too complicated a question by starting with this business of reconstructing a tree based on a list of parent links. – amalloy May 30 '19 at 16:53