Themes on Streams

> {-# LANGUAGE DeriveFunctor, FlexibleInstances #-}

Recall that a stream is a countably infinite sequence of values:

> data Stream a = a :> Stream a
>   deriving (Functor, Show)
> 
> sHead (a :> _) = a
> sTail (_ :> s) = s

Streams are lovely things (especially in a lazy language) with many nice properties.

> type Theme = String
> type Consciousness = Stream Theme

The remainder of this blog post (in two parts) will be of type Consciousness.

Theme 1: Stream is a monad

The other day I read Jeremy Gibbons’s blog post about the stream monad, proving the monad laws for the version of join that diagonalizes nested streams:

> instance Monad Stream where
>   return a       = a :> return a
>   s >>= f        = sJoin (fmap f s)
> 
> sJoin (s :> ss) = sHead s :> sJoin (fmap sTail ss)

sJoin takes a stream of streams, and outputs a stream with the first element of the first stream, the second element of the second stream, … the nth element of the nth stream.

I recommend reading his post, it’s a very cool example of using universal properties and equational reasoning.

Theme 2: Streams are (isomorphic to) functions

In a comment on Jeremy’s post, Patai Gergely noted that insight into this issue can be gained by observing that Stream a is isomorphic to Nat -> a: there is one item in a stream at every natural number index.

Of course, (->) Nat is a monad: in fact, (->) e is a monad (the "reader monad") for any type e. And what does join for the (->) e monad do? Why, it duplicates an argument:

> rJoin :: (e -> (e -> a)) -> (e -> a)
> rJoin s e = s e e

A little thought shows that this corresponds exactly to the diagonalizing join on Streams: rJoin s e = s e e can be read as "the eth element of rJoin s is the eth element of the eth stream in the stream of streams s." See?

So I told my officemate Daniel about this, and it occurred to us that there’s nothing special here about Nat at all! rJoin is polymorphic in e; R -> a is a monad for any type R.

Functors which are isomorphic to (->) R for some concrete type R are called representable; so what this means is that all representable functors are monads. (Not that we were the first to think of this.)

Theme 3: Streams are comonads

Hmm, but Stream is a comonad too, right?

> class Comonad w where
>   extract   :: w a -> a
>   duplicate :: w a -> w (w a)
> 
> instance Comonad Stream where
>   extract                = sHead
>   duplicate s@(hd :> tl) = s :> duplicate tl

And since Stream is isomorphic to (->) Nat, that type must be a comonad too. What is the corresponding comonad instance for (->) Nat?

> type Nat = Integer   -- just pretend, OK?
> 
> instance Comonad ((->) Nat) where

Extracting from a stream just returns its head element, that is, the element at index 0. So extracting from a Nat -> a applies it to 0.

>   extract = ($0)

Duplicating a stream gives us a stream of streams, where the nth output stream contains consecutive elements from the original stream beginning with the nth. Put another way, the jth element from the ith stream in the output is the (i+j)th element of the original stream:

>   duplicate s i j = s (i + j)

Neat. Unlike the implementation of join for the monad instance, however, this is definitely making use of the particular structure of Nat. So this throws some cold water on our hopes of similarly generalizing this to all representable functors.

…or does it?

Theme 4: Comonads for representable functors

In the previous paragraph I said "this is definitely making use of the particular structure of Nat", but I was being deliberately obtuse. Nat has lots and lots of structure, surely we weren’t using all of it! In fact, we only mentioned the particular natural number 0 and the addition operation. Hmm… zero and addition… what’s interesting about them? Well, zero is the identity for addition, of course, and addition is associative — that is, the natural numbers form a monoid under addition with zero as the identity. So just as a wild guess, perhaps it’s the monoid structure of Nat which makes the comonad instance possible?

In fact… yes! It turns out that comonad structures on R -> a are in one-to-one correspondence with monoid structures on R. To prove this, we can… oh, darn, looks like we’re out of time! (Read: this blog post is getting too long and if I don’t publish something soon I never will.) I’ll continue in another post, but in the meantime you might fancy trying to prove this yourself.

About these ads
This entry was posted in haskell, math and tagged , , , , , . Bookmark the permalink.

3 Responses to Themes on Streams

  1. Derek Elkins says:

    I recommend my Monad.Reader article in Issue 13.

  2. Ben Moseley says:

    You might be interested in “The essence of the Iterator pattern” by Jeremy – it talks about these “Naperian” functors.

  3. Pingback: Themes on Streams, Part II « blog :: Brent -> [String]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s