Applicatives

Conjunction junctor, what's your functor?

Event is a Functor. It benefits from all the functorial goodness that functorness adorns unto type constructors like Maybe and Array. Equally if not more importantly, Event is an Applicative Functor. But is it a Monad? To find out, read on!

Events as functors

As we've seen in Deku, to do anything interesting with an Event we need to map over it. In this section, we’ll learn how to define map for Event and discuss its performance characteristics.

The meaning of map

Using the simplified type of Event from the Events section, we can define Event's Functor instance like so.

newtype Event a =
  Event (a -> Effect Unit) -> Effect (Effect Unit)

instance Functor Event where
  map f (Event e) = Event ((lcmap <<< lcmap) f e)

The function lcmap is like map but it maps over the left side of a profunctor (in our case, a function) instead of the right side.

To fulfill the functor laws, map applies the function to each value emitted by the event.

Performance considerations

The double-application of lcmap winds up creating two additional functions on top of the original event. That means two additional thunks, which can tank performance if you chain together hundreds of maps for the same event. This is the case of most functors, and for small numbers of maps it doesn't matter, but when every millisecond counts you don't want your maps to bog you down!

There are two common solutions to the performance problem with maps, both of which can help improve performance if needed:

• Combine several maps into a single function if possible.
• Use a structure like a Free Semigroupoid to collect function applications and fold over them to compose them. While this is inefficient for small quantities of maps, it pays off for 100s of maps.

Applicative

In addition to being a Functor, Event is an Applicative Functor. The implementation of the applicative functions, as well as their conformity to the applicative laws, is less obvious than those of functor, so we take a bit extra care to define how these are defined and why they’re lawful.

Applicative as bi-sampling

All applicative functors accumualte the effects of two separate terms into a final term. In the case of Event the apply function, aka <*>, must fulfill this requirement. As a reminder, the signature of this function is:

forall a b. Event (a -> b) -> Event a -> Event b

The final event requires both the left and right sides to produce a value, so Event b will not emit before it has received at least one value from the left and right events.

To be a lawful applicative functor, Event needs to accumualte the effects from both sides. That means that when one side emits a value, an event must be emitted provided there has been at least one value from the other side. This can be thought of as bi-sampling, meaning that when a value is emitted from the left event, it samples the most recent value from the right event and vice versa.

An important corner case arises when both events emit a value at the same time. In this case, the first event emitted will use the new left side with the old right side followed by the new left and right side. This is because, in the browser, there is no true co-temporality. One event is always admitted before the other, and if the events happen during the same tick, the left event is always interpreted before the right one.

Getting around impurities

To define pure for events, we need a function whose signature is forall a. a -> Event a and that conforms to the applicative laws:

• Identity: (pure identity) <*> v = v
• Composition: pure (<<<) <*> f <*> g <*> h = f <*> (g <*> h)
• Homomorphism: (pure f) <*> (pure x) = pure (f x)
• Interchange: u <*> (pure y) = (pure (_ $ y)) <*> u

So we need to pull a temporality out of thin air that will satisfy these four laws. What temporality should we choose? A single value that is emitted in 42 seconds? A value that is never emitted? A value that is emitted on the next browser tick after subscription? A value that is emitted immediately?

It's not at all obvious which one to choose, but it turns out that the only lawful implementation of pure is the one that emits a value immediately.

Let's walk through the laws to verify that they’re satisfied by our implementations of apply and pure.

• Identity: If we emit the identity function, it will necessarily arrive before the event on the right side as events are interpreted left-to-right, which means that it will apply to every future value on the right side.
• Composition: The right side of composition preserves the temporality of all three events, favoring g over h due to the left-to-right rule and then favoring f over the applied result. Because pure (<<<) is applied to f, f's temporality will remain unchanged. Furthermore, f still wins out over g and g still wins out over h in the left-to-right order, so we have the same tie-breaking mechanism for events in the same tick.
• Homomorphism: this is the easiest to verify. Because pure will have the same temporality on the left and right regardless of its implementation, it will be homomorphic.
• Interchange: This is the most interesting rule to verify because it is the only one that inverts the left-to-right order of its terms, which potentially changes the temporality of events during the same tick. It should be clear that, if u arrives any time after the initial browser tick, there will be no issue because the (pure y) and (pure (_ $ y) will be cached and used as soon as the value event from u is emitted. However, in the case where u also happens on the initial browser tick, we need to confirm that the order of application is irrelevant. Indeed, because pure has no other side effect aside from being emitted immediately, its presence on the right or left of u is immaterial, and as the final value will only be emitted once both events have fired at least once, the two formulations are equivalent.

Now that we've gotten that out of the way, let's do what y'all came here for - a giant fizz-bang using applicatives! Specifically, we’ll use the fact that Event's instance of Semigroup is defined as lift2 append.

module Examples.PurityOutOfThinAir where

import Prelude
import Deku.Toplevel (runInBody)

import Data.Array (intercalate)
import Deku.Control (text)
import Deku.Toplevel (runInBody)
import Effect (Effect)
import ExampleAssitant (ExampleSignature)
import FRP.Event (fold)
import FRP.Event.Time (interval)
import FRP.Poll (sham)
import Deku.Toplevel (runInBody)

main :: Effect Unit
main = do
  i0 <- interval 804
  i1 <- interval 1222
  i2 <- interval 568
  void $ runInBody do
    let
      alternate e a b = sham $
        map
          (if _ then a else b)
          (fold (pure <$> not) true e)
    text
      $ intercalate (pure " ")
          [ alternate i0.event "Functional" "Imperative"
          , pure "programming"
          , alternate i1.event "is" "isn't"
          , alternate i2.event "fun!" "boring!"
          ]

Yet again, we see the ubiquitous fold function. We'll get a full explanation of what it does once we reach Fix and fold.

Monads and flattening

By now, the suspense must be killing you. Is Event a monad? Is it not a monad? The answer is “maybe”. Or even better, the answer is “what do you think?” Read on for a bit of information before you form an opinion!

The keepLatest function

One candidate for a Monad instance of Event is keepLatest.

keepLatest :: forall a. Event (Event a) -> Event a

You can see that its signature is the same as that of join, so it's a promising candidate for a monad's bind function, as bind can always be derived from join.

keepLatest keeps the latest inner event stream omitted by the outer stream. To see an example of this, let's nest two intervals and use a fold to distinguish between events. Again, we haven't defined fold yet because we don't have enough tools and terms to, but you may already be able to guess what it does from its usage on this page!

module Examples.TheKeepLatestFunction where

import Prelude
import Deku.Toplevel (runInBody)

import Control.Alt ((<|>))
import Deku.Control (text)
import Deku.Toplevel (runInBody)
import Effect (Effect)
import ExampleAssitant (ExampleSignature)
import FRP.Event (fold, keepLatest)
import FRP.Event.Class (once)
import FRP.Event.Time (interval)
import FRP.Poll (sham)
import Deku.Toplevel (runInBody)

main :: Effect Unit
main = do
  i0 <- interval 1600
  i1 <- interval 600
  void $ runInBody do
    let count = fold (pure <$> add 1) 0
    text $ sham
      ( show <$> keepLatest
          ( i0.event $>
              ((once i0.event $> 0) <|> count i1.event)
          )
      )

The result is a tresillo rhythm reminiscent of great tunes like Jelly Roll Morton's New Orleans Blues and Roger and Heart's Johnny One Note. This is due to the fact that we keep the latest inner event emitted by the outer event, cancelling the previous inner event. And because the inner event emits every 600 ms, when it resets at 1600 ms, it is cut off 400 ms into the event, creating 600 + 600 + 400, or 3+3+2, or tresillo.

Event as a monad

So naturally, we are led to ask if keepLatest is a viable candidate to usher Event into the pantheon of monad-ness? Our definition bind would be bind m f = keepLatest (f <$> m). Armed with this definition, we would need to verify that it fulfills the monad laws.

• Left Identity: pure x >>= f = f x
• Right Identity: x >>= pure = x
• Associativity: (x >>= f) >>= g = x >>= (\k -> f k >>= g)

While identity holds, associativity does not. This is because, on the left side, x distributes to f and g whereas on the right side it adds to f which then adds to g. The result is that the left side would have more events because f and g would both be contributing impulses, whereas on the right side, only g is contributing impulses.

The only viable monad definition would be one that doesn't have restarting - namely, one where each new outer event triggers an inner event but doesn't clean up the old one. This is often called flatMap in FRP frameworks. So, at least in theory, Event can be a monad. But, by convention, it's not. This is a deliberate choice of several frameworks, including purescript-hyrule, to make it hard for people to accidentally create situations where, after lots of binds, 1000s of events are spewing every second because the previous ones haven't been cleaned up.

So there's your answer - Event is not a monad for your own safety. We may change our minds about this in the future, but so far, no one seems to miss flatMap, so the benefits of adding it don't seem to offset the cost of someone accidentally frying their CPU.