Archive for 5th December 2008

Sequences, segments, and signals

The post Sequences, streams, and segments offered an answer to the the question of what’s missing in the following box:

discreteStream Sequence
continuousFunction ???

I presented a simple type of function segments, whose representation contains a length (duration) and a function. This type implements most of the usual classes: Monoid, Functor, Zip, and Applicative, as well Comonad, but not Monad. It also implements a new type class, Segment, which generalizes the list functions length, take, and drop.

The function type is simple and useful in itself. I believe it can also serve as a semantic foundation for functional reactive programming (FRP), as I’ll explain in another post. However, the type has a serious performance problem that makes it impractical for some purposes, including as implementation of FRP.

Fortunately, we can solve the performance problem by adding a simple layer on top of function segments, to get what I’ll call “signals”. With this new layer, we have an efficient replacement for function segments that implements exactly the same interface with exactly the same semantics. Pleasantly, the class instances are defined fairly simply in terms of the corresponding instances on function segments.

You can download the code for this post.


  • 2008-12-06: dup [] = [] near the end (was [mempty]).
  • 2008-12-09: Fixed take and drop default definitions (thanks to sclv) and added point-free variant.
  • 2008-12-18: Fixed appl, thanks to sclv.
  • 2011-08-18: Eliminated accidental emoticon in the definition of dup, thanks to anonymous.

Continue reading ‘Sequences, segments, and signals’ »