Fix and fold

Behold the crown jewel of functional reactive programming!

We've seen the fold function over and over in this documentation, and yet we haven't been able to define it yet. To get there, we needed a thorough understanding of Events, their instances, and how sampling works. Armed with that knowledge, we’ll be able to precisely define what fold is, and even more generally, what fix is for an Event.

Fixed points

Fixed points come up all over functional progrmaming. Browsing the term fix on Pursuit, there are around ~20 versions of fix in various libraries. One of the most magical aspects of Event is the unique and intuitive way fixed points relate to events. In this section, we’ll define what fixed points are in general before delving into their Event-specific representation.

What is a fixed point?

A fixed point of a function is a value that is mapped to itself by the function. Because fixed points are invariant under function application, one way to arrive at a fixed point is to continue providing the output of a function as its input until the value converges.

In functional programming, we tend to think of fixed points of systems, meaning how do systems converge after repeated application of some entity like a function. The standard pattern is to define fix as a function that takes a closure where some arbitrary entity that can be repeatedly applied to a system's input or output, let's call it u, can be used, then returning u as the result. This is a bit of a mind-melt, as it looks as if the value is being used before it is created.

As an example, let's consider a function of type (a -> b) as our unit that will be repeatedly applied to an input. That is, it applies itself recursively to its input parameter until it converges at a term of type b. We'll fix a as Int and b as Int as well.

fix :: forall a b. ((a -> b) -> (a -> b)) -> a -> b
fix f = go
  where
    defer f = \x -> f unit x
    go = defer \_ -> f go

myFunction = fix (\f a -> if a > 100 then 100 else f (a + 1))

If your brain isn't hurting yet, you either have studied this stuff before, you’re a genius, or you’re not thinking hard enough. In the above example, f is myFunction even though myFunction doesn't exist yet (it's in the process of being defined). We know it's f because, otherwise, what else is pushing all the values up to 100 incrementally? And yet, in spite of this mind-bender, none of it is magical. If you follow the control flow of fix, you can trace how it flows step by step.

The reason that fixed points only make sense for unfoldable things like functions or streams or events (things that go on and on and on…) is because the fixed point needs repeated application. A function (a -> b) can be applied ad infinitum until it produces its value, a cofree comonad never ends, an event potentially keeps emitting, etc.

This power comes at a price, however. Repeated application of anything in computing runs the risk of going into an infinite loop if you’re not careful. So, to avoid overflow, there has to be some reasonable end condition that applies in all cases.

The fix function for events

If we consider events as streams of values, one way to build intuition about fix with respect to events is to think of streams that feed into each other in the natural world. Imagine you’re at a sunny, warm beach. You dig a little canal from the sand down into the ocean and create a small loop for water to feed back into itself. Assuming that the water you pour into the canal has enough force when it reaches the loop, some particles will go around, rejoin the stream, and even potentially go around again before they empty into the ocean.

While subscribing to events in the browser will never reach the volume of events as the ocean subscribing to the water molecules of your beach experiment, the idea is the same. Values from an event loop back into the same stream, reaching their final destination at a later time and perhaps with some transformation.

As an example, let's write an event that feeds back into itself using fix. We'll create a mechanism that lags by one event. That is, the first thing you click on will not change the value, and from then on, whenever you click, the previous value will be displayed.

module Examples.ALagUsingFix where

import Prelude
import Deku.Toplevel (runInBody)

import Control.Alt ((<|>))
import Data.Compactable (compact)
import Data.Maybe (Maybe(..))
import Data.String (Pattern(..), Replacement(..), replaceAll)
import Data.Tuple (Tuple(..), fst, snd)
import Data.Tuple.Nested ((/\))
import Deku.DOM.Attributes as DA
import Deku.Control (text, text_)
import Deku.DOM as D
import Deku.Do as Deku
import Deku.Hooks (useState')
import Deku.DOM.Listeners as DL
import Deku.Toplevel (runInBody)
import Effect (Effect)
import ExampleAssitant (ExampleSignature)
import FRP.Event (fix, sampleOnRight)
import Deku.Toplevel (runInBody)

buttonClass :: String -> String
buttonClass color =
  replaceAll (Pattern "COLOR") (Replacement color)
    """mb-3 inline-flex items-center rounded-md
border border-transparent bg-COLOR-600 px-3 py-2
text-sm font-medium leading-4 text-white shadow-sm
hover:bg-COLOR-700 focus:outline-none focus:ring-2
focus:ring-COLOR-500 focus:ring-offset-2 mr-4"""

main :: Effect Unit
main = void $ runInBody Deku.do
  setWord /\ word <- useState'
  let
    button text color = D.button
      [ DA.klass_ (buttonClass color), DL.click_ \_ -> (setWord text) ]
      [ text_ text ]
  D.div_
    [ D.div_
        [ button "Hickory" "green"
        , button "Dickory" "pink"
        , button "Dock" "indigo"
        ]
    , D.div_
        [ text_ "Previous word: "
        , text
            ( pure "None" <|>
                ( compact $ snd <$> fix
                    ( \e -> sampleOnRight
                        (pure Nothing <|> (fst <$> e))
                        ((Tuple <<< Just) <$> word)
                    )
                )
            )
        ]
    ]

HickoryDickoryDock

Previous word: None

Before we delve into the inner workings of the function above, it's important to note that what we've just done is created State in an event-based architecture. It's a pretty meager state - just remembering what happened one tick ago. But this mechanism will be the basis of all stateful work in events and will allow us to do a host of operations, from debouncing to folding.

To understand how the fix mechanism work, let's first isolate the full event:

compact $ snd <$> fix
  ( \e -> sampleOnRight
      (pure Nothing <|> (fst <$> e))
      ((Tuple <<< Just) <$> word)
  )

From this definiton, we know that the event must be producing a tuple and that the second value of this tuple must be a

fixedEvent :: Event (Tuple ?hole (Maybe String))
fixedEvent = fix
  ( \e -> sampleOnRight
      (pure Nothing <|> (fst <$> e))
      ((Tuple <<< Just) <$> word)
  )

To fill in the type hole, let's look at the inner function. We know that it must be a Maybe because it is alted withpure Nothing. So we can refine our hole as:

fixedEvent :: Event (Tuple (Maybe ?hole) (Maybe String))
fixedEvent = fix
  ( \e -> sampleOnRight
      (pure Nothing <|> (fst <$> e))
      ((Tuple <<< Just) <$> word)
  )

To refine it further, let's look at the sampleOnRight operation. We know that it must produce a tuple because the incoming event is a tuple, which means that the second argument to sampleOnRight must be of type Maybe String -> Tuple (Maybe ?hole) (Maybe String). Looking at the function, we see that it is filling in the left side of the tuple with Just word, and knowing that word is a String, we now know that the type of fixedEvent is Tuple (Maybe String) (Maybe String).

From the section on Effect systems, we know that in sampleOnRight, the right event will fire before the left event, creating a lag of one value. That means that the second value of the tuple will lag the first by one, and because it is hydrated with the incoming first value, it will always be the value of ((Tuple <<< Just) <$> word) from a previous event emission. Thus, this function works like a FIFO queue, with the value of word starting at the left of the tuple and moving to the right before it falls off completely to make way for new values.

To extend the example, we can use our fixed function as a building block to create lags of arbitrary depth.

module Examples.SeveralLagsUsingFix where

import Prelude
import Deku.Toplevel (runInBody)

import Control.Alt ((<|>))
import Data.Compactable (compact)
import Data.Maybe (Maybe(..))
import Data.String (Pattern(..), Replacement(..), replaceAll)
import Data.Tuple (Tuple(..), fst, snd)
import Data.Tuple.Nested ((/\))
import Deku.DOM.Attributes as DA
import Deku.Control (text, text_)
import Deku.DOM as D
import Deku.Do as Deku
import Deku.Hooks (useState')
import Deku.DOM.Listeners as DL
import Deku.Toplevel (runInBody)
import Effect (Effect)
import ExampleAssitant (ExampleSignature)
import FRP.Event.Class (fix, sampleOnRight)
import Deku.Toplevel (runInBody)

buttonClass :: String -> String
buttonClass color =
  replaceAll (Pattern "COLOR") (Replacement color)
    """mb-3 inline-flex items-center rounded-md
border border-transparent bg-COLOR-600 px-3 py-2
text-sm font-medium leading-4 text-white shadow-sm
hover:bg-COLOR-700 focus:outline-none focus:ring-2
focus:ring-COLOR-500 focus:ring-offset-2 mr-4"""

main :: Effect Unit
main = void $ runInBody Deku.do
  setWord /\ word <- useState'
  let
    lag n e
      | n <= 0 = e
      | otherwise =
          compact $ snd <$> fix
            ( \ev -> sampleOnRight
                (pure Nothing <|> (fst <$> ev))
                ((Tuple <<< Just) <$> lag (n - 1) e)
            )
    button text color = D.button
      [ DA.klass_ (buttonClass color), DL.click_ \_ -> (setWord text) ]
      [ text_ text ]
  D.div_
    [ D.div_ $
        [ button "Hickory" "green"
        , button "Dickory" "pink"
        , button "Dock" "indigo"
        ]
    , D.div_ $ [ 0, 1, 2, 3, 4 ] <#> \n -> D.div_
        [ text_ $ "Word with a lag of " <> show n <> ": "
        , text (pure "None" <|> lag n word)
        ]
    ]

HickoryDickoryDock

Word with a lag of 0: None

Word with a lag of 1: None

Word with a lag of 2: None

Word with a lag of 3: None

Word with a lag of 4: None

Using this technique, you can create powerful state machines that articulate arbitrary relationships between items in the past. So long as there is a sampling function that stops the fixed point from turning into an infinite loop, you can articulate any stateful poll you so choose.

Folding events

One special category of fixing is folding. In this section, we’ll define the fold function from fix, build a simple counter using fold, and discuss when to use one versus the other.

The fold function

Folding is a type of fixed point that stores an event's previous value combined with a transformation to produce a new value. The definition is:

fold :: a b. (b -> a -> b) -> b -> Event a -> Event b
fold f b e = fix \i -> sampleOnRight (i <|> pure b) ((flip f) <$> e)

This looks similar to the lag functions we created above, but instead of creating a tuple we create an arbitrary function that combines b and a to produce a b. The type b can, of course, include an a, ie Maybe (Tuple Int a). This allows you to output both a state and the value of the event.

Two simple counters

Let's create two counters - one that uses the State-based methods we learned early in this documentation and one using folding. They'll both do the same thing, but the fold method is a little classier, as you’ll be able to brag to your friends that you’re using fixed points. Your friends may appear indifferent, but they’ll secretly envy you.

module Examples.ASimpleCounter where

import Prelude
import Deku.Toplevel (runInBody)

import Data.Tuple.Nested ((/\))
import Deku.DOM.Attributes as DA
import Deku.Control (text, text_)
import Deku.DOM as D
import Deku.Do as Deku
import Deku.Hooks (useState)
import Deku.DOM.Listeners as DL
import Deku.Toplevel (runInBody)
import Effect (Effect)
import ExampleAssitant (ExampleSignature)
import FRP.Event (fold)
import Deku.Toplevel (runInBody)

buttonClass =
  """inline-flex items-center rounded-md
border border-transparent bg-indigo-600 px-3 py-2
text-sm font-medium leading-4 text-white shadow-sm
hover:bg-indigo-700 focus:outline-none focus:ring-2
focus:ring-indigo-500 focus:ring-offset-2 mr-6""" :: String

main :: Effect Unit
main = void $ runInBody Deku.do
  setCount /\ count <- useState 0
  D.div_
    [ D.button
        [ DA.klass_ buttonClass
        , DL.runOn DL.click $ count <#> (add 1 >>> setCount)
        ]
        [ text_ "Increment" ]
    , D.div_
        [ text_ "Counter 1 using state hooks: "
        , text (show <$> count)
        ]
    , D.div_
        [ text_ "Counter 2 using "
        , D.code__ "fold"
        , text_ ": "
        , text (show <$> (fold (pure <$> add 1) (-1) count))
        ]
    ]

Increment

Counter 1 using state hooks: 0

Counter 2 using fold: 0

Time leaks

We've seen that fixed points can be dangerous because they lead to potentially infinite loops. But there's another, even more devious way that they’re dangerous - time leaks ⌛😵‍💫.

Time leaks occur when the past has to be re-lived in its entirety to arrive at the present. As an example, consider the incrementing of a counter by one. There are two ways to think of this sequence:

• 1 2 3 4 5 ...
• 1 (1 + 1) (1 + 1 + 1) (1 + 1 + 1 + 1) (1 + 1 + 1 + 1 + 1) ...

Even though these two representations of our counter are equivalent conceptually, they diverge computationally. That is, the first example uses the result produced by the past to achieve the present, whereas the second example has to re-live the past step-by-step to get to the present.

Of course, we want programs to be precise according to our intentions, so there are situations where we could want to recompute the past in order to compute the present. But usually we don't. And thankfully, in functional programming, this concept is embodied by the notion of Referential transparency. A referentially transparent expression can be replaced with its corresponding value, which is why a compiler can and does replace the prolix 1 + 1 + 1 + 1 + 1 with its terser homologue 5.

Time leaks come in two flavors. The benign flavor recomputes the past as an application runs, causing it to get progressively slower and eventually crash. At this point, recriminations ensue, someone reboots the server, and we all forget about it until the next time.

A more insidious time leak occurs when the operation in question is not a pure function like addition but rather an effectful computation like debiting a bank account. Instead of repeating the procedure once (ie debiting 10 dollars) we wind up rerunning all of the procedures until the present one, potentially leading to catastrophic data loss.

Let's see this in action. We'll set up two fixed points, one with a time leak and one without. Both fixed points will run an effectful computation on each tick, which will cause one counter to spin out of control whereas the other one stays tame.

Yikes, that's leakier than an abstraction created by an object-oriented programmer!

There's an important semantic distinction between the first and second examples that leads to this outcome. In the first example, we’re creating a fixed point for a type of Effect b. This is all well and good, but look at how we’re using it. We're left binding it, then running an effectful computation f, and then emitting the result. But as monads are just blueprints for programs yet to be executed, by continuously building off of the incoming Effect b to produce the new Effect b, we are creating an ever-increasing blueprint. The result is that, when each one is interpreted, all of the effects up until the present are executed every time the event emits a value.

In the second example, on the other hand, we don't have this problem: the incoming b is a pure value so we do not need to left-bind on it. This is not to say that the Effectmagically disappears - we still have to eliminate it via bindToEffect. But as we learned in the Effects section, bindToEffect “swallows” an effect into its event. This works more like a monadic bind or join, which does not accumulate effects but rather tacks on effects to a sequence.

This difference is subtle, and unless you’re an experienced FRP-er, it is difficult to repair time leaks, let alone spot them. And when you do, while you may get the eternal admiration of your FRP community, you will probably spend hours obsessively pouring over the problem that you could have spent doing other things. So, here's a list of ways to avoid time leaks:

• As much as possible, use primitives from your FRP library that already exist for these purposes. These have been heavily tested and vetted.
• When possible, use Polls to separate out the read-only effectful parts of a computation from the pure ones. A poll is a continuous function of time, so one way to think of anything effectful in FRP is how it is behaving at any given moment, be it a random-number generator or a GET request to an API. Sampling polls on events, doing some work, and then sampling more polls as you need them is not only a better way to write FRP - it makes the use of side effects crystal clear to those reading your code, which makes refactoring easier.
• If (when) you’re using Deku, do all of the effectful work in listeners like click or slider. For example, if you have a game state that updates whenever you click a button based on the previous game state and a current timestamp, this can be modeled as DL.runOn DL.click $ state <#> \s -> now >>= newState s.

That being said, sometimes you just gotta write a time leak, if nothing else than to be reminded of the immense power you wield as a reactive programmer. Only by admiring, then loathing, then coming to terms with your abilities can you use them humbly in the world of mortals that we have no choice but to inhabit.

When to fix and when to fold

In short, it's up to you. They're actually isomorphic. Like a lot of fixed-pointy-thingees (for example the Y-combinator), you can do the same thing several ways. In general, fixed points are harder to read but can feel more expressive or elegant.