http://blog.garillot.net/post/65324621946/look-ma-no-queues

noqueues.ml

type 'a tree =
  |Node of 'a * 'a tree * 'a tree
  |Leaf of 'a

let rec print_rec_aux_cps (tree: 'a tree) (and_then: 'a list list -> 'a list list) =
  match tree with
    |Leaf(v) -> (and_then [[v]])
    |Node(v,l,r) ->
      let new_then = fun left_lines ->
        print_rec_aux_cps r (fun right_lines ->
          and_then ([v]::List.map2 (fun l1 -> fun l2 -> l1@l2) left_lines right_lines)) in
      print_rec_aux_cps l new_then

let print_rec_cps (tree: 'a tree) =
  List.flatten (print_rec_aux_cps tree (fun x -> x))

let rec big_example_cps (n: int) (k: int) (and_then: int tree -> int tree) : int tree =
  if n = 0 then (and_then (Leaf k)) else
    let new_then = fun l ->
      big_example_cps (n-1) (k + int_of_float (2.**(float n))) (fun r -> and_then (Node(k,l,r))) in
    big_example_cps (n-1) (k+1) new_then

let big_example (n:int) : int tree =
  big_example_cps n 0 (fun x -> x)

NoQueues.scala

import scala.collection.immutable.Queue
import scala.annotation.tailrec

object NoQueues {

  abstract class Tree
  case class Node(value: Int, left: Tree, right:Tree) extends Tree
  case class Leaf(value:Int) extends Tree

  def extract(t:Tree): Int = t match {
    case Leaf(v) => v
    case Node(v,_,_) => v
  }

  def printLevelsWithQueue(t:Tree): List[Int] = {
    val q = Queue[Tree](t)
    def print_aux(q: Queue[Tree]): List[Int] =
      if (q.isEmpty) Nil else {
        val (tree, remq) = q.dequeue
        tree match{
          case Leaf(v) => v :: print_aux(remq)
          case Node(v, l, r) => v :: print_aux(remq :+ l :+ r)
        }
      }
    print_aux(q)
  }

  val example = Node(1,Node(2,Leaf(4), Leaf(5)), Node(3, Leaf(6), Leaf(7)))

  def printLevelsWithNoQueueAndMultipleRecursion(t:Tree): List[Int] = {
    def print_aux_rec(t:Tree): List[List[Int]] = t match {
      case Leaf(v) => List(List(v))
      case Node(v, l, r) => {
        val leftLines = print_aux_rec(l)
        val rightLines = print_aux_rec(r)
        List(v) :: ((leftLines,rightLines).zipped map {(l1,l2) => l1:::l2})
      }
    }
    print_aux_rec(t).flatten
  }

  def printLevelsWithNoQueuesAndCPS(t:Tree): List[Int] = {

    def print_aux_rec_cps(t:Tree, andThen: List[List[Int]] => List[List[Int]]): List[List[Int]] = t match {
      case Leaf(v) => andThen(List(List(v)))
      case Node(v, l, r) => {
        def newThen = (leftLines:List[List[Int]]) =>
         print_aux_rec_cps(r, (rightLines: List[List[Int]]) =>
         andThen (List(v) :: ((leftLines, rightLines).zipped map (_ ::: _))))
        print_aux_rec_cps(l,newThen)
      }
    }
    print_aux_rec_cps(t,{(x) => x}).flatten
  }

  def bigExample(n: Int, k: Int):Tree =
    if (n == 0) Leaf(k) else {
      import scala.math._
      val left = bigExample(n-1, k+1)
      val right = bigExample(n-1, k + pow(2,n).toInt)
      Node(k, left, right)
    }

  def bigExample_cps(n:Int, k:Int, andThen:Tree => Tree): Tree =
    if (n == 0) andThen(Leaf(k)) else {
      import scala.math._
      def nextThen = (l:Tree) =>
        bigExample_cps(n-1, k+pow(2,n).toInt,
                       (r:Tree) => andThen(Node(k,l,r)))
      bigExample_cps(n-1,k+1,nextThen)
    }

  def main(args: Array[String]){
    println("RES withQueues: " + printLevelsWithQueue(example))
    println("RES with multiple rec: " + printLevelsWithNoQueueAndMultipleRecursion(example))
    println("RES with CPS: " + printLevelsWithNoQueuesAndCPS(example))
    println(print_rec_)
    //println(extract(bigExample(1000,0)))
    //println(extract(bigExample_cps(10,0,{(x)=>x})))
  }

}