Skip to content

Instantly share code, notes, and snippets.

@huitseeker

huitseeker/NoQueues.scala Secret

Created Oct 28, 2013
Embed
What would you like to do?
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)
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})))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment