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:
| infinite | finite | |
| discrete | Stream | Sequence |
| continuous | Function | ??? |
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.
Edits:
- 2008-12-06:
dup [] = []near the end (was[mempty]). - 2008-12-09: Fixed
takeanddropdefault 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.