Motivation

A fundamental requirement in GUI applications is to maintain consistency between program state (variables holding some data) and the visual UI. Multiple solutions have been adopted to the above problem, but the most used one remains the Callback and Mutation model

• We attach some event listeners to the UI
• On each event occurrence, we update the program state
• Then have some mechanism to propagate this state change, either manually or automatically by some library.
• And finally project all the changes into the UI, again either manually (imperatively) or automatically using some library/framework.

Another solution is the use of Functional Reactive Programming (FRP): we represent UI events as Streams and then combine those streams using various functions to produce other Streams. Program state can be represented using Behaviors: an abstraction to represent time varying values.

To manage state changes and propagation, one popular way is to use Observables: think of a kind of a Box where we put some value. Each time we modify the value inside the box, the program takes care of notifying the user code. Observables can also be combined to produce other observables, like we combine cells in a spreadsheet to produce other cells. An Observable library also usually provides some declarative way keep the UI up to date with the data in observables.

In this post, I’d like to share an implementation of Observable-like abstractions using an (almost) pure functional approach. While you will not probably find new shiny concepts here, if you’ve ever tried, as I did, to implement some form of Observables using the traditional Event Emitters and dependency graphes, then you may find the functional approach presented here more compelling and elegant.

Credit: Conal Elliot’s paper

The approach I propose here is described (purely and more formally) in a Conal Elliot’s (draft) paper Applicative Data-Driven Computation.

The article can be a little hard to follow for those non familiar with the Haskell programming language. In this post I’ll try to present the concept using JavaScript in a hopefully accessible way.

A link to the Gist containing the source code is present at the end of this article

First, what do we mean by ‘Data-Driven’ ?

We’ll start by quoting the first paragraph of the paper

Graphical user interfaces (GUIs) are usually programmed in an “unnatural” style, in that implementation dependencies are inverted, relative to logical dependencies. We suggest that this reversal results directly from the imperative, data-driven orientation of most GUI libraries.

Let’s try to understand what the author means by terms like inverted dependencies and logical dependencies.

Consider this simple example

const a = 100
const b = divide(a, 10)
const c = multiply(a, sum(a, b))

In JavaScript, the above lines correspond to executable statements to be executed sequentially (try to put the declaration of c before b, JavaScript will be unable to resolve b, because it’s not yet declared at the time of evaluating c). In a pure FP language like Haskell, there is no notion of executable statements. We're not telling the compiler to execute the lines above sequentially (in fact We're not telling it to execute anything). We're just writing definitions for equivalences. b = divide(a, 10) means literally that the 2 terms of the equation are equivalent, and that the compiler can use divide(a, 10) in place of b, whenever b appears in an expression. We’re not talking about assignment or memory storage, just equations.

In the example above, to obtain the value of c we demand it (typically via a main function). The compiler starts evaluating c by replacing it with its equivalent term multiply(a, sum(a, b)). Then to evaluate the new term, we substitute multiply with its equivalent definition and so on. This process continues until we can reach irreducible terms (primitive terms which can not be replaced by other terms, like constant literals).

This form of evaluation, also known as demand-driven evaluation, has one particular property: dependencies are logically resolved in the right order. For example, the program can not evaluate c before b because the value of b is needed in order to evaluate c.

If this seems all obvious, then you understand what the author means by logical dependencies. When we want to get the value of an expression which depends on other expressions, the expression will evaluate the other sub-expressions it depends on. The dependency chain is automatically resolved through simple function application (or term reduction).

And now, what could be the meaning of inverted dependencies and Data-Driven orientation?

Imagine that we’re programming an UI application, and that the value of a is retrieved from some UI control like an input box. Typically we attach a listener that observes the changes made by the user to the input value, then we update the program state in an imperative way.

You may be thinking that if we transfer the whole block of the precedent code inside the listener

// represents the program state
var a, b, c
input.addEventListener('change', () => {
  a = input.value
  b = divide(a, 10)
  c = multiply(a, sum(a, b))
})

Then we get the same result as above. In reality, there is a subtle and an important difference. It’s not obvious to illustrate in an imperative language like JavaScript. To make it more obvious let’s rewrite the first example in a way to mimic an FP language.

function a() {
  return 100
}

function c() {
  return multiply(a(), sum((a(), b())
}

function b() {
  return divide(a(), 10)
}

Have you noted how we’ve put the c declaration before b. What happens if we invoke c() on the console? do we still get the right value? of course yes. It doesn't matter at all in which order we put the above declarations. Evaluating a function will always resolve the dependencies in the correct order.

Now what happens if we change the order in the second example?

//...
input.addEventListener('change', () => {
  a = input.value
  c = multiply(a, sum(a, b))
  b = divide(a, 10)
})

Since c is updated before b, its value is computed using a stale value of b. Here you'll notice that the order in which we put things does crucially matter. We have to put our statements in the correct order of dependencies. Put another way, instead of relying on simple function invocation, which naturally resolves its dependencies in the logical order. We now have the burden to ensure the order of things by ourselves. Or also: instead of starting from the bottom - the output value which is c - and pulling all its inputs, we take the inverse route: we start from the top - the input value which is a - and push updates to all the outputs ourselves. The computation proceeds in an inverted order.

You may object that we can make b and c simple functions instead of variables, and then update the UI by invoking them. Indeed this is a step in the right direction: do not update derived data, but compute it on demand.

However in real code, the situation is much more complex and it's often tedious to manage derived data manually. Also, we likely need to update some part of the UI which depend on the dynamic data. Managing those dependencies manually is often complex and error prone.

And finally, what’s this Data-Driven thing? It describes a programming style (often associated with Data-Flow architectures) where “the availability of data (inputs) triggers the operations to be executed on it”. In this style of programming, we’re in charge of manually propagating data changes, and thus implementing dependencies correctly in our code. By subscribing to some data sources, each time the data source notifies some change we need to update the dependent data in the correct order.

Quoting the author again

While outputs depend on inputs from a user and semantic point of view, the data-driven approach imposes an implementation dependence of inputs on outputs.

also

This paper presents simple, functional interfaces for data-driven programming in general and GUI programming in particular, in which program dependencies directly mirror logical dependencies.

The solution presented in this post is more informal and simplified to make it accessible (Especially I’m occulting IO). Also I dont present the part of the author’s functional model of GUIs (maybe in another post).

The model described in the article builds on top of 3 concepts

• Getters (Extractors in the paper) for retrieving some piece of state
• Notifiers abstract over change notification
• Sources combine the 2 previous concepts to represent time varying state.

Getters

A Getter is a function that takes no parameter and returns a value

Getter a :: () -> a

I’m writing type annotations in a pseudo Haskell notation. The declaration above means that a Getter for a given type ais a function which takes nothing and return that type.

Example

// message :: Getter String
const message = () => 'Hello world!'

// scrollTop :: Element -> Getter Number
function scrollTop(element) {
  return () => element.scrollTop
}

current value of `a`
var a = 10
// getA :: Getter Number
const getA = () => a

Our abstraction defined. We should provide some way to make it composable using functions as we do with simple values.

We start with computations on a single value. Given a Getter a and a function f :: a -> b, we'll derive a Getter b which will return f(a) if the original Getter returns a.

// gmap :: ((a -> b), Getter a), Getter b
function gmap(fn, getter) {
  return () => fn(getter())
}

Note that gmap simply denotes function composition

// compose :: ((a -> b), (x -> a)) -> (x -> b)
function compose(f, g) {
  return x => f(g(x))
}

Just replace the x in the type annotation with ().

For example, given the current value of a DOM input, we’d like a Getter with the trimmed and upper-cased text

// inputValue :: HTMLInputElement -> Getter String
function inputValue(input) {
  return () => input.value
}

// getValue :: Getter String
const getValue = inputValue(document.getElementById('my-input'))

function sanitizeText(text) {
  return text.trim().toUpperCase()
} 

const getSanitizedText = gmap(sanitizeText, getValue)

Of course we can write our Getter directly as () => domInput.value.trim().toUpperCase() but by doing this, we lose the advantage of composition. We'll see how later on the ‘Sources’ section.

To compose Getters we’ll define a gcombine function. Given 2 inputs Getter a and Getter b and a binary function f :: (a, b) -> c. We'd like to derive a Getter c whose value is f(a, b).

// gcombine2 :: ((a, b) -> c, Getter a, Getter b) -> Getter c
function gcombine2(fn, getter1, getter2) {
  return () => fn(getter1(), getter2())
}

As an example, given 2 Getters for 2 DOM inputs, we derive a Getter for their sums (I know I lack creative demos, this is just to illustrate)

const getX = inputValue( document.getElementById('x-input') )
const getY = inputValue( document.getElementById('y-input') )

function sum(x, y) {
  return Number(x) + Number(y)
}

const getSumXY = gcombine2(sum, getX, getY)

We can define gcombine3 or gcombine4 for combining with 3-ary or 4-ary functions. But let's just generalize to a variable number of parameters

// gcombine :: ((...a) -> b, ...Getter a) -> Getter b
function gcombine(fn, ...getters) {
  return () => fn(...getters.map(g => g()))
}

Note: We can make the fn parameter itself a Getter to combine with dynamic functions.

And that’s it for Getters.

Notifiers

Next we’ll introduce Notifiers. Quoting the author

value extraction is not enough; we also need to construct change notifiers. We will represent a notifier as the ability for clients to “subscribe” actions to be invoked whenever an event occurs.

A Getter allows us to get a stable reference to some piece of state. While a Notifier informs us whenever this piece of state changes.

First let’s define some type signatures

Listener a :: a -> ()
Unsubscribe :: () -> ()
Notifier a :: Listener a -> Unsubscribe

This may seem familiar if you’ve worked with Event Emitters. A Notifier for a given type a is a function which takes a listener for the same type and returns a function to unsubscribe the listener when invoked.

A simple exemple could be subscribing to DOM input changes

function domNotifier(target, event) {
  return (listener) => {
    target.addEventListener(event, listener)
    return () => {
      target.removeEventListener(event, listener)
    }
  }
}

// inputChanged :: Notifier Event
const inputChanged = domNotifier(someDOMInput, 'change')

const unsubscribe = inputChanged(e => {
  console.log('Got a change event', e)
})

As in the previous section, we define the map function. Given a Notifier a and a function f :: a -> b, we'll derive a Notifier b. The resulting Notifier will notify f(a) whenever the original Notifier notifies a

// nmap :: (a -> b, Notifier a) -> Notifier b
function nmap(fn, notifier) {
  return listener => {
    return notifier(a => listener(fn(a)))
  }
}

Our implementation simply substitutes the given listener with another one that intercepts the reported event data, transforms it with the mapping function, and finally passes the transformed data to the original listener.

For example, we can transform inputChanged in our previous example, from a Notifier Event to a Notifier String by mapping it with a function that extracts the value from the DOM event.

const targetValue = event => event.target.value
const inputValueChanged = nmap(targetValue, inputChanged)

We’re not going to compose Notifiers like we did with Getters (using Applicative). Instead we opt for the merge operation. Given 2 Notifiers, we'll build a Notifier that notifies changes from both sources (merging 2 sources into one).

// merge2 :: (Notifier a, Notifier b) -> Notifier (a | b)
function merge2(notifier1, notifier2) {
  return listener => {
    // subscribes the passed listener to both notifers
    const unsubscribe1 = notifier1(listener)
    const unsubscribe2 = notifier2(listener)

    // result function unsubscribe also from both notifiers
    return () => {
      unsubscribe1()
      unsubscribe1()
    }
  }
}

Similarly, we can extend the above definition to an arbitrary list of notifiers

// merge :: (...Notifier a) -> Notifier a
function merge(...notifiers) {
  return listener => {
    const unsubscribes = notifiers.map(
      notifier => notifier(listener)
    )
    return () => {
      unsubscribes.forEach(unsubscribe => unsubscribe())
    }
  }
}

As an example, consider the classic up/down demo when we subscribe to clicks on 2 buttons Up and Down

const btnUp = document.getElementById('btn-up')
const btnDown = document.getElementById('btn-down')

const upDown = merge2(
  nmap(() => 'Up', domNotifier(btnUp)),
  nmap(() => 'Down', domNotifier(btnDown))
)

upDown(type => console.log('Got a click on', type))

And to complete we’ll define one more operator. We’ll call it Never. It simply represents a Notifier which doesn't report any change (We'll use it later to define constant sources of data). The implementation is just a noop function.

// Never :: Notifier ()
const Never = () => {}

Now that we have our ingredients, let’s get to the main stuff.

Sources

To represent sources of data that may change, we use a pair of Getter & Notifier. The Getter allows us to extract the up-to-date version of the data while the Notifier notifies us when any change happens to that data.

// simple factory function
function Source(getter, notifier) {
  return {
    getter,
    notifier
  }
}

The simplest example of Sources is the constant Source whose data never changes

// sconst :: a -> Source a
function sconst(a) {
  return Source(
    () => a,  // always return the same data
    Never     // never report changes
  )
}

Another example, we can represent the value of a text input as a Source which will report changes made by the user on every change event (or also input events)

function inputValueSource(element, event) {
  return Source(
    () => element.value,
    domNotifier(element, event)
  )
}

const myInput = document.getElementById('my-input')
const myInputValue = inputValueSource(myInput, 'change')

As we did previously. Let’s define the map function. Given a Source a and a function f :: a -> b, we'll derive a new Source b whose Getter returns f(a) (whith the original Source'Getter returning a).

// smap ::  ((a -> b), Source a) -> Source b
function smap(fn, src) {
  return Source(
    gmap(fn, src.getter), // maps over the Getter
    src.notifier          // reuses the same Notifier
  )
}

Our goal is to transform Source a to Source b given some function a -> b. For example, imagine we have a source for a numeric value, and we want to get a source representing the double of that value.

A :: Source Number
doubleOfA :: Source Number
doubleOfA = smap(x => x * 2, A)

We want the Getter of our derived Source to always return the double of the value returned by the Getter of the original Source. That’s why in our implementation, we map the passed function over the Getter of the original Source.

Similarly, our new Source should report changes whenever the original Source reports changes itself. Since a change in the original Getter’s value will likely (but not necessarily) result in a change on the transformed value, we simply reuse the Notifier of the original Source.

To compose multiple Sources we’ll build on top the composition of its constituents. i.e. we compose input Sources by composing their Getters and Notifiers respectively.

We’ll start with binary functions: Given some input Sources Source a and Source b and a binary function f :: (a, b) -> c, we'll derive a Source whose Getter returns f(a, b) (with the 2 input Sources Getters returning resp. a and b). Also, we want our new Source to report changes whenever any of the input Sources reports changes because a change on any input value will likely result in a change on the output value.

// scombine2 :: ((a, b) -> c, Source a, Source b) -> Source c
function scombine2(fn, src1, src2) {
  return Source(
    gcombine2(fn, src1.getter, src2.getter),
    merge2(src1.notifier, src2.notifier)
  )
}

The implementation compose 2 Sources by

• composing their Getters using the mapping function
• merging their Notifiers to get a change notification whenever any of the input Notifiers reports some change.

And similarly we define a generalized version which works with a variable number of parameters

// scombine :: ((...a) -> b, ...Source a) -> Source b
function scombine(fn, srcs) {
  return Source(
    gcombine(fn, ...srcs.map(src => src.getter)),
    merge(...srcs.map(src => src.notifier))
  )
}

Finally, we’ll define a react function (runDD in the paper) which will execute some action whenever the Source changes. In our implementation, the action will be passed the current value of the Source as a parameter

// Action a :: a -> ()
// react :: (Source a, Action a) -> Unsubscribe
function react(src, action) {
  const listener = () => action(src.getter())

  // executes the action as initialization
  listener()

  // returns a function to unsubscribe the action
  return src.notifier(listener)
}

Sources provide a low level and a generic abstraction upon which we can build higher level ones. But they come equipped with a solid compositional foundation (yes Math). You can define sources of multiple types (Mutable variables, Behaviors, Server data …) and combine them using the common combining method.

Some Examples of Sources

• Knockout/Mobx like observables
• Redux Store state
• Reactive Behaviors

Knockout/Mobx like observables

We can define Sources that reflects values of mutable variables. We provide the initial value at the Source creation and expose an imperative set method to mutate the value inside the Source. Each change will propagate throughout all Sources which depend on the root Source.

We start by defining a simplified implementation of event emitters

function Emitter() {
  
  let listeners = []

  return {
    subscribe(listener) {
      listeners.push(listener)
      return () => {
        listeners.splice(listeners.indexOf(listener), 1)
      }
    },

    emit(data) {
      listeners.forEach(listener => listener())
    }
  }
}

Then our mutable Source instance

function Mutable(seed) {

  const emitter = Emitter()

  const src = Source(
    () => seed,
    emitter.subscribe
  )
  // provide a method to mutate the state manually
  src.set = newValue => {
    seed = newValue
    emitter.emit()
  }

  return src
}

Now we can create and combine them using the Source composition capability.

const ma = Mutable(1)
const mb = Mutable(2)

const mc = scombine(
  (a, b) => a + b,
  ma, mb
)

react(mc, value => {
  console.log('c = ', value)
})

ma.set(100)

Avoiding Glitches

There is a little issue in the Mutable implementation above. Suppose we have this example

const ma = Mutable(1)

// mb depends on ma
const mb = smap(
  a => a * 2,
  ma
)

// mc depends on both ma & mb
const mc = scombine(
  (a, b) => a + b,
  ma, mb
)

react(mc, value => {
  console.log('c = ', value)
})

ma.set(10)
/**
The console message is reported twice. Due to a redundant notification
=> 30
=> 30
**/

When we set the value of ma the action registered in react gets executed twice. This happens because of our dependency chain

• mb depnds on ma
• mc depends both on mb and ma

Due to how scombine and merge are implemented we end up subscribing to the original source ma twice. The first time, react registers its listener to mb which simply registers it to ma, (remember smap reuses the notifier of the input Source), the second time it subscribes directly to ma. Because of this we get a redundant subscription and notification.

A simple solution is to prevent Emitter from registering the same listener twice. We can do this by replacing the internal array of listeners with a Set (a Set ensures that only one copy of the element is stored inside it)

function Emitter() {
  let listeners = new Set()

  return {
    subscribe(listener) {
      listeners = listeners.add(listener)
      return () => {
        listeners = listener.delete(listener)
      }
    },

    emit(data) {
      listeners.forEach(listener => listener())
    }
  }
}

A more general Solution (presented in the paper) will be making the notifier member of Source itself a Set. We can then define merge like an operation which merges together 2 Sets. react will subscribe to all elements in the final Set. Because the Set ensures uniqueness of elements inside it, any combined Source passed to react will have exactly one copy of each source notifier, even if we endup recombining the same source more than once.

Redux Store’s state

Defining a Source instance for Redux Stores is trivial, because we already have the required elements: a Getter and a Notifier.

function reduxSource(store) {
  return Source(
    store.getState,
    store.subscribe
  )
}

We can then combine multiple stores into one Source. The resulting Source could for example provides an aggregation of all the states of the combined stores

const storeA = createStore(
  combineReducers({
    sliceOneA: ...,
    sliceTwoA: ...
  })
)

const storeB = createStore(
  combineReducers({
    sliceOneB: ...,
    sliceTwoB: ...
  })
)

const srcA = reduxSource(storeA)
const srcB = reduxSource(storeB)

const combinedSrc = scombine((stateA, stateB) => {
  return {stateA, stateB}
}, srcA, srcB)

/**
Will have a state shape of
{
  stateA: {
    sliceOneA: ...,
    sliceTwoA: ...
  },
  stateB: {
    sliceOneA: ...,
    sliceTwoA: ...
  }
}

Notifications will bubble up from both stores.
**/

We can even combine Redux Sources with other types of Sources like Mutables.

Reactive Behaviors

Reactive Behaviors are like an hybrid between free Mutables and Redux encapsulated state. To create a Behavior, we need to provide a

• An initial value
• A list of pairs (Notifier, reducer) // reducer :: (state, event) -> state

The Getter for the Behavior will first returns the initial value. But each time a Notifier in the list of pairs (Notifier, Reducer) reports some event we invoke the corresponding reducer with the current value of the Behavior and the reported event.

For example, here is the classic upDwon demo (the example is trivial but can be extended to handle more complex cases of incremental state)

<button id=up>Up</button>
<button id=down>Down</button>
<div id=count></div>

const onUp = domNotifier(document.getElementById('up'), 'click')
const onDown = domNotifier(document.getElementById('down'), 'click')
const divCount = document.getElementById('count')

const count = Behavior(0,
  [onUp, (count, _) => count + 1],
  [onDown, (count, _) => count - 1]
)

react(count, value => {
  divCount.textContent = `Count = ${value}`
})

A possible implementation of Behaviors on top of Sources

function Behavior(seed, ...cases) {

  cases.forEach(([notifier, reducer]) => {
    notifier(event => {
      seed = reducer(seed, event)
    })
  })

  return Source(
    () => seed,
    merge(...cases.map(([notifier, _]) => notifier))
  )
}

Further developments

Possible ideas

• scombine (and therefore gcombine) re-applies the function on each notification even if the data has not changed. We can memoize the combining function to avoid wasteful recomputations
• Add support for dynamic dependencies: Right now, you have to provide the input sources to scombine at the invocation. Sometimes it's not possible to know in advance the list of dependencies (eg aSource containing an array of Sources). A possible solution could be declaring the notifier member of a Source itself as a Source. ie instead of Source a :: (Getter a, Notifier ()) we'll have instead Source a :: (Getter a, Notifier () | Source (Notifier ()) )
• Define a Monad instance for Notifier (join, flatmap) to perform Side Effects
• Connect Sources to React components

Gist containing the source code

function Greeting({name}) {
  return (
    <h1>Hello {name}!</h1>
  );
}

We want to show this component inside a box. The box will draw a selection outline around our component when the user clicks on it, and will toggle the selection state each time it's clicked.

First We’ll show the direct way

class GreetingBox extends React.Component {

  constructor(props)  {
    super(props)
    this.state = { selected: false }

    this.toggleSelection = () => {
      this.setState( state => ({ 
        selected: !state.selected 
      }))
    }
  }

  render() {
    const style = {
      cursor: 'default',
      border: this.state.selected ? '1px dotted black': 'none'
    }
    return (
      <div style={style} onClick={this.toggleSelection}>
        <Greeting name='World' />
      </div>
    )
  }
}

Of course, above there is an unnecessary coupling between GreetingBox and Greeting. A selection box is typically unaware of what’s inside it, and I guess this is a well known thing. But here I want to show another thing I noticed. it maybe something experienced React developers already know, but I couldn’t find any explicit mention to it in the the React docs (esp. performance related ones).

First let’s add a simple log statement inside our render methods

function Greeting () {
  console.log('Greeting.render()')
  ...
}

class GreetingBox extends React.Component {
  ...
  render() {
    console.log('GreetingBox.render()')
    ...
  }
}

And then render our application into a dom node (#app in our example)

ReactDom.render(
  <GreetingBox />,
  document.querySelector('#app')
)

Now run this application and observe the console messages

You can use this online demo

You’ll see that each time you click on GreetingBox, Greeting's render method is being called. But this is natural, isn't it? GreetingBox.setState triggers a re-render of the component, which will trigger itself calling children's render method (unless shouldComponentUpdate prevents it).

Now let’s change our implementation of GreetingBox and make a generic container (not in the sense of Container/Smart vs Presentational/Dumb).

class SelectableBox extends React.Component {
  ... 
  render() {
    ...
    return (
      <div style={style} onClick={this.toggleSelection}>
        {this.props.children}
      </div>
    )
  }
}

We made our box generic and unaware of its rendered content.

Let’s rewrite our application with the new implementation

function App() {
  console.log('App.render()')
  return (
    <SelectableBox>
      <Greeting name='World' />
    </SelectableBox>
  )
}

Instead of an ad-hoc component GreetingBox, we're making our application by composing SelectableBox and Greeting. We're passing Greeting as the children property of of SelectableBox.

Now let’s re-execute the application

ReactDom.render(
  <App />,
  document.querySelector('#app')
)

You can use this online demo

If you observe the console message you’ll see that this time the Greeting’s render method is no longer called when you click on the message. Even if the SelectableBox’s state is updated.

It may seem confusing to some people. Greeting is rendered inside SelectableBox and rendering the latter will naturally trigger a re-render of its children, unless we put a shouldComponentUpdate barrier. But apparently this wasn’t the case. Why ?

I think it’s due to 2 things

• A hard assumption that React makes about render methods being pure with regard to the Component’s props and state
• and a special, and also lesser known, concept that React has: the Owner/Ownee relation in a rendered component tree (vs the traditional parent/child relation). (Update: make sure to read comments made by Dan Abramov at the end of this post about this assumption)

There is a section in the React docs that explains the relation. The section is brief but I think it’s clear enough.

The important bits are:

In React, an owner is the component that sets the props of other components.

The owner-ownee relationship is specific to React, while the parent-child relationship is simply the one you know and love from the DOM

Back to our example:

• the App component is the owner of both SelectableBox and Greeting because it sets their props in its render method.
• the SelectableBox is the parent of Greeting because it renders it inside its proper render tree. SelectableBox doesn’t affect its children in any way but acts as a mere visual placeholder for it.

As mentioned above, you may have thought that updating a component always triggers a re-render and reconciliation of its children but as it appears from our example, this only applies to owned components.

I’m not sure how this is implemented under the hood. But one possible way (which React may or may not be using) is to perform some form of memoization on instances’s render method.

Since render methods are assumed to be pure (with regard to props and state), an update to a non owner component will not modify children’s props, so a memoized render will not actually invoke the instance’s render method but just return the latest cached result (last element returned by render). Reconciliation on this case will be very fast because we will have the same memory reference for both the old and the new element and can skip the much slower deep comparison process.

In this case however we update App which is the Greeting's owner:

class App extends React.Component {

  constructor(props)  {
    super(props)
    this.state = { dummy: 0 }

    this.updateState = () => {
      this.setState( state => ({ 
        dummy: ++state.dummy 
      }))
    }
  } 

  render() {
    console.log('App.render()')
    return (
      <div>
        <button onClick={this.updateState}>
          Update App state
        </button>
        <SelectableBox>
          <Greeting name='World' />
        </SelectableBox>
       </div>
    )
  }
}

See what happens with this online demo

If you click the ‘Update App state’ button and watch the console output, you will notice that updating App's state triggers a re-render of all its owned components (SelectableBox and Greeting).

Even if the passed props didn’t change (no props were passed toSelectableBox and a constant 'World' is always passed to thename prop of Greeting), the render method of App constructs new SelectableBox and Greeting elements, which in turn triggers (I guess) the invocation of render methods on the corresponding Component’s instances. Here we need to optimize with the well known shouldComponentUpdate if want to prevent the unnecessary rendering.

I think this behavior is what sets React apart from other virtual DOM libraries. In a raw virtual DOM approach (the lib only provides abstraction for virtual nodes, diff and patch, but not for Components), there is only one relation: the parent/child, which typically reflects the real DOM hierarchy. Updating a virtual node will trigger the reconciliation of all its children, because the lib has no knowledge of data flow dependencies (who’s responsible of setting props on a virtual node). To optimize, we need to use an explicit optimization/memoization (like thunks in Snabbdom)

In some situation this can be really crucial for the application’s performances. Imagine that our top level App renders an expensive part of its tree inside a Dockable container.

<App>
  <Dock>
    ... some component tree we need to dock
  </Dock>
  ... some other component tree here
</App>

Suppose the Dock component provides some UI to allow adjusting its width via mouse dragging. In a raw virtual dom approach, each mouse movement will cause a reconciliation of the entire Dock's children tree unless you put some explicit/manual optimization barrier.

However in React, mouse movements will only trigger a reconciliation on the Dock component but not on the expensive child subtree because Dock doesn't own it. And all this is handled automatically by the underlying React model, no manual or explicit optimization is required.

As a side note, I tried the above example with Preact which is a popular alternative implementation with a similar React api.

Online demo with preact

You’ll notice that when you click on the message, triggering an update on SelectableBox, The Greeting render method is called even if SelectableBox doesn’t own it. So it appears that Preact doesn’t have support, at the time of this writing, of the Owner/Ownee relation.

Update, Dan Abramov made some comments about the Owner/ownee assumption

Dan Abramov on Twitter

@YassineElouafi2 I don't think it's owner/ownee. (We're actually trying to kill the tracking of current owner because it causes issues.)

Dan Abramov on Twitter

@YassineElouafi2 Most likely it's because this.props.children is referentially equal between renders since App wasn't re-rendered.

Dan Abramov on Twitter

@YassineElouafi2 React bails out if the elements are referentially equal.

Elm Architecture & Side Effects: example with Snabbdom/JSX

In a previous post we saw how to write web applications based on the Elm architectural pattern (using plain JavaScript and Snabbdom for Virtual DOM rendering). The main benefit of Elm architecture being that we can describe the application logic as a set of pure functions.

This article treats the next logical step: how to deal with Side Effects in the pure Elm model : server API calls, Asynchronous Actions …

The Login example

During this post we’ll develop a simple login application : the user is provided with a login form when he must enter a username and a password. Then the entered credentials are validated against a remote API, if the login is successful the user is redirected either to an admin page if he has the admin role or a guest page otherwise.

We’ll start with a pure version without side effects, then we’ll enhance the application by introducing side effects and a nested hierarchy of components.

To stay focused the API will be mocked by a simple local timeout-ed function.

Full sources of this example are here

The Setup

To start our project we need the following libs:

• snabbdom : for Virtual DOM creation and patching
• snabbdom-jsx : to generate Snabbdom virtual nodes using JSX
• union-type: to represent Actions

We’ll also need babel to compile ES2015 and JSX code into compatible JavaScript code. To build the browser bundle, you can either use Browserify or Webpack; in this post i’ll use the first one.

You can use the following into your package.json file to get things up quickly

then run ‘npm install’ to pull all dependencies

To host the JS application w’ll use this index.html file in the root of our example directory

You can get the ‘style.css’ file from here.

Finally create a ‘js’ sub-directory. All our application code will go inside it. The final directory layout should look like

Et voilà! We’re ready to start

The Login Component : iteration 1

Create a Login.js file inside the js directory (from now on all JavaScript files must be put here). Here is our first version

Our component defines 2 functions, ‘init’ which returns the initial state and ‘view’ which constructs a virtual node from a given state. For now, ‘Login’ is passive and doesn’t fire any action so we don’t have Actions or an ‘update’ function. All we do is showing data we get from the input state.

To bootstrap our application. Create a ‘main.js’ file then copy the following content

The main module connects the component to the real DOM via the ‘dispatch’ function and continually reacts to all state changes by constructing new virtual nodes then patching the real DOM with them.

All we have to do now is

npm run build

It should compile all JavaScript files in the js directory and generate a ‘build.js’ file in the root of the example directory. Now open the index.html in the browser and normally you should have something like this

If something goes wrong, let me a comment or create an issue in the GitHub repository.

The Login Component : iteration 2

Now let’s add some action. First we’d like to save the user input into our state. We’ll also add a status message below the button, when the user submits the form, we’ll show the entered credentials in the status message. Later we’ll use it to show error messages.

Below the modifications to our code

So here is what we did:

1. We added 3 actions, 2 to get the ‘name’ and ‘password’ inputs, and one to react to the submit event of the form.
2. Since our data model has changed, the ‘init’ function also initializes the status message with an empty string.
3. We added 2 event handlers to hookup user events (see below)
4. updated the view : we added the status message and connected DOM events to our event handlers
5. Handled the actions in an ‘update’ function by setting the appropriate field (using the awesome (…) spread ES7 syntax thanks Babel!).

‘onInput’ is a Higher Order Function, it takes an action, a dispatcher and returns another function : this is the real event handler that takes the input event, extracts the input string from event.target and then calls dispatch with that result.

In the view each input field creates its appropriate event handler by providing its particular action to the Higher Order Function ‘onInput’. This way we don’t have to create an event handler for each input for our view, especially, if you have a bunch of input fields in your form. Just one parametrized function to rule them all.

Actually, we can do better than that. Since we’ll likely need to extract the user input from event.target quite a lot, let’s create a helper function for that. Create a ‘helpers.js’ file and add the following function

Some of you may have already guessed. For ‘pipe’ it’s just function composition but in the other sens : take an input and send it through a pipeline of functions. Much like node pipes

Now back to the Login.js

This is surely much better. Our event handlers are directly created by the pipe function. The event object travels through a set of pure functions until it reaches the dispatch callback.

‘onSubmit’ is another Higher Order Function (or a curried function if you like) which returns the form submit handler. It fires the Login action and do some necessary dirty stuff to prevent the browser from refreshing the web page.

That’s it, hit ‘npm run build’ again and refresh your browser page. Enter some data in the form and hit RETURN or click the Submit button. Normally you should see the entered data below the button.

Now let’s get to the dirty stuff : Side effects.

The Login Component : iteration 3

We’ll now make our Login a bit more realistic. Submitting the form should trigger some API call to validate the entered credentials, and get the response : for now we’ll just show a success or an error message. Later we’ll see how to redirect to an appropriate page on a successful login.

We’ll mock our API call with a simple local function using setTimeout, this way we can test our code locally without need to create a server side code.

Create an ‘api.js’ file with the following content

For our testing purpose, a simple array will be sufficient. The exported function delays the response by 200ms to simulate a server call.

Now to the real question.

When and where should we make the API call ?

Well, as it turns out, there can be multiples answers.

In this post and the followings, w’ll expose 3 possible solutions

1. Make the API call directly in the event handler
2. The standard Elm solution : changes the signature of the ‘update’ function to make it return the desired Side Effect (update : (state, action) → (state, Effect).
3. The third is inspired by this interesting post on the Redux Github site. And tries to address an issue we’ll see with the Elm approach.

Actually, all the 3 solutions share a common pattern, a side effect (like an asynchronous call) commonly involves 3 actions.

1. A start action, before we trigger the side effect. In response to this action, the update function can react by setting some pending flag to show some spinner or loading indicator for example.
2. An outcome action, when the side effect is carried out and we get an eventual response : either a success or an error. So we’ll have to create a separate action for each possible outcome.

Login Component : Iteration 4

First, the Login action has been split into 3 actions as we described above : a start action and 2 possible outcomes.

Next, the onSubmit is called now with the current state as an additional parameter. Then both state and dispatch are passed down to the ‘doLogin’ function which triggers the API call.

doLogin first fires the start action, which is handled by update to display the “Please wait…” status message. Then makes the API call which returns a promise : either resolved with the success message or rejected with the login error. The promise response is handled by firing the appropriate outcome action. Which in turn is handled by update to notify the user via the status field.

This method has the advantage of being simple. It doesn’t add much boilerplate to our component while still keeping the update free of side effects. We’ll see next how this method fit in a nested hierarchy.

The App component

We’ll now expand our requirements : instead of showing a success login message. We’ll redirect the user to an appropriate page.

Create a new file App.js to hold the content of our new component.

We’ll go with the content step by step. First we define the state shape and its actions

Our state holds a page dictionary, the current user name, the current page and, since the App component will embed the Login component, we maintain the current Login state.

We define 2 actions : one for switching to the appropriate page once we get a successful login and another to route Login Actions to their destination.

Next the view function

If the user has been successfully logged in, we show the appropriate page (Guest or Admin). Otherwise we show the Login page. Note how we pass onLogin callback : the Login component will call this function in the case of a successful login with the user name. onLogin, in turn, fire the ShowPage action passing it the same username.

The update function

ShowPage is simply handled by setting the user name in the state. As we saw in the view, the user name will be used as a key to access the appropriate page from the pages dictionary.

UpdateLogin handler simply routes the inner action to Login and save its new returned state.

We’ll still have to define the code for the Admin and Guest pages. For our example, they are simple passive views that display the current user

Admin.js

Guest.js

And don’t forget to update the code for the Login component

And that’s it! we can finally hit npm run build to check the results.

And voilà! You have now a skeleton code for a simple router : You can enhance it for example to make the App component route actions for Admin and Guest. Thus allowing the child pages to be full reactive components (hint: add currentState field and an UpdatePage action). You can also hook up to the hashchange or popstate event of the window to trigger the ShowPage Action.

I’m going to stop here to get some sleep. Next post we’ll see the Elm solution to address side effects. Good night.

React was a true addition to the JavaScript community. While one can find JSX — the HTML like syntax inside JavaScript — controversial. It is not the same for the Virtual DOM concept.

For the non familiar, Virtual DOM is a simplified memory representation of the real DOM state at a certain moment. The idea is : instead of directly updating the real DOM with imperative statements, you build a virtual DOM each time your UI state changes, and the underlying library updates the physical DOM accordingly

It’s important to note that the update operation doesn’t replace the whole DOM tree (like setting innerHTML with an HTML string), but only replaces the parts of the DOM that actually changed (modify Node properties, adding a child element…). i.e. incremental updates are inferred by diffing the old and the new Virtual DOM versions., then patching the real DOM to reflect the new version.

The Virtual DOM concept has been often emphasized for its speedy performance. But there is also an equally important — if not more important — property. The concept makes it possible to represent the UI as a function of its state. This makes it possible to explore new ways of writing web applications.

In this post we examine how the concept of Virtual DOM fits in a web application. W’ll start by simple examples then present an architecture to write virtual DOM based applications (hint: if you love pure functions, you won’t be deceived).

For that, we will opt for a standalone and plain JavaScript (no JSX) virtual DOM library, because we need to examine the smallest basic puzzles.

There are a few good standalone virtual DOM libraries around, for my post i will use snabbdom (paldepind/snabbdom), a small lib written by Simon Friis Vindum. But the examples can be implemented in any other similar lib like the Matt Esch’s virtual-dom.

Quick snabbdom tutorial

Snabbdom is provided as a set of CommonJs modules. So we need a client side module bundler like browserify or webpack.

First let’s examine how to bootstrap a basic application

Above we ‘init’ the core snabbdom module with a set of extensions. In snabbdom, functionalities like toggling classes, styles and even setting properties on DOM elements are delegated to separate modules. For our case, we will just use the default modules.

The core module exposes only one function ‘patch’, which is returned by the init method. We use it to create the initial DOM as well as updating it later.

Here is what a basic Hello example looks like in snabbdom

‘h’ is a helper function to create virtual nodes. W’ll discover the usage in the rest of this post, for now just remember it takes 3 inputs:

1. a selector like ‘‘div#id.class’
2. an optional data object which specifies properties of the virtual node (class, styles, events …) as w’ll see later.
3. Optionally, a string or an array of child virtual nodes.

The first time, patch expect a placeholder DOM element and an initial virtual node. It then creates the initial DOM tree that mirrors the virtual one. In subsequent calls, we provide it with the previous and the new virtual nodes. It then diffs the 2 virtual nodes and patches the DOM with the necessary modifications to take it into a new state that mirrors the new virtual representation

In order to get things up quickly, I created a GitHub repository with the all basic stuff to start right away. So the first step is to clone the repository at (yelouafi/snabbdom-starter). After that install the dependencies with ‘npm install’. The kit uses Browserify for browser bundling, Watchify for automatic rebuilds on file change, and Babel to allow us writing nice ES6 code and transpile it to ES5 compatible code.

After installing type

npm run watch

This will start the Watchify module, which will create the browser bundle ‘build.js’ inside the ‘app’ folder. The module will also watch for changes we make in JavaScript files and rebuild the bundle automatically (for manual builds you can type ‘npm run build’).

To run the application, open the ‘app/index.html’ file in the browser. Normally, you should see a ‘Hello world’ message on the screen.

All the examples w’ll see in this post can be found on the GitHub repo, each example is implemented in a specific branch, w’ll link to each branch throughout the post; the README file of the repo contains links to all branches.

A dynamic view

Sources for this example in the dynamic-view branch

To highlight the dynamic aspect of the Virtual DOM, w’ll build a very simple clock. Change ‘app/js/main.js’ as below

The virtual node construction has been delegated to a separate function ‘view’, which takes as input the current state (the current date).

The example illustrates a typical pattern in virtual DOM based applications. At the very low level, the application behavior consists of constructing new virtual trees successively at different moments of interest (timer, user events, server events…) and then patching the actual DOM with the changes compared to the latest virtual node. In our example, we construct a new virtual tree every second and update the DOM with it.

Event reactivity

Sources for this example are in the event-reactivity branch

The next example introduces event handling through a basic greeting app

In snabbdom, we set element’s properties through the ‘props’ object, which get handled by the ‘props’ module. Similarly we set event listeners through the ‘on’ object which get handled by the ‘eventlisteners’ module.

In the above example, the ‘update’ function plays the same rule as ‘setInterval’ from the previous example : it constructs a new virtual tree, using the data extracted from the incoming event, then calls patch to update the DOM with the new created tree.

Structuring complex applications

The benefit of using a standalone virtual DOM library is that we become free to structure our application the way we like. You can adopt the old good MVC pattern, or opt for a ‘more modern’ architecture like Flux.

In this post i’ll present a less-known architectural pattern I’ve encountered in Elm (an FP language that compiles to JavaScript). The pattern is known among Elm developers as Elm Architecture, so w’ll stick to that name in the rest of this post. The main advantage is that it allows us to write the whole application as a set of pure functions.

But before, w’ll take a moment to reason about the overall behavior of our example above. In this process w’ll take some inspiration from this excellent talk of André Staltz’s.

The main loop

Let’s examine the overall process of the last example :

1. evaluate the ‘view’ function with an initial state and construct our first virtual node. Within the ‘view’ function, a listener is attached to the ‘input’ event of the text input
2. patch the DOM with the new virtual node; attaching BTW the input event listener to the real DOM
3. waiting for user action : ticktock, ticktock…
4. the user finally types something, triggering the input event which calls the ‘update’ function
5. within ‘update’ we update the state (by constructing a new one)
6. we evaluate again the view function, passing it the new state constructed by the handler (same as step 1)
7. calling ‘patch’ again will repeat the above process again (same as step 2)

The steps above describe a cyclical process. By getting rid of the implementation details we can establish an abstract sequence of function calls.

‘user’ is an abstraction of user interactions. What we get is a circular sequence of function calls. Note that the ‘user’ function is asynchronous, otherwise w’ll have an infinite recursion.

Let’s turn the above process into real code

The ‘main’ function mirrors the cyclic process described above : given an initial state (our initial data), a DOM element and a top component (a pair view+update), ‘main’ evaluates the top component’s view function to construct a new virtual node from the current state, then patches the DOM with that virtual node.

Note the parameters passed to the ‘view’ function : first the current state and second the main event handler : a callback that handles events from the generated view. The handler is responsible for constructing a new state for the application and restarting the UI cycle with the new data (state + virtual node).

Construction of the new state is delegated to the top component’s ‘update’ function which is a simple (and pure) function : at each moment, given a current state and a current program input (event/action), it returns a new state for our application.

Note also that — beside the side effect in the patch method call — the main function has no mutated state.

The main function is somewhat similar to the ‘main’ event loop of low level GUI frameworks. The point here is to take back the control over the UI event dispatching process : in its actual state, the DOM API forces us into an Event Driven paradigm by adopting the Observer pattern. But we don't want to use the Observer pattern here as w’ll see in a moment.

Elm architecture

In an Elm-architecture based program, the basic building blocks are a set of modules, or, let’s say components. Each component has 2 basic functions : ‘update’ and ‘view’, along with a specific data contract : the ‘model’ type owned by the component and a set of actions that updates instances of that model.

1. ‘update’ is a pure function that takes 2 arguments : the current state which is an instance of the ‘model’ owned by the component and the current ‘action’ which describes the update operation that needs to take place. It returns a new ‘model’ instance.
2. ‘view’ takes also 2 inputs : the current ‘model’ instance and an event channel which can be any mechanism by which events are propagated, in our examples w’ll use a simple callback function (the ‘handler’ argument). The function then returns a new virtual node that will get applied to the real DOM.

As said above, Elm architecture walks away from the traditional Observer pattern that characterize typical event driven programs. Instead, the architecture favors a centralized model of dispatching (like in React/Flux), where any event : 1- bubbles up to the top component, 2- then tunnels down through a tree like hierarchy of components. During this phase, a component can choose to handle the action itself and/or forwards it to one or all of its children.

Another key property of the architecture is that the entire program state is held into one big data object. And each component in the tree is responsible for passing its children the part of state they own (w’ll see a concrete example of that).

In our demonstration w’ll use the same examples as in the Elm website as they perfectly illustrates the pattern.

Example 1 : a basic counter

Sources for this example are in the counter-1 branch

The counter component is defined in its own module ‘counter.js’

The counter component is defined by the following properties

1. Model : a simple ‘Number’
2. View : provides the user with 2 buttons in order to increment/decrement a counter , and a text that shows the current count.
3. Update : sensible to 2 actions : INC and DEC that increments or decrements the counter value.

The first thing to note is that the view/update are both pure functions, they have no dependency on any external environment besides their input. The counter component itself doesn’t hold any state or variable, it just describes how to construct a view from a given state, and how to update a given state with a given action. Thanks to its purity, the counter component can be easily plugged into any environment that is able to supply it with its dependencies : a state (number) and an action.

Second note, the ‘handler.bind(null, action)’ expression on the click event listener for each button. We are translating the raw user event (mouse click) into a meaningful action to our program (Increment or Decrement). Using ES6 symbols is better than raw strings (avoids collisions in action names), but w’ll see later a better solution provided by the so-called union types.

To see how our component can be tested; here is an example using the ‘tape’ testing library

You can run the test using ‘babel-node’ command

babel-node test/counterTest.js

Example 2: a pair of counters

Sources for this example are in the counter-2 branch

W’ll follow the same path as in Elm tutorial and augment slightly the counter example, w’ll now have 2 counters. Moreover, w’ll provide also a ‘reset’ button to reset both counters to ‘0’;

First, we have to modify our counter component to provide support for the reset operation. For that w’ll introduce a new function ‘init’ whose role is to construct a new fresh state (a count) for the counter.

‘init’ can be very useful in many situations. For example, initializing the state with data from the server or the local storage. It can also create a rich data model from a plain JavaScript object (e.g. enriching the plain object with some prototype properties and methods).

‘init’ is different in purpose from ‘update’ : while the latter derives a new state from a state and an action that updates that state, the former construct a new fresh state, optionally from some input (default value, server data …etc) , and totally ignores the previous state.

Second, w’ll have to add another component that will manage the 2 counters. We implement the code in a separate module ‘twoCounters.js’.

First we need to define our model and its associated set of actions

The model exports 2 properties: ‘first’ and ‘second’ to hold the states of the 2 counters. We define 3 actions on : the first reset both counters to ‘0’. W’ll see the use of the 2 others in a moment.

The component has also an ‘init’ method to create a state from scratch

The view function is responsible for rendering the 2 counters as well as providing the user with a button to reset them.

The thing to note is the 2 parameters passed to the child views:

1. Each view gets its relevant part (model.first/model.second) of the parent state.
2. The dynamic handler parameter that’s passed down to the children’s views : For example, an action triggered from the first child counter will be wrapped in an ‘UPDATE_FIRST’ action, so when the parent’s update function is invoked, w’ll be able to forward the original action (stored in the ‘data’ attribute) to the correct counter.

The rest of the code implements the update function and exports the component’s properties

The update function handles 3 actions:

1. the RESET action ‘init’ each counter to its default state.
2. the UPDATE_FIRST and UPDATE_SECOND are, as we just saw, wrappers around a counter action. The function forwards the wrapped action to the concerned child counter along with its specific state.

Note the use of {…model, prop: val }; we are using the ES7 object spread properties (like Object.assign) which always returns a new extended instance. We never modify the state passed in the argument but always returns a new state object with the relevant modifications. This is important to ensure the purity of the update function.

The rest of the code in ‘main’ simply invokes the top component with an initial state

The code of ‘twoCounters’ illustrates the typical pattern in an application with nested components :

1. The components of an application are organized in a tree like hierarchy.
2. the main function invokes the top component’s view function with the global application state as parameter (and also the main handler).
3. When rendering its view, each parent invokes the children’s view functions, passing them the relevant parts of the state.
4. views translates raw DOM/user events into actions meaningful to the application.
5. actions triggered from child components bubbles up through parents up to the top component. Unlike the DOM event bubbling, a parent can not handle the action in this phase. All it can do is adding information to the triggered action (see next).
6. During the bubbling phase, the parent view function may intercept actions from its children in order to augment them with the needed information; typically information needed to identify the originating child when dispatching actions to the children.
7. The action ends up in the main handler, which will triggers the dispatching phase by invoking the top component’s update function.
8. each parent’s update function is responsible of dispatching the action to its children’s update functions.Typically using the information added during the action bubbling phase.

Example 3 : A list of counters

Sources for this example are in the counter-3 branch

Following the same path of Elm tutorial, w’ll expand further our example to manage an arbitrary list of counters. W’ll also provide the user with buttons to add new counters as well as remove existing counters.

The code for the ‘counter’ component will remain the same. W’ll have also to define a component ‘counterList’ to manage the array of counters.

As usual, we start by defining the model, the set of associated actions

The component’s model defines 2 properties

1. a list of pairs (id, counter), the ‘id’ property plays the same role as the properties ‘first’ and ‘second’ in the previous example; it’ll allow the component to uniquely identify each child counter.
2. a ‘nextID’ property to maintain an auto-increment value, we will use this value to assign new IDs to each newly added counter.

Next we define the ‘init’ method which constructs a default state (note that ‘init’ can also take an optional parameter in case we have a saved state)

Then we define the view function

The main view provides 2 buttons to trigger the ‘ADD’ and ‘RESET’ actions. The rendering of each counter is delegated to the ‘counterItemView’ function

The function adds a remove button to the item view and annotates the actions triggered by the ‘counter’ view with the id of the originating counter.

Next the update function

The code follows the same pattern in the previous example, children’s actions are forwarded to the originating child using the id information stored in the bubble phase. This is handled by UPDATE case which delegates to the ‘updateCounter’ function

The other actions are handled by the component itself (you can find the whole source on the GitHub repository).

The same pattern above can be applied to any tree of components and to any at degree of nesting. In spite of some overhead code that bubbles up actions and tunnels down updates, we get an uniform architecture for the whole application.

Representing Actions with union types

In the previous examples we used JavaScript ES6 Symbols to represent action types. And inside the views, we created objects carrying the action type as a well as additional information (id, wrapped child action).

In a real scenario w’d have to move the logic of action creation to a separate factory function (something like Action Creators in React/Flux). In the remaining of this post i’ll present an alternative that’s more in spirit of FP : union types. They are a subset of Algebraic Data Types used in FP languages like Haskell, you can think of them like Enumerations but with more powerful capabilities.

Concretely, an union type will provides us with the following features at once

1. Define a type describing all possible values of our actions
2. For each possible value provide us with a factory function
3. Provide a control flow mechanism (called pattern matching) to handle all possible variants.

Unions types are not present natively in JavaScript, so w’ll use a library that emulates them. In our examples w’ll use union-type (github/union-type) a small and nice library written by the same author of snabbdom.

first we install the library by :

npm install --save union-type

Here is how we define the counter actions

‘Type’ is the only function exported by the library. We use it to define our union type ‘Action’ which contains the 2 possible actions.

the returned ‘Action’ type contains factory function to create all the possible actions

The view creates an Increment and a Decrement action.

The update function demonstrates the use of pattern matching against different variants

The ‘Action’ type exports a ‘case’ method which takes 2 arguments

• An object of the form (variant name, handler function).
• the value to match against

The case method then matches the provided actions against all specified cases and call the corresponding handler function. The return value is that returned by the matched handler.

Similarly, here is how ‘counterList’ actions are defined

‘Add’ and ‘Reset’ are empty actions (i.e. they don’t have any field), ‘Remove’ has one field (the child counter’s id). Finally the ‘Update’ action has 2 fields : the child’s id and the action triggered by that child.

We use, as usual, pattern matching in the update function

Note that the Remove and Update handlers both take parameters. If a case is matched successfully, the ‘case’ method will extract the fields from the case instance and passes them to the handler function.

So the typical pattern is :

• model the actions as an union type
• inside the view function, create actions using the factory functions provided by the union type (Action creation can also be delegated to a separate function if the logic of creation is more complex).
• inside the update function, use the ‘case’ method to match against the possible values of the union type.

TodoMVC example

In this repository (github/yelouafi/snabbdom-todomvc)you can find an implementation of the canonical todoMVC application using the concepts in this lesson. The application consists of 2 modules :

• ‘task.js’ which define a component that renders a single task as well as updating its state
• ‘todos.js’ which manages the task list as well as filtering and updating.

The filtering is implemented using a trivial router based on ‘hashchange’ events. To trap window events into the main UI cycle the example use the hook feature of snabbdom (embedded as a Snabbdom extension, see ‘app/js/snabbdom-modules/window-events.js’).

Conclusion

W’ve seen how to write a virtual DOM based applications using a small and standalone library. This can be helpful when we don’t want to be forced into the choices made by the React framework (esp. classes) or when we need a small sized JavaScript library.

The Elm architecture provides a simple pattern to write complex virtual DOM applications with all the benefits of pure functions. This gives a simple and regular structure to our code. Using regular patterns makes the application easier to maintain especially in teams with members changing frequently. A new member can quickly grasp the overall architecture of the code.

Being also implemented exclusively with pure functions, w’re sure that changing a component won’t cause undesirable side effects as long as the component code respects its contract.

EDITS :

• 31–07–2015 : Added an explicit ‘init’ function in place of the ‘INIT’ action (as in the Elm tutorial)

In the post From Callback to Future -> Functor -> Monad we clearly saw how Futures/Promises map to some well known constructs from FP and category theory.

First we saw that Futures are Functors, because they are able to take a function and apply it to their eventual outcome. Next we saw that they are also Monads because they are able to describe a computation as a sequence of steps through mapping a Monadic function (i.e. a function that returns itself a Monad (=Future)) then flattening the result to get the final result.

In this post w’ll meet another less famous construct from category theory. We will see what it represents and how it can be useful.

Another view of Parallelism

Remember the following use case from the first Post ?

suppose we are trying to fetch some content from some web URL that can be sometimes unavailable, upon a failure of our request, we’ll try an alternative URL, we can use ‘flatMapError’ to catch the first failure and return the alternative request

resultF = requestF('/url1').flatMapError( err => requestF('/url2') )

First we request the ‘main’ server and, upon failure, we request the alternative one. The example above can be rewritten with Promises

resultP = requestP(‘/url1’).catch( err => requestP(‘/url2’) )

Both examples illustrate well the sequential nature of Monads. Things has to be done one after one. But you may notice that there is a better way to solve the above use case. We don’t have to wait for the first request to fail in order to try the alternative url, we can send the 2 requests in parallel and just pick the first incoming response, the faster wins.

But how do we express this parallelism in Futures? we already saw that lifted functions which take multiple arguments can be used to describe parallel operations. But clearly this is not the kind of parallelism we want, so what’s the other kind ?

Lifting revisited

let’s quickly review the concept of lifting. We saw that the ‘lift’ function

1. takes a function that operates on non future values and
2. returns another function that applies the same transformation to future values.

// String -> Number (non lifted version)
function length(str) { 
  return str.length;
}

//Future String -> Future Number (lifted version)
lengthF = lift(length)

We also saw that a lifted function that takes multiple Futures has to wait for all of them to complete before applying the underlying function.

Suppose now we want to lift the following function

// [a] -> [a]
function multi_id(...args) {
  return args;
}

the function acts like an identity function but with multiple arguments, the return value is as an array of the passed inputs. Lifted to Futures, it’ll return a Future holding a list of all completion values from the input Futures.

[Future a] -> Future [a]
multi_idF = lift(multi_id)

For promises, the lifted multi-id function is called ‘Promise.all(iterable)’ which “returns a promise that resolves when all of the promises in the passed in ‘iterable’ argument have resolved”. As you can see, ‘Promise.all’ is just the special case of lifting the multi-Identity function.

Now, let’s imagine the above function in terms of the logical ‘and’ (‘&&’) operator, in a sens that the ‘completed’ property of the output future is a logical and (‘&&’) applied to the ‘completed’ property of all given futures

all(fut0, fut1, ..., futN) = fut0 && fut1 && ... && futN

Viewed from this perspective, what’s the meaning of the logical ‘or’ (‘||’) operation applied on futures?

In an ‘and’ operation, we examine all the terms of the expression so the evaluation wont stop until the last term. Similarly in futures, the evaluation wait for the last completed future and returns all the futures.

Let’s transpose the same reasoning to ‘or’. In an ‘or’ operation, we stop the evaluation when we encounter the first ‘true’ term. So similarly for futures, an ‘or’ operation stops on the first completed future.

Below how we may implement this operation for 2 futures

Future.prototype.or = function(fut2) { 
  const resultF = new Future();
  this.ready(tryComplete); 
  fut2.ready(tryComplete);
  return resultF;

  function tryComplete(fut) {
    if(!resultF.completed) 
      resultF.complete(val);
  }
}

As we are only interested in the winner future, we only complete the future if it has not been already completed.

Back to our previous example, we can now express our parallelism

resultF = requestF(‘/url1’).or( _ => requestF(‘/url2’) )

We can easily extend the ‘or’ function to multiples arguments using the ‘forEach’ method. In this case, w’ll be defining (something similar) another operation that also exists in promises, ‘Promise.race(iterable)’ which “returns a promise that resolves or rejects as soon as one of the promises in the iterable resolves or rejects”.

Actually this a not quite the same, Promise.race will return as soon as a promise in the iterable rejects while in our example we have to wait for the **latest promise that resolves successfully**.

Category Theory, again

I’ll now introduce our 3rd guest from the Category theory land. Besides been a Functor and a Monad, a Future is also a Monoid.

The most intuitive (although restrictive) way of thinking of Monoids is that they are additives. Take the analogy with the ‘or’ operation, you can start with an expression ‘a or b’, the terms of expressions are booleans, and so the result. Add another term to the expression ‘a or b or c’, the result is still a boolean. Repeat the process above with numbers and you’ll get the same result. Monoids are just simple as that (yet a very useful abstraction).

The fact that the ‘or’ operation on booleans returns always a boolean (just as the ‘+’ operation on numbers always returns a number) leads us to refine the definition : Monoids needs an *additive* operation that doesn’t fall outside; take for example the ‘+’ operator applied only to the range [1..12]. The range [1..12] along with the ‘+’ operation is not a Monoid because ‘11+10’ is not contained within the range. But the same range with the operation ‘(x+y) modulo 12’ (more accurately 13) forms a Monoid because whenever we jump by the given operation we don’t fall outside the range. This property is called closure. Of course Futures under the ‘race’/’or’ operation verify this as the result is always a Future.

A Monoid need also something else, called the identity element. Which is a value that is always neutral with respect to the additive operation. For the example of numbers under the ‘+’ operation, the identity element is zero ‘0’. With respect to the multiplication ‘x’ it is ‘1’. In the case of booleans under the ‘or’ operation it is the ‘false’ constant because ‘false or x’ will always yield ‘x’.

So what’s the identity element for Futures? The element has to be neutral with respect to the ‘or’/’race’ operation, i.e.

future.or(identF) == identF.or(future) == future

We need a future with the latest time of completion we can imagine, i.e. where ‘completion time == Infinity’. In other words, the identity element for Futures is the never ending future.

Future.never = new Future();

Additive yes, but in what order?

In fact, we have to add another requirement, the additive operation has to be associative. Meaning “the order in which the operations are performed does not matter as long as the sequence of the operands is not changed”(1). I m pretty sure you’ve already encountred associativity in your Math School,

a + (b + c) = (a + b) + c

For Futures it means

fut1 or (fut2 or fut3) = (fut1 or fut2) or fut3

It’s not difficult to verify that the above property holds for futures. If you want to go for a formal proof, you can use a pair ‘(value, time)’ to denote the meaning of futures; and define the ‘or’ operation as

(v1, t1) or (v2, t2) = (vk, tk) such as tk = min(t1, t2)

I will not list the detailed proof here (I’m not that strong on Math :) ). Just note that the associativity of futures under ‘or’ results from the associativity of numbers under the ‘min’ operation

min(t1, min(t2, t3)) == min(min(t1, t2), t3)

In terms of promises, it means the 3 expressions below are equivalent

Promise.race([p1, p2, p3])
Promise.race([p1, Promise.race([p2, p3]))
Promise.race([Promise.race([p1, p2]), p3]))

So to resume, a Monoid can be described with a pair (M, op) with the following properties.

• x ‘op’ y = z with the requirement that x, y, z are members of M (op is known as ‘append’ or ‘mappend’)
• Existence of an identity element ‘id’ such as ‘x op id = id op x = x’ for all x in M (sometimes called also ‘empty’ or ‘mempty’)
• Associativity. (x op y) op z = x op (y op z) for all x, y, z in M

Monoidal reduction

You should be already familiar with the ‘Array.reduce’ operation. The function reduces (or folds) an array into a single value, by successively applying a binary operation to all the elements of the array. Here is the well known example of summing numbers in an array using ‘0’ as a seed.

function sum(array) { 
  return array.reduce( (acc, n) => acc + n, 0)
}

we know that numbers form a Monoid under the ‘+’ operation. Doesn’t this give you some ideas?

If we abstract away the specific ‘number’ and ‘+’ and replace them with the more generic ‘Monoid’ and ‘append’ (additive operation) then we can normalize the ‘reduce’ operation to be working with any Monoid instance.

function sumM(array) {
  return array.reduce( (acc, m) => acc.append(m), identity)
}

Since Futures are Monoids themselves we can write the multi-argument Promise.race in terms of monoidal reduction

Future.or = function(…args) {
  return args.reduce( (acc, fut) => acc.or(fut), Future.never )
}

The ‘array.reduce’ method expects only a binary operation and optionally a seed value. But with Monoids we have additional information, we know that the binary operation is associative and that the identity element is neutral in respect to that operation.

The advantage of using Monoids is a more generic and predictable code. Using an explicit interface along with well defined properties conveys better meaning to the code, make the code more flexible and maintenable.

Uses of Monoids

Example: the Writer Monad

A typical example of Monoids is often illustrated with the Writer Monad. As for other Monads, it’s best understood through a use case : Suppose we have defined a pipeline of transformations by sequencing a set of functions, for example

function increment(num) { return num + 1;   }
function square   (num) { return num * num; }
function modulo10 (num) { return num % 10;  }

result = modulo10( square( increment(...) ) )

Now in order to see what’s going on inside this pipeline, we can run the example through a debugger, but sometimes this is not possible. In this case the usual solution is to log messages into the console or any other output.

The Writer Monad solves the problem by embedding the log messages directly into the intermediate and the final results. In the above example the type of the of the manipulated value is a Number. the Writer Monad will wrap the number value, say, into a pair (String, Number) where String is the type of the log messages and Number is the domain type manipulated by the functions.

function WriterStr(log, val) {
  this.log = log;
  this.val = val;
}

WriterStr.prototype.bind = function (fn) {
  var w = fn(this.val);
  return new WriterStr(this.log + ‘\n’ + w.log, w.val);
}

WriterStr.unit(val) {
  return new WriterStr(“”, val);
}

WriterStr requires the 2 operations requierd in Monads

• ‘unit’: simply wraps the value by adding an empty log message
• ‘bind’ : chains the successive computations by accumulating the log messages from each step into the running log.

In order to integrate our previous pipeline we have to change the normal functions into monadic ones. i.e. make them returning WriterStr instances instead of plain numbers

function increment(num) { 
 return new WriterStr(“adding 1 to “ + num, num + 1); 
}

function square(num) { 
 return new WriterStr(“squaring “ + num, num * num); 
}

function modulo10(num) {
 return new WriterStr(“applying modulo 10 to “ + num, num % 10); 
}

var result = increment(5).bind( val => 
               square(val).bind( val => 
                 modulo10(val)))

//result: 
{
  "log":"adding 1 to 5\nsquaring 6\napplying modulo 10 to 36",
  "val":6
}

The final result is a pair (log, val) where val is the final result of the computation while log, its side effect, is a description of all steps involved in the computation.

Now note how the Writer ‘unit’ lifts a normal value by joining an empty string to it, and how ‘bind’ applies the string concatenation on each step. As you may have already noted, String with the concatenation operation is a Monoid where the identity element is the empty string.

String.prototype.append = String.prototype.concat
String.identity = ""

So the Writer Monad can in fact work with any Monoid not just strings

function Writer(append, identity) {
  function W(log, val) {
    this.log = log;
    this.val = val;
  }
 
  W.unit = function(val) {
    return new W(identity, val);
  }
 
  W.prototype.bind = function(fn) {
    var w = fn(this.val);
    return new W(append.call(this.log, w.log), w.val);
  }
 
  return W;
}

var WriterList = Writer(Array.prototype.concat, []);

and now the monadic functions has to return log messages as arrays to match the expected type for WriterList

function increment(num) { 
  return new WriterList([“adding 1 to “+num], num + 1); 
}
...

Other examples

This link gives an interesting use of Monoids: exploit the generality of the Monoid interface and 2–3 finger trees to define a general purpose tree structure. The tree can then be reused to implement multiples data structures (lists, priority queues) by just modifying the underlying Monoid interface.

Conclusion

Monoids are simple structures that can be found easily everywhere : numbers, strings, lists and futures/promises are just some examples.

Their main advantage is to provide a more abstract way to factor operations that follow a pattern of appending starting from an ‘empty’ element. If you search through your source code there is a great chance you’ll find this pattern.

Below some links if you’re willing to learn more about Monoids (if you don’t mind reading Haskell code)

• Monoid chapter from Haskell wikibook
• Monoids and Finger Trees (example cited above)
• sigfpe article with many examples of Monoid uses
• Monoids definition in fantasy-land (a specification of common Alegbraic Structures in JavaScript)
• Brian Beckman: Don’t fear the Monad, talk about Monads that explains Monoids with an accessible language

fs.readFile(‘…’) // => a Future/Promise

Similarly, we w’d like to represent the meaning of functions like this

someEventSource.on('event', ...)  // => ?

The second code shares the asynchronous semantics of the first, hence the use of callbacks in both cases. But instead of a single future value, we are dealing here with multiples future values, more exactly a sequence of successive future values.

In this article, we will talk about an abstraction that captures the above meaning, the famous concept of Stream.

Look at the Wikipedia definition of streams

a sequence of data elements made available over time

A Stream can be viewed like a standard list. But like Promises/Futures, it enriches the meaning of its elements with the notion of time of occurrence.

Streams are becoming a central abstraction in JavaScript, especially on the server side. There are of course the builtin Node streams. But recent years saw the raise of another type of streams called Reactive Streams, they are based on the Reactive Programming paradigm and was made popular into JavaScript by libraries like Rx.js and Bacon.js (not to confound with the Reactive Streams initiative, which is another newcomer).

The basic idea is that you can represent different asynchronous data like events or HTTP responses by an unifying concept called observable collections. Then you can manipulate those collections by standard array operations like map, filter, reduce, forEach …etc.

This article is about an interesting experiment : we will use functional programming and algebraic data types to derive a pure functional definition of RP like streams. You’ll see that it’s quite simple to roll your own, beautiful, [Reactive] Stream implementation in a surprisingly simple and extensible way.

The key difference is that for our Streams, Promises are the unit of asynchrony. The other characteristic is that they will be much easier to implement using a pure FP style (if you are familiar with Haskell or similar, you’ll recognize it immediately).

Note: Full sources are in this Github repo.

On the meaning of Streams

Ok, how can functional thinking helps us to derive a nice and clean definition of streams ?

The first thing is to come up with the right representation for the stream type. By right i mean the one that can describe all possible variants of a stream. What can be a Stream ?

To represent our concept, w’ll use Algebraic Data Types (ADT) we saw in the previous post. We need to find all the possible variants of streams that capture our intent.

Since Streams are a super concept of lists let’s examine the standard lists variants. So first

Stream a = Empty

Naturally a stream can be empty, meaning with no occurrences on it.

Second the standard recursive definition

Stream a = Cons a (Stream a)

You can think of it in this sens : at the moment we have an occurrence (head), there could be more occurrences on the future or there could be nothing more (empty), in either case the following occurrences (tail) are also a Stream.

Stream a = Abort Object

w’d like to consider the case when a data stream, like an incoming HTTP message, interrupts due to some error, in which case we say the stream aborts with a given error.

Now time for our VIP guest

Stream a = Future (Promise (Stream a))

Literally, a Stream can be of a type ‘Future’, the type holds a value of type ‘Promise (Stream a)’ : i.e. a Promise that will resolve eventually to a Stream.

It looks like a strange variant, how can a stream be a future of itself ?

Imagine the following case : w’d like to get a sequence of mouse move events until a mouse press event occurs. If the user presses the mouse immediately, no mouse moves will occur so the stream will be empty. If the user moves the mouse some time before pressing it then the stream will have some occurrences, i.e. not empty.

You may see the problem : we don’t know yet if the stream is empty or not until we get the first mouse move or the first mouse press. Put another way, a Stream can be a future value that will resolve to another Stream representation (possibly more concrete Empty or Cons). It happens that we already have Promises for this just purpose.

Here is our complete definition

Stream a = Empty
    | Abort Object
    | Future (Promise (Stream a))
    | Cons a (Stream a)

Our representation now complete, we implement it using the the adt helper from the previous post

Before we move on how to program our Stream let’s first see some examples (all the factory functions below can be found on the Github sources).

Asynchronous Recursion

The nice thing about ADTs is that implementing functions that operates on them tends to be similar : pattern matching and recursion.Our Stream is nothing more than an old good recursive ADT. It means we can program it as we do with any other recursive data type like List.

As a first demonstration, let’s define the effectful (with side effects) ‘forEach’ method. W’d like to execute an action on all occurrences of a stream, another action when the stream aborts and finally one when the stream ends

The whole method is a long chained ternary expression that matches each possible variant on the stream type. We can write such chained code because the conditional operator (?:) is associative to the right.

The big news: all stream operations we will define in this article will be nothing more than conditional expressions (yes i’m serious, all operations). FP developers will recognize that this construct maps directly to pattern matching in FP languages.

First, let’s also define a helper debug method

Like arrays/lists, Stream is also a Functor, the ‘map’ operation, applied on a stream, return a stream of the successive results transformed from the successive occurrences on the input stream

Note how in the case of a promised stream, w’re doing a sort of asynchronous recursion because the promise callback will execute asynchronously in a microtask queue. It means we get the benefits of a clean and concise functional/recursive code without fear of stack overflow problems.

The error handling equivalent of map, called ‘mapError’ extends the lifetime of an aborted stream by another stream

From Haskell to JavaScript (in no time)

If you are a Haskeller (if you are not it’s OK, you can follow reading) then you have certainly recognized the similarities with the definitions of functions on standard lists. The nice thing above is that you can easily adapt most of the concise FP definitions to define the same functions on streams.

For example take the Haskell definition of filter which returns the list of elements that satisfy a given predicate (if you don’t know Haskell JavaScript code will follow immediately)

And here is the equivalent definition on Streams: instead of filtering elements of a list, we filter incoming occurrences as they happen

The only difference is the Abort and Future case, which are trivially defined.

A little bit more elaborated example is the ‘span’ function which takes 2 inputs: a predicate and a list, and returns a tuple of :

1- first elements that satisfy the predicate and
2- the remainder of the list

Haskell code

Applied to streams, the function return a pair of streams: the first yields the first occurrences that satisfies the predicate and the second yields the remainder of the stream. The JavaScript code is derived straight from the Haskell equivalent

Taking a more elaborated example, the ‘groupBy’ function, which groups occurrences into nested sublists/substreams given a predicate, is defined in terms of span

Then the equality grouping function is trivially derived

Using the same declarative approach, we can define all imaginable list operations on streams. If you know the Haskell definition (or any equivalent FP definition), then you know the Stream definition. No hard to follow async code, no event listeners, no error prone async state manipulation just pure FP code and promises.

Here are some other functions that are defined in the source code. You may try to define them by youreself before looking at the Sources, just think about the meaning of the resulting streamsfor each case and the answer comes quite naturally

• take(n) takes the first n occurrences from the stream
• skip(n) skips the first n occurrences on the stream
• takeWhile(predicate) takes the longest prefix that satisfy the predicate.
• skipWhile(predicate) returns the suffix remaining after takeWhile
• break(predicate) like span but the first stream is the longest prefix of occurrences that do not satisfy predicate

Streams and Promises interplay

Our ADT Streams play nicely with Promises in various ways. In this section w’ll see some useful operations that combine the 2 concepts.

1- Streams reduce to Promises

As a first example, let’s take the well known ‘reduce’ method (known as ‘foldl ’in Haskell). When applied to arrays, the method yields a single value representing the result of the accumulation, like the sum of an array of numbers:

[1,2,3].reduce( (prev, cur) => prev + cur ) // => 6

Now applied to streams (for example the sum of a stream of numbers), the final result is a future value because w’d have to wait for all future occurrences on the stream. So, the meaning of ‘Stream.reduce(…)’ is effectively a promise that will resolve to the final result of the accumulation or will be rejected in case of the stream aborted.

I find this meaning more logical than the one found in libraries like Rx or Bacon where the result of the accumulation is a single occurrence stream. It feels to me as if normal functions returned a single element array [x] instead of simply returning x itself. As a rule of thumb, we can say that Streams reduce to Promises

Higher abstract operations can be defined on top of ‘reduce’.

‘length’ which yields the number of occurrences in a stream

‘all’ Checks if all occurrences satisfy a predicate

2- Streams reduce as soon as possible

We may be tempted, as we did for ‘all’, to define the peer function ‘any’ — which yields true if any occurrence satisfies the predicate — in terms of reduce like this

this.reduce( (prev, cur) => prev || !!pred(cur), false )

While the above code will yield the correct value. We must be aware of the meaning of time, because ‘reduce’ will wait for all occurrences on the stream before completing the promise. But we know that the result of an ‘or’ operation can be deduced as soon as we get a ‘true’ operand

false || /* stop here */true || false || true

Similarly on streams, we must yield a result on the first occurrence that satisfy the predicate

Hence the 2nd rule of thumb : Streams reduce as soon as possible.

3- *Until

A key interplay between Streams and Promises is the *until operators which act on a Stream based on the completion time of a Promise.

For example, the ‘takeUntil(promise)’ will take occurrences on the stream until a given promise is resolved, or will abort the result stream if the promise is rejected.

Here is our first attempt

Let’s review the code, the first variant is trivial. For the 2nd variant, if the stream has already a head then yield the head and forward the until request to the tail (this way we yield all past occurrences).

The third variant deserves some discussion: Promise.race(arr) will return a promise that will complete as soon as one of the input promises complete, so if the ‘untilP’ promise completes first we stop taking by yielding an empty stream, and if the future stream complete first we continue taking.

There is a subtle performance problem above, if ‘Promise.race’ completes with an empty Stream (‘untilP’ wins), the second promise ‘this.promise.then( s => s.takeUntil(promise), …)’ is still active. ‘Promise.race’ just returns the winner promise, it does not stop the other competing promises from continuing (Promise cancellation is an under-discussion topic and no standard way has emerged yet).

If we can’t cancel the fulfillment of the future stream itself, we can at least stop the fulfillment propagation and thus prevent the wasetful execution of the chained blocks (like ‘s => s.takeUntil(promise)’ above). And w’d like to keep our pure FP approach so w’ll have to avoid any state manipulation.

A simple and still pure FP solution is lazy evaluation, instead of the competing promises resolving themselves to the desired value, w’ll make them resolve to a lazy value and delay the evaluation until we get the winning promise. So the code will have something like

You can convert a promise callback returning a normal value to another returning a lazy one by simply inserting an ‘() =>’ in front of the callback body, so a callback with the form ‘x => y’ will become ‘x => () => y’.

So now if the ‘untilP’ promise resolves first, no further execution will happen on the loser’s chained blocks because evaluation will be postponed until we know which way to go.

Similarly to takeUnil, can you derive skipUntil which skips occurrences until a promise complete?

4- Asynchronous mapping (and filtering, taking…)

Previously, we have defined the ‘map’ operation as taking a function of type ‘a -> b’ which results on a ‘Stream b’ whose occurrences are values transformed from the input ‘Stream a’. The direct consequence of the type signature ‘a -> b’ is that the resulting occurrences will happen as soon as the sources occurrences occur. Put another way, w’are only acting on the value meaning of occurrences not their time meaning.

What if the mapping function can’t return a value immediately ? Imagine for example that we have a stream of button clicks that is mapped to a stream of ajax requests.

// result : Stream (Promise aResponseType)
result = Stream.fromDomEvent(fetchButton, 'click')
               .map( e => $.ajax(...) )

The logical meaning of the above code is that we want to map button clicks to the future responses from the ‘$.ajax(…)’ calls and not to the ajax promises themselves.

We can define a an asynchronous version of ‘map’ — something like ‘asyncMap’ — to handle this case. Another solution is to extend the codomain (i.e. the range of the permissible outputs) of the mapping function to accept promises beside normal values, so the type signature will pass from ‘a -> b’ to ‘a -> b | Promise b’ so the mapping can now return either present or future values. This way, we can have a single function that handles both the sync and async cases.

the trick is in ‘Promise.resolve( f(this.head) )’. Promise.resolve() can take both a normal value as well as another promise. In which case it’ll follow the passed in promise and wait for its completion.

The above reasoning is not restricted to ‘map’, it can be extended to any stream function that takes a callback (like filter, span, takeWhile, …etc).

Taking the filter example, we can make the predicate asynchronous, thus extending the range of its use cases (if the filtering decision depends for example on some asynchronous IO operation)

As said above, the same pattern can be extended to all other stream operations, opening the door to a full range of new use cases. And all this without any state manipulation neither any buffering mechanism. Just simple conditional expressions.

Combining multiples Streams

In imperative code, defining operations on multiples streams is a non trivial task. Because elements on different streams can occur in different moments and at different rates, we have to solve synchronization problems between different sources (ever tried to drive a state machine whose transitions depend on multiple time-separated inputs?).

In the case of ADT Streams the only additional complication you get is that you’ll have to pattern-match against combined cases. Usually, combined operations involves 2 streams which lead to pattern matching -at most-on 4 x 4 cases, but, as w’ll see, most cases reduce to the same answer and you’ll get generally less variants to check.

Take for example the ‘concat’ operation, which like in arrays, joins 2 streams in a sequential manner : it means the concatenation will first yield all occurrences of the first stream then passes to the 2nd.

Because all decisions depend only on the first stream, we don’t have to pattern-match on all the possible combinations but just on the first one. So the 4x4 cases reduces only to 4 cases.

Note the concatenation of 2 streams delays the occurrences from the second stream even if they occur before or interleaved withe the first one. It’s as if they were buffered and released after the end of the first stream. Even worse, they will never occur if the first stream is aborted.

If we want to suppress the delay effect and yields occurrences from both streams at their time, then what we need is a ‘merge’ operation that takes into account the position in time of each occurrence

On merging 2 streams, past values (‘Cons’ case) always takes precedence (with a bias toward the 1st stream). But if the 2 streams are both promises we run a race between the two and the winner will take precedence. As with the *until functions, we use lazy values to prevent unnecessary and wasteful merging on the loser promise.

Another famous multi-list operation is ‘zip’, which pairs elements from 2 lists based on their positions ([1,2,3] zip [‘a’, ‘b’] => [ [1, ‘a’], [2, ‘b’] ]). On streams, it means each occurrence on the 2 input streams has to wait for its peer to happen before yielding the while pair :

Monadic Streams

Until now we have considered occurrences of a Stream as normal JavaScript values. What if the incoming occurrences are Streams by themselves ? i.e. what is the meaning of a Stream of Streams? or put another way: How do we flatten a 2-layered stream ?

There is no single answer to the above question as we can combine nested streams in different ways.

We can merge the nested streams: we yield occurrences from the 1st incoming stream (that comes with the 1st occurrence), then when the 2nd stream appears we merge it with 1st stream and so on. For example, imagine we have a chat room with new users coming over time, and each user can type multiple messages in the chat room. The chat room can be viewed as a stream of incoming users, and each incoming user himself can be viewed as a stream of incoming messages, so we end up with a stream whose occurrences (users) are themselves streams(messages from each user). The log of all messages from all users, present and futures, is the merge of messages from all users.

Another way to flatten a 2-layered Stream is to concatenate the nested streams side by side, i.e. we take all occurrences from the 1st incoming stream, then we take the occurrences from the 2nd incoming stream …etc. As a practical example, imagine now we’re sending an ajax request each time the user hits a button, and suppose we can get, for each request, a stream representing the response body, so we end up with a stream whose occurrences (ajax responses) are themselves streams (body of each response). The log of all bodies, printed one after another, is the concatenation of bodies from all ajax responses.

In fact, if you think a little about it, flattening a stream is quite similar to the ‘reduce’ operation, we combine nested occurrences by a binary function as they appear on the stream. So we can define a generic flattening version

Then we can define specialized versions in terms of the generic flatten. For example the flatten-by-merge operation can be defined like this

Similarly, the flatten-by-concat is

And so you can easily flatten by any binary operation.

The meaning of the monadic operation ‘flatMap’ (or bind, or chain) is less obvious : mapping a stream with a function that transforms each occurrence on the source stream into a child stream, then flatten all generated streams.

For example, the meaning of ‘mergeMap’ is mapping with a function that transforms occurrences into sub-streams then merge all generated streams

Similarly, ‘concatMap’ concatenates generated sub-streams

Throttling and Debouncing

I did not want to conclude before testing how ADT streams can handle some advanced operations found on RP Stream libraries, i’ll take the famous examples of throttling and debouncing.

You may be aware of the terms from libraries like JQuery or Underscore. There are also present with multiple variants on most RP libraries.

The simplest of both is throttling; a simple illustration is when handling mouse move events, instead of running the handler on each mouse event, you may prefer to skip some move events for performance reason. For example you may choose to handle a single mouse move event once each 50 milliseconds.

If you look to a conventional/imperative implementation of throttling (for example form Underscore sources), you’ll see a bunch of state variables and timeouts operations along with the required synchronization code. As i intend to keep my promise on the beginning of this article, the actual Stream definition will be no more than a single conditional expression

Let’s review the code, throttle takes a generator function ‘() => Promise’, w’ll use it to generate a new event whenever we start a new throttling iteration. This way we can throttle by any event not just timeouts.

As soon as we get an input, we yield it then skip all subsequent inputs until the throttling event terminates (‘skipUntil’ will skip occurrences from the tail until the passed in promise completes).

The case of debouncing is a little bit complicated. Basically, debouncing is a technique that can be used to optimize handling of events that occurs at a rapid rate.

For example, if you’re handling the window ‘resize’ event in the browser, you’ll get all ‘resize’ events as the user keeps dragging the mouse. If you’re doing some heavy DOM manipulations inside your handler you may prefer to let the user finish resizing and react directly to the final result (window size). We can suppose that if a period of 500ms passed without receiving any resize event, then the user may have finished dragging and then we handle the last event occurred before this quiet period. We say that w’ve debounced the resize event by a delay of 500ms.

Implementing debouncing can be a bit tricky using imperative stateful code, w’ve get to run timeouts on each event occurrence and do some state housekeeping in order to keep track of the delay between successive occurrences.

As usual, in our ADT streams, this is just another conditional expression

‘debounce’ takes also a generator function to make new debouncing events. We use an accumulating input ‘last’ to mark if w’re inside an ongoing debounce operation (ie w’ve a last input to be checked). The ‘undef’ special value let us know if there were any precedent input (we can’t use null or undefined because streams can yield any JavaScript value).

As soon as w’ve got an input (the Cons case) we start debouncing using its value. And if the tail is a future, we run a race between a new generated event (call to ‘event()’ inside Promise.race) and the tail itself, if the debouncing event wins, it means no occurrences happened in the stream during this period so we include the last input and start a new debouncing iteration. if instead, the future tail wins, then there were occurrence(s) before the debouncing event, so the last input is not (yet) included and we continue debouncing with the completed tail.

Note we do not discard yet the last input because w’d have to know the type of the completed tail : if it is Empty or Abort then we include the last input (because w’re sure there will be no more occurrences). If it is a Cons, then we effectively discard it and restart debouncing with the new head.

As a said, that’s a little more complicated but even, w’ve managed to do it with a simple (a little longer) conditional expression, meaning no state and no imperative code.

Conclusion

You can find the complete sources at Github along with usage instructions.

Note it’s more about experimenting a concept than releasing a new library. The main intention of the Github Sources is to provide a starting point for anyone willing to go further with this. Hopefully, there will be people providing some useful feedback on the concept and its real world feasibility. What follows are some general thoughts on the practical issues

Testing vs proof

I putted some unit tests in the sources (obviously this is far from enough). For a lot of reasons, it’s a not a good idea to test this kind of code in a real machine so i used the concept of a Virtual Scheduler borrowed from the RX library. The scheduler can generate virtual and precise timeouts events so we can test all Stream operations in a precise and deterministic environment.

But i’m still thinking that, speaking of unit tests, it’s never enough. We feed our functions with some inputs and make assertions on the output. Unit testing, while important, is just a poor, and probabilistic way of proof.

While we can’t go for a formal proof method, we can do better than standard unit tests: i’m thinking of something like Quickcheck in Haskell, w’re still in the testing land, but now instead of testing a few inputs we test for invariants, i.e. general properties that our function should satisfy. This is best motivated by this quote from the above link

(…) you might be able to guess some more interesting cases to check for “edge” conditions (…). But another issue is figuring out what the right answers should be for such cases. This is not too difficult for a simple function, but can be much harder for more complex problems — — even for experienced programmers.

So the idea is to think of properties a function should verify for each possible input, write the property assertion and the testing framework will try to fail the assertion by checking it against a high number of generated inputs. A simple example is of the ‘reverse’ function on lists : logically, reversing an already reversed list shoud yield the original list

reverse( reverse(list) ) == list

Obviously this is more reliable than testing against 2 or 3 sample inputs.

I think there exist some Quickcheck based libraries in JavaScript so the idea should be feasible. The trick is — of course — to come out with pertinent assertions for each stream function.

Resource consumption

In reality, i’m less worried about the correctness of the definitions (they are derived from Haskell after all) than i’m about resources, time and memory.

For the time question, i think the key factor is the promise case : promises execute their then blocks asynchronously in a microtask queue, this prevents stack issues but can introduce some latency issues, especially when we’re dealing with occurrences happening at an extremely rapid rate. For most use cases, i think this is less from an issue, because in a microtask queue (a true and not a timeout emulator) w’re still far from the milliseconds magnitude but maybe i’m missing something here.

For the memory issue, ADT Streams in themselves are very lightweight objects (one or 2 variables), and the question translates directly to a more general Garbage Collector/Object retention problem. If you hold a long living reference to a huge Stream (like a global variable in the browser) then the entire Stream chain will be kept in memory. So we’ve to avoid global or other kind of long living references (like module properties).

IMO, the real cool thing about ADT Streams is that they open a full, and infinite, range of possibilities on stream programmability.

The ADT concept simplifies a lot the programming model, and the Promise variant makes handling asynchronous cases a lot more simple. Instead of providing a big monolithic library with a huge list of operations, we can instead provide just a tiny core with a small set of operations and anyone can define the needed operations using a clean and beautiful FP style.

At the heart of functional thinking is to ask about the meaning of things. In the case of functions, it’s reasoning about their return values. But, that’s actually insufficient, as important as is, to give the full answer.

Basically, a function is a relation between a set of inputs -a domain- and a set of outputs -a codomain- (along with a fundamental constraint: the same inputs always produces the same outputs). So we have also to ask, in addition of the return value, about the permissible inputs and outputs of a function. In the world of programming, that leads us straight to reasoning about types.

It maybe be surprising to talk about types in a dynamic language like JavaScript, without static/explicit typing. The truth is, consciously or subconsciously, you are always reasoning with your types, JavaScript still has to check your types, although this is delayed until execution (late binding). And you still has to think of what operations you can invoke on this or that variable.

In this post i’ll (try to) show you that type thinking is more than tagging a variable with a data type to get those precious compiler messages, and more importantly, you don’t have to work with a statically typed language in order to reason about your program types (just as you don’t need to work in a purely functional language in order to do functional thinking).

The post use a Haskell-like syntax to denote functions type signature :

=> ‘f : a -> b’ means f is a function that takes an argument of type a and returns a result of type b. a and b are considered generic types
=> Multiple arguments are enclosed in parentheses : ‘f : (a, b) -> b’
=> ‘a | b’ denotes an union type either of type ‘a’ or type ‘b’.
=> ‘Future a’ means a ‘Future’ parametrized with a generic type ‘a’

Error handling revisited

You may recall in the post about Futures how we solved the error handling problem: we introduced the concept of failure to our Future type, thus derived the new operations for error handling: ‘fmapError’ and ‘flatMapError’.

The truth is that i’m not fully convinced with the above solution (i’m pretty sure any FP guy would think the same thing).

First with more concepts comes more complication, we’d have to deal with more cases both in our semantic model and our implementation. IMO, a ‘Future’ has to deal only with one thing, describing values that will occur in the future and nothing more. Any meaning that may be given to this values must be defined in their proper computational context. FP is all about expressing complex things out from composing simpler things (while in contrast, imperative programming is often about expressing simple things using more complex things under the hood).

And after all, errors are not necessarily a proper concept of Futures but are relevant to any function, be it synchronous or asynchronous.

Second reason is practical, actually i’d rather classify errors into 2 kinds:

1. Semantic errors are integral part of the problem space (like converting a string to a number that may fail if the string is not a valid numeric representation)
2. Runtime errors are errors that typically arise from bugs in the code (type error, undefined function name, …)

Observe this code from the definition of ‘fmap’

Future.prototype.fmap = function(fn) {
    // ...             
    try { 
        fut.complete( fn(val) );    
    }
    catch(err) { 
        fut.fail(err);              
    }                 

}

The ad-hoc catch statement inside ‘fmap’ will catch both error types — semantic and bugs — and fail the future with whatever error is caught. While i find it natural to fail the Future with an expected erroneous result of a function call, i don’t think it’s same for bugs or runtime errors.

Third and more fundamentally, the solution isn’t really in the spirit of functional thinking, which is all about defining functions.

A try/catch block makes sens only if we are thinking in terms of executable statements, but in denotational thinking there is not such a meaning to the above code. Denotational world is made of relations between things without reference to any execution model.

So how do we deal with errors in functional terms? it’s quite simple, and you may already know it, just consider the simple code below, what’s the type of the following ‘toNumber’ function

const toNumber = str => Number(str)

Before you answer, consider what happens if you run this expression?

toNumber("not a number") // => NaN

Executing the equivalent code in a language like Java will immediately throw a ‘ NumberFormatException’ at your face but above instead it returns a curious ‘NaN’ type. Believe it or not, but the JavaScript solution is more or less similar to what we may do in a purely functional language.

In the Java case, we say that ‘toNumber’ is a partial function. Indeed, it can’t give an answer to all inputs. So the function just raises an exception. Put another way, the function isn’t defined over the full domain of strings but only those representing valid number representations.

What JavaScript does actually is simulating a common pattern in FP : extending the codomain of the function— the set of its permissible outputs — so the function can actually return either a valid number or the curious ‘NaN’ value.

Let’s apply the same trick to our error handling problem: If a function may return some error, we just extend it’s codomain to permit errors as return values; So we also define a new type

Result a = Success a  | Error Object

The meaning of above is: ‘Result’ defines, for each underlying type ‘a’, a new type that is either a ‘Success’ holding a value of the same type ‘a’ or an ‘Error’ holding an error object. Both sides of the definition are called variants of the Result type. Think of ‘Success’ and ‘Error’ as specializations of the more abstract ‘Result’ giving us more information about a given ‘Result’ value.

You can view ‘Result’ as another box type, just like ‘Array’ or ‘Future’ defined in the previous post. And by box, i mean it gives a context to an underlying value. If you take only a value of type ‘a’, its meaning is nothing more than that given by its type. Now, put it inside a ‘Success’ box, and the meaning is enriched, it now denotes a successful result of a computation.

This makes a subtle and important difference, you can move a ‘Result’ all around within your code without any loss of its initial context. Contrast this with inline error handling when you have to deal with the error as soon as it occurs, otherwise you lose its context (a typical problem in node async functions, where errors can get lost if you forget to handle them in place).

‘Result’ is an example of what we call Algebraic Data Types or just ADTs, which are basically types formed by composing other types. ‘Success’ and ‘Error’ are also called constructors because they give us concrete instances of the ‘Result’ type (actually they are more factory functions than traditional JavaScript constructors).

A possible implementation of ‘Result’ in JavaScript is given below:

// private constructor
function Result(isError, data) {
    this.isError = isError;
    this.data = data;
}

// public factories
Result.Success = val => new Result(false, val);
Result.Error = err => new Result(true, err);

Here is an example of usage with a Future and an async node function

// readFileF : (String, Object) -> Future (Result String)
function readFileF(file, options) {
    var f = new Future();
    fs.readFile(file, options, (err, data) => { 
        const res = err ? Result.Error(err) : Result.Success(data);
        f.complete(res);
    });
    return f;
}

Since ‘readFile’ may fail, we wrap its result in a Result type to denote its outcome (Success or Error).

In final, we obtain a value of type ‘Future (Result String)’, a Future holding the eventual Result of the file read operation.

As with Future, Result type is a Functor instance (let’s call its mapping method ‘map’ as in Arrays):

// map : (Result a, a -> b) -> Result b
Result.prototype.map = function(f) {
    return this.isError ? this : Result.Success( f(this.data) );
}

above, ‘map’ applies the function only to successful values and forward errors.

The peer function to handle errors do the inverse, catching and transforming errors while forwarding successful results:

// mapError : (Result a, a -> b) -> Result b
Result.prototype.mapError = function(f) {
    return this.isError ? Result.Success( f(this.data) ) : this;
}

Result is also a Monad, we define the sequencing operation ‘chain’ (which is more sounding than flatMap)

// chain: (Result a, a -> Result b) -> Result b
Result.prototype.chain = function(f) {
    return this.isError ? this : f(this.data);
}

Like ‘map’, ‘chain’ captures and transforms valid results while forwarding errors.

And the error handling equivalent which do the inverse

// chainError : (Result a, a -> Result b) -> Result b
Result.prototype.chainError = function(f) {
    return this.isError ? f(this.data) : this;
}

In the same spirit of the first post, we lift normal functions to act on values of type Result.

// lift1 : (a -> b) -> (Result a -> Result b)
Result.lift1 = f => (res => res.map(f))

// error equivalent
Result.liftError = f => ( res => res.mapError(f) )

For lifting functions with more than 1 argument, since Result is a Monad instance, we can apply the same trick used with Future: using the sequencing operation (chain) to collect arguments, for example here is ‘lift2’ which lifts 2-ary functions

// lift2 : ( (a, b) -> c ) -> ( (Result a, Result b) -> Result c )
Result.lift2 = f => ((res1, res2) =>
    res1.chain( v1 =>
        res2.chain( v2 => 
            Result.Success(v1, v2)
        )
    ))

Or we can cheat by looking directly inside the Result box

// lift : ( (a, b, ...) -> x ) -> ( (Result a, Result b, ...) -> Result x ) 
Result.lift = function(f) {
    return (...args) => {
        for(var i = 0, len = args.length; i < len; i++) {
            var ai = args[i];
            if(ai.isError) return ai;
        }
        return Result.Success( f.apply(this, args) )
    }
}

‘lift’ proceeds only if all its arguments are successful otherwise it returns the first error encountered.

Here is an example of counting the length of a file content.

// String -> Future (Result Number)
readFileF('test.txt').map( s => s.length );

We can even implement the error handling operations as methods of Future

// this : Future (Result a)
// f    : Result a -> Result b
Future.prototype.fmap = function(f) {   
    var fut = new Future();
    this.ready( res => fut.complete(f(res)) );    
    return fut;
}       

// f : a -> b
// mapSuccess, mapError: (Future(Result a), f) -> Future(Result b)
Future.prototype.mapSuccess = function(f) {
    return this.fmap( Result.lift(f) );
}

Future.prototype.mapError = function(f) {
    return this.fmap( Result.liftError(f) );
}

// fut: Future (Result Number)
fut = readFileF('invalid path')
        .mapSuccess( s => s.length )
        .mapError( () => -1 )

To catch errors in monadic computations

// f : a -> Future (Result b)
// flatMapSuccess : (Future (Result a), f) -> Future (Result b)
Future.prototype.flatMapSuccess = function(f) {
    return this.flatMap( 
      res => res.isError ? Future.unit(res) : f(res.data)
    )
};

Future.prototype.flatMapError = function(f) {
    return this.flatMap( 
      res => res.isError ? f(res.data) : Future.unit(res)
    );
}; 

// requestF : String -> Future (Result String)
resultF = requestF('/url1')
           .flatMapError( res => requestF('/url2') )

Recursive ADTs

The type definition of Result is quite simple: a disjoint union between 2 other types. But the real power of ADTs lies elsewhere.

Consider the definition below, ubiquitous in functional programming literature, and quite similar to a linked list definition as found in imperative languages

List a = Empty | Cons a (List a)

The above annotation can be read as:

• ‘List’ is a type that defines, for each underlying type ‘a’, a new type which can be either:
• an ‘Empty’ list, or
• a ‘Cons’ of 2 values :
• the first, its head, is of the underlying type ‘a’ and the second, its ‘tail’, is another List of ‘a’.

‘List’ is a typical example of a recursive type, i.e. a type that may be defined in terms of itself.

The form ‘List a = Empty | Cons a (List a)’ — borrowed from Haskell syntax — looks a clean and concise way to express things. Unfortunately, JavaScript doesn’t have syntax support for ADTs. We can still implement them using functions and objects, like we did early, but i propose another solution: a helper function that can make an ADT with a more concise syntax using ES6 object literals

function List() {}
adt(List, {
  Empty : new List(), // a singleton
  Cons  : (head, tail) => ({head, tail}) // a factory function
});

Not as concise as the Haskell definition but still better than verbose object creations (If you are interested here is the source code of ‘adt’).

An interesting property of types like List is that implementing operations on them follows naturally their recursive nature, take a look at the below definitions of some familiar list operations:

The well known ‘map’ function to transform list elements through a mapping function ‘f’

// map : (a -> b, List a) -> List b
function map(f, list) {         
  return list.isEmpty ? List.Empty
                      : List.Cons(f(list.head), map(f, list.tail))
}

The ‘filter’ function can be defined the same way

// aBoolean : Object (JavaScript view of truth)
// filter : (a -> aBoolean, List a) -> List a
function filter(f, list) {
  return list.isEmpty ? 
                 List.Empty
               : (f(list.head) ?
                    List.Cons(list.head, filter(f, list.tail))
                  : filter(f));             
}

‘take’ which takes the first ‘n’ items from the beginning of the list

// take : (Number, List a) -> List a
function take(n, list) {
        return this.isEmpty || n < 1 ? 
            List.Empty
          : List.Cons(list.head, take(n-1, list.tail)) 
}

The usage of recursion in all the definitions above is a fundamental pattern in recursive types. It is a typical case of pattern matching because we are matching each variant in the type in order to decide what to do.

Infinity via Laziness

Another useful property of recursive types is the ability to define infinite data structures. Consider for example this function which builds an infinite list from a single value

// repeat : a -> List a
repeat = val => List.Cons( val, repeat(val) )

// takes 5 'Hi's
take(5, repeat('Hi'))

If you run this code in JavaScript, you’ll soon get a “Maximum call stack size exceeded” error.

This simple example illustrates the most fundamental difference between (purely) functional and imperative languages.

In order to evaluate the ‘take(5, repeat(‘Hi’))’ call, JavaScript starts from inside; as detailed in the sequence below

1. evaluate take(5, repeat(‘Hi’)) leads to evaluating the 2 given arguments
2. evaluate the 1st argument 5
3. evaluate repeat(‘Hi’) which expands to List.Cons( ‘Hi’, repeat(‘Hi’) )
4. again evaluate the 2 arguments of List.Cons, starting with ‘Hi’
5. then evaluate repeat(‘Hi’) which brings us back to step 3

And so on, since there is no terminating condition to break the recursive calls the program will, theoretically, never terminates.

In a typical FP language like Haskell the evaluation will starts from outside. Evaluation of ‘take(5, repeat(‘Hi’))’ will not evaluate the given arguments immediately, instead the runtime expands the body of ‘take’. In FP jargon, we say that expression ‘take(5, repeat(‘Hi’))’ is substituted with the equivalent definition.

In the example above, we can trace the evaluation by respectively subsituing terms in the experssion by their corresponding definitions. Here is an illustration of the first steps

1 => take(5, repeat('Hi'))

2 => *repeat('Hi')*.isEmpty || 5 < 1 ? 
            List.Empty
          : List.Cons(*repeat('Hi')*.head, 
                      take(5-1, *repeat('Hi')*.tail))

// expands *repeat('Hi')*
3 => List.Cons('Hi', repeat('Hi')).isEmpty || 5 < 1 ?
         List.Empty
       : List.Cons(List.Cons('Hi', repeat('Hi')).head,
                   take(5-1, List.Cons('Hi', repeat('Hi')).tail)) 

4 => List.Cons(List.Cons('Hi', repeat('Hi')).head, 
               take(5-1, List.Cons('Hi', repeat('Hi')).tail))

5 => List.Cons('Hi', take(4, repeat('Hi')))

6 => List.Cons('Hi', take(4, **same as in step 2**))

Note how the evaluation of ‘repeat(‘Hi’)’ is delayed until the step 3, where we look into the list in order to decide if it’s empty or not. Also note how the expansion from the step 3 gives us only ‘List.Cons(‘Hi’, repeat(‘Hi’))’ instead of the entire list. We don’t actually need the full/infinte list in order to evaluate if the list is empty or not, the returned ‘List.Cons(‘Hi’, …)’ expression is sufficient by itself.

So completing the sequence of evaluations above will expand repeat(‘Hi’) only when necessary, as we are advancing in our process. Once we reach the step where ‘n == 0’ , the ‘take’ expression will yield the ‘List.Empty’ result so no further evaluation will take place.

We say pure FP languages are lazy. They defer evaluation of expressions until necessary. In the example above, the need to evaluate the second argument will not occur until the take function start looking inside the given list to make a decision (if empty stop taking, if not continue taking). “start looking inside” in FP jargon is called pattern matching because we are matching the List ADT with each of its variants. This is the reason we say that in FP, evaluation is essentially driven by pattern matching.

In contrast, languages like JavaScript are said to be strict, or with eager evaluation because expressions like in function arguments will be evaluated immediately.

Although JavaScript is not a lazy language, it’s easy to define infinite types by simulating laziness. Back to the List example, we modify the list definition

List a = Empty 
       | Cons a (List a)
       | Lazy () -> List a

The new definition adds a new variant, a List can now also be a ‘Lazy’ list with a thunk : a getter function taking no input and returning a ‘List’. This way, the thunk function can express our meaning without actually evaluating it, we’ll decide ourselves when to force its evaluation. In fact, you can use this trick to transform any expression ‘x’ by simply putting ‘() =>’ in front of it(eg. ‘x+y’ will become ‘() => x+y’ and if x and y are themeslves lazy values the expression becomes ‘() => x()+y()’).

The new definition using our adt helper function is

function List() {}
adt( List, {
  Empty : new List(),
  Cons  : (head, tail) => ({head, tail}),
  Lazy  : thunk => ({thunk})
})

Now we can create an infinite list by making the 2nd argument to ‘repeat’ a lazy list

repeat = val => List.Cons(val, List.Lazy(() => repeat(val)))

Here is an example on how to define the ‘filter’ function given the new definition

// filter: (a -> aBoolean, List a) -> List b
function filter(pred, list) {
  return list.isEmpty ? List.Empty
       : list.isCons  ? 
           ( pred(list.head) ?
               List.Cons(list.head, filter(pred, list.tail)
             : filter(pred, list.tail)
            )
        /* isLazy */ List.Lazy( () => filter(pred, list.thunk())
}

In the case of a lazy list, we just return another lazy list that reflects the filter on the materialized list.

The question here, when to force the evaluation of a lazy list?

We’ve seen that in FP languages, evaluation is principally driven by pattern matching, but in our precise case, that’s entirely up to us. We could implement all list functions lazily like in ‘filter’ above, but it obviously doesn’t make sense, sooner or later we’ll have to do something with the real values.

For example, we can decide to force evaluation in the ‘take’ function (making it a strict function in a certain term)

// take : (Number, List a) -> List a
function take(n, list) { 
  return list.isEmpty || n < 1 ? List.Empty 
      :  list.isCons ? List.Cons(list.head, take(n-1, list.tail))
      :  /* isLazy  */ take(n, list.thunk()) // forces evaluation

Here is an example that builds an infinite list of natural numbers, then takes the first 5 odd ones.

// an infinite list of natural numbers
nats = start => List.Cons(start, List.Lazy(() => nats(start+1)))

// an infinite list of odd naturals
odds = filter(n => n%2, nats(0))

// 5 first odd naturals
fiveodds = take(5, odds) 

Recursive ADTs offers a more concise way to define operations using pattern matching and recursion, but in the cons part, if you have a big List, recursion can be a problem in the case of languages like JavaScript (here is a useful link to read more about this). This is not a problem in functional languages like Haskell which handle recursive calls quite efficiently.

Conclusion

ADTs are muchmore than just a syntax sugar or a repackaging of the existing OOP types. They offer a conceptual basis to reason about your program entities, forcing you to think explicitly about your function’s domains and codomains.

Simple ADTs like the ‘Result’ type, can serves as a context that enriches the meaning of simple values with additional information (is this value an error or a success value ?)

Recursive ADTs can offer a powerful abstraction to model complex data structures and implement their operations in a beautiful and concise code.

A fundamental concept in functional programming is composition. It simply describes the mechanism by which we combine simpler things to build more complicated things, then combine the new resulting things to build higher-complicated things and so on.

With composition, you never hit a wall, because you must always ask yourself “What is the return value of this function ?”, or put another way “What is the meaning of this thing ?”

If you’ve been in Node.js you are certainly aware of the code below

fs.readFile('...', function (err, data) {
  if (err) throw err;
    ....
});

As a quick reminder, the code above is a typical use of continuation-passing style (CPS)functions. The CPS function, ‘fs.readFile’, takes an extra parameter, which is a callback representing the continuation. Once finished, the CPS, instead of returning a value to the caller, calls the continuation function, the callback, passing it the result of it’s own computation.

I don’t mind using callbacks in my code. In fact, callbacks are great for things such as representing side effects or event notification, but once your start using them to manage your control flow, you’re trapped. Why ? because they do not compose.

So let’s just ask “What’s the meaning, the denotation or the return value of the above function ?”. The answer is ‘undefined’. And we can’t do anything useful with ‘undefined’, apart from testing that it’s actually … undefined.

The problem is that, inside the callback, you’ve been teleported to another flow of execution and this is a one way ticket.

Think of callbacks as the famous Black holes of physics:

A black hole is a mathematically defined region of spacetime exhibiting such a strong gravitational pull that no particle or electromagnetic radiation can escape from it

Particularly

In many ways a black hole acts like an ideal black body, as it reflects no light

Callback functions, also, reflect no light in a program flow.

If later, while trapped inside the first callback, you use another callback style function, then you lose the second flow and you fall into another hole. The more you use callbacks, the more you sink into hell.

So how can we move forward in our code without falling into black holes?

The answer is composition. But to use composition, we must get something from a function, and we know that CPS functions do not reflect anything. So we must, someway, make them return something. But what value are they supposed to return ? Well this is the motivation for this article.

Even if you are already aware of existing JavaScript solutions. I, strongly, recommend you to go through this post. You’ll see the power of denotational (ie functional) thinking and how it allows us to derive clean and concise semantics for those solutions.

Welcome to the future

If we think about those functions: file read operations, network requests, DOM events, … what do they have in common?

They describe operations that can not be achieved in the immediate, I mean we can not afford to wait for their completion in our current program flow (like we do with normal functions). So they describe future results.

So let’s make them return a special type: Future, to denote their eventual outcome. The key idea is to have a first class value which can be passed to other functions.

What’s the meaning of a Future ? it simply denotes a value who will occur after a certain time (which can be 0). The meaning of time can be an explicit event like when we say after x seconds, but can also given in relative terms, like when we say that 2 Futures complete at the same time or that a Future completes after another one.

Now this is important:

Outcome of a Future always denotes an immutable value.

That means, in any way we can’t change the completion value. This constraint doesn’t just simplify our implementation, it also simplifies our reasoning about its semantics.

Our Future could be implemented with a dead simple state machine. The machine starts as pending then evolves to completed and will stop here. Once completed, it’ll stay forever.

Internally, the ‘Future’ type will still rely on callbacks, but they will not serve any control flow mechanism. Instead, we’ll use them only for their right purpose: event notification.

function Future() {
    // a list to store pending subscribers
    this.slots = [];
}

// notify completion
Future.prototype.ready = function(slot) {        
    if(this.completed)
        slot(this.value);
    else
        this.slots.push(slot);
}

//a simple log utility
function logF(f) {
    f.ready( v => console.log(v) );
}

We provide external implementors with a method to complete the Future

Future.prototype.complete = function(val) {
    // ensure immutability
    if(this.completed)
        throw "Can't complete an already completed future!" 

    this.value = val;
    this.completed = true;

    // notify subscribers
    for(var i=0, len=this.slots.length; i<len; i++) {
        this.slots[i](val);
    }

    // release all, we don't need this anymore
    this.slots = null;
}

The simplest example of a Future, is one that completes immediately with a given value. We’ll define a method called unit with that purpose

// unit : Value -> Future<Value>
Future.unit = function(val) {
    var fut = new Future();
    fut.complete(val);
    return fut;
}

logF( Future.unit('hi now') );

Above, i used a type annotation to makes it simple to reason about the code:

‘unit : Value → Future<Value>’ means simply that:

1. ‘unit’ is a function
2. it takes a generic type ‘Value’ as input and
3. returns a ‘Future’ instance holding a value of this generic type.

Using the generic term ‘Value’ means we don’t actually care about the type, because the type information is irrelevant here.

another example is a value delayed by some time

// delay: (Value, Number) -> Future<Value>
Future.delay = function(v, millis) {
    var f = new Future();
    setTimeout(function(){
        f.complete(v);
    }, millis);
    return f;
}

logF( Future.delay('hi, it\'s been 5 seconds', 5000) );

The result of ‘delay’ is a Future that completes after a given duration with a given value.

Getting back to the ‘readFile’ example, instead of CPS functions, we can now uses a function returning a Future :

var fs = require('fs');

// readFileF: (String, Object) -> Future<String>
function readFileF(file, options) {
    var f = new Future();
    fs.readFile(file, options, function (err, data) {
      // We'll deal with errors later in the post
      if (err) throw err;
      f.complete(data);
    });
    return f;
}

logF( readFileF('test.txt', { encoding: 'utf8'}) )

The result of ‘readFileF’ denotes a Future holding the content of a file whose name is given as argument.

Acting on Futures: meet our 1st guest

You can think of ‘Future’ as a magic box holding the eventual outcome of a function.

But in order to do anything useful, we have to provide our Future type with some useful operations. Otherwise i’ll be just as if we’ve created another useless `undefined`.

So what operations can we describe in terms of Futures ?

Let’s start with computations on values held by the Future box, we’ll call it ‘fmap’ (a contraction of function map or perhaps better future map)

Here’s an example of ‘fmap’. Given a Future holding the content of a text file, we’d like to calculate the length of this content.

var textF = readFileF('test.txt', { encoding: 'utf8'});

// fmap: ( Future<String>, (String -> Number) ) -> Future<Number>
var lengthF = textF.fmap( text => text.length )
logF( lengthF )

The meaning of ‘lengthF’ is a Future holding the length of a file whose content is held itself by a given Future.

To generalize, ‘fmap’ takes 2 inputs:

1. a Future value
2. a mapping function over normal values.

Its output is a Future holding the result of the mapping function applied to the outcome of the input Future. Note that both input and output complete at the same time.

Informally, we can describe it like this

fmap( Future<value>, func ) = Future< func(value) >

Implementing `fmap` is just a few lines (we’re going to define it as a method on the Future prototype)

Future.prototype.fmap = function(fn) {
    var fut = new Future();
    this.ready(function(val) {
        fut.complete( fn(val) );
    });
    return fut;
}

We complete the output Future when the input Future completes. And we take care of applying the mapping function.

Back to the example above, we transformed a Future holding the content of a file to another Future holding the length of this content.

Sounds familiar ? it’s quite similar to the well known map method of JavaScript arrays. Actually, it’s exactly the same concept:

• the ‘Array’ type is a box holding multiple values
• the ‘Future’ type is a box holding a future value
• ‘Array.map(…)’ transforms the values inside the Array box and gives us another Array box encapsulating the transformed values
• ‘Future.fmap(…)’ transforms the value inside the Future box and gives us another Future box encapsulating the transformed value.

So meet our 1st guest, we say both Array and Future types are Functors. That’s because they can take a normal function, apply it to whatever inside and return another instance representing the result of the transformation.

Array and Future aren’t the only Functors, whenever you encounter

• a type acting as a context for other types
• knows how to apply a normal function inside it

then there is a good chance that this type is a Functor.

Now that we are able to map futures to another futures. it would be be cool if we can apply functions directly to Futures like we do with normal values.

So Instead of calling

textF.fmap( c => c.length )

we would like to have a special kind of function ‘lengthF’ that acts directly on Futures

// lengthF : Future<String> -> Future<Number>
function lengthF(strF) {
   return strF.fmap( s => s.length )
}

Looks trivial, yet we can now rewrite the file example like this

nbCharsF = lengthF( readFileF('...') )

We say that ‘lengthF’ is a lifted function. Lifting a function over a box-type like functors promotes function application from normal values to the box-type values. In our case, we are lifting a function ‘length: String -> Number’ which acts on Strings to a function ‘lengthF: Future<String> -> Future<Number>’ which acts on Futures.

To generalize, we define a function called ‘lift1’ (because it lifts only functions with arity 1, ie taking 1 input)

Future.lift1 = function(fn) {
    return fut => fut.fmap(fn);
}

This simple abstraction allows us to convert an asynchronous invocation into a normal function invocation. In our example ‘lengthF( readFileF(…) )’.

By composing ‘readFileF’ with ‘lengthF’ we are able to denote asynchronous computations yet without leaving the main program flow.

How about functions with many arguments ? (or Meet our 2nd guest)

Before we answer this question, let’s take a little time to think about a fundamental fact: What types are allowed to live inside our Future box ? do a Future have the same meaning for all types ?

The meaning of a ‘Future<String>’ is obvious: a value of type string that will be available in the future. Can the same reasoning be extended to all other types ? Numbers, Objects, Arrays ? certainly … How about Futures themselves ? what’s the meaning of ‘Future<Future>’, ie a Future of a Future ?

To get an intuition for this idea, let’s pick a simple example, we want to inspect a directory then read the content of the first file inside (for simplicity we’ll suppose there are no nested directories).

in Node we can use the async function ‘fs.readdir’ to get an array of file names inside a given directory. We’ll first derive our Future-ish function

// readDirF : String -> Future< Array<String> >
function readDirF(path) {
    var f = new Future();
    fs.readdir(path, (err, files) => {
      // hold on, it's coming
      if (err) throw err;
      f.complete(files);
    });
    return f;
}

The meaning of ‘readDirF’ is a Future holding an array of the names of the files in a given directory.

In order to solve our problem, we need to

1. Read the content of a directory which gives us a Future holding an array of Strings representing file names.
2. Pick the first file name then read its content.

Can we use ‘fmap’ here ? let’s see what happens if we run this code in Node

var resultF = readDirF("testdir")
               .fmap(files => readFileF(files[0]))

logF( resultF )

And we get…oops

{ slots: [] }

Clearly, there is something wrong here. Instead of getting the content of the file in the console, we get the the textual representation of an object which is obviously a Future instance.

That’s because ‘fmap’ takes whatever result is returned by its mapping function and completes the output Future with it. As the mapping function above returned another Future (the result of ‘readFileF’), ‘fmap’ just blindly completed ‘resultF’ with it.

But a Future can’t complete with another Future, it has still to wait for the resulting, nested Future to complete before going on.

So we need a guard function to watch for this case. Instead of completing immediately, it’ll wait for the nested Future to complete.

We’ll call it ‘flatten’, because it flattens a ‘Future<Future>’ (a 2 layered Future) into a simple Future

// flatten: Future< Future<Value> > -> Future<Value>
Future.prototype.flatten = function() {
    var fut = new Future();
    this.ready(function(fut2) {
        fut2.ready( function(val){
            fut.complete(val);
        } );
    });
    return fut;
}

And we can get our result like this

var result = 
  readDirF("testdir")
    .fmap(files => readFileF(files[0], {encoding: 'utf8'}))

logF( result.flatten() )

Instead of calling ‘fmap’ and ‘flatten’ each time, we’ll pack this use case in a single call: an ad-hoc function that will do both operations : map to a 2 Layered Future then flatten it. To stay meaningful, we’ll name it ‘flatMap’ (awful, i know)

Future.prototype.flatMap = function( fn ) {
    return this.fmap(fn).flatten();
}

Conceptually, what we described above is a way of sequencing 2 dependent computations, ‘readFileF’ depends on ‘readDirF’ because the first function takes its input (file name) from the outcome of the second function (list of file names).

Now let me introduce our second guest, Besides being a Functor, a Future is also a Monad, because it defines a way for describing a computation as a sequence of steps. using the above ‘flatMap’ method we can chain together multiple function calls with each step taking its input from the previous step.

As for Functors, there are many use cases for Monads; technically, all a Monad needs is

• a way of lifting a normal value to a Monadic one: in our example, it’s the ‘Future.unit’ which makes a Future from a normal value.
• a way of chaining 2 consecutive operations: each Monad has its proper logic of chaining. In our case, the logic is handled with ‘flatMap’ which is to wait for the completion of a Future before moving forward.

We’ve seen that the 2nd operation (flatMap) can also be defined in terms of 2 other operations (‘fmap’ and ‘flatten’), if you have a Functor which defines an ‘fmap’ function, all you need is a flattening operation to simplify a 2 layered structure.

So now, let’s return to the main question, how can we lift a function that takes multiple arguments to act on Futures?

Let’s pick the file example again, this time we would like to concatenate the content of all files in a given directory, our code will look like

// concatF : (Future<String>, ...) -> Future<String>
var resultF = concatF( text1F, text1F, ...)

What is the meaning of the above function? The result denotes a Future holding the concatenation of all strings held by the input Futures. Logically, ‘concatF’ needs to wait for all the input Futures in order to proceed, so the output completes when all inputs compete.

for implementation, We’ll start with the case of 2 arguments

// lift2: ( (a, b) -> c) -> ( (Future<a>, Future<b>) -> Future<c>)
Future.lift2 = function(fn) {
    return (fut1, fut2) => {
        fut1.flatMap( value1 =>
            fut2.flatMap( value2 => 
                Future.unit( fn(value1, value2) );
            )
        )
    };
}

In spite of the appearances, the code’s logic is rather simple, let’s go step by step:

• ‘Future.lift2’ takes a “function which acts on 2 normal values” and returns a “function which acts on 2 Futures”
• What the returned (lifted) function does actually is
• use ‘flatMap’ to sequence 2 operations (with a nested call),
• the first operation does nothing by itself, it just binds the first outcome to the variable ‘value1’ which remains visible in the scope
• the second , nested, operation, apply the function fn to the 2 outcomes: ‘value1’ and ‘value2’
• since ‘fn’ returns a normal value, and ‘flatMap’ expects a Future value, we use ‘Future.unit’ to lift the normal result to a Future result.

The trick here is: run ‘flatMap’ on all Futures in sequence allows the function to wait on all futures, and nested ‘flatMap’ calls gives the function a scope for all completion values.

The last use of ‘Future.unit’ to lift the result suggests that multi-argument lifted functions are different from Monadic ones which describes sequential operations (like ‘readFile’ inside ‘readDir’).

Here is an example that concatenates the content of 2 files

var concat2F = Future.lift2( (str1, str2) => str1+' '+str2 );

var text1F = readFileF('test1.txt', {encoding: 'utf8'});
var text2F = readFileF('test2.txt', {encoding: 'utf8'});

logF( concat2F(text1F, text2F) );

Note that even in the case of the second Future ‘text2F’ completes before the first ‘text1F’, the function has still to wait for ‘text1F’. Upon its completion, the function will proceed immediately because ‘text2F’ has already completed.

We can conclude that a multi-argument function does not depend on the order of completion of its inputs, nor their interdependence. In fact, we can also reformulate this meaning like this:

• if ‘fmap’ denotes a single operation, and
• ‘flatMap’ denotes sequential operations, then
• multi-argument lifted functions denotes parallel operations.

That makes sense, because, like in the example above, we run the Futures all at once and wait for their completion before proceeding to the computation.

We can easily extend the the pattern used in lift2 to lift3 or lift4, but we’ll just generalize to an arbitrary number of arguments, all we need is the 2 tricks from above: nesting and scoping

function toArray(args) {
  return Array.prototype.slice.call(args);
}

Future.lift = function(fn) {
  return function() {            
    var futArgs = toArray(arguments), // our future arguments
        ctx = this; // save context ('this')

    return bindArg(0, []);

    function bindArg(index, valArgs) {        
      // wait the current Future argument        
      return futArgs[index].flatMap(function(val) {  
        // collect completion values               
        valArgs= valArgs.concat(val);

        // not yet the last Future argument ?
        return (index <  futArgs.length - 1) ?                  
          // flatMap (wait) the next argument
          bindArg(index+1, valArgs) : 
         
          // last reached, apply the collected vales
          Future.unit( fn.apply(ctx, valArgs) ); 
      });           
    }
  }
}

‘lift’ reuse the same trick used in ‘lift2’. Since we don’t know in advance the exact number of inputs, we use a recursive call to iterate over all of them, waiting for their completion then collecting the outcomes on the way (wait/flatMap Future at index, then save the completion value and repeat the process with the next Future input until all inputs are processed). Once we reach the last input Future in the chain we proceed to function application, then we return the lifted result.

We could have used another structure called ‘Applicative Functor’ to implement n-ary lifting. But then we’d have to go through some explanations involving terms like lambdas and currying, so will just skip this today.

Error handling

Recall in our process of converting ‘fs.readFile’ how we’ve ignored the error value

function readFileF(file, options) {
    var f = new Future();
    fs.readFile(file, options, function (err, data) {          
      if (err) throw err;
      ...

We can’t do that in a real code. Because we’re not in the main program flow (the outest), there is no way for us to catch the error. In the case above, the error propagates upward and finding no handler in the way, Node just aborts the whole program.

What if we need instead to catch the error to have a chance to fix it, or possibly redirect it to somewhere like a meaningful error message for the user.

A possible solution is to augment the semantics of Future with the notion of failure. Until now we didn’t gave any meaning to the outcome of a Future, but now we’ll think of Future as a context with 2 possible outcomes (completion or failure), so we have to review the semantics in the context of a possible failure.

First, we had a method ready to notify completion so we also define a method to notify failure.

function Future() {
    this.slots = [];
    this.failslots = [];
}

Future.prototype.failed = function(slot) {
    if(this.hasFailed)
        slot(this.error);
    else
        this.failslots.push(slot);
}

We also define a method to fail the future.

Future.prototype.fail = function(err) {  
    if(this.completed || this.hasFailed)
        throw "Can't fail an already settled future!"        
    this.hasFailed = true;
    this.error = err;
    for(var i=0, len=this.failslots.length; i<len; i++) {
        this.failslots[i](err);
    }
}

Now what’s the new meaning of the ‘fmap’ operation ?

In the example ‘readFileF(…).fmap( s => s.length)’, No meaning can be given to the length of a non existing file. Logically, we’d like to transform only valid results so the output Future will complete with a transformed value only if the input Future completed with success, otherwise it’ll just fail with the same error. Also, if the mapping function failed in its transformation, we must also fail the output.

Future.prototype.fmap = function(fn) {
    var fut = new Future();
    this.ready( val => {            
        try        { fut.complete( fn(val) );    }
        catch(err) { fut.fail(err);              }          
    });

    this.failed( err => fut.fail(err) );

    return fut;
}

For ‘flatten’ it’s a little more complicated. We have 2 futures : outer and inner, and each one has also 2 possible outcomes : completion or failure. That gives us 4 cases to handle (2x2)

Future.prototype.flatten = function() {
    var fut = new Future();

    // 1- outer fails && inner fails => output fails
    // 2- outer fails && inner completes => output fails
    this.failed( _ => fut.fail(err) );

    // 3- outer completes && inner fails => output fails 
    this.ready( fut2 =>
        fut2.failed( err => fut.fail(err) );           
    ); 

    // 4- outer completes && inner completes => output completes
    this.ready( fut2 =>
        fut2.ready( val => fut.complete(val) );
    );      
    return fut;
}

In the case of ‘flatten’, the output completes only and only if both inner and outer inputs complete.

We don’t have to modify ‘flatMap’ or ‘lift’. Since they are derived from ‘fmap’ and ‘flatten’, they automatically inherit their error handling semantics.

Ok, we made our future skip all subsequent computations in case of failure, which leaves us with a failed Future. So what operations can we do with a failed Future ?

There is only one, we can catch future errors and try to fix them, how ? by defining an operation that can transform a failed Future to a completed one, which can then be reintegrated again in our computation.

We’ll have to define a peer function for ‘fmap’, we’ll call it ‘fmapError’. It’s like a flipped version of fmap

Future.prototype.fmapError = function(fn) {
    var fut = new Future();
    this.ready( val => fut.complete(val)  );
    this.failed( err => {
        try         { fut.complete( fn(err) );    }
        catch(err1) { fut.fail( err1 );           }            
    });
    return fut;
}

‘fmapError’ acts as an async catch statement, valid results pass through the function while errors are caught and sent in to the mapping function.

Here is a simple example

readFileF('unknown file').fmapError( err => 'alternate content' )

But what if you we want to catch errors in a monadic fashion, ie inside a pipeline of sequential operations ?

For this, we’ll define flatMapError which is nothing more than the peer version of flatMap.

Future.prototype.flatMapError = function( fn ) {
    return this.fmapError(fn).flatten();
}

As an example of use, suppose we are trying to fetch some content from some web URL that can be sometimes unavailable, upon a failure of our request, we’ll try an alternative URL, we can use ‘flatMapError’ to catch the first failure and return the alternative request

resultF = requestF('/url1').flatMapError( err => requestF('/url2') )

The meaning of ‘resultF’ is a Future whose content is the outcome of the first request to ‘url1’ in case of a success and the outcome of the second request to ‘url2’ if the first request failed.

Side effects

We’ve defined all needed operations to describe computations in a composable way. Using the so far defined functions, we can work with asynchronous functions in a simple synchronous style, passing our Futures around as if they were normal values.

But each computation has to reach an end. That’s the right time to do our side effects operations: updating our UI, logging into the console, saving to a database…

A quick temptation is to define a special method ‘do’ to denote this type of operations. But then we have, as usual, to ask what is the meaning of do, what’s its return value ?

If we simply make it return a Future with no value transformation, then it’ll have the same denotation as ‘future.fmap( Id )’ (Id being the identity function x => x); But we know actually they are not the same. We should not have this kind of distortions in our abstract model: things that denotes the same thing are just supposed to be the same thing.

Another question is related to the meaning of time: does ‘do’ complete in the same time as the input Future ? What if our side effect operation consist of sending updates to a remote server ? we should wait for the server response. Morever the server response can (and it’s often) be relevant to our app.

In fact, it’s clear from the above, that side effect operations are nothing more than functions that are chained to a given Future and returns themselves another Future. This is precisely the denotation of ‘flatMap’ and ‘flatMapError’. Put another way, side effect operations are just Monadic functions (if you have some Haskell background, you’ve probably made the link to the IO Monad).

So what’s the point about Promises

If you are already aware of Promises, then you obviously noted the similarities between Futures and Promises, you may have also noted how I avoided to mention them all the way.

If you want, take the Future class, mix together fmap, flatMap, mapError and flatMapError into a single big monolithic method and you’ll end up with something more or less similar to the ‘Promise.then’ method.

Of course, There will be always someone to argue that implementing a Fully compliant specification of Promises is far more complicated. He may even tell me something like You’re Missing the Point of Promises.

If you take a minute to read the above Promise/A+ specification, you’ll notice it doesn’t describe the Promise operations in terms of the values they denote but rather describes a process to be followed by any compliant implementation. Put another way, the specification is operational and not denotational. Operational semantics are strongly tied to their execution model. This is why, in the specification, you can notice references to things like

onFulfilled or onRejected must not be called until the execution context stack contains only platform code

or also references to the state internals of a promise

A promise must be in one of three states: pending, fulfilled, or rejected. When pending, a promise: may transition to either the fulfilled or rejected state.

In contrast to operational semantics, Denotational semantics do not focus on what steps should be carried out, nor the internal representation in order to achieve some computation. It rather focus on the meaning of things, and this meaning must be defined in term of other meanings that are either: well defined themselves, or fairly obvious to be defined (like values or functions).

If you understand from above that the Promise specification is useless, or that Promises themselves are useless, then You are missing the point of my article. And probably you’re also (partly) missing the point of Promises.

You can always view Promises only as an imperative construct that mimics the ‘;’ (used to sequence synchronous statements), and then use them exclusively to sequence asynchronous statements. Another way is to consider them from a more functional view; ie as future values. Then you’ll start more to use them as asynchronous results of function evaluation. You’ll more and more use lifting to derive Future-ish functions and then compose those functions as you do with normal ones.

The point of this article is not to present any alternative to Promises, but essentially to demonstrate the power of denotational thinking. Along the way, we kept asking about the meaning of things and this led us to a fairly clear specification of our concept, (even if the semantics were presented in informal terms).

Using well known abstractions, like Functors and Monads, which already have solid mathematical underpinning, made it quite easy to reason about properties of Futures and derive the implementation of some operations. this may be a question of style, but i doubt we could have achieved that if we took a purely operational reasoning.

Source code is available at this Gist

Hacker Noon is how hackers start their afternoons. We’re a part of the @AMI family. We are now accepting submissions and happy to discuss advertising & sponsorship opportunities.

If you enjoyed this story, we recommend reading our latest tech stories and trending tech stories. Until next time, don’t take the realities of the world for granted!

From Callback to Future -> Functor -> Monad was originally published in HackerNoon.com on Medium, where people are continuing the conversation by highlighting and responding to this story.