Home > Mobile >  minimal value of Binary Tree
minimal value of Binary Tree

Time:11-06

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 as. You thus will need to check both. The second item is an a. Your f should thus determine the minimum of two Maybe as 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.

  • Related