Nil Value for Tree a -> a in Haskell

Question

So I have a tree defined as

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

I know I can define Leaf to be Leaf a. But I really just want my nodes to have values. My problem is that when I do a search I have a return value function of type

Tree a -> a

Since leafs have no value I am confused how to say if you encounter a leaf do nothing. I tried nil, " ", ' ', [] nothing seems to work.

Edit Code

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


breadthFirst   :: Tree a -> [a]
breadthFirst x =  _breadthFirst [x]

_breadthFirst    :: [Tree a] -> [a]
_breadthFirst [] =  []
_breadthFirst xs =  map treeValue xs ++
                _breadthFirst (concat (map immediateChildren xs))

immediateChildren                       :: Tree a -> [Tree a]
immediateChildren (Leaf)              =  []
immediateChildren (Node n left right) =  [left, right]

treeValue                         :: Tree a -> a
treeValue (Leaf)                =  //this is where i need nil
treeValue (Node n left right)   =  n

test = breadthFirst (Node 1 (Node 2 (Node 4 Leaf Leaf) Leaf) (Node 3 Leaf (Node 5 Leaf Leaf)))

main =
  do putStrLn $ show $ test

Answer 1

In Haskell, types do not have an "empty" or nil value by default. When you have something of type Integer, for example, you always have an actual number and never anything like nil, null or None.

Most of the time, this behavior is good. You can never run into null pointer exceptions when you don't expect them, because you can never have nulls when you don't expect them. However, sometimes we really need to have a Nothing value of some sort; your tree function is a perfect example: if we don't find a result in the tree, we have to signify that somehow.

The most obvious way to add a "null" value like this is to just wrap it in a type:

data Nullable a = Null | NotNull a

So if you want an Integer which could also be Null, you just use a Nullable Integer. You could easily add this type yourself; there's nothing special about it.

Happily, the Haskell standard library has a type like this already, just with a different name:

data Maybe a = Nothing | Just a

you can use this type in your tree function as follows:

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

You can use a value wrapped in a Maybe by pattern-matching. So if you have a list of [Maybe a] and you want to get a [String] out, you could do this:

showMaybe (Just a) = show a
showMaybe Nothing  = ""

myList = map showMaybe listOfMaybes

Finally, there are a bunch of useful functions defined in the Data.Maybe module. For example, there is mapMaybe which maps a list and throws out all the Nothing values. This is probably what you would want to use for your _breadthFirst function, for example.

Answer 2

So my solution in this case would be to use Maybe and mapMaybe. To put it simply, you'd change treeValue to

treeValue                         :: Tree a -> Maybe a
treeValue (Leaf)                =  Nothing
treeValue (Node n left right)   =  Just n

Then instead of using map to combine this, use mapMaybe (from Data.Maybe) which will automatically strip away the Just and ignore it if it's Nothing.

 mapMaybe treeValue xs

Voila!

Maybe is Haskell's way of saying "Something might not have a value" and is just defined like this:

data Maybe a = Just a | Nothing

It's the moral equivalent of having a Nullable type. Haskell just makes you acknowledge the fact that you'll have to handle the case where it is "null". When you need them, Data.Maybe has tons of useful functions, like mapMaybe available.

Answer 3

In this case, you can simply use a list comprehension instead of map and get rid of treeValue:

_breadthFirst xs = [n | Node n _ _ <- xs] ++ ...

This works because using a pattern on the left hand side of <- in a list comprehension skips items that don't match the pattern.

Answer 4

This function treeValue :: Tree a -> a can't be a total function, because not all Tree a values actually contain an a for you to return! A Leaf is analogous to the empty list [], which is still of type [a] but doesn't actually contain an a.

The head function from the standard library has the type [a] -> a, and it also can't work all of the time:

*Main> head []
*** Exception: Prelude.head: empty list

You could write treeValue to behave similarly:

treeValue :: Tree a -> a
treeValue Leaf = error "empty tree"
treeValue (Node n _ _) = n

But this won't actually help you, because now map treeValue xs will throw an error if any of the xs are Leaf values.

Experienced Haskellers usually try to avoid using head and functions like it for this very reason. Sure, there's no way to get an a from any given [a] or Tree a, but maybe you don't need to. In your case, you're really trying to get a list of a from a list of Tree, and you're happy for Leaf to simply contribute nothing to the list rather than throw an error. But treeValue :: Tree a -> a doesn't help you build that. It's the wrong function to help you solve your problem.

A function that helps you do whatever you need would be Tree a -> Maybe a, as explained very well in some other answers. That allows you to later decide what to do about the "missing" value. When you go to use the Maybe a, if there's really nothing else to do, you can call error then (or use fromJust which does exactly that), or you can decide what else to do. But a treeValue that claims to be able to return an a from any Tree a and then calls error when it can't denies any caller the ability to decide what to do if there's no a.