# How could this be written using continuation passing style?

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.

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.

• 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. – Onorio Catenacci May 23 '14 at 16:06
• 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. – sasajuric May 23 '14 at 16:09
• 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? – José Valim May 23 '14 at 19:18
• Yep it's tail recursive now. I wasn't even aware of this technique. Cool! – sasajuric May 24 '14 at 5:38
• 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/… – José Valim May 24 '14 at 7:58

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

• 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.

• 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. – sasajuric May 23 '14 at 16:27