Friday, November 15, 2013

Applicative Functors

Well, perhaps it's time to resurrect this blog from benign neglect. I must admit that I've been spending close to zero time thinking about comonads and coalgebras lately. This is partly a consequence of having a Real Job, and partly a consequence of the fact that the remainder of my time apart from this is devoted to homotopy type theory and whiskey.

Herein, I simply wish to share a picture of what applicative functors are in category theoretic language.

To this end, let $F: \mathcal{C} \rightarrow \mathcal{D}$ be a functor between cartesian closed categories. We shall call $F$ applicative if there exists a natural transformation of bifunctors $\alpha: F(-^{-}) \rightarrow F(-)^{F(-)}$ (the blanks are different here - is that confusing?). In other words, an applicative functor doesn't necessarily "preserve" exponentials, but there is a map.

In Haskell, $\alpha$ is typically denoted <*>

Also, recall that functor application is actually a function fmap :: Functor f => (a -> b) -> f a -> f b

(I don't want to terminate these sentences with periods because I don't want to gum up the syntax in some way. How do people usually deal with this?)

Now, as fmap can be rather cumbersome to write, I've seen <$> used instead. Well, that makes plenty of sense actually: the operator $ is a special case of this with respect to the identity functor.

Now, a common use of this is to deal with functions that take multiple arguments "inside" of functors. Remember that everything in Haskell is curried by default, so, for instance, addition has the following type:

(+) :: Num a => a -> a -> a


(<$>) (+) :: (Functor f, Num a) => f a -> f (a -> a)

So if we compose that with <*>, we get:

(<*>) . ((<$>) (+)) :: (Num a, Control.Applicative.Applicative f) => f a -> f a -> f a

So, we can now perform addition "inside" any applicative functor, so if you evaluate

(((<*>) . ((<$>) (+))) (Just 1)) (Just 2)

you get

Just 3

Of course, what I wrote above is really ugly, so in practice we would actually use the infix form:

(+) <$> Just 1 <*> Just 2

Now, if you were going to do something like this often, you might as well define a new operator:

let (<+>) x y = (+) <$> x <*> y

So that

Just 1 <+> Just 2

evaluates to

Just 3

Of course, the example functor I am using is rather special, as it creates an "extra value" for any given type. You might wonder what happens when I add nothing to just a number:

Just 1 <+> Nothing

Well, it evaluates to:


Well, after all, Maybe is a functor from types to pointed types, so I think it makes perfect sense that our natural transformation preserves the new "basepoint" which we call Nothing.

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

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)))

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
*Main> (duplicate . (member 3)) t

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)