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.

Daniel · Accepted Answer · 2014-04-30 15:50:41Z

5

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.

edited Apr 30, 2014 at 15:50

answered Feb 14, 2014 at 4:21

Daniel

27.8k12 gold badges65 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jvkloc · Accepted Answer · 2021-07-26 11:27:09Z

1

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

answered Jul 26, 2021 at 11:27

jvkloc

9361 gold badge7 silver badges15 bronze badges

Collectives™ on Stack Overflow

Trying to implement path record for Haskell binary tree search

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related