Searching through a Binary Tree and returning level of a value-CodePudding

I'm attmepting to create a function that searches through a tree for a value and returns the level that the value is at, returning -1 if the value can't be found. To attempt this, I have written the following:

tree_search (NODE a t1 t2) x = tree_search_helper (NODE a t1 t2) x 1
tree_search_helper (NODE a t1 t2) x h = tree_search_helper t1 x h
  where
    tree_search_helper (NODE a t1 t2) x h 
      | not (tree_search_helper t1 x h 1 == -1) = tree_search_helper t1 x h 1  
      | (a == x) = h
      | otherwise = tree_search_helper t2 x h 1
    tree_search_helper (LEAF a) x h 
      | (a == x) = h 
      | otherwise = -1

However, no matter the input, it returns "1". Can anyone find the issue present!

CodePudding user response：

Defining a function tree_search_helper and then defining a local function with the same name using where is bound to lead to trouble. Let's consider the problem.

You have a tree type defined as such:

data Tree a = LEAF a | NODE a (Tree a) (Tree a) 
  deriving (Show, Read, Eq)

You want to find out how deeply located a given value is, or return some value indicating it isn't found. As @chepner indicated in comments, this is a good use for the Maybe type, since we will maybe find a level.

The simplest case is we look at a leaf and see if it has the value we want. If it is, we return the current level, which we passed in as an argument. Otherwise we return Nothing to indicate the value wasn't found.

level (LEAF a) v cur_level 
  | a == v    = Just cur_level
  | otherwise = Nothing

The other possibility is that we look at a node. If it has the value we're looking for, it's just as easy as the leaf. If it doesn't then we have to look in the left or right branches, incrementing the current level by one each time.

Remember that the function returns Maybe so we pattern match the result of recursively calling level on he left branch to determine if it found the value. If it didn't, we can search the right branch.

level (NODE a l r) v cur_level
  | a == v    = Just cur_level
  | otherwise =
      case level l v (cur_level   1) of
        Just l  -> Just l
        Nothing -> level r v (cur_level   1)

If passing the current level as 0 on the first go each time is annoying, we can hide this.

level t v = level' t v 0
  where
    level' (LEAF a) v cur_level
      | a == v    = Just cur_level
      | otherwise = Nothing
    level' (NODE a l r) v cur_level
      | a == v    = Just cur_level
      | otherwise = 
          case level' l v (cur_level   1) of
            Just l  -> Just l
            Nothing -> level' r v (cur_level   1)

CodePudding user response：

If you make a call with tree_search_helper t2 x h 1 it will be interpreted as (tree_search_helper t2 x h) 1, so you make a call with the same level, and increment it with one. As a result, the not (tree_search_helper t1 x h 1 == -1) will always be true, since the tree_search_helper t1 x h 1 can never return -1.

You thus can rewrite the code to:

tree_search_helper :: Eq a => Tree a -> a -> Int -> Int
tree_search_helper (NODE a t1 t2) x h 
  | tree_left != -1 = tree_left
  | a == x = h
  | otherwise = tree_search_helper t2 x (h 1)
  where tree_left = tree_search_helper t1 x (h 1)
tree_search_helper (LEAF a) x h 
  | a == x = h 
  | otherwise = -1

and the tree_search is just:

tree_search :: Eq a => Tree a -> a -> Int
tree_search t x = tree_search_helper t x 1

Using -1 is however not very common in Haskell, usually one returns a Maybe Int, and uses Nothing in case the item can not be found, so:

import Data.Maybe(isJust)

tree_search_helper :: Eq a => Tree a -> a -> Int -> Maybe Int
tree_search_helper (NODE a t1 t2) x h 
  | isJust tree_left = tree_left
  | a == x = Just h
  | otherwise = tree_search_helper t2 x (h 1)
  where tree_left = tree_search_helper t1 x (h 1)
tree_search_helper (LEAF a) x h 
  | a == x = Just h
  | otherwise = Nothing

CodePudding user response：

A better return type would be Maybe Int, where Just h represents a successful search and Nothing represents a failed search. This lets you take advantage of the Monoid instance of the Alt wrapper for Maybe.

tree_search :: Eq a => Tree a -> a -> Maybe Int
tree_search t x = go x 1 t
    where go h (Leaf y) | x == y = Just h
                        | otherwise = Nothing
          go h (Node y l r) | x == y = Just h
                            | otherwise = let rec = go (h 1)
                                          in getAlt (Alt (rec l) <> Alt (rec r))

Alt x <> Alt y, when used with Maybe values, behaves kind of like or for Boolean values: Alt x if x is a Just value, Alt y otherwise.