Trying to implement path record for Haskell binary tree search

Question

I've been playing around with binary trees in Haskell, and I am attempting to implement a dfs variant that returns the path (composed of left and rights) from the root node to the node containing the value searched for. I think it would be best to return a Maybe Directions type.

Here is what has been implemented so far.

data Tree a = Empty | Node a (Tree a) (Tree a)
    deriving (Show, Eq)

data Direction = L | R 
    deriving (Show)
type Directions = [Direction] 

inTree :: (Eq a) => a -> Tree a -> [Direction]
inTree val (Node x l r)
    | val == x = []
    | l /= Empty = L:(inTree val l)
    | r /= Empty = R:(inTree val r)
    | otherwise = 

but I have no idea how to have it traverse the entire tree. I feel as though I might be thinking too imperatively.

Answer 1

Your idea to use Maybe Direction is good. I would rewrite your function as follows:

inTree :: (Eq a) => a -> Tree a -> Maybe [Direction]
inTree val Empty = Nothing
inTree val (Node x l r)
    | val == x = Just []
    | otherwise = (fmap (L:) (inTree val l)) <|> (fmap (R:) (inTree val r))

fmaping a function f on a Maybe results in Nothing if the original value is Nothing and Just (f v) if it's Just v. In our case if the recursive call found the value (so it's returning a path Just [Direction]) we append the Direction we took at the current node.

The <|> operator comes from the Alternative instance of Maybe. It's a left biased choice on maybes. Here we use it to pick the subtree which returned Just [Direction] (if there was any).

A good exercise is to modify the code so that it returns all the paths to the xs in the tree.

Answer 2

Here is a less streamlined version similar to the style presented in the question. This might be useful for anyone on a more basic level of learning Haskell and not yet understanding the contents of the Control.Applicative library.

inTree :: Eq a => a -> Tree a -> Maybe [Direction]
inTree _ Empty = Nothing
inTree val (Node x l r)
  | val == x  = Just []
  | otherwise = case inTree val l of Just ys -> Just (L : ys)
                                     Nothing -> case inTree val r of Just ys -> Just (R : ys)
                                                                     Nothing -> Nothing