## Future values

A future value (or simply “future”) is a value that might not be knowable until a later time, such as “the value of the next key you press”, or “the value of LambdaPix stock at noon next Monday” (both from the time you first read this sentence), or “how many tries it will take me to blow out all the candles on my next birthday cake”. Unlike an imperative computation, each future has a unique value — although you probably cannot yet know what that value is. I’ve implemented this notion of futures as part of a library Reactive.

Edits:

• 2008-04-04: tweaked tag; removed first section heading.

You can force a future, which makes you wait (block) until its value is knowable. Meanwhile, what kinds of things can you do a future now?

• Apply a function to the not-yet-known value, resulting in another future. For instance, suppose `fc :: Future Char` is the first character you type after a specific time. Then `fmap toUpper fc :: Future Char` is the capitalized version of the future character. Thus, `Future` is a functor. The resulting future is knowable when `fc` is knowable.
• What about combining two or more future values? For instance, how many days between the first time after the start of 2008 that the temperature exceeds 80 degrees Fahrenheit at (a) my home and (b) your home. Each of those dates is a future value, and so is the difference between them. If those futures are `m80, y80 :: Day`, then the difference is `diff80 = liftA2 (-) m80 y80`. That difference is becomes knowable when the later of the `m80` and `y80` becomes knowable. So `Future` is an applicative functor (AF), and one can apply a future function to a future argument to get a future result (`futRes = futFun <*> futArg`). The other AF method is `pure :: a -> Future a`, which makes a future value that is always knowable to be a given value.
• Sometimes questions about the future are staged, such as “What will be the price of milk the day after it the temperature next drops below freezing” (plus specifics about where and starting when). Suppose `priceOn :: Day -> Future Price` gives the price of milk on a given day (at some specified place), and `nextFreeze :: Day -> Future Day` is the first date of a freeze (also at a specified place) after a given date. Then our query is expressed as `nextFreeze today >>= priceOn`, which has type `Future Price`. `Future` is thus a monad. (The `return` method of a monad is the same as the `pure` method of an AF.) From another perspective on monads, we can collapse a future future into a future, using `join :: Future (Future a) -> Future a`.

These three ways of manipulating futures are all focused on the value of futures. There is one more, very useful, combining operation that focuses on the timing of futures: given two futures, which one comes first. Although we can’t know the answer now, we can ask the question now and get a future. For example, what is the next character that either you or I will type? Call those characters `mc, yc :: Future Char`. The earlier of the two is `mc `mappend` yc`, which has type `Future Char`. Thus, `Future ty` is a monoid for every type `ty`. The other monoid method is `mempty` (the identity for `mappend`), which is the future that never happens.

### Why aren’t futures just lazy values?

If futures were just lazy values, then we wouldn’t have to use `pure`, `fmap`, `(<*>)` (and `liftA`_n_), and `(>>=)`. However, there isn’t enough semantic content in a plain-old-value to determine which of two values is earlier (`mappend` on futures).

## A semantics for futures

To clarify my thinking about future values, I’d like to have a simple and precise denotational semantics and then an implementation that is faithful to the semantics. The module `Data.SFuture` provides such a semantics, although the implementation in `Data.Future` is not completely faithful.

### The model

The semantic model is very simple: (the meaning of) a future value is just a time/value pair. The particular choice of “time” type is not important, as long as it is ordered.

``````newtype Future t a = Future (Time t, a)
``````

Delightfully, almost all required functionality comes automatically from the derived class instances, thanks to the standard instances for pairs and the definition of `Time`, given below. Rather than require our time type to be bounded, we can easily add bounds to an arbitrary type. Rather than defining `Time t` now, let’s discover the definition while considering the required meanings of the class instances. The definition will use just a bit of wrapping around the type `t`, demonstrating a principle Conor McBride expressed as “types don’t just contain data, types explain data”.

### Functor

The `Functor` instance is provided entirely by the standard instance for pairs:

``````instance Functor ((,) a) where fmap f (a,b) = (a, f b)
``````

In particular, `fmap f (Future (t,b)) == Future t (f b)`, as desired.

### Applicative and Time

Look next at the `Applicative` instance for pairs:

``````instance Monoid a => Applicative ((,) a) where
pure x = (mempty, x)
(u, f) <*> (v, x) = (u `mappend` v, f x)
``````

So `Time t` must be a monoid, with `mempty` being the earliest time and `mappend` being `max`. We’ll define `Time` with the help of the `Max` monoid:

``````newtype Max a = Max { getMax :: a }
deriving (Eq, Ord, Read, Show, Bounded)

instance (Ord a, Bounded a) => Monoid (Max a) where
mempty = Max minBound
Max a `mappend` Max b = Max (a `max` b)
``````

We could require that the underlying time parameter type `t` be `Bounded`, but I want to have as few restrictions as possible. For instance, `Integer`, `Float`, and `Double` are not `Bounded`, and neither are the types in the `Time` library. Fortunately, it’s easy to add bounds to any type, preserving the existing ordering.

``````data AddBounds a = MinBound | NoBound a | MaxBound

minBound = MinBound
maxBound = MaxBound
``````

With these two reusable building blocks, our `Time` definition falls right out:

``````type Time t = Max (AddBounds t)
``````

For our `Monad` instance, we just need an instance for pairs equivalent to the Monad Writer instance.

``````instance Monoid o => Monad ((,) o) where
return = pure
(o,a) >>= f = (o `mappend` o', a') where (o',a') = f a
``````

Consequently (using `join m = m >>= id`), `join ((o, (o',a))) == (o `mappend` o', a)`. Again, the standard instance implies exactly the desired meaning for futures. `Future (t,a) >>= f` is available exactly at the later of `t` and the availability of `f a`. We might have guessed instead that the time is simply the time of `f a`, e.g., assuming it to always be at least `t`. However, `f a` could result from `pure` and so have time `minBound`.

### Monoid

The last piece of `Future` functionality is the `Monoid` instance, and I don’t know how to get that instance to define itself. I want `mappend` to yield the earlier of two futures, choosing the first argument when simultaneous. The never-occuring `mempty` has a time beyond all `t` values.

``````instance Ord t => Monoid (Future t a) where
mempty  = Future (maxBound, error "it'll never happen, buddy")
fut@(Future (t,_)) `mappend` fut'@(Future (t',_)) =
if t <= t' then fut else fut'
``````

## Coming next

Tune in for the next post, which describes the current implementation of future values in Reactive. The implementation uses multi-threading and is not quite faithful to the semantics given here. I’m looking for a faithful implementation.

A following post will then describe the use of future values in an elegant new implementation of functional reactive programming.