3

I have a data structure,

datatype 'a tree = Leaf | Branch of 'a tree * 'a * 'a tree

and I want to write a function that traverses this tree in some order. It doesn't matter what it does, so it could be a treefold : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b. I can write this function like this:

fun treefold f acc1 Leaf = acc1
  | treefold f acc1 (Branch (left, a, right)) =
    let val acc2 = treefold f acc1 left
        val acc3 = f (a, acc2)
        val acc4 = treefold f acc3 right
    in acc4 end

But because I inevitably have two branches in the last case, this is not a tail-recursive function.

Is it possible to create one that is, given the type signature is allowed to be expanded, and at what cost? I also wonder if it's even worth trying; that is, does it give any speed benefits in practice?

sshine
  • 15,635
  • 1
  • 41
  • 66
  • 1
    See this: http://stackoverflow.com/questions/9323036/tail-recursive-function-to-find-depth-of-a-tree-in-ocaml – Dave L. Sep 28 '13 at 19:21

2 Answers2

5

You can achieve a tail-recursive treefold using continuation-passing style:

fun treefold1 f Leaf acc k = k acc
  | treefold1 f (Branch (left, a, right)) acc k =
    treefold1 f left acc (fn x => treefold1 f right (f(a, x)) k)

fun treefold f t b = treefold1 f t b (fn x => x)

For example:

fun sumtree t = treefold op+ t 0

val t1 = Branch (Branch(Leaf, 1, Leaf), 2, Branch (Leaf, 3, Leaf))

val n = sumtree t1

results in n = 6 as expected.

seanmcl
  • 9,740
  • 3
  • 39
  • 45
2

Like @seanmcl writes, the systematic way to convert a function to be tail-recursive is to use continuation-passing style.

After that you probably want to reify your continuations and use a more concrete data type, like a list for instance:

fun treefoldL f init tree =
    let fun loop Leaf acc [] = acc
          | loop Leaf acc ((x, right) :: stack) =
            loop right (f(x,acc)) stack
          | loop (Branch (left, x, right)) acc stack =
            loop left acc ((x, right) :: stack)
    in  loop tree init [] end
kfl
  • 56
  • 3
  • Thank you, Ken. I mostly asked because I became impatient lurking at other people asking SML questions and thought that I would ask a question people might like to answer. :) (It seems that a new chapter on continuations are added in H&R's new F# book.) – sshine Oct 06 '13 at 21:01