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

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 2

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.