5
\$\begingroup\$

Is there a way to use CPS in this code to make the two insert functions tail-call optimized?

defmodule BTree do

  defstruct tree: {node: nil, left: nil, right: nil}
  def new(element), do: %BTree{tree: {node: element, left: nil, right: nil}}

  #insert when there's some data in the tree
  def insert(%BTree{tree: {node: e, left: l, right: r}}, element) when e > element do
    newl = if l == nil, do: new(element), else: insert(l, element)
    %BTree{tree: {node: e, left: newl, right: r }}
  end

  def insert(%BTree{tree: {node: e, left: l, right: r}}, element) when e < element do
    newr = if r == nil, do: new(element), else: insert(r, element)      
    %BTree{tree: {node: e, left: l, right: newr }} 
  end

  def height(%BTree{tree: {node: _, left: l, right: r}}) do
    lh = if l != nil, do: height(l), else: 0
    rh = if r != nil, do: height(r), else: 0
    1 + max(lh, rh)
  end

end 

#BTree.new(10) |> BTree.insert(5) |> BTree.insert(15) |> BTree.height()

As always any comments on idiomatic Elixir code and style are welcome as well.

\$\endgroup\$
11
\$\begingroup\$

I would like to slightly rewrite the problem before making it continuation based because it will make it clearer and avoid duplication:

defmodule BTree do
  defstruct tree: nil
  def new(e), do: %BTree{tree: {e, nil, nil}}

  def insert(%BTree{tree: root}, element) do
    %BTree{tree: do_insert(root, element)}
  end

  defp do_insert(nil, element) do
    {element, nil, nil}
  end

  defp do_insert({e, l, r}, element) when e > element do
    {e, do_insert(l, element), r}
  end

  defp do_insert({e, l, r}, element) when e < element do
    {e, l, do_insert(r, element)}
  end

  defp do_insert({_, _, _} = tuple, _element) do
    tuple
  end
end 

BTree.new(10) |> BTree.insert(5) |> BTree.insert(15) |> IO.inspect

The previous code was generating a BTree for every node. Instead, we simply treat each node as a tuple with three elements (the node item, left and right). When inserting an element, we traverse the tree until we reach nil. We can make it tail recursive by passing a function and invoking the previous one at each step:

defmodule BTree do
  defstruct tree: nil
  def new(e), do: %BTree{tree: {e, nil, nil}}

  def insert(%BTree{tree: root}, element) do
    do_insert(root, element, &%BTree{tree: &1})
  end

  defp do_insert(nil, element, fun) do
    fun.({element, nil, nil})
  end

  defp do_insert({e, l, r}, element, fun) when e > element do
    do_insert(l, element, &fun.({e, &1, r}))
  end

  defp do_insert({e, l, r}, element, fun) when e < element do
    do_insert(r, element, &fun.({e, l, &1}))
  end

  defp do_insert({_, _, _} = tuple, _element, fun) do
    fun.(tuple)
  end
end 

BTree.new(10) |> BTree.insert(5) |> BTree.insert(15) |> IO.inspect

Note though I find this code much harder to understand and I don't think you would get any benefit in practice.

\$\endgroup\$
  • \$\begingroup\$ I agree; one of the reasons I used a struct as opposed to a simple tuple is that it seems a bit easier to follow (to me anyway). Thanks for taking the time to share your insights sir. \$\endgroup\$ – Onorio Catenacci May 23 '14 at 16:06
  • \$\begingroup\$ Unless I'm missing something, this code is not tail recursive. do_insert is calling itself, and then passes the result of a recursive call to a provided lambda. \$\endgroup\$ – sasajuric May 23 '14 at 16:09
  • \$\begingroup\$ Sasa, it is not tail recursive in the sense it is not calling itself, but last call optimization will still apply on the Erlang VM, right? \$\endgroup\$ – José Valim May 23 '14 at 19:18
  • \$\begingroup\$ Yep it's tail recursive now. I wasn't even aware of this technique. Cool! \$\endgroup\$ – sasajuric May 24 '14 at 5:38
  • 1
    \$\begingroup\$ Interestingly, it is actually the technique we use to reduce HashDict (which internally is a tree) so it is suspendable: github.com/elixir-lang/elixir/blob/… \$\endgroup\$ – José Valim May 24 '14 at 7:58
5
\$\begingroup\$

First of all, I agree with José about practical benefits. I would never aim for tail recursion in this example because:

  • it reads much harder
  • there are almost no benefits

That being said, here's my take on making this function tail-recursive. It's not based on continuation, and I didn't clean up the structs (though I agree with José on this):

defmodule BTree do
  defstruct node: nil, left: nil, right: nil
  def new(element), do: %BTree{node: element, left: nil, right: nil}

  def insert(tree, element), do: insert(tree, element, [])

  defp insert(nil, element, parents) do
    Enum.reduce(parents, new(element), &set_child/2)
  end

  defp insert(%BTree{node: e, left: l} = node, element, acc) when e > element do
    insert(l, element, [node | acc])
  end

  defp insert(%BTree{node: e, right: r} = node, element, acc) when e < element do
    insert(r, element, [node | acc])
  end

  defp set_child(%BTree{node: value} = parent, %BTree{node: child_value} = child) when value > child_value do
    %BTree{parent | left: child}
  end

  defp set_child(%BTree{node: value} = parent, %BTree{node: child_value} = child) when value < child_value do
    %BTree{parent | right: child}
  end

  def height(%BTree{node: _, left: l, right: r}) do
    lh = if l != nil, do: height(l), else: 0
    rh = if r != nil, do: height(r), else: 0
    1 + max(lh, rh)
  end
end

BTree.new(10) |> BTree.insert(5) |> BTree.insert(15) |> IO.inspect

The idea is to accumulate the result linearly, and then combine it when you've come to the end. Here, I walk the tree and accumulate visited parents in the acc variable. At the end, I have to re-create all parents of the new element so that the hierarchy is proper. This is done from within the first clause of insert/3.

I didn't test it thoroughly, so it may not be correct. However, it is definitely tail-recursive :-)

Again, I can't stress enough that I wouldn't be aiming for tail recursion here. If you want to practice tail-recursion, I think list processing might be a much better (and easier) fit.

\$\endgroup\$
  • 1
    \$\begingroup\$ To clarify why I wouldn't go for tail recursion here. The thing is that in binary tree, you do log2 operations. This means that for a tree of e.g. million elements, you only need to do 20 steps (which will be the max depth of your stack). In contrast, if it was a list, you'd do all million steps (on average), and hence have a much bigger stack trace. So if it was a list, and my code was generic enough (so I can't predict all inputs), I might aim for tail recursion. Otherwise, I'd go for a simpler code that is easier to understand. \$\endgroup\$ – sasajuric May 23 '14 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.