Efficient Functional Maps

Functional Balanced Search Trees

Idea:

• update creates a new path (copying only log(n) nodes)
• lookup and update in log(n)

We present a simplified example that stores integers

• a real implementation stores comparable objects
• instead of '<' below, we would use the comparison method

Case Class Definition

sealed abstract class BST
case class Empty() extends BST
case class Node(left: BST, value: Int, right: BST) extends BST

Checking Membership in Tree

def contains(key: Int, t : BST): Boolean = t match {
case Empty() => false
case Node(left,v,right) => {
if (key == v) true
else if (key < v) contains(key, left)
else contains(key, right)
}
}

Inserting into Tree

def add(x : Int, t : BST) : Node = t match {
case Empty() => Node(Empty(),x,Empty())
case t @ Node(left,v,right) => {
if (x < v) Node(add(x, left), v, right)
else if (x==v) t
else Node(left, v, add(x, right))
}
}

Ensuring Balancing: Red-Black Trees

Idea:

• prevent tree from degenerating into a list with bad sequence of insertions
• rebalance tree after each change

Invariants that imply balancing formulated using nodes of two colors: red and black.

• red node must have black children
• each path in tree from root to children must have the same number of black nodes

Data Type with Colors

sealed abstract class Color
case class Red() extends Color
case class Black() extends Color

sealed abstract class Tree
case class Empty() extends Tree
case class Node(color: Color, left: Tree, value: Int, right: Tree) extends Tree

Inserting with Balancing

def add(x: Int, t: Tree): Tree = {
def ins(t: Tree): Tree = t match {
case Empty() => Node(Red(),Empty(),x,Empty())
case Node(c,a,y,b) =>
if      (x < y)  balance(c, ins(a), y, b)
else if (x == y) Node(c,a,y,b)
else             balance(c,a,y,ins(b))
}
makeBlack(ins(t))
}

def balance(c: Color, a: Tree, x: Int, b: Tree): Tree = (c,a,x,b) match {
case (Black(),Node(Red(),Node(Red(),a,xV,b),yV,c),zV,d) =>
Node(Red(),Node(Black(),a,xV,b),yV,Node(Black(),c,zV,d))
case (Black(),Node(Red(),a,xV,Node(Red(),b,yV,c)),zV,d) =>
Node(Red(),Node(Black(),a,xV,b),yV,Node(Black(),c,zV,d))
case (Black(),a,xV,Node(Red(),Node(Red(),b,yV,c),zV,d)) =>
Node(Red(),Node(Black(),a,xV,b),yV,Node(Black(),c,zV,d))
case (Black(),a,xV,Node(Red(),b,yV,Node(Red(),c,zV,d))) =>
Node(Red(),Node(Black(),a,xV,b),yV,Node(Black(),c,zV,d))
case (c,a,xV,b) => Node(c,a,xV,b)
}

def makeBlack(n: Tree): Tree = n match {
case Node(Red(),l,v,r) => Node(Black(),l,v,r)
case _ => n
}

Benefit Summary

• keep old versions (e.g. when exiting scope, the old scope is around)
• easier to prove correct

Imperative Table with Update Log

Emulate functional behavior using an imperative hash table

• internally mutable, observationally immutable

Insertion:

• updates the hashtable
• creates a log entry that specifies how the old version differs from new one

Old version:

• checks if the value has been changed, if so uses log to look it up
• otherwise looks up the log in the table

Benefits:

• constant-time access for last version produced in computation