What kind of thing is a movie? Or a song? Or a trajectory from point A to point B? If you’re a computer programmer/programmee, you might say that such things are sequences of values (frames, audio samples, or spatial locations). I’d suggest that these discrete sequences are representations of something more essential, namely a flow of continuously time-varying values. Continuous models, whether in time or space, are often more compact, precise, adaptive, and composable than their discrete counterparts.
Functional programming offers great support for sequences of variable length. Lazy functional programming adds infinite sequences, often called streams, which allows for more elegant and modular programming.
Functional programming also has functions as first class values, and when the function’s domain is (conceptually) continuous, we get a continuous counterpart to infinite streams.
Streams, sequences, and functions are three corners of a square. Streams are discrete and infinite, sequences are discrete and finite, and functions-on-reals are continuous and infinite. The missing corner is continuous and finite, and that corner is the topic of this post.
You can download the code for this post.
- 2008-12-01: Added Segment.hs link.
- 2008-12-01: Added
Monoidinstance for function segments.
- 2008-12-01: Renamed constructor “
DF” to “
FS” (for “function segment”)
- 2008-12-05: Tweaked the inequality in
(t :-># a).
I’ll be using Wouter Swierstra’s Stream library. A stream is an infinite sequence of values:
data Stream a = Cons a (Stream a)
Stream is a functor and an applicative functor.
instance Functor Stream where fmap f (Cons x xs) = Cons (f x) (fmap f xs) instance Applicative Stream where pure = repeat (<*>) = zipWith ($) repeat :: a -> Stream a repeat x = Cons x (repeat x)
Recently I’ve gotten enamored with comonads, which are dual to monads. In other words, comonads are like monads but wearing their category arrows backwards. I’ll be using the comonad definitions from the category-extras library.
The most helpful intuitive description I’ve found is that comonads describe values in context.
return method injects a pure value into a monadic value (having no effect).
return :: Monad m => a -> m a
The dual to monadic
extract (sometimes called “
counit” or “
coreturn“), which extracts a value out of a comonadic value (discarding the value’s context).
category-extras library splites this method out from
Comonad into the
extract :: Copointed w => w a -> a
Monadic values are typically produced in effectful computations:
a -> m b
Comonadic values are typically consumed in context-sensitive computations:
w a -> b
(Kleisli arrows wrap the producer pattern, while CoKleisli arrows wrap the consumer pattern.)
Monads have a way to extend a monadic producer into one that consumes to an entire monadic value:
(=<<) :: (Monad m) => (a -> m b) -> (m a -> m b)
We more often see this operation in its flipped form (obscuring the conceptual distinction between Haskell arrows and arbitrary category arrows):
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
Dually, comonads have a way to extend a comonadic consumer into one that produces an entire comonadic value:
extend :: (Comonad w) => (w a -> b) -> (w a -> w b)
which also has a flipped version:
(=>>) :: (Comonad w) => w a -> (w a -> b) -> w b
Another view on monads is as having a way to
join two monadic levels into one.
join :: (Monad m) => m (m a) -> m a
Dually, comonads have a way to
duplicate one level into two:
duplicate :: (Comonad w) => w a -> w (w a)
For a monad, any of
(>>=) can be used to define the others.
For a comonad, any of
(=>>) can be used to define the others.
The Stream comonad
What might the stream comonad be?
The Stream library already has functions of the necessary types for
duplicate, corresponding to familiar list functions:
head :: Stream a -> a head (Cons x _ ) = x tails :: Stream a -> Stream (Stream a) tails xs = Cons xs (tails (tail xs))
tail :: Stream a -> Stream a tail (Cons _ xs) = xs
tails are just what we’re looking for.
instance Copointed Stream where extract = head instance Comonad Stream where duplicate = tails
There is also a
Monad instance for
Stream, in which
pure as expected) and
join is diagonalization, producing a stream whose nth element is the nth element of the nth element of a given stream of streams.
Exercise: The indexing function
(!!) is a sort of semantic function for
(!!) is a morphism for
In other words, the meaning of the functor is the functor of the meanings, and similarly for the other type classes.
Comonad case has a little wrinkle.
See the posts on type class morphisms.
Lists and other possibly-finite sequence types add an interesting new aspect over streams, which is concatenation, usually wrapped in a
class Monoid o where mempty :: o mappend :: o -> o -> o
Lists also have
drop operations, which can undo the effect of concatenation, as well as a notion of
Let’s generalize these three to be methods of a new type class,
Segment, so that we can defined continuous versions.
class Segment seg len where length :: seg -> len drop :: len -> seg -> seg take :: len -> seg -> seg
For lists, we can use the prelude functions
instance Segment [a] Int where length = Prelude.length drop = Prelude.drop take = Prelude.take
Or the more generic versions:
instance Integral i => Segment [a] i where length = genericLength drop = genericDrop take = genericTake
These three functions relate to
mappend, to give us the following “Segment laws”:
drop (length as) (as `mappend` bs) == bs take (length as) (as `mappend` bs) == as t <= length as ==> length (take t as) == t t <= length as ==> length (drop t as) == length as - t
Streams and lists are discrete, containing countably many or finitely many elements. They both have continuous counterparts.
When we think of a stream as a function from natural numbers, then John Reynolds’s alternative arises: functions over real numbers, i.e., a continuum of values. If we want uni-directional streams, then stick with non-negative reals.
Many stream and list operations are meaningful and useful not only for discrete sequences but also for their continuous counterparts.
instance Functor ((->) t) where fmap = (.) instance Applicative ((->) t) where pure = const (f <*> g) x = (f x) (g x) instance Monad ((->) t) where return = const f >>= k = t -> k (f t) t
As a consequence,
join f == f >>= id == t -> f t t
Assume a type wrapper,
NonNeg, for non-negative values.
For discrete streams,
r == NonNeg Integer, while for continuous streams,
r == NonNeg R, for some type
R representing reals.
instance Monoid o => Copointed ((->) o) where extract f = f mempty instance Monoid o => Comonad ((->) o) where duplicate f x = y -> f (x `mappend` y)
Finite and continuous
Functions provide a setting for generalized streams. How do we add finiteness? A very simple answer is to combine a length (duration) with a function, to form a “function segment”:
data t :-># a = FS t (t -> a)
The domain of this function is from zero to just short of the given length.
Now let’s define class instances.
Exercise: Show that all of the instances below are semantically consistent with the
Empty function segments have zero duration. Concatenation adds durations and samples either function, right-shifting the second one.
instance (Ord t, Num t) => Monoid (t :-># a) where mempty = FS 0 (error "sampling empty 't :-># a'") FS c f `mappend` FS d g = FS (c + d) ( t -> if t <= c then f t else g (t - c))
Segment operations are easy to define:
instance Num t => Segment (t :-># a) t where length (FS d _) = d drop t (FS d f) = FS (d - t) ( t' -> f (t + t')) take t (FS _ f) = FS t f
Notice what’s going on with
The length gets shortened by
t (the amount dropped), and the function gets shifted (to the “left”) by
There’s also a tantalizing resemblance between this
drop definition and
duplicate for the function comonad.
We’ll return in another post to tease out this and
I’ve allowed dropping or taking more than is present, though these cases can be handled with an error or a by taking or dropping fewer elements (as with the list
fmap applies a given function to each of the function values, leaving the length unchanged.
instance Functor ((:->#) t) where fmap h (FS d f) = FS d (h . f)
zip pairs corresponding segment values and runs out with the shorter segment.
(See More beautiful fold zipping for the
instance Ord t => Zip ((:->#) t) where FS xd xf `zip` FS yd yf = FS (xd `min` yd) (xf `zip` yf)
pure produces a constant value going forever.
(<*>) applies functions to corresponding arguments, running out with the shorter.
instance (Ord t, Bounded t) => Applicative ((:->#) t) where pure a = FS maxBound (const a) (<*>) = zipWith ($)
extract pulls out the initial value (like
instance Num t => Copointed ((:->#) t) where extract (FS _ f) = f 0
duplicate acts like
The generated segments are progressivly
dropped versions of the original segment.
instance Num t => Comonad ((:->#) t) where duplicate s = FS (length s) (flip drop s)
I don’t know if there is a monad instance for
Simple diagonalization doesn’t work for
join, since the nth segment might be shorter than n.
The instances above remind me strongly of type class instances for several common types.
Another post will tease out some patterns and reconstruct
(t :-># a) out of standard components, so that most of the code above can disappear.
Another post incorporates
(t :-># a) into a new model and implementation of relative-time, comonadic FRP.