How to return a value in this recursive function?

Questions / Help
1

HI,

I have a Zipper tree and try to label (with integers) the nodes in pre-order.

When the function detects state == index it continues processing

instead stopping the processing and return the state value.

See this code:

   
  def find_node( nil, _, _), do: nil
  
  def find_node(_ , state), do: {:ok, state}
   
  def find_node(node, index, counter) do
  
       v = value(node)

       Agent.update(counter, fn x -> x + 1 end )
       state = Agent.get(counter, &(&1))
             
       if index == state do
        
       #-------------------------------------------------------------
       #At his point the function should stop and return with 
       #the state equal to index
       #-------------------------------------------------------------
       
       end
      
       find_node(left(  node), index, counter)
   
       find_node(right( node), index, counter)
 
  end
2

You can’t do an »early return« in Elixir. You will need to use case, cond or with instead. There is a very helpful guide on the Elixir website about case, cond and if and also a good section about with.

Note that the way you’ve set up the function right now, will also not work with your two find_node/3 calls. The result of the first find_node will simply be discarded.

So maybe you should do something like this instead:

if index == state do
  index
else
  with nil <- find_node(left(node), index, counter) do
    find_node(right(node), index, counter)
  end
end

Like this, the function will return index if index == state. If it finds a node on the left side, it will return that, otherwise it will return the result of the find_node call for the right side.

3

Actually that’s not entirely accurate (even though in principle with “return” you are correct). The problem is that other programming languages have put a bias in peoples minds that throw is an error mechanism - well in Erlang/Elixir it isn’t - throw simply allows the function to “throw” (rather than “return”) a value up in the air and float it up the calling chain to however will bother to “catch” it. That’s why there are three different “catch” classes/categories:

  • :error - runtime errors which in Elixir can also be handled via rescue
  • :exit - to catch exits, i.e. exit(reason) from within the process (being a target of Process.exit cannot be “caught” - you have to trap exits (with Process.flag(:trap_exit,true)) and process :EXIT messages). These should be treated as the true exceptions in Elixir/Erlang.
  • values which are simply “thrown”.

Learn You Some Erlang shows a non-failure use case of throw - an example of a tree search implementation which throws the found value back to the root call of the search where the thrown value is caught.

3 Likes
4

As an aside, why are you using the agent like a mutable variable? just keep the counter as a function argument, using Agents as mutable state in this way is a misuse of Agents.

3 Likes
5

Instead of requiring the use of an ‘early return’, you can just return from your recursion here without problems.

Something like:

# Public API: Returns {:ok, value_of_node_at_target_index} or {:error, index}.
def find_node(zipper_tree, target_index), do: find_node(zipper_tree, target_index, 0)

# Base case: Empty (sub)tree
defp find_node(nil, target_index, current_index), do: {:error, current_index}

# Recursive case: Try current node, or left subtree, or right subtree.
defp find_node(zipper_tree, target_index, current_index) do
  if target_index == current_index
    {:ok, value(zipper_tree)}
  else
    with {:error, left_child_index}  <- find_node(left(zipper_tree),  index, current_index + 1)),
         do:  find_node(right(zipper_tree), index, left_child_index + 1))
  end
end

Other notes:

  • What are the first two function clauses in your example code for? At least the second one only takes two parameters and not three.
  • Either use some_value | nil or {:ok, value} | {:error, error_msg} as return values, but mixing them is probably not such a good idea as it is less explicit in what is going on.
  • You really do not need an agent here, if you just thread the index you are currently looking at to the recursive function calls (which my code example shows).
  • Just try the current index or otherwise the first non-error child tree.
7

Hi guys,

Many thanks for your help!!!

I agree the second clause is wrong.

My problem is to replace a random selected subtree from tree A with a random selected subtree from tree B. Each tree is a expression. One (sub)criteria was that only branch nodes, determined by a logical or arithmetic operator, should be selected. But there could be a number of the same operators (e.g. and, and, +, +, +, *, *, etc.) in the tree! To select (random) one of them I had to use a target_index. I agree, it is a trick.

Here you find the adapted code which give the required index and the subtree.

  def find_node( nil, _, _), do: nil

  def find_node(node, index, counter) do
  
       v = value(node)
    
       Agent.update(counter, fn x -> x + 1 end )
       state = Agent.get(counter, &(&1))

       if index == state do
          {index, node.focus}
       else
         with  nil <- find_node(left(node), index, counter) do
           find_node(right(node), index, counter)
         end
       end
  end
  
  #--------------------------------------------------------------------
  
  test "Find target_index N in zipper" do
  
   root = t11() |> from_tree
   
   {:ok, counter} = Agent.start(fn -> 0 end )
  
   target_index = 8
 
   {current_index, focus } = find_node(root,target_index,counter)
   
   assert current_index == target_index
     
   end 
   
  #--------------------------------------------------------------------
  
  test "Find node.focus in zipper" do
  
   root = t11() |> from_tree
   
   {:ok, counter} = Agent.start(fn -> 0 end )
  
   target_index    = 8
 
   {current_index, focus } = find_node(root,target_index,counter)
   
  assert  focus  ==  %BinTree{left: %BinTree{left: nil, right: nil, value: 3},
 right: %BinTree{left: nil, right: nil, value: "c"}, value: "*"}
   end

Many thanks for your help,

Thiel Chang

8

Hi Phillipp,

Many thanks for your help. I implemented the solution and it worked; of
course -:slight_smile: