Return tree for function with non-binary tree

Question

I have a non-binary tree:

data MultTree b = DataNode b | IndexNode Int Int [MultTree b] deriving (Show)

Note: DataNode's are treated like leafs and IndexNode's like branches.

Now I try to achieve that in IndexNode the smaller Int value is set to the smallest value of DataNode of the subtree and the bigger Int value is set to the biggest value of DataNode of the subtree.

For IndexNode's without a subtree the smaller Int value is set to minBound::Int and the bigger one to maxBound::Int

This is my function so far:

dataInterval:: (Ord a) => MultTree a -> MultTree a
dataInterval (DataNode x) = (DataNode x)
dataInterval(IndexNode x y [])
      | x > y  = (IndexNode (maxBound :: Int) (minBound :: Int) [])
      | x < y  = (IndexNode (minBound :: Int) (maxBound :: Int) [])
      | x == y = (IndexNode x y [])
datenInterval (IndexNode x y subtrees)
      | x > y  = (IndexNode (maxValue subtrees) (minValue subtrees) (map (dataInterval subtrees)))
      | x < y  = (IndexNode (minValue subtrees) (maxValue subtrees) (map (dataInterval subtrees)))
      | x == y = (IndexNode x y (map (dataInterval subtrees)))

have to call the function dataInterval recursively.

Now I do not know how to do that, because dataInterval expects a tree but somehow I have to call the complete list. dataInterval does not allow that.

Question: How can I achieve calling dataInterval recursively by using the subtrees in the list? So each tree of subtrees list will be called ?

I think it might be some functionality like map, but returning subtrees instead of a list.

At the moment the error message looks like that:

Couldn't match expected type MultTree a2 with actual type [MultTree a] * In the first argument of datenIntervalle, namely subtrees In the first argument of map, namely (datenIntervalle subtrees) In the third argument of IndexNode, namely (map (datenIntervalle subtrees))

sample tree & complete code:

t2 :: MultTree Int
t2 = IndexNode 3 42 [IndexNode 7 8 [DataNode 3, DataNode 5, DataNode 7, DataNode 9], DataNode 6, IndexNode 10 23 [DataNode 99, DataNode 78, DataNode 24]]

dataList:: MultTree a -> [a]
dataList(DataNode x) = [x]
dataList(IndexNode _ _ subtress) = concat' (map dataList subtress)

maxValue :: (Ord a) => MultTree a -> a
maxValue tree = maximum (dataList tree)

minValue :: (Ord a) => MultTree a -> a
minValue tree = minimum (dataList tree)

dataInterval:: (Ord a) => MultTree a -> MultTree a
dataInterval(DataNode x) = (DataNode x)
dataInterval(IndexNode x y [])
      | x > y  = (IndexNode (maxBound :: Int) (minBound :: Int) [])
      | x < y  = (IndexNode (minBound :: Int) (maxBound :: Int) [])
      | x == y = (IndexNode x y [])
dataInterval(IndexNode x y subtrees)
      | x > y  = (IndexNode (maxValue subtrees) (minValue subtrees) (map (dataInterval subtrees)))
      | x < y  = (IndexNode (minValue subtrees) (maxValue subtrees) (map (dataInterval subtrees)))
      | x == y = (IndexNode x y (map (dataInterval subtrees)))

Answer 1

I will post answer on your question also answering your last comment:

I have removed the the curved bracket and get an error. I would really appreciate it if you post some code. My error message: Couldn't match expected type MultTree Int' with actual type [MultTree a]'

The problem here is that you specify type of minBound :: Int. But in type of your function you said that you have tree of any type a which is Ord.

dataInterval:: (Ord a) => MultTree a -> MultTree a

So, Int is not equals to a. If you don't want your tree be polymorphic, you can just have dataInterval :: MultTree Int -> MultTree Int for example. But this is not the best solution. You can use minBound and maxBound for polymorphic type but you need to add Bounded constraint to a in type signature. And you don't need to specify type of minBound in your function because Haskell has type inference. So here is complete working example (I also removed some () because Haskell is not Lisp):

data MultTree b = DataNode b | IndexNode b b [MultTree b] deriving (Show)

t2 :: MultTree Int
t2 = IndexNode 3 42 [ IndexNode 7 8 [ DataNode 3
                                     , DataNode 5
                                     , DataNode 7
                                     , DataNode 9
                                     ]
                    , DataNode 6
                    , IndexNode 10 23 [ DataNode 99
                                      , DataNode 78
                                      , DataNode 24
                                      ]
                    ]

dataList :: MultTree a -> [a]
dataList (DataNode x)             = [x]
dataList (IndexNode _ _ subtrees) = flattenSubtrees subtrees

flattenSubtrees :: [MultTree a] -> [a]
flattenSubtrees = concatMap dataList

maxValue :: Ord a => [MultTree a] -> a
maxValue trees = maximum (flattenSubtrees trees)

minValue :: Ord a => [MultTree a] -> a
minValue trees = minimum (flattenSubtrees trees)

dataInterval :: (Bounded a, Ord a) => MultTree a -> MultTree a
dataInterval (DataNode x) = DataNode x
dataInterval node@(IndexNode x y [])
      | x > y  = IndexNode maxBound minBound []
      | x < y  = IndexNode minBound maxBound []
      | x == y = node
dataInterval (IndexNode x y subtrees)
      | x > y  = IndexNode (maxValue subtrees) (minValue subtrees) mappedSubtrees
      | x < y  = IndexNode (minValue subtrees) (maxValue subtrees) mappedSubtrees
      | x == y = IndexNode x y mappedSubtrees
  where
    mappedSubtrees = map dataInterval subtrees

I want to notice that this function implementation is not efficient. Because you traverse full tree each time you need to evaluate min and max values whereas in reality it's enough to traverse only last level after you found result for subtrees. Result of function call on t2 is:

ghci> dataInterval t2 
IndexNode 3 99 [IndexNode 3 9 [DataNode 3,DataNode 5,DataNode 7,
DataNode 9],DataNode 6,IndexNode 24 99 [DataNode 99,DataNode 78,
DataNode 24]]