Checking if an element exists in a tree

Question

I defined a tree as follows and want to check if a given element is an element of a given tree or not. Here's the code I have, but it doesn't work fully. It only seems to work on the head.

I'm new to Haskell and can't figure out how to fix this.

data MyTree a = Leaf a | Node [MyTree a] deriving (Eq)

isElem :: (Eq a) => MyTree a -> MyTree a -> Bool
isElem (Node []) _ = error
isElem (Node (h:t)) (Leaf a) 
    | (Leaf a) `elem` (h:t) = True
    | otherwise = False

Here's my second attempt.

isElem :: (Eq a) => MyTree a -> MyTree a -> Bool
isElem (Node []) a = False
isElem (Node (h:t)) a
    | (a == h) = True
    | otherwise = (isElem (Node t) a)

Answer 1

In this answer, I explain how to implement isElem from scratch by following the structure of the datatype MyTree.

Following the structure

Your isElem function should look for an element all over a MyTree, so probably the structure of isElem should be similar to the structure of MyTree.

data MyTree a = Leaf a | Node [MyTree a]

To make the structure of MyTree clearer, let's call [MyTree a] a forest, because a forest contains multiple trees.

data MyTree a = Leaf a | Node (MyForest a)
type MyForest a = [MyTree a]

Now we have two types, and this helps us understand that we need two functions:

isTreeElem :: MyTree a -> a -> Bool
isForestElem :: MyForest a -> a -> Bool

I changed the second argument from MyTree a to a, as proposed in bheklilr's answer.

Implementing isTreeElem

Let's start with isTreeElem. We follow the structure of MyTree by pattern matching:

isTreeElem (Leaf x) y = ...
isTreeElem (Node forest) y = ...

In the equation for Leaf, there is only one location in the tree where the y could be. So we return True if x == y and False if x /= y. In other words:

isTreeElem (Leaf x) y = x == y

In the equation Node, we need to keep searching for y in the whole forest. So we simply call isForestElem.

isTreeElem (Node forest) y = isForestElem forest y

This is the first place where our decision to introduce MyForest and isForestElem pays out: We can follow the structure of trees without thinking about forests. In this case, we see that a node contains a forest, so we immediately know that isTreeElem (Node ...) should call isForestElem. To implement this, we don't have to think about what forests are or how isForestElem works, because these decisions are encapsulated in the isForestElem function.

Implementing isForestElem

At some point, we also need to implement isForestElem. A forest is just a list, so we follow the structure of [...] by pattern matching:

isForestElem [] y = ...
isForestElem (tree : forest) y = ...

In the case for [], there is no place left to search for y, so we return False:

isForestElem [] y = False

In the case for tree : forest, the y could either be in the tree or in the forest, so we call the corresponding functions and combine their result with the or operator ||:

isForestElem (tree : forest) y = isTreeElem tree y || isForestElem forest y

The is the second place where our decision to introduce MyForest and isForestElem pays out: We can follow the structure of forests without thinking about trees. In this case, we see that a forest contains a tree, so we immediately know that isForestElem (... : ...) should call isTreeElem. To implement this, we don't have to think about what trees are or how isTreeElem works, because these decisions are encapsulated in the isTreeElem function.

Note that we could have implemented isForestElem first and isTreeElem second without changing any of the reasoning.

The code

Here's what we have so far:

data MyTree a = Leaf a | Node (MyForest a)
type MyForest a = [MyTree a]

isTreeElem :: MyTree a -> a -> Bool
isTreeElem (Leaf x) y = x == y
isTreeElem (Node forest) y = isForestElem forest y

isForestElem :: MyForest a -> a -> Bool
isForestElem [] y = False
isForestElem (tree : forest) y = isTreeElem tree y || isForestElem forest y

Using list functions

If you want to write more functions that operate on MyTree, you can follow this recipe of always implementing a forest and tree version of every function. But at some point, you might notice that the forest versions are all very similar and kind-of boring. They feel like boilerplate that doesn't contribute a lot to your programs, but needs to be written anyway. If and when that's the case, you might want to use the list operations from the Prelude and Data.List modules instead of writing your own forest operations. For example:

isForestElem forest x = any (\tree -> isTreeElem tree x) forest

Or if we change the argument order of isTreeElem and isForestElem, we can even write:

isTreeElem :: a -> Tree a -> Bool
isTreeElem = ...

isForestElem :: a -> Forest a -> Bool
isForestElem x = any (isTreeElem x)

Now isForestElem is so simple that we might want to inline it into isTreeElem:

isTreeElem :: a -> MyTree a -> Bool
isTreeElem y (Leaf x) = x == y
isTreeElem y (Node forest) = any (isTreeElem y) forest

At some point, you should start to write code that is more like the last version of isTreeElem. But as an intermediate step, while you're learning Haskell (and functional programming?), you might want to focus on code like the firest version above, with separate isTreeElem and isForestElem functions. If you carefully structure your data types, the simple principle that the structure of the code should follow the structure of the data can get you a long way.

PS. By the way, the deriving Foldable trick in András Kovács's answer is also following the structure of the datatype, but automates it more.

Answer 2

I assume you're interested in implementing the function yourself (and bheklir addressed that), but you could also just derive it automatically:

{-# LANGUAGE DeriveFoldable #-}

import qualified Data.Foldable as F

data MyTree a = Leaf a | Node [MyTree a] deriving (Eq, F.Foldable)

isElem = F.elem 

Answer 3

If we had a binary tree

data BinTree a
    = Empty
    | Branch a (BinTree a) (BinTree a)
    deriving (Eq, Show)

Then we could do a search as

isElem :: (Eq a) => a -> BinTree a -> Bool
isElem a Empty = False
isElem a (Branch c left right)
    | a == c    = True
    | otherwise = isElem a left || isElem a right

Notice how in the second guard, I recursively call isElem on both the left and the right leaves. If one of them returns True, then the overall return value will be True because of the logical or (||). This recursion is the key to the algorithm.

I'd like you to think about how to apply recursion to not just 2 branches, but N branches, then combine them using or. Additionally, I would recommend that you define the function as

isElem :: (Eq a) => a -> MyTree a -> Bool

And to avoid the use of error. This function should never error. Either an element is in the tree or it isn't, there isn't a third state it could be in. Just return False instead.