# 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
}
}```

## 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: