0

I'm trying to write a function that combines a list of rose trees with the their parent node being the highest values of the root nodes of the given rose trees. For example; 

RosesToRose [Rose 1 [Rose 1 [], Rose 2 []], Rose 3 [], Rose 4 [Rose 10 []]]

should return Rose 4 [Rose 1 [Rose 1 [], Rose 2 []], Rose 3 [], Rose 4 [Rose 10 []]]

I'm getting an error " Non-exhaustive patterns in function rosesToRose" and I'm not sure whats causing it. Tried matching against an empty list as input and got the same error. Any suggestions would be appreciated.

My code: 

data Rose a = Rose a [Rose a]
    deriving Show

rosesToRose:: (Ord a, Num a )=> [Rose a] -> Rose a
rosesToRose [(Rose node tree)] = Rose (maxRoseNode [(Rose node tree)]) [(Rose node tree)]

maxRoseNode:: (Ord a,Num a) =>[Rose a] -> a
maxRoseNode trs = case trs of
    [] -> 0
    (Rose node tree):xs -> maximum  ([maxRoseNode xs] ++ [node])
anon0987654321
  • 35
  • 5

1 Answers1

1

The pattern you use will only match a list with exactly one element. Indeed the pattern:

rosesToRose [(Rose node tree)] = …

matches a list with one Rose object. But in your sample data, you pass it a list with three elements. Furthermore the maxRoseNode does not make much sense if you pass the same list with one element.

You can solve the problem, by just matching this with a variable (rs for example), and then construct a Rose with maxRoseNode rs as value, and rs as children:

rosesToRose :: (Ord a, Num a) => [Rose a] -> Rose a
rosesToRose rs = Rose (maxRoseNode rs) rs

You can improve the readability (and efficiency) of maxRoseNode, by first checking if it is an empty list, and if not, calculate the maximum of the items wrapped in the Roses:

maxRoseNode:: (Ord a, Num a) => [Rose a] -> a
maxRoseNode [] = 0
maxRoseNode xs = maximum (map (\(Rose x _) -> x) xs)

Here \(Rose x _) -> x is a lambda expression that will map a Rose x _ object to x.

For example:

Prelude> rosesToRose [Rose 1 [Rose 1 [], Rose 2 []], Rose 3 [], Rose 4 [Rose 10 []]]
Rose 4 [Rose 1 [Rose 1 [],Rose 2 []],Rose 3 [],Rose 4 [Rose 10 []]]
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • Thanks. Just to confirm, the lambda expression in maxRoseNode is just evaluating the root of each node tree, instead of processing the whole tree - which increases the efficiency? – anon0987654321 Oct 19 '19 at 11:14
  • @anon0987654321: yes, but that has not much to do with the lambda-expression itself. We simply never recurse on the children of the `Rose` tree. So the maximum calculates the maximum over the values in the list, not the children (or grandchildren, etc.) of these nodes. – Willem Van Onsem Oct 19 '19 at 11:15