5th December 2008, 12:14 am

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
`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’ »

The post Sequences, streams, and segments offered an answer to the the question of what’s missing in the following box: infinitefinite discreteStream Sequence continuousFunction ??? I presented a simple type...

30th November 2008, 11:29 pm

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.

| **infinite** | **finite** |

**discrete** | Stream | Sequence |

**continuous** | Function | *???* |

You can download the code for this post.

**Edits**:

- 2008-12-01: Added Segment.hs link.
- 2008-12-01: Added
`Monoid`

instance for function segments.
- 2008-12-01: Renamed constructor “
`DF`

” to “`FS`

” (for “function segment”)
- 2008-12-05: Tweaked the inequality in
`mappend`

on `(t :-># a)`

.

Continue reading ‘Sequences, streams, and segments’ »

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