I am trying to define a minTree function using foldTree define by:
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree f e Leaf = e
foldTree f e (Node left x right) = f (foldTree f e left) x (foldTree f e right)
Here what I have so far.
minTree :: (Ord a) => Tree a -> Maybe a
minTree f e Leaf = e
minTree tree = foldTree f e tree
where
f x nothing = Just x
f x (Just y) = Just (min x y)
e = Nothing
But this code does not work and give a some error that I don't understand how to fix. Can someone help me to figure out what is wrong and how to fix it.
CodePudding user response:
In your example b ~ Maybe a
. This thus means that the first and the third parameter of f
are Maybe a
s. You thus will need to check both. The second item is an a
. Your f
should thus determine the minimum of two Maybe a
s and an a
, so something like:
minTree :: Ord a => Tree a -> Maybe a
minTree tree = foldTree f Nothing tree
where f Nothing y Nothing = Just y
f Nothing y (Just z) = …
f (Just x) y Nothing = …
f (Just x) y (Just z) = …
where I leave implementing the …
parts as an exercise. Since a
is a member of the Ord
typeclass, you can work with min :: Ord a => a -> a -> a
.