CODEWITHSUNDEEP
haskell
user3050163
user3050163

Reputation: 135

Find the top of the tree(the root) in haskell

I have a tree like this:

data Tree a
  = Empty
  | Leaf a
  | Node a (Tree a) (Tree a) String
  deriving (Show)

and I need a function which finds the top of the tree. I have written this:

root :: Tree a -> a
root (Leaf a) = a
root (Node a _ _ _) = a

which perfectly works, but when I have an Empty tree, I have an error message.

If I add 

root Empty = Empty

I have an error again because it does not return a value of type a. What can I do ?

Upvotes: 2

Views: 1289

Answers (1)

Nikita Volkov
Nikita Volkov

Reputation: 43310

You have no sensible value of a in case of the Empty constructor. The type Maybe encodes exactly what you need in this case: a sensible value or no value. Therefore the following would be an idiomatic way of implementing your function:

root :: Tree a -> Maybe a
root (Leaf a) = Just a
root (Node a _ _ _) = Just a
root _ = Nothing

You can easily compose this function with other functions of your library using functors, applicative functors and monads. E.g.:

functionOnPlainA :: a -> a
functionOnPlainA = error "implement me"

-- So simply we can lift our plain function to work on values of type `Maybe`.
-- This is a Functor example.
functionOnMaybeA :: Maybe a -> Maybe a
functionOnMaybeA = fmap functionOnPlainA

-- Because the above is so simple, it's conventional to inline it,
-- as in the following:
applyFunctionOnPlainAToResultOfRoot :: Tree a -> Maybe a
applyFunctionOnPlainAToResultOfRoot tree = fmap functionOnPlainA $ root tree

-- And here is an example of how Monads can serve us:
applyRootToMaybeTree :: Maybe (Tree a) -> Maybe a
applyRootToMaybeTree maybeTree = maybeTree >>= root

Upvotes: 11

Related Questions