Wednesday, February 20, 2013

Splay tree access is coalgebraic

Splay trees are balanced binary trees that keep the most recently accessed or inserted item at the top.  More information can be found at http://en.wikipedia.org/wiki/Splay_tree

We wish to define splay trees in Haskell and then make an observation about a certain coalgebraic behavior.

We begin with an import that will become relevant later and the type definition:

> import Control.Comonad
>
> data SplayTree a = Null | Node (SplayTree a) a (SplayTree a)
>   deriving (Eq)

We also want a way of seeing it.  We could have just derived Show, but I like this better:

> instance (Show a) => Show (SplayTree a) where
>   show (Node Null stuff Null) = "[" ++ (show stuff) ++ "]"
>   show (Node left stuff Null) = "(" ++ (show left) ++ "<--[" ++ (show stuff) ++ "])"
>   show (Node Null stuff right) = "([" ++ (show stuff) ++ "]-->" ++ (show right) ++ ")"
>   show (Node left stuff right) =
>       "(" ++ (show left) ++ "<--[" ++ (show stuff) ++ "]-->" ++ (show right) ++ ")"
>   show Null = ""


The functionality of a splay tree derives from classic binary tree operations, together with a "splay" function.  The splay function takes care of the rebalancing.  We begin by defining a textbook binary search tree insert function.

> binsert :: Ord a => a -> SplayTree a -> SplayTree a
> binsert x (Node left stuff right)
>          | x <= stuff = Node (insert x left) stuff right
>          | x > stuff  = Node left stuff (insert x right)
> binsert x Null = Node Null x Null

The actual splay tree insert will follow once we've defined splay:

> insert x t = splay x (binsert x t)

The splay function is a series of rotations that depends upon where the recently used item, below denoted as x, lies in relation to the root.  In fact, we are interested in various configurations where x is the child or grandchild of the current node.  If it is not, we just recursively go down a level.  This function assumes that x is a member of the tree already.  The possibilities are in correspondence with the nice pictures in the above wikipedia page.

We might be already balanced:

> splay x (Node left y right) | x == y = (Node left x right)

What if x is the child of the current node ("zig" or "zag")?  A simple rotation will do:

> splay x (Node (Node l1 y l2) p right)
>             | x == y = Node l1 x (Node l2 p right)
> splay x (Node left p (Node r1 y r2))
>             | x == y = Node (Node left p r1) x r2

Or, x is the left child of the left child (zig-zig) or the right child of the right child (zag-zag):

> splay x (Node (Node (Node ll1 y ll2) p lr) g right)
>           | x == y = Node ll1 x (Node ll2 p (Node lr g right))
> splay x (Node left g (Node rl p (Node rr1 y rr2)))
>           | x == y = Node (Node (Node left g rl) p rr1) x rr2

The other possibilities are a "zigzag" or "zagzig":

> splay x (Node (Node ll p (Node lr1 y lr2)) g right)
>           | x == y = Node (Node ll p lr1) x (Node lr2 g right)
> splay x (Node left g (Node (Node rl1 y rl2) p rr))
>           | x == y = Node (Node left g rl1) x (Node rl2 p rr)

These cases cover when we do not see x as a child or grandchild:

> splay x Null = Null
> splay x (Node left stuff right)
>       | x <= stuff = splay x (Node (splay x left) stuff right)
>       | x > stuff = splay x (Node left stuff (splay x right))

And there you have it!  Let's give it a try:

*Main> insert 3 (insert 4 (insert 2 (insert 0 Null)))
(([0]<--[2])<--[3]-->[4])

Notice that 3 is on the top since it was last accessed.  Neat!

Membership testing is somewhat interesting.  We wish to determine if x is in the tree and splay the tree if this is the case.  As such, membership will have an interesting type.

We start off with plain binary tree membership:

> bmember :: Ord a => a -> SplayTree a -> Bool
> bmember x Null = False
> bmember x (Node left y right) | x == y = True
>                               | x < y  = bmember x left
>                               | x > y  = bmember x right

And now we do the required splaying if we find x:

> member :: Ord a => a -> SplayTree a -> (Bool, SplayTree a)
> member x t | (x `bmember` t)     = (True, splay x t)
>            | not (x `bmember` t) = (False, t)

Note the type signature of member.  The part SplayTree a -> (Bool, SplayTree a) looks coalgebraic.  Let's see if we can more formally clarify that.

Consider the functor $Bool \times -$.  Mathematically, we can identify this with $\mathbb{Z}/{2} \times -$, which has two different monad structures corresponding to the addition and multiplication in $\mathbb{Z}/{2}$.  In terms of boolean algebra, these are or and and, respectively.

However, there is also a comonadic structure on $Bool \times -$.  Let's see if we can define it:

> newtype BoolFunct a = BoolFunct (Bool, a)
>
> instance Functor BoolFunct where
>   fmap f (BoolFunct (b, x)) = BoolFunct (b, f x)

Due to reasons that I do not fully understand, Haskell does not let me declare that (Bool,a) is a functor for any type a.  This is why I need the silly type constructor 'BoolFunct'.

The comonadic structure is induced by the diagonal:

> instance Comonad BoolFunct where
>  extract (BoolFunct (b, x)) = x
>  duplicate (BoolFunct (b, x)) = BoolFunct (b, BoolFunct (b, x))

Of course, one should also check the comonadic laws, namely that duplicate is coassociative and that extract is a counit.  This is left as an exercise for the reader.

By the way, I'm a bit bothered that these things are called 'laws' in the community.  Physics has 'laws'.  Mathematics has axioms.  We are really just verifying that an object satisfies the axioms.  But I digress...

Let's make an observation:

*Main> :type member 3
member 3 :: (Num a, Ord a) => SplayTree a -> (Bool, SplayTree a)

That's interesting.  Detecting whether or not the number 3 is a member seems to give a coalgebra SplayTree Integer -> BoolFunct SplayTree Integer.  Of course, one should be dutiful and verify that this is indeed a coalgebraic structure.  In fact, this is trivial as soon as you write down the commutative diagram.  Here is an example demonstrating coassociativity:

*Main> let t = insert 4 (insert 5 (insert 2 (insert 3 Null)))
*Main> ((fmap (member 3)) . (member 3)) t
(True,(True,([2]<--[3]-->([4]-->[5]))))
*Main> (duplicate . (member 3)) t
(True,(True,([2]<--[3]-->([4]-->[5]))))

There you have it!  Accessing a splay tree is a coalgraic operation.  I'm not sure if this is a useful observation or not, but part of the mission of this blog is to collect interesting comonads and coalgebras in the Haskell world to understand them better.


Addendum: What I've posted above is correct in spirit but not in letter.  If I really want to make member a coalgebra over the comonad BoolFunct, then I need to use the type constructor:

> cmember :: Ord a => a -> SplayTree a -> BoolFunct (SplayTree a)
> cmember x t = BoolFunct (member x t)