DEV Community: Gabriel Lebec

When Nesting Promises is Correct

Gabriel Lebec — Sat, 20 Apr 2019 04:01:35 +0000

Intro

By now, promises are well-established in the JS ecosystem, not only being officially specified in ECMAScript, but even having a first-class syntactic sugar in the form of async functions.

When learning promises, many JS developers are told that a major advantage of promise chaining is that it keeps the code "flat", avoiding the pyramid of doom of nested callbacks. While this is partly true, it also puts undue emphasis on code appearance, running the risk of missing the point.

True "callback hell" is less about indentation – in fact, by naming callback functions and factoring them out to the top level, one can often flatten out async code without the need for promises. Instead, callback hell is when we lose the composable vanilla function API (pass in data, receive result), where returned values can be bound to variables, aggregated in collections, passed to other functions, and combined in first-class ways.

All of this preamble is to give context to the following statement: nesting promises is often an antipattern, but not always. In fact, there is a common situation in which a little nesting can make perfect sense, though there exist several alternatives. This short article will demonstrate a common scoping issue with promises and multiple solutions for that issue.

The Setup

For these examples, we will imagine that the function getPuppyById is an AJAX method returning some data via a promise. Puppies will be objects with a bestFriend foreign key to another puppy:

{
    id: 4,               // this puppy's id
    name: 'Mr. Wiggles', // this puppy's name
    bestFriend: 17       // id of this puppy's best friend (another puppy)
}

If we wish to fetch puppy #1's best friend's name, we can chain calls to getPuppyById:


    
const getPuppyById = (id) => new Promise((res) => {
    const time = Math.random() * 500 + 500
    setTimeout(() => res({
        1: { name: 'Floof', id: 1, bestFriend: 7 },
        7: { name: 'Rex', id: 7, bestFriend: 1 }
    }[id]), time)
})


    
const friendNameP =
    getPuppyById(1)                               // first fetch
    .then(pup1 => getPuppyById(pup1.bestFriend))  // second fetch
    .then(friend => friend.name)                  // data transformation

friendNameP  // our goal, a promise for the best friend name
    .then(name => console.log('friend name', name))
    .catch(e => console.error(e))

This works just fine when our early results are just discardable steps towards our desired final result.

The Problem

However, what if we wanted to produce a promise for both puppies' names – the original and the friend? Because the callback passed to then introduces a function scope, the first puppy may no longer be in scope further down the chain.


    
const getPuppyById = (id) => new Promise((res) => {
    const time = Math.random() * 500 + 500
    setTimeout(() => res({
        1: { name: 'Floof', id: 1, bestFriend: 7 },
        7: { name: 'Rex', id: 7, bestFriend: 1 }
    }[id]), time)
})


    
const twoPuppyNamesP =
    getPuppyById(1)                               // first fetch
    .then(pup1 => getPuppyById(pup1.bestFriend))  // second fetch
    .then(friend => {
        return [pup1.name, friend.name] // ERROR – pup1 no longer in scope!
    })

// DO NOT EDIT BELOW

twoPuppyNamesP  // our goal, a promise for the puppy and friend names
    .then(names => console.log('puppy names', names))
    .catch(e => console.error(e))

There are multiple ways to solve this, which we will examine in a moment. Before we do so, go ahead and fix the above code snippet using whatever technique you may prefer. Only edit the top half of the snippet; you are trying to make twoPuppyNamesP fulfill its promise (hah) of delivering both puppies.

Solutions

Library-Specific: Bluebird `bind`

Before promises became official in ES2015, third-party implementations like Bluebird were popular. Bluebird is still used by some codebases for its speed and wide array of utility methods.

Though it breaks section 2.2.5 of the A+ promise spec to do so, Bluebird includes a special feature in which you can set the this value of a promise chain – providing a shared mutable namespace in which to save intermediate results. The specific method is named bind.

.bind also has a useful side purpose - promise handlers don't need to share a function to use shared state


    
const getPuppyById = (id) => new Promise((res) => {
    const time = Math.random() * 500 + 500
    setTimeout(() => res({
        1: { name: 'Floof', id: 1, bestFriend: 7 },
        7: { name: 'Rex', id: 7, bestFriend: 1 }
    }[id]), time)
})


    
const P = require('bluebird')
const toBluebird = p => P.resolve(p)

const twoPuppyNamesP =
    toBluebird(getPuppyById(1))                   // first fetch
    .bind({})                                     // set 'this' for chain
    .then(function (pup1) {                       // arrows don't have 'this'
        this.pup1 = pup1                          // saving state for later
        return getPuppyById(pup1.bestFriend)      // second fetch
    })
    .then(function (friend) {
        return [this.pup1.name, friend.name]  // accessing 'pup1' in shared state
    })

twoPuppyNamesP  // our goal, a promise for the puppy and friend names
    .then(names => console.log('puppy names', names))
    .catch(e => console.error(e))

While this works, it has significant drawbacks:

it complicates the promise chain with spec-breaking features
it requires using function functions to access this
it is non-portable knowledge tied to a specific library

A+-Compliant, ECMA-Approved: `Promise.all`

If only we could pass multiple values down through a promise chain – even when one of those values is a pending promise, whose value we wish to access further down the chain.

Of course, we do not need to wish for such a feature, as it is available via the Promise.all static method. By returning an array of both synchronous values and promise values, wrapped in a call to all, we get access to an array of synchronous values in the next then.


    
const getPuppyById = (id) => new Promise((res) => {
    const time = Math.random() * 500 + 500
    setTimeout(() => res({
        1: { name: 'Floof', id: 1, bestFriend: 7 },
        7: { name: 'Rex', id: 7, bestFriend: 1 }
    }[id]), time)
})


    
const twoPuppyNamesP =
    getPuppyById(1)                                   // first fetch
    .then(pup1 => {
        const friendP = getPuppyById(pup1.bestFriend) // second fetch
        return Promise.all([pup1, friendP])           // collect both results
    })
    .then(([pup1, friend]) => {                       // array destructuring
        return [pup1.name, friend.name]               // data transformation
    })

twoPuppyNamesP  // our goal, a promise for the puppy and friend names
    .then(names => console.log('puppy names', names))
    .catch(e => console.error(e))

Even though the array passed to .all has a mix of normal and promise values, the resulting overall promise is for an array of normal values.

This strategy will work in any setting that supports ES2015, and is thus much more portable than the Bluebird bind trick. Unfortunately, it too has cons:

more verbose return lines
more complex function parameters and destructuring
as the chain grows, passing down multiple results does not scale well
overall, a lot of redundant "plumbing" of early values through the chain

Controlled State, Shared Scope

We now come to one of the most common and viable techniques for sharing state through a promise chain – use a mutable or reassignable variable(s) in a higher scope. As each handler in a then chain is invoked, it will set and/or read the values of a shared let binding or the properties of a shared object.


    
const getPuppyById = (id) => new Promise((res) => {
    const time = Math.random() * 500 + 500
    setTimeout(() => res({
        1: { name: 'Floof', id: 1, bestFriend: 7 },
        7: { name: 'Rex', id: 7, bestFriend: 1 }
    }[id]), time)
})


    
let pup1                                              // shared binding

const twoPuppyNamesP =
    getPuppyById(1)                                   // first fetch
    .then(gotPup1 => {
        pup1 = gotPup1                                // save state
        return getPuppyById(pup1.bestFriend)          // second fetch
    })
    .then(friend => {
        return [pup1.name, friend.name]               // data transformation
    })

twoPuppyNamesP  // our goal, a promise for the puppy and friend names
    .then(names => console.log('puppy names', names))
    .catch(e => console.error(e))

This may seem "illegal" considering how we normally consider async code to work, but in fact it is guaranteed to work as expected as later callbacks in a then chain can only be invoked after earlier callbacks. So the usage of pup1 in the second then will work because pup1 is guaranteed to have been assigned in the callback of the previous then.

This has some distinct advantages:

it is relatively clear even for people without advanced knowledge of promises
it is setting-agnostic
it is relatively light on syntax
the chain remains flat, reducing mental load

As always, there are still tradeoffs to consider, however.

shared mutable state is risky; care should be taken to only allow the promise chain to read or modify these variables
- reading outside the chain is not guaranteed to work due to indeterminate timing
- writing outside the chain can break guarantees within the chain
we now need two versions of the variable name – a parameter name like gotPup1 and a shared state variable like pup1 – to avoid shadowing

If the promise chain is itself contained within a short function scope, disciplined use of shared state in a local setting can be concise and easy way to solve the issue of passing information down the chain.

The Punchline: Nested Promises

This article opened with the promise (hah) of showing a situation in which a small bit of nesting can be a valid and useful technique. The key point is that with a nested chain, an inner then still has scope access to the results from an outer then.


    
const getPuppyById = (id) => new Promise((res) => {
    const time = Math.random() * 500 + 500
    setTimeout(() => res({
        1: { name: 'Floof', id: 1, bestFriend: 7 },
        7: { name: 'Rex', id: 7, bestFriend: 1 }
    }[id]), time)
})


    
const twoPuppyNamesP =
    getPuppyById(1)                                   // first fetch
    .then(pup1 => getPuppyById(pup1.bestFriend)       // second fetch
        .then(friend => [pup1.name, friend.name])     // nested then
    )

twoPuppyNamesP  // our goal, a promise for the puppy and friend names
    .then(names => console.log('puppy names', names))
    .catch(e => console.error(e))

In such cases, it is crucial to remember to return the nested promise chain to the parent promise chain. In the example above we use the implicit return of an arrow function to accomplish this, but it is a common error to forget the return keyword when in a bracket-enclosed function body.

The biggest advantage that the above pattern has over an outer-scope variable is that it is stateless – there is no explicit mutation occurring in the visible code, only a declarative sequence of functional transformations.

As always, we can identify some disadvantages:

this approach does not scale well for passing down each result from many then calls – one quickly returns to the "pyramid of doom" for such cases
with nesting comes increased mental load in parsing and understanding the logic of the promise chain
as is often the case with promise chains, it can be especially difficult to decide on a sensible formatting scheme with respect to where .then appears (same line? next line? indented?) and where to position the callback function

Silly Experiment: Formatting Tricks

Speaking of formatting, there is no reason why one cannot format a nested promise chain in a "flat" way, if we allow for piling up of parentheses:


    
const getPuppyById = (id) => new Promise((res) => {
    const time = Math.random() * 500 + 500
    setTimeout(() => res({
        1: { name: 'Floof', id: 1, bestFriend: 7 },
        7: { name: 'Rex', id: 7, bestFriend: 1 }
    }[id]), time)
})


    
const twoPuppyNamesP =
    getPuppyById(1)                              // first fetch
    .then(pup1 => getPuppyById(pup1.bestFriend)  // second fetch (missing closing paren)
    .then(friend => [pup1.name, friend.name]))   // nested then (extra closing paren)

twoPuppyNamesP  // our goal, a promise for the puppy and friend names
    .then(names => console.log('puppy names', names))
    .catch(e => console.error(e))

The longer the nested chain, the more we defer closing parens to the last line, where they will pile up like afterthoughts. In a language like Haskell in which function application doesn't use parens, this isn't a problem! But for JavaScript, it gets a little silly. Compare and contrast:

-- Haskell

_then = (>>=) -- renaming for JS readers; can't use 'then' b/c it's a keyword

pupsIO =
    getPuppyById 1
    `_then` \pup1 -> getPuppyById (bestFriend pup1)
    `_then` \pup2 -> getPuppyById (bestFriend pup2)
    `_then` \pup3 -> getPuppyById (bestFriend pup3)
    `_then` \pup4 -> getPuppyById (bestFriend pup4)
    `_then` \pup5 -> pure [pup1, pup2, pup3, pup4, pup5]

// JavaScript

const pupsP =
    getPuppyById(1)
    .then(pup1 => getPuppyById(pup1.bestFriend)
    .then(pup2 => getPuppyById(pup2.bestFriend)
    .then(pup3 => getPuppyById(pup3.bestFriend)
    .then(pup4 => getPuppyById(pup4.bestFriend)
    .then(pup5 => [pup1, pup2, pup3, pup4, pup5]))))) // lol

The Promised Land: Async/Await

Moving past our promise chain woes, we return to the real issue at hand – promise chains are composed from callback functions, and functions syntactically introduce new scopes. If we didn't have sibling scopes, we could share access to previous results.

Lo and behold, this is one of the problems solved by async functions.


    
const getPuppyById = (id) => new Promise((res) => {
    const time = Math.random() * 500 + 500
    setTimeout(() => res({
        1: { name: 'Floof', id: 1, bestFriend: 7 },
        7: { name: 'Rex', id: 7, bestFriend: 1 }
    }[id]), time)
})


    
const getTwoPuppyNamesP = async () => {  // a shared async function scope
    const pup1 = await getPuppyById(1)                 // first fetch
    const friend = await getPuppyById(pup1.bestFriend) // second fetch
    return [pup1.name, friend.name]                    // data transformation
}

const twoPuppyNamesP = getTwoPuppyNamesP() // async funcs return promises

twoPuppyNamesP  // our goal, a promise for the puppy and friend names
    .then(names => console.log('puppy names', names))
    .catch(e => console.error(e))

The advantages are substantial:

far less noise (no .then calls or callback functions)
synchronous-looking code with access to previous results in scope

The cost is pretty minimal:

the await keyword may only be used inside an async function, so we need to wrap our promise code in a function body

Async/await is analogous to Haskell's do-notation, where do is like async and <- is like await:

-- Haskell

twoPuppyNames = do
    pup1   <- getPuppyById 1
    friend <- getPuppyById (bestFriend pup1)
    pure [name pup1, name friend]

One major difference is that async/await in JS is only for promises, whereas Haskell's do notation works with any monad.

Conclusion

With the advent of async/await, programmers are using raw promise chains less often. Async/await has its own subtleties to master, but it neatly solves at least one awkward aspect of promise chains, namely accessing previous async results in a sequence of operations.

As the title to this article suggested, when writing a manual promise chain it is sometimes perfectly valid to use a little local nesting. Doing so keeps multiple results in scope, without needing special library tricks or stateful assignments.

In any case, I hope that these examples will help people learning JS promises to understand them a little better and use them more confidently.

The FP Papers: Hughes Lists

Gabriel Lebec — Wed, 17 Apr 2019 00:32:15 +0000

Sitting on my drive is an ever-expanding collection of papers related to functional programming and related topics. Some of these papers are considered classics in the field, having introduced or popularized techniques which are now staples of FP. Others provide rich perspectives on familiar topics, revealing deep mathematical principles embedded in common programming patterns.

Partly as motivation to actually read through these papers, and partly because I enjoy breaking down and translating such material for a wider community (e.g. in JavaScript), I am beginning a new article series, tentatively titled "The FP Papers" (imaginative, I know). This is the first entry in that series.

A Novel Representation of Lists and its Application to the Function "Reverse"

Authors	Year	DOI	Pages
R. John Muir Hughes	1986	https://doi.org/10.1016/0020-0190(86)90059-1	4

A representation of lists as first-class functions is proposed. Lists represented in this way can be appended together in constant time, and can be converted back into ordinary lists in time proportional to their length. Programs which construct lists using append can often be improved by using this representation. For example, naive reverse can be made to run in linear time, and the conventional ‘fast reverse’ can then be derived easily. Examples are given in KRC (Turner, 1982), the notation being explained as it is introduced. The method can be compared to Sleep and Holmström's proposal (1982) to achieve a similar effect by a change to the interpreter.

John Hughes is an author and co-author of several of my favorite FP papers, including "Why Functional Programming Matters" and "QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs". In this paper, he introduces a rather clever data structure – an immutable list with a constant time (O(1)) append operation. These lists are frequently referred to as difference lists (DLists) or sometimes Hughes lists.

Mutation?

Even in a mutable setting, this would be a challenge. Consider a singly-linked list class with handles to the first and last nodes; append could conceivably done in constant time by "re-wiring" the first list's last node to point to the second list's first node:

List A:                       List B:
first         last            first         last
<1> -> <2> -> <3>             <a> -> <b> -> <c>
               |               ^
               —————append—————|

List A's last pointer would be updated accordingly (to point to <c>). Yet the above implementation has a glaring flaw; it uses structural sharing in a mutable setting. If anything modifies List B, the changes will now also show up in List A!

List A:              (List B)
<1> -> <2> -> <3> -> <a> -> <b> -> <c>
                             |
                           change (List B)
                             |
List A:                      V
<1> -> <2> -> <3> -> <a> -> <x> -> <c>
             (oops — List A now modified too)

In some cases this may be intended, but it is very easy to accidentally begin changing lists. Even if we never change node values, the act of appending itself is a mutation, so for instance if someone appended a List C to List B, they would accidentally be affecting List A also. Oops!

To get around this risk, a mutable linked list will typically copy nodes to be appended:

List A:                       List B:
first         last            first         last
<1> -> <2> -> <3>             <a> -> <b> -> <c>
               |               |      |      |
               —————append————copy   copy   copy
                               |      |      | 
                               V      V      V
                              <a> -> <b> -> <c>

The operation is now "safe" as modifying the original List B will not affect A (and vice-versa), but it is linear (O(n) time) with respect to List B's length.

Purity?

Perhaps there exists a reasonable implementation for constant-time-appendable mutable lists, but that isn't the point of Hughes's paper. In purely functional code, there aren't any (direct) mutations. The classical functional list structure (aka a Cons list) is a singly-linked list implemented as nested pairs; the first cell of each pair is a value, the second cell is a pointer to the next pair (or to the empty list). In Scheme, Haskell, and JS respectively:

; Scheme
(cons 1 (cons 2 (cons 3 nil)))
; (list 1 2 3)

-- Haskell
1 : 2 : 3 : []
-- [1, 2, 3]

// JavaScript
const cons = (val, next) => ({ val, next })
cons(1, cons(2, cons(3, null)))
// { val: 1, next: { val: 2, next: { val: 3, next: null }}}

The restriction of no mutation means that to append two such lists (producing a new List C) is O(n) where n is the length of the first list.

List A:                       List B:
first         last            first         last
<1> -> <2> -> <3>       ———>  <a> -> <b> -> <c>
 |      |      |        |
copy   copy   copy   append
 |      |      |        | 
 V      V      V        |
<1> -> <2> -> <3> ——————|
List C

We must copy <3> to change its next pointer, and we must in turn copy <2> to change its next to point to the new <3>, and so on. Yet we can safely share List B's nodes because nothing will ever actually change them.

Overall, this is quite similar to our first attempt at appending mutable lists, but reversed – we have to copy the left list rather than the right.

The Paper

Representations

With the context established, we can start actually reading this paper. Hughes begins by discussing a general notion of abstract data types, represented by concrete data types. Perhaps confusingly, Hughes's choice of "abstract" and "concrete/representational" will refer to familiar Cons lists and the titular novel list representation respectively.

Whenever an abstract data type A is represented by a concrete data type R, two functions must be defined:

abs: R -> A

rep: A -> R

In this case, the abs function will convert a Hughes list (aka DList) to a Cons list; the rep function will convert a Cons list to a DList. The abs function must be a left inverse of rep; that is, when round tripping a Cons list to DList (via rep) and back ( via abs), then you must end up where you started. In this sense, abs "undoes" rep.

Now, suppose we want to have an append function for Cons lists. Hughes makes the point that if we can define an append function for DLists, we get the Cons version for free – we can convert Cons lists to DLists, append them, and then convert the resulting DList back to a Cons List.

             ————— ConsListAppend ————————————————————————————————
             |                                                   |
ConsListA —> | —rep—> DListA —> ———————————————                  |
             |                  | DListAppend | —> DListC —abs—> | —> ConsListC
ConsListB —> | —rep—> DListB —> ———————————————                  |
             |                                                   |
             —————————————————————————————————————————————————————

Hughes frames this relationship in terms of an interesting general law:

[given f: A -> A and g: R -> R, g "implements" f precisely if:]

FORALL r: R.f(abs r) = abs(g r)

This law is stated in terms of partially applied functions, a topic slightly out of scope for this article. Thankfully, partial application isn't strictly necessary to understand DLists per se; the main takeaway for this law is that a "correct" DListAppend would give us ConsListAppend as previously illustrated.

The DList, Defined

Hughes now drops, with almost no ceremony, the actual "novel representation of lists" promised.

…the representation function, rep, is just append.

rep L = append L

(Here we are making use of the KRC convention that all functions are curried.)

Careful! There are some subtleties packed into this short snippet. Hughes uses append L to mean a function that prepends L (to an implicit list L2). This might clarify why that is so:

append A B -- a list     (A ++ B / append B to A / prepend A to B)
append A   -- a function (A ++ ? / append ? to A / prepend A to ?)

In JavaScript, we might write this rep function as follows:

const rep = consList1 => (consList2 => append(consList1, consList2))
//              ^        \                                         /
//              |         —————————————————————————————————————————
//              |                            |
//         input list L                output DList

This underscores a very important point – a DList is a function. If we called rep(cons(1, cons(2, cons(3, null))) we'd get back a DList representing the Cons list [1, 2, 3]; yet the typeof that DList value would be 'function'. How can this be? Well, as Hughes points out, we can easily convert the DList back to a Cons list – by passing in the empty list null. Try it below:


    
// Cons list implementation
const cons = (val, next) => ({ val, next })
const append = (c1, c2) => {
    if (!c1) return c2
    return cons(c1.val, append(c1.next, c2)) // recursively copies c1 nodes
}

// convert  Cons List -> DList
const rep = consList1 => (consList2 => append(consList1, consList2))

// convert  DList -> Cons List
const abs = DList => DList(null)

// create a Cons list and its DList equivalent
const cl1 = cons(1, cons(2, cons(3)))
const dl1 = rep(cl1)
console.log(typeof dl1) // 'function'

// convert from the DList back to a Cons list
const cl2 = abs(dl1)
console.log(cl2) // { val: 1, next: { val: 2, next: { val: 3, next: null }}}

Or in Haskell:

-- (:) is Cons, ([]) is empty list "Nil"
-- [1, 2, 3] is a Cons list (1 : 2 : 3 : [])
-- (++) is append

type DList a = [a] -> [a]

repr :: [a] -> DList a
repr cl = (cl ++)

abst :: DList a -> [a]
abst dl = dl []

cl1 = [1, 2, 3]

dl1 = repr cl1
cl2 = abst dl1

main :: IO ()
main = print (cl1 == cl2) -- True

The "trick" is that a DList function captures the passed-in Cons list used to construct it via closure. So a DList "contains" a Cons list, which can be recovered by applying the DList.

Constant Time Append

Once again, Hughes introduces the killer feature of DLists with little fanfare:

The new representation is interesting because two representations can be appended together by composing them as functions, so we can define

appendR f g = f · g

(Function composition is written using a dot in KRC.)

Function composition is the act of creating a new function which connects the output of function g to the input of function f. In JS:

const compose = (f, g) => (x => f(g(x))
//              \    /    \           /
//               ————      ———————————
//                |             |
//           input funcs     the composition (a fn)

Notice that function composition returns a new function but it does NOT invoke either f or g to do so. Rather, the resulting composition when applied calls g and then f in that order. So regardless of how expensive f or g are, the act of composing them is free – that is, constant time. Actually using the composition will still be expensive, however.

//                   O(1)   O(f) + O(g)
//                   ————   ———————————
//                     |     |
const compose = (f, g) => (x => f(g(x)))

How does this apply to DLists? Since DLists are functions, they can be composed together in constant time… and the result is a new DList:


    
// Cons list implementation
const cons = (val, next) => ({ val, next })
const append = (c1, c2) => {
    if (!c1) return c2
    return cons(c1.val, append(c1.next, c2)) // recursively copies c1 nodes
}

// convert  Cons List -> DList
const rep = consList1 => (consList2 => append(consList1, consList2))

// convert  DList -> Cons List
const abs = DList => DList(null)


    
// 'cons', 'append', 'rep', and 'abs' in scope

const compose = (f, g) => (x => f(g(x)))

const c12 = cons(1, cons(2, null))
const c34 = cons(3, cons(4, null))

const d12 = rep(c12)
const d34 = rep(c34)

// O(1)
const d1234 = compose(d12, d34)

// O(n)
const c1234 = abs(d1234)

console.log(c1234)

-- in Haskell:
c12 = [1, 2]
c34 = [3, 4]

d12 = repr c12
d34 = repr c34

d1234 = d12 . d34

main = print (abst d1234) -- [1, 2, 3, 4]

How does this work? Hughes lays out a short and clear logical proof in his paper, but we can informally note that since a DList prepends its internal list, composing two DLists is a function which first prepends the right list, then prepends the left list, to whatever list is passed in:

DListA:                   DListB:
prepend (<a> -> <b>)      prepend (<c> -> <d>)

DListC = (DListA · DListB):
prepend (<c> -> <d>) then prepend (<a> -> <b>)

abs DListC (i.e., apply DListC to Nil):
prepend (<c> -> <d>) to Nil
then prepend (<a> -> <b>) to the above
result is (<a> -> <b> -> <c> -> <d>)

The careful reader will probably have some concerns at this point. As Hughes notes:

Function composition is an efficient operation. It can always be performed in constant time, so it remains to be shown that abs is reasonably efficient.

Provided that a 'functional list' is built using only rep and appendR, abs can convert it into an ordinary list in time proportional to its length.

This seems like a cheat. Sure, DLists can be composed in O(1) time, but we still need O(n) time to convert a Cons list to a DList or vice-versa! What's the point?

The answer is that functions are lazy. The code "inside" of a DList – the body of the function, containing the append operation – does not execute just because a DList is constructed. And we can build a DList without starting from a Cons list!


    
// Cons list implementation
const cons = (val, next) => ({ val, next })
const append = (c1, c2) => {
    if (!c1) return c2
    return cons(c1.val, append(c1.next, c2)) // recursively copies c1 nodes
}

// convert  Cons List -> DList
const rep = consList1 => (consList2 => append(consList1, consList2))

// convert  DList -> Cons List
const abs = DList => DList(null)


    
// 'cons', 'append', 'rep', and 'abs' in scope

// O(1) creation of two DLists: remember, function body does not run YET
const d12 = c2 => append(cons(1, cons(2, null)), c2)
const d34 = c2 => append(cons(3, cons(4, null)), c2)

const compose = (f, g) => (x => f(g(x)))
const appendD = compose

const d1234 = appendD(d12, d34)

-- Haskell
d12 = \c2 -> [1, 2] ++ c2
d34 = \c2 -> [3, 4] ++ c2

d1234 = d12 . d34

In the above example, no actual Cons list was ever constructed. Two functions that could produce Cons lists were defined, but neither function body actually ran, so the runtime cost remained hypothetical. Yet we defined a new DList which represents the concatenation of the two hypothetical Cons lists, and all of this in constant time.

Converting this list back down to a Cons list does take linear time, of course.

// JS: O(n)
d1234(null) // cons(1, cons(2, cons(3, cons(4, null))))

-- HS: O(n)
d1234 [] -- [1, 2, 3, 4]

When abs applies such a function to the empty list to convert it back into an ordinary list, it computes

append L1 (append L2 … (append Ln []) …).

The cost of computing (append A B) is independent of B—it is just the length of A. Therefore, the cost of computing the expression above is the sum of the lengths of L1,L2,…,Ln, that is, the length of the final list.

And that is one of the primary tradeoffs of the DList: if you expect to perform many append operations, and only need the final result at the very end, a DList can prevent duplicate work; often this will reduce an overall O(n^2) algorithm to O(n).

Reverse

"A Novel Representation of Lists" is just the first half of this paper's title; the second half is "and its Application to the Function 'Reverse'". Hughes uses a naive singly-linked list reverse function to illustrate an O(n^2) algorithm which can be improved via DLists.

// JS
const reverse = cl => {
    if (!cl) return cl
    return append(reverse(cl.next), cons(cl.val, null))
}

-- Haskell
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

Consider the the following pseudocode expansion of the reverse call on a cons list [1, 2, 3, 4]:

reverse [1, 2, 3, 4]

// recursive applications of reverse
append(reverse [2, 3, 4], [1])
append(append(reverse [3, 4], [2]), [1])
append(append(append(reverse [4], [3]), [2]), [1])

// sequential applications of append
append(append(append([4], [3]), [2]), [1])
  - append(append([_, 3], [2]), [1])
  - append(append([4, 3], [2]), [1])
append(append([4, 3], [2]), [1])
  - append([_, _, 2], [1])
  - append([_, 3, 2], [1])
  - append([4, 3, 2], [1])
append([4, 3, 2], [1])
  - [_, _, _, 1]
  - [_, _, 2, 1]
  - [_, 3, 2, 1]
  - [4, 3, 2, 1]

Because a Cons list append is proportional to the left list length, and as we keep building up a bigger and bigger list, we end up performing the same work. append takes an average of O(n/2) time, and we do it for n elements, resulting in O(n^2) time overall.

Using DLists, we switch to an O(1) append:


    
// Cons list implementation
const cons = (val, next) => ({ val, next })
const append = (c1, c2) => {
    if (!c1) return c2
    return cons(c1.val, append(c1.next, c2)) // recursively copies c1 nodes
}

// convert  Cons List -> DList
const rep = consList1 => (consList2 => append(consList1, consList2))

// convert  DList -> Cons List
const abs = DList => DList(null)

// DList append
const compose = (f, g) => (x => f(g(x)))
const appendD = compose


    
// 'cons', 'append', 'rep', 'abs', and 'appendD' in scope

// Cons List -> reversed Cons List
const reverse = consList => {
    return abs(rev(consList))
}

// Cons List -> reversed DList
const rev = consList => {
    if (!consList) return (c2 => c2) // O(1) empty DList, prepends nothing
    return appendD(                  // O(1) append (function composition)
        rev(consList.next),          // O(n) recursive reversal
        c2 => cons(consList.val, c2) // O(1) DList of one value
    )
}

const c1234 = cons(1, cons(2, cons(3, cons(4, null))))
const c4321 = reverse(c1234) // O(n)

console.log(c4321)

-- Haskell

reverseC :: [a] -> [a]
reverseC c = abst (rev c)

rev :: [a] -> DList a
rev [] = id
rev (x:xs) = (rev xs) . (x :)

main = print (reverseC [1, 2, 3, 4]) -- [4, 3, 2, 1]

Conclusion

It should be noted that this is not the only way to define an efficient reverse function; this problem is used mostly as a small, familiar example to illustrate how DLists work. The DList solution generalizes a hand-coded tail-recursive reverse:

const reverse = initList => {
    const go = (oldList, newList) => {
        if (!oldList) return newList
        const newerList = cons(oldList.val, newList)
        return go(oldList.next, newerList)
    }
    return go(initList, null)
}

Or using foldl in Haskell:

reverse :: [a] -> [a]
reverse = foldl (flip (:)) []

Hughes also goes on to demonstrate another use case for DLists, breaking up a line of text (in the form of a list of characters) into words (separated by a space).

The paper finishes with some notes regarding performance – namely, that a hand-coded efficient reverse was faster than using DLists, but of course DLists were significantly faster than the naive approach. At the time of publication (1986), DLists were found to have a practical performance improvement for certain applications.

What about DLists today? As the popular Haskell package dlist notes:

Difference lists are a list-like type supporting O(1) append. This is particularly useful for efficient logging and pretty printing (e.g. with the Writer monad), where list append quickly becomes too expensive.

That package hides the clever yet tiny implementation of DLists behind an easy-to-use API; similar work could be done easily enough in JavaScript.

The dlist README has links to additional interesting resources on the subject. Ultimately I think that the DList implementation is worth examining because it show how representing data lazily, as a function, can unlock new and surprising capabilities. This shows up in other functional representations, such as Church encodings.

Hughes's paper is a small 4-page gem, and this article is… not. Hopefully however it makes the idea more accessible to a typical JavaScript programmer. If so, I may add more entries to this series in the future.

Property Testing with JSVerify · Part III

Gabriel Lebec — Mon, 25 Mar 2019 02:25:18 +0000

Part III: Intermediate JSVerify Usage

In Part I, we explored the concept of property testing and saw basic JSVerify usage.
In Part II, we took a detailed look at the language of JSVerify's README, including the meaning of types like generator, shrink, and arbitrary.
Armed with both conceptual knowledge and library-specific jargon, we are now ready to take a deeper dive into using JSVerify.

Using Built-In Arbitraries

JSVerify features a string-based Domain-Specific Language (DSL) documented here for describing the desired arbitrary data you want to test. The simplest possible examples use built-in primitive arbitraries by name.

// a dummy property used to produce example output
jsc.assert(jsc.forall(
    'integer', 'nat', 'number', 'bool', 'falsy', 'char',
    (int, nat, num, bool, fls, chr) => {
        console.log(int, nat, num, bool, fls, chr)
        return true
    }
))

`int`	`nat`	`num`	`bool`	`fls`	`chr`
`6`	`4`	`-5.293295592069626`	`false`	`''`	`´`
`-3`	`6`	`6.371534138917923`	`false`	`false`	`"`
`-6`	`2`	`6.8075778381899`	`false`	`NaN`	`-`
`5`	`2`	`0.37970419274643064`	`false`	`null`	`ø`
`-1`	`6`	`-8.00378399901092`	`true`	`0`	`\u001e`
`-5`	`3`	`11.162152161821723`	`true`	`false`	`n`
`4`	`4`	`-8.52733048191294`	`false`	`NaN`	`Z`
`14`	`12`	`-20.764524302445352`	`false`	`undefined`	`' '`
`4`	`14`	`-2.3603379679843783`	`false`	`undefined`	`«`
`...`	`...`	`...`	`...`	`...`	`...`

Note, however, that using the DSL is optional; the functions the DSL refers to are available for direct use, and are also valid inputs to forall.

// equivalent to previous example
jsc.assert(jsc.forall(
    jsc.integer, jsc.nat, jsc.number, jsc.bool, jsc.falsy, jsc.char,
    (int, nat, num, bool, fls, chr) => {
        console.log(int, nat, num, bool, fls, chr)
        return true
    }
))

Some of the built-in primitive arbitraries are parameterized – they act as functions with parameters, for things like min and max bounds or to choose from an array of options. Expressing this using the string DSL can be tricky or unsupported, however. In such cases it is often easier to use the ordinary JS function equivalent:

// a dummy property used to produce example output
jsc.assert(jsc.forall(
    jsc.integer(-2, 2), jsc.nat(5), jsc.elements([true, null]),
    (int, nat, trueOrNull) => {
        console.log(int, nat, trueOrNull)
        return true
    }
))

`int`	`nat`	`trueOrNull`
`2`	`2`	`true`
`2`	`1`	`null`
`-1`	`5`	`null`
`1`	`5`	`true`
`0`	`0`	`null`
`...`	`...`	`...`

Combinators: Deriving New Arbitraries from Existing Arbitraries

We have seen:

atomic ("primitive") arbitraries, e.g.
- jsc.bool : arbitrary bool
- jsc.integer : arbitrary integer
functions which map vanilla values to arbitraries, e.g.
- jsc.integer(min: integer, max: integer) : arbitrary integer
- jsc.elements(args: array a): arbitrary a

The next level in this hierarchy would be:

functions which take arbitraries and return new arbitraries, e.g.
- jsc.array(arb: arbitrary a): arbitrary (array a)
- dict(arb: arbitrary a): arbitrary (dict a)

This kind of library design is known as the combinator pattern, and is a powerful yet concise way to build up complex functionality. Given a variety of primitive values and a selection of combinators, new values can be produced that can be fed back into those combinators, and so on – a self-reinforcing loop which creates a combinatorial explosion of possibilities.

We have already seen one example combinator: the jsc.array function takes an arbitrary (e.g. jsc.nat) and returns a new arbitrary (which generates arrays of that arbitrary value).

jsc.forall(
    '[nat]', jsc.array(jsc.nat), // these are both equivalent
    (arrayOfNats1, arrayOfNats2) => { /* use generated values */ }
)

`arrayOfNats1`	`arrayOfNats2`
`[7, 40, 4, 2]`	`[18, 40, 15, 6]`
`[11]`	`[26]`
`[]`	`[]`
`[]`	`[14, 13, 17, 12]`
`[3]`	`[3, 6, 5]`
`...`	`...`

Since the return value of jsc.array is itself an arbitrary, it can become the input to jsc.array again, to yield arrays-of-arrays:

jsc.forall(
    '[[nat]]', jsc.array(jsc.array(jsc.nat)), // again, equivalent
    (arrArrNat1, arrArrNat2) => { /* use generated values */ }
)

`arrArrNat1`	`arrArrNat2`
`[ [], [ 2, 10 ] ]`	`[ [ 1 ] ]`
`[ [ 10, 26, 9, 7 ] ]`	`[]`
`[ [ 22, 3, 17, 16 ], [ 13 ], [ 0, 23 ] ]`	`[ [ 5, 10, 18, 4, 17 ], [ 17, 21 ] ]`
`...`	`...`

At this point we can begin to see why JSVerify includes a string-based DSL for specifying input types. '[[nat]]' is much more concise than jsc.array(jsc.array(jsc.nat)). On the other hand, method calls can be typed (e.g. for TypeScript), don't require learning a new syntax, and are a superset of what is possible with the DSL.

Some more examples of combinators are demonstrated below:

Combinator	String DSL Form	Method Call Form	Two Example Generated Values
`pair`	`'pair nat bool'`	`jsc.pair(jsc.nat, jsc.bool)`	① `[4, false]` ② `[0, true]`
`tuple`	`'nat & nat & bool'`	`jsc.tuple([jsc.nat, jsc.nat, jsc.bool])`	① `[0, 18, true]` ② `[9, 2, true]` (all types will be used per generation)
`sum`	`'char ¦ nat ¦ bool'`	`jsc.sum([jsc.char, jsc.nat, jsc.bool])`	① `9` ② `'h'` (a random type will be chosen per generation)
`fn`	`'a -> bool'`	`jsc.fn(jsc.bool)`	① a function which maps `1` to `true`, `'hi'` to `false`, `null` to `true`… ② a function which maps all inputs to `false`…
`record`	`'{ name: asciinestring; age: nat }'`	`jsc.record({ name: jsc.asciinestring, age: jsc.nat })`	① `{ name: 'KUW<.', age: 0 }` ② `{ name: '^L', age: 37 }`

⚠️ (NB: for the sum type, we have substituted the "broken bar" symbol ¦ for the pipe character | because Markdown syntax uses the pipe character in tables.)

Putting it all together, you can specify reasonably complex arbitrary data with a minimal amount of work. And if your property fails, the failing input case can be automatically shrunk by JSVerify.

jsc.forall(
    '[{ start: integer & integer; end: integer & integer }]',
    (lineSegments) => { /* use generated values */ }
)

`lineSegments`
`[ {start: [26, 6], end: [20, -4]} ]`
`[]`
`[ {start: [11, -6], end: [-14, 8]}, {start: [-14, -15], end: [11, -15]} ]`
`...`

Transforming Arbitraries

With the supplied primitive arbitraries and combinators, you can do a lot, but not everything. As a very small example, what if very specifically want arbitrary even natural numbers? One strategy is to start with something close (integers) and transform them inside your property:

jsc.assert(jsc.forall(
    'integer',
    (integer) => {
        const evenInt = integer * 2
        return funcThatUsesEvens(evenInt) === 'cool'
    }
))

This works (for some problems), but has a downside: if we ever encounter a failure, the failing input case that is logged is pre-transformation.

Error: Failed after 13 tests and 9 shrinks. rngState: 93bc7e5e6160384cf8;
Counterexample: 7

What we would really like is a value of type arbitrary even, so the failing cases are the even numbers fed into our function under test. JSVerify gives the capability to transform an existing arbitrary into a new arbitrary via the .smap (surjective map) prototypal method:

.smap(f: a -> b, g: b -> a, newShow: (b -> string)?): arbitrary b

In other words, given arbA : arbitrary a, you can create a transformed arbB : arbitrary b by providing (at least) two functions:

f: a -> b is a function that transforms the input case to the form you desire
g: b -> a is a function that maps derived values back to the original type (necessary for shrinking)

Applied to our example of even numbers:

// arbitrary even
const arbEven = jsc.integer.smap(
    n => n * 2, // function to transform integer numbers to evens
    e => e / 2  // function to map even numbers back to integers
)

jsc.assert(jsc.forAll(arbEven, e => {
    return funcThatUsesEvens(e) === 'cool'
}))

As the docs note, the first function passed to smap should be surjective. If you "map back" your derived value x using the second function, then the first function should bring you back to x exactly. That is, f(g(x)) always equals x.

With our arbitrary even type implemented, our failures now show actual even numbers which fail:

Error: Failed after 13 tests and 9 shrinks. rngState: 93bc7e5e6160384cf8;
Counterexample: 14

Defining Custom Arbitraries from Scratch

In Part II, we saw an example generator, shrink, and show function for a hypothetical "hydra"-type value.

const generatorHydra = (size) => {
    const hydra = { heads: size ** 2 }
    return hydra
}

const shrinkHydra = (hydra) => {
    if (hydra.heads <= 0) return []
    return [{ heads: hydra.heads - 1 }] // valid but inefficient
}

const showHydra = (hydra) => `{ heads: ${hydra.heads} }`

Together, these three functions almost make up the complete manual definition of a custom arbitrary hydra value.

const almostArbitraryHydra = {
    generator: generatorHydra,
    shrink: shrinkHydra,
    show: showHydra
}

However, there is one bit of spice we need to apply before this can actually be used in JSVerify as an arbitrary hydra. JSVerify assumes that generators, shrinks, and arbitraries will have certain methods – for example, arbitraries will have .smap as shown earlier. In order to add these methods to your own from-scratch arbitraries, JSVerify provides three helper functions named bless.

const arbitraryHydra = jsc.bless({
    generator: jsc.generator.bless(generatorHydra),
    shrink: jsc.shrink.bless(shrinkHydra),
    show: showHydra
})

jsc.bless(arbLike: {...}) : arbitrary a
jsc.generator.bless(genLike: (size: nat) -> a) : generator a
jsc.shrink.bless(shrinkLike: a -> [a]) : shrink a
(there is no bless for show – it doesn't need it)

The bless functions "upgrade" pseudo-generators / pseudo-shrinks / pseudo-arbitraries into bona-fide full versions suitable for use by e.g. jsc.forall.

With our holy hydra fully evolved, we can use it in a property:

jsc.assert(jsc.forAll(hydra, (h) => {
    return h.heads >= 0
}))

If we wanted to refer to the hydra arbitrary by name using the String DSL, we would add it to a namespace object and pass in that map as our penultimate env argument to forall:

const env = { hydra: hydra }

jsc.assert(jsc.forAll('hydra', env, (h) => {
    return h.heads >= 0
}))

Deriving Generators

When defining new arbitraries, it was sometimes useful to start with existing arbitraries and use either combinators (like array) or transformations (like smap) on them. Similarly, when defining our own generators, it is sometimes useful to start with an existing generator.

Generator Combinators

Some of the same combinators exist for generators as for arbitraries. For example:

jsc.generator.array(gen: generator a): generator (array a)
- "given a generator of a, the array method returns a generator for arrays of a"
jsc.generator.tuple(gens: (generator a, generator b...)): generator (a, b...)
- "given an array of generators for a, b, etc., the tuple method returns a generator for arrays of form [a, b] etc."

// (size: nat) -> [char, [nat], bool]
const generatorCharNatsBool = jsc.generator.tuple([
    jsc.char.generator,
    jsc.generator.array(jsc.nat.generator),
    jsc.bool.generator
])
// example outputs:
// ['h', [0, 3], true]
// ['#', [91, 3, 84], false]

Note that generator combinator methods live on jsc.generator.COMBINATOR_NAME whereas existing generators for a primitive can be found as jsc.PRIMITIVE_NAME.generator.

Transforming Generators

Transforming a generator is easier than transforming a full arbitrary. With an arbitrary value, smap needed a pair of functions – one to derive data, and one to map derived data back to the original type. Generators have a map method which just needs the transformer:

(gen: generator a).map(f: a -> b): generator b

// (size : nat) -> nat
const evenGenerator = jsc.generator.nat.map(n => n * 2)
// example outputs:
// 12
// 0
// 54

const yellGenerator = jsc.generator.string.map(s => s + '!')
// example outputs:
// '!'
// 'c><92&X.!'
// 's'72$!'

Given a generator of a-type values, and a transforming function a -> b, the map method will give you a generator of b-type values.

As a side note: this is precisely the type needed to define a functor – a structure which can be mapped over. Just like arrays can be mapped (transforming the values in the array, but leaving the array structure alone), generators can be mapped (transforming the output of the function, but leaving its function nature / input type alone). Functors show up extensively in functional programming, but you don't need to know their theory in order to use map.

Dependently-Generated Values

Let's consider something more challenging – a generator customized by other generators. As an example, we might want to generate both a nonempty array of values, and a random index on that array, e.g. to pass into includes.

for all a ∈ Array x | a.length > 0,
    for all i ∈ Nat | i < a.length,
        a.includes(a[i])

We know how to generate arbitrary nonempty arrays, e.g. jsc.nearray(jsc.bool).
We know how to generate arbitrary naturals with a max size, e.g. jsc.nat(8).

What we haven't seen yet is how to make the input of one generator (e.g. nat) rely on values from the output of another generator (e.g. nearray). As a first attempt, something like map seems promising:

// Will not work
const genArrIdx =
    jsc.generator.nearray(jsc.bool.generator) // gen [bool]
        .map(arrBools => { // [bool] ->
            const maxIdx = arrBools.length - 1
            const arbIdx = jsc.nat(maxIdx)
            return arbIdx.generator // gen nat
        }) // -> gen (gen nat)

Unfortunately, this does quite not work – we have actually created a generator of (generator of nat). Consider this analogous example of returning an array from array map:

const result =
    [1, 2, 3] // array int
        .map(num => { // int ->
            return [num, num] // array int
        }) // -> array (array int)

console.log(result) // [[1, 1], [2, 2], [3, 3]]

Just as mapping an array to arrays returns a nested array, mapping a generator to generators returns a nested generator. To un-do this nesting, we need a new function, .flatMap.

// Almost there…
const genArrIdx =
    jsc.generator.nearray(jsc.bool.generator)
-       .map(    arrBools => {
+       .flatMap(arrBools => {
            const maxIdx = arrBools.length - 1
            const arbIdx = jsc.nat(maxIdx)
            return arbIdx.generator // gen nat
-       }) // -> gen (gen nat)
+       }) // -> gen nat

This gives us a generator nat with no nesting. But as you may recall, we really wanted an array alongside a randomly-generated valid index on that array, not just the index alone. To solve this, we can use an inner map to combine our two results:

// Works
const genArrIdx =
    jsc.generator.nearray(jsc.bool.generator)
        .flatMap(arrBools => {
            const maxIdx = arrBools.length - 1
            const arbIdx = jsc.nat(maxIdx)
            return arbIdx.generator
+               .map(idx => {
+                   return [arrBools, idx]
+               }) // -> gen [array bool, nat]
-       }) // -> gen nat
+       }) // -> gen [array bool, nat]

A bit more tersely, and with JS syntax highlighting:

// generator [array bool, nat]
const genArrIdx =
    jsc.generator.nearray(jsc.bool.generator).flatMap(arrBools => {
        const maxIdx = arrBools.length - 1
        const arbIdx = jsc.nat(maxIdx)
        return arbIdx.generator.map(idx => [arrBools, idx])
    })

The flatMap method is just like map except the function passed to it should return generators of values rather than just plain values. Where map would produce a nested generator, flatMap removes the nesting.

(generator a)    .map(a ->            b ) : generator b
(generator a).flatMap(a -> (generator b)) : generator b

As a side note: this is precisely the type needed to define a monad – a structure which can be un-nested after mapping. Like functors, monads show up often in functional programming, though again all you really need to know practically for this library is "return a generator in the function passed to flatMap".

Technically, flatMap is just a convenience method. We could have defined our array+index generator manually as follows:

const genArrIdx =
    jsc.generator.bless((size) => {
        // create and use array generator:
        const genArrBool = jsc.generator.nearray(jsc.bool.generator)
        const arrBools = genArrBool(size)
        const maxIdx = arrBools.length - 1
        // create and use index generator:
        const genIdx = jsc.nat(maxIdx).generator
        const idx = genIdx(size)
        // return resulting generated values
        return [arrBools, idx]
    })

Note how we pass the size parameter through all the generators ourself; flatMap handles this for us.

Regardless of which style (applying size or using flatMap) you prefer, when you sequence dependent generators you must write your own corresponding shrink function for the result. Shrinks aren't provided automatically, like they are with smap.

Writing Shrinks

Like full arbitrary a and lower-level generator a functions, shrink functions can be written from scratch or derived from existing shrinks. The derivation method is smap, like with arbitraries.

(shrink a).smap(f: a -> b, g: b -> a): shrink b

const shrinkEven = jsc.nat.shrink.smap(
    n => n * 2, // convert nat to even
    e => e / 2  // convert even to nat
)

console.log(shrinkEven(32)) // [ 16, 24, 28, 30 ]

Earlier, we defined our own generator [array bool, nat] function for constructing pairs of random arrays with random valid indexes (less than the array length). A corresponding shrink would have to preserve the property that the nat value remains a valid index. In this case, a first attempt might re-use existing shrinks:

// Looks good, but there is an error…
const shrinkArrIdx = jsc.shrink.bless(([arr, idx]) => {
    // shrink arrays, ensure valid index
    const shrinkArrBool = jsc.shrink.nearray(jsc.bool.shrink)
    const shrunkArrs = shrinkArrBool(arr)
    const shrunkArrsWithIdx = shrunkArrs.map((shrunkArr) => {
        const validIdx = Math.min(shrunkArr.length - 1, idx)
        return [shrunkArr, validIdx]
    })
    // shrink index, re-use existing array
    const shrunkIdxs = jsc.nat.shrink(idx)
    const shrunkIdxsWithArr = shrunkIdxs.map((shrunkIdx) => {
        return [arr, shrunkIdx]
    })
    // flat list of shrunk values? nope, this breaks:
    return [...shrunkArrsWithIdx, ...shrunkIdxsWithArr]
})

Unfortunately, this fails.

TypeError: shrunkArrsWithIdx is not iterable

How odd – doesn't a shrink function return an array? That's what the type annotation seems to promise:

"shrink is a function a -> [a], returning smaller values."

In reality, though, the array-based shrinks currently return lazy sequences as defined by the lazy-seq package, by the same author as JSVerify. This improves the performance of shrinking arrays, which could otherwise be combinatorially expensive.

Looking at the lazy-seq API docs, we can see that lazy sequences can be combined using an append method – so that's what we'll do here.

const shrinkArrIdx = jsc.shrink.bless(([arr, idx]) => {
    if (!arr.length) return []
    const shrinkArrBool = jsc.shrink.nearray(jsc.bool.shrink)
    const shrunkArrs = shrinkArrBool(arr)
    const shrunkArrsWithIdx = shrunkArrs.map((shrunkArr) => {
        const validIdx = Math.min(shrunkArr.length - 1, idx)
        return [shrunkArr, validIdx]
    })
    const shrunkIdxs = jsc.nat.shrink(idx)
    const shrunkIdxsWithArr = shrunkIdxs.map((shrunkIdx) => {
        return [arr, shrunkIdx]
    })
-   return [...shrunkArrsWithIdx, ...shrunkIdxsWithArr]
+   return shrunkArrsWithIdx.append(shrunkIdxsWithArr)
})

This is not yet documented in JSVerify, so again be aware that the use of lazy-seq methods on shrunk arrays may not be officially supported or subject to SEMVER rules. Cf. issue #297

Putting It All Together

Below is a complete, working implementation of our relatively involved arbitrary <array bool, index>.

// generator <array bool, index>
const genArrIdx =
    jsc.generator.nearray(jsc.bool.generator).flatMap(arrBools => {
        const maxIdx = arrBools.length - 1
        const arbIdx = jsc.nat(maxIdx)
        return arbIdx.generator.map(idx => [arrBools, idx])
    })

// shrink <array bool, index>
const shrinkArrIdx = jsc.shrink.bless(([arr, idx]) => {
    // shrink arrays, ensure valid index
    const shrinkArrBool = jsc.shrink.nearray(jsc.bool.shrink)
    const shrunkArrs = shrinkArrBool(arr)
    const shrunkArrsWithIdx = shrunkArrs.map((shrunkArr) => {
        const validIdx = Math.min(shrunkArr.length - 1, idx)
        return [shrunkArr, validIdx]
    })
    // shrink index, re-use existing array
    const shrunkIdxs = jsc.nat.shrink(idx)
    const shrunkIdxsWithArr = shrunkIdxs.map((shrunkIdx) => {
        return [arr, shrunkIdx]
    })
    // lazy sequence of shrunk values
    return shrunkArrsWithIdx.append(shrunkIdxsWithArr)
})

// arbitrary <array bool, index>
const arbArrIdx = jsc.bless({
    generator: genArrIdx,
    shrink: shrinkArrIdx
})

The moral of the story here might be "arbitraries whose generators sequence other generators are more trouble than they are worth." Of course, it will depend on the actual problem at hand, and in practice, it seems that such sequenced generators are not often needed. Much of the time, a new arbitrary value can be derived using smap. Also, strictly speaking an arbitrary may omit the shrink, but that reduces the usefulness of property testing to an extent. Ultimately it is up to the developer to weigh the options.

Summary

Arbitraries: "blessed" objects with generator, shrink, and show fns
- JSVerify ships with a selection of primitive (atomic) arbitraries like jsc.nat.
- Combine arbitraries into more complex arbitraries using combinator functions like jsc.array.
- Transform arbitraries into new arbitraries using the .smap method.
- Define custom arbitraries from complete scratch by using the jsc.bless method on an object wrapping a generator, shrink, and optional show function.
- Arbitraries can be passed in directly to forall, or else referenced by string DSL name with the help of an env argument.
Generators: "blessed" functions from size to pseudorandom data
- The generators for built-in arbitraries can be accessed as jsc.ARB_NAME.generator.
- Combine generators using provided combinators such as jsc.generator.array.
- Transform generators using the map method.
- Sequence generators using the flatMap method.
- Define custom from-scratch generators by calling jsc.generator.bless on a function from size to random data.
- Randomness in a from-scratch generator should be accomplished using jsc.random and/or by calling existing generators with the size.
Shrinks: "blessed" functions from data to a collection of smaller data
- The shrinks for built-in arbitraries can be accessed as jsc.ARB_NAME.shrink.
- Combine shrinks using provided combinators such as jsc.shrink.array.
- Transform shrinks using the smap method.
- Define custom from-scratch shrinks by calling jsc.shrink.bless on a function from data to arrays (or lazy-seq values) of "smaller" values.
- A good shrink should put small and/or likely-to-fail values near the start of the output collection.
Shows: functions from data to a string
- The default show function is JSON.stringify
- It is good practice, though not absolutely required, for a show function to output valid JS code

Using existing arbitrary values is quick, easy, and powerful on its own. Combinators and smap can also sometimes be a relatively painless way to yield the arbitrary value desired. More advanced use cases, building up complex data with interdependencies, can require more fluent wielding of flatMap and/or manual definition of the shrink function. However, the benefits of having a fully-defined arbitrary for your property tests might be worth the extra difficulty.

At its best, property testing can provide a large amount of value and confidence for a small degree of effort and code. It is my hope that with greater knowledge of this approach in the JavaScript community, libraries like JSVerify may be more widely explored, maintained, extended and supported. Consider using JSVerify to augment your next project's test suite – you might find it catching mistakes you wouldn't have noticed with just a few unit tests.

Addendum

In the process of writing this article, I came to appreciate that JSVerify is useful but also has a few rough edges and outstanding issues. I would encourage anyone interested in JS property testing to also take a look at some of the competing tools in this space, including:

Property Testing with JSVerify · Part II

Gabriel Lebec — Mon, 25 Mar 2019 02:21:31 +0000

Part II: JSVerify Docs and Details

In Part I we explored what property checking is, its benefits over traditional unit testing, and saw some of the basics of using the JSVerify library.

JSVerify's official description is "Property-based checking. Like QuickCheck." Since QuickCheck is a Haskell library, JSVerify uses functional jargon and idioms that may be unfamiliar to JavaScript developers. In Part II, we take a close look at the language and concepts of JSVerify's API documentation.

Type Documentation

Functional programming and static types are highly complementary. Type signatures specify sets of allowed inputs and resulting outputs for a given function, which in turn inform the programmer how functions can be used and combined.

In the JSVerify docs, "types and function signatures are written in Coq/Haskell-influenced style". One of the best explanations of Haskell-style type signatures in JS is the Ramda Wiki. However, JSVerify's style differs somewhat from Ramda, so below is a short introduction to its particular type syntax.

Documentation	Meaning
`x : y`	`x` is of type `y` / must be of type `y` / returns type `y`
`myFunc( )`	A library method with the name `myFunc`
`myFunc(thing: string) : bool`	`myFunc` takes a parameter `thing` which must be a `string`, and returns a `bool`
`a`	any type at all, so long as it consistent with other "`a`"s in the type signature
`a -> [a]`	A (possibly-anonymous) function which takes in a param of any type `a` and returns an array of `a`-type values
`a -> array a`	Same as above
`a -> b`	A function which takes in params of any type `a` and returns values of any type `b` (possibly the same as `a`)
`message: string?`	An optional parameter `message` that must be a `string`
`...`	a variadic number of additional arguments or elements
`= true`	a default value for the preceding parameter
`arbLike: {…}`	a parameter `arbLike` which must be an Object
`{ b: bool }`	an object whose `b` property is of type `bool`
`void`	`undefined`

Here is an actual line from the documentation, for example:

assert(prop: property, opts: checkoptions?) : void
  ^      ^       ^       ^         ^     ^      ^
  A      B       C       D         E     F      G

A. documenting the `jsc.assert` function
B. first parameter, named `prop`
C. `prop` must be of type `property` (see below)
D. second parameter, named `opts`
E. `opts` must be of type `checkoptions` (see below)
F. `opts` is an optional parameter
G. `jsc.assert` returns `void` (i.e. `undefined`)

Key JSVerify Types

The property and checkoptions types above certainly don't sound like the more familiar string, bool, etc. In typed functional languages, we often invent our own types as needed to be concise yet unambiguous about which functions work with which values.

Vanilla JS doesn't have a first-class notion of custom types. However, JSVerify's docs use custom type names as aliases for the specific values returned from or expected by certain functions. Below are some of the most important examples.

`generator a`

"a function (size: nat) -> a"

A generator of type a is any function mapping a "size" (natural number, int >= 0) to a pseudorandom value of type a. For example, a function of type generator string might map 0 to the empty string, 1 to a randomly-chosen character, and 2 to a randomly-constructed two-character string.

In reality, the size input can be interpreted differently depending on the generator, and does not have to literally mean length or value. Some examples:

jsc.generator.array: the length of generated arrays will be up to the logarithm of the size param. This is presumably a performance-related restriction.
jsc.number.generator: size is the maximum absolute value, e.g. a size of 5 could result in any number between -5 and +5.
jsc.bool.generator: the size parameter is ignored, and each bool is returned at a probability of 0.5.

// example `generator hydra`
const generatorHydra = (size) => {
    const hydra = { heads: size ** 2 }
    return hydra
}

Deterministic Randomness

A major feature of QuickCheck-like property testing libraries is that they are deterministically pseudorandom. Given a seed string (via the options object for jsc.assert, or the --jsverifyRngState CLI flag), they will reproduce failing test cases exactly, helping the developer to investigate the failure.

When implementing a custom generator, it is important to adhere to this implementation detail, and not use Math.random. JSVerify provides utility functions jsc.random and jsc.random.number instead, which internally use the seed to produce replicable results.

const randomGreetingGenerator = (ignoredSize) => {
    const pseudoRandomIndex = jsc.random(0, 2)
    return ['hi', 'yo', 'sup'][pseudoRandomIndex]
})

`shrink a`

"a function a -> [a], returning smaller values"

A shrink of type a is a function which given a value of type a returns an array of "smaller" values of type a. "Smaller" is an abstract concept which will vary for each type, but in general will mean fewer elements, numbers closer to zero, etc.

jsc.shrink.integer: if the input integer i is 0, the shrink returns an empty array []; else, i is mapped to the finite series [0, ⌊1/2·i⌋, -⌊1/2·i⌋, ⌊3/4·i⌋, -⌊3/4·i⌋, …].
jsc.bool.shrink: in essence, bool => bool ? [false] : []
jsc.elements.shrink: the elements generator returns randomly-selected values from an array, e.g. [a, b, c]; the elements shrink returns the sub array to the left of whatever element is being shrunk. Shrinking c would return [a, b]; shrinking a returns [].

// example `shrink hydra`
const shrinkHydra = (hydra) => {
    if (hydra.heads <= 0) return []
    // theoretically valid but impractically inefficient:
    return [{ heads: hydra.heads - 1 }]
}

When an input case fails a property check, JSVerify uses the shrink function to search for smaller cases that also fail. If JSVerify finds that an early value in the output array fails, it can skip property-checking and shrinking of the later values. Good shrinks therefore place small, likely-to-fail values near the start of their output:

// example `shrink hydra`
const shrinkHydra = (hydra) => {
    if (hydra.heads <= 0) return []
    // a more practical shrink:
    return [
        { heads: 0 }, // a common & minimal edge case
        { heads: Math.floor(hydra.heads * 1/2) }, // potential time-saver
        { heads: Math.floor(hydra.heads * 3/4) },
        { heads: Math.floor(hydra.heads * 7/8) },
        { heads: hydra.heads - 1 } // thorough search
    ]
}

`show`

"a function a -> string"

In Haskell, the show function converts any data structure in the Show class to a String. Best practice is for the string to be valid Haskell code, so you could reconstruct the data by copying the string into your program.

For JSVerify, show will be called whenever a failing case is reported, with the resulting string included in the error message as the counterexample.

jsc.show.array: essentially arr => '[' + arr.join(', ') + ']'
by default, most built-in show functions are just JSON.stringify

// example `show : hydra -> string`
const showHydra = (hydra) => `{ heads: ${hydra.heads} }`

Because failing cases can be replicated using the reported PRNG seed, it is not strictly necessary for show to return valid JS code, but it is often good practice for the same reasons as in Haskell.

`arbitrary a`

"a triple of generator, shrink and show functions."
{generator: nat -> a, shrink: a -> array a, show: a -> string}

An arbitrary value of type a is a concept tying together the generator, shrink and show functions for a type a. It is implemented in JSVerify via an object wrapping those three functions. For example, the abitrary string type is any object which can generate, shrink, and show strings on demand.

// example `arbitrary hydra`
const arbitraryHydra = {
    generator: generatorHydra,
    shrink: shrinkHydra,
    show: showHydra
}

In some contexts, the shrink and show functions are actually optional. Without a shrink, however, JSVerify will be unable to simplify failing cases; they will be reported as they are.

`property`

As of this writing, property is used in at least three distinct ways in the JSVerify docs:

to refer to the library method jsc.property
as the overall return type for jsc.forall (see Y below)
as the return type for the prop parameter of forall (see X below)

forall(
    arbs: arbitrary a ...,
    userenv: (map arbitrary)?,
    prop : a -> property       // X
): property                    // Y

Unfortunately, X and Y do not actually refer to the same type, so in my humble opinion the X type should be renamed verification. In the remainder of this article, a property type will refer to Y.

So what is this property type anyway? In short, forall acts as a "property constructor", and other methods like assert and check act as "property consumers". In terms of official JS types, the values returned by forall are of type function:

const prop_strSliceEql = jsc.forall('string', str => str.slice() === str)
console.log(typeof prop_strSliceEql === 'function') // true

However, it is not the role of the developer to manually invoke a property. Rather, property values will be passed to check or assert to actually use them.

// assert(prop: property, opts: checkoptions?) : void
jsc.assert(prop_strSliceEql) // runs without error

Being able to navigate type-based documentation, noting which function outputs and inputs line up, is a key skill in the typed functional programming world. It isn't actually necessary for us to know how property-type values are implemented, because they are an intermediate value both produced by and consumed by JSVerify library methods.

forall( ... ) → property
                   ↓
         assert(property, ...) → void

Verification (unofficial)

As mentioned above, the property returned from prop and the property returned from forall are not the same type, so for our purposes we will (informally) refer to the former as "verifications."

forall(
    arbs: arbitrary a ...,
    userenv: (map arbitrary)?,
-   prop : a -> property
+   prop : a -> verification
): property

Verification values can be any type at all, but JSVerify exhibits different behaviors depending on the type:

Verification	Behavior
`true`	property is considered verified
falsy values	property is considered failed
most truthy values	property is considered failed, with the value appended to the error message
thenable which fulfills	property depends on fulfillment value (see above)
thenable which rejects	property is considered failed, with the reason appended to the error message
function	property verification depends on function return value

Some of the above behaviors are not explicitly documented, and may act in unspecified or unintended ways depending on usage. Caveat emptor.

`checkoptions`

The options object optionally object passed to check or assert, used to configure number of tests run, the size parameter for generators, an rng seed, etc. Documented here.

`env` / `typeEnv` / `map arbitrary`

An optional argument to the following library methods:

forall
compile
assertForall
checkForall
record
suchthat

The env type is an object which maps names of arbitraries (as string keys) to definitions for arbitraries (as objects). For example:

const arbitraryHydra = {
    generator: generatorHydra,
    shrink: shrinkHydra,
    show: showHydra
}

// : env
const env = {
    hydra: arbitraryHydra
}

Environment objects extend JSVerify's built-in DSL of arbitrary data (e.g. strings, numbers, arrays of arbitraries) with new, custom arbitraries. When you pass in an environment to forall, it is merged with the defaults, so you can specify any mix of data from both sets:

const exampleProp = jsc.forall(
    'nat',             // asking for built-in `arbitrary natural`
    'hydra',           // asking for custom `arbitrary hydra`
    env,               // object providing the `hydra` arbitrary
    (nat, hydra) => {  // property verifier receiving both data
        return hydra.heads + nat > 0
    }
)

(Note that the above example will not yet work, because we have not covered JSVerify's concept of "blessing" generators, shrinks, and arbitraries. We will cover the bless methods later in Part III.)

On the other hand, instead of using the string DSL, you can pass custom arbitraries to forall directly:

const exampleProp = jsc.forall(
    'nat',             // asking for built-in `arbitrary natural`
    arbitraryHydra,    // asking for custom `arbitrary hydra`
    (nat, hydra) => {  // property verifier receiving both data
        return hydra.heads + nat > 0
    }
)

We will see more about using the DSL vs. JS values in Part III.

Property Testing with JSVerify · Part I

Gabriel Lebec — Mon, 25 Mar 2019 02:19:21 +0000

Abstract: JSVerify is a JavaScript library for property-based testing, inspired by the classic Haskell library QuickCheck. JSVerify's API documentation appears to assume a certain level of familiarity with "type tetris" and functional idioms like monads. This article demonstrates the basics of the JSVerify library API, including how to create and use arbitrary values, data generators, and data shrinks, in ways that a typical JavaScript developer can understand.

Part I: What is Property Testing?

John Hughes, one of the original authors of QuickCheck, gives a compelling demonstration of the power of property tests in the following video. Watch if you wish, or read on – we will cover the essentials further below.

In short, property tests:

Specify expected laws (aka properties) for all intended inputs
Generate large numbers of random inputs to check, usually via a convenient DSL or API
Verify that the expected properties hold for all generated cases
Simplify failing cases progressively, to find a boundary that introduces the failure

Property testing is a form of evidence by example that code might be correct, or is definitely incorrect. It lies between the two extremes of unit tests (manually-specified individual cases) and formal machine-checked logic proofs (impractical in some languages or systems).

Unit Testing

Let's consider a small example. If we wanted to verify the correctness of a custom sort function, we might write a unit test in the form of a Chai assertion executed via the Mocha test framework:

describe('`sort`', () => {
    // unit test:
    it('transforms `[2, 1, 3]` to `[1, 2, 3]`', () => {
        expect(sort([2, 1, 3])).to.deep.equal([1, 2, 3])
    })
})

How confident are you that sort is correct? Probably not very. Sort could easily be broken without failing this test, if it:

merely swaps the first two elements
always returns [1, 2, 3]
fails on two-digit numbers (or higher)
fails on a list containing duplicate elements
fails on lists with only the first (or last) item out of order
fails on an empty list
fails on lists of even length

As humans, we tend to fall short of imagining every possible edge and corner case. This is partly because we make assumptions about how code will be used, focusing on the happy path. Writing multiple unit tests for each of the above would help, but is a lot of work for only a moderate increase in confidence that sort is generally correct.

Ad-Hoc Property Testing via Dynamic Assertions

When a programmer specifies that sorting [2, 1, 3] returns [1, 2, 3], they don't necessarily care about that one specific array. Rather, the point is to verify certain properties (characteristics) of sorting, such as:

sort results in an ordered array
sorting an already-sorted array does nothing (idempotence)
sort merely moves elements without addition, change, or removal

Such properties describe what actually matters conceptually, far more than any one specific case. Testing veterans will sometimes have developed ad-hoc techniques for confirming such concepts, for example by dynamically generating inputs and assertions.

const TESTS = 100
const LIMIT_LEN = 50
const LIMIT_NUM = 1000

const randomInt = () =>
    Math.floor(Math.random() * LIMIT_NUM)

const randomArr = () =>
    Array(Math.floor(Math.random() * LIMIT_LEN))
        .fill(null)
        .map(randomInt)

const isOrdered = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) return false
    }
    return true
}

describe('`sort`', () => {
    for (let t = 0; t < TESTS; t++) {
        it('outputs ordered arrays`', () => {
            expect(isOrdered(sort(randomArr())).to.equal(true)
        })
    }
})

This is a step in the direction of full-blown property testing, but if the spec fails, all we see is the following opaque message:

ERROR: expected `false` to be `true`

There are some nontrivial downsides to the above attempt:

a lot of ad-hoc code for generating random inputs
the randomArray function probably produced the empty list more than necessary (once suffices)
did you notice that the randomInt function never produces negative numbers? Oops!
failure is non-instructive, what input caused it?
what did sort actually return for that input?
if the random input which failed is large, which part of it actually caused the failure?
if the suite is run multiple times, randomness means we may never encounter that failure case again

Some of this can be mitigated, e.g. by writing custom Chai matchers (extra work), logging (polluting test output), or other means. However, some of these issues have already been addressed by property-testing systems.

First-Class Property Testing with JSVerify

Here is the same check for ordering, written using a dedicated generative testing library.

const jsc = require('jsverify')

const isOrdered = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) return false
    }
    return true
}

describe('`sort`', () => {
    it('outputs ordered arrays', () => {
        // property test:
        jsc.assert(jsc.forall('[integer]', (arr) => {
            return isOrdered(sort(arr))
        }))
    })
})

Note that we did not need to write our own randomInt and randomArr functions – JSVerify handled this for us. Breaking it down:

jsc.forall – the heart and soul of this library, it ties together data generators with a property-checking function; forall returns a "Property" value (meant to be used by other JSVerify functions).
- '[integer]' – a string declaration of what data we want JSVerify to generate, specifically an array of integers. JSVerify parses a Domain-Specific Language (DSL) for describing input data (more on this later).
- (arr) => { ... } – a function which will receive the randomly-generated data, responsible for verifying the expected property by returning true if that property holds.
jsc.assert – takes the "Property" returned by forall, and executes the logic it represents as an assertion (throwing an error on failure). This lets JSVerify integrate with test frameworks like Mocha.

Running this code gives us a more telling result:

Error: Failed after 7 tests and 3 shrinks. rngState: 86ac1d5e6093784bf2;
Counterexample: [2, 10]

Interesting! What does it all mean?

Error – Mocha is reporting that our assertion failed.
Failed after 7 tests – JSVerify generated six input cases before it discovered a seventh case that violated our property.
and 3 shrinks. – The failing counterexample could be simplified in three steps to reach a minimal failing counterexample (JSVerify actually took more steps than this, but who's counting?).
rngState: 86ac1d5e6093784bf2; – JSVerify uses a seed-based pseudo-random generator to produce values. Unlike Math.random(), we can deliberately use this seed to deterministically reproduce the failing test, if desired.
Counterexample: [2, 10]. JSVerify indicates that [2, 10] is the smallest input data it could find that failed our property check.

If we (temporarily) instrument our code as follows, we can investigate a bit deeper:

describe('`sort`', () => {
    it('outputs ordered arrays', () => {
        jsc.assert(jsc.forall('[integer]', (arr) => {
            const output = sort(arr)
            const ok = isOrdered(output)
+           console.log(
+               ok ? '✔️' : '❌',
+              'input:', arr,
+              'output:', output
+           )
            return ok
-       }))
+       }), {
+           rngState: '86ac1d5e6093784bf2'
+       })
    })
})

Note the second parameter to jsc.assert is an options object permitting us to manually set the pseudorandom seed, replicating the results we saw previously. (Alternatively, when using Mocha you can force the use of a particular rngState using --jsverifyRngState.) When this modified test is run, we see the following logged:

OK	Input	Output	Notes
✔️	`[]`	`[]`	JSVerify begins with "small" inputs.
✔️	`[2]`	`[2]`	The first six cases are all ok.
✔️	`[9]`	`[9]`	…
✔️	`[23]`	`[23]`	…
✔️	`[-9, 33, 33, 18, 31]`	`[-9, 18, 31, 33, 33]`	…
✔️	`[3]`	`[3]`	…
❌	`[20, 9, 10]`	`[10, 20, 9]`	Oops! Our property failed on the seventh case.
❌	`[9, 10]`	`[10, 9]`	JSVerify "shrinks" the array, but it still fails.
✔️	`[10]`	`[10]`	Shrunk again, but now the prop holds. Back up.
✔️	`[0, 10]`	`[0, 10]`	JSVerify shrinks the values in the array. `9` -> `0` is still ok.
❌	`[4, 10]`	`[10, 4]`	Halving `9` -> `4` fails, so shrinking restarts from here.
✔️	`[10]`	`[10]`	JSverify isn't perfect; we see some redundant checks.
✔️	`[0, 10]`	`[0, 10]`	…
❌	`[2, 10]`	`[10, 2]`	Halving `4` -> `2` fails again; shrink from here.
✔️	`[10]`	`[10]`	More redundant checks.
✔️	`[0, 10]`	`[0, 10]`	…
✔️	`[1, 10]`	`[1, 10]`	This time, `2` -> `1` results in a passing output.
✔️	`[-1, 10]`	`[-1, 10]`	What about negative ints? Still ok.
✔️	`[2]`	`[2]`	From here on, JSVerify does a logarithmic search of integers between `-10` and `10`.
✔️	`[2, 0]`	`[0, 2]`	…
✔️	`[2, 5]`	`[2, 5]`	…
✔️	`[2, -5]`	`[-5, 2]`	…
✔️	`[2, 7]`	`[2, 7]`	…
✔️	`[2, -7]`	`[-7, 2]`	…
✔️	`[2, 8]`	`[2, 8]`	…
✔️	`[2, -8]`	`[-8, 2]`	…
✔️	`[2, 9]`	`[2, 9]`	…
✔️	`[2, -9]`	`[-9, 2]`	No failures, so JSVerify concludes `[2, 10]` is a minimal counterexample.

This experiment demonstrates several clever aspects of JSVerify's shrinking procedure for arrays of integers:

It checks for both smaller arrays and smaller values in the array
It checks commonly-neglected edge cases like [], 0, and negative integers
It uses binary search for good performance

Diagnosing the Problem

Revisiting our original test, the combination of global it + jsc.assert(jsc.forall(...)) is common enough that JSVerify offers a property method for it. (Using this convenience method means you can no longer pass in the options object to assert, so keep that in mind.)

describe('`sort`', () => {
-   it('outputs ordered arrays', () => {
-       jsc.assert(jsc.forall('[integer]', (arr) => {
-           return isOrdered(sort(arr))
-       }))
-   })
+   jsc.property('outputs ordered arrays', '[string]', (arr) => {
+       return isOrdered(sort(arr))
+   })
})

Manually running our test suite (without fixing the PRNG seed) multiple times eventually generates at least two distinct minimal failing input cases for us to consider:

Error: Failed after 4 tests and 13 shrinks. rngState: 04214a57f39806becd;
Counterexample: [2, 10]
...
Error: Failed after 1 tests and 8 shrinks. rngState: 0092ae01573f6d84bc;
Counterexample: [-1, -2]
...

Sorting aficionados may already have figured out what's going on – like Array#sort, our sort operates lexicographically rather than numerically. If the developer didn't intuit this issue, they could manually trace the logic of their sorting function on these inputs, either on paper or using debugging tools. Since JSVerify "shrunk" the counterexamples, debugging them will be simpler than if the original failure was reported.

But Wait, There's More!™ Check Out This One Weird Trick™

There is (apparently undocumented, as of yet) a feature that can make failure reporting more informative. If you return anything other than a boolean from your property check, it is appended as a string to the error message. This lets us include the output (or anything else we care to log) upon failure.

jsc.property('outputs ordered arrays', '[string]', (arr) => {
    const output = sort(arr)
    return isOrdered(output)
+       ? true
+       : 'sort returned ' + JSON.stringify(output)
})

Error: Failed after 2 tests and 14 shrinks. rngState: 86fd6b284e01a5c793;
Counterexample: [2, 10]; Error: sort returned [10,2]

Summary & Try It Yourself

In this first part, we saw the fundamentals of generative testing and getting started with JSVerify. In Part II, we will explore the JSVerify API in greater depth. Before doing so, however, try using JSVerify yourself below:


    
const jsc = require('jsverify')

// https://en.wikipedia.org/wiki/De_Morgan%27s_laws
const deMorgansLawsHold = (p, q) => {
    theorem1 = !(p && q) === (!p || !q)
    theorem2 = !(p || q) === (!p && !q)
    return theorem1 && theorem2
}

// A correct property
const result1 = jsc.check(jsc.forall(
    jsc.bool, jsc.bool,
    deMorgansLawsHold
), { quiet: true }) // silences console logs

// An incorrect property
const result2 = jsc.check(jsc.forall(
    jsc.nearray(jsc.bool),
    (nonEmptyArrBools) => {
        const idxOfFalse = nonEmptyArrBools.indexOf(false)
        return (idxOfFalse >= 0)
            ? true
            : 'indexOf found false at: ' + idxOfFalse
    }
), { quiet: true })

// Predict! Is this property correct or incorrect? Try it and see…
const result3 = jsc.check(jsc.forall(
    '[json]', 'json',
    // jsc.array(jsc.json), jsc.json, // equivalent spec
    (arr, jsVal) => {
        const newArr = arr.concat(jsVal)
        return newArr.length === arr.length + 1
    }
), { quiet: true })

console.log("de Morgan's laws hold?", result1)
console.log("index of false in a nonempty array is at least 0?", result2)
console.log("concatenating on a random JS value increases length by 1?", result3)

Four Ways to Immutability in JavaScript

Gabriel Lebec — Wed, 13 Feb 2019 00:13:16 +0000

Abstract

This article presents four different techniques to immutably update data structures in JavaScript:

Natively, using spread syntax and other features
Via Ramda's lens abstraction
Via Michel Weststrate's immer library
Via Facebook's immutable library

Many of the code snippets are runnable and editable, and you are encouraged to experiment with them.

Introduction

Functional programming techniques and design patterns are increasingly popular in JavaScript applications. Tools and frameworks such as RxJS, Redux, and React take inspiration from functional reactive programming, for example.

Among the many varied features of FP, the interrelated facets of purity, immutability, and persistent data structures yield benefits such as referential transparency and idempotence. To put it simply, avoiding mutation and side effects makes code easier to reason about and compose.

JavaScript is a multi-paradigm programming language. It allows for functional approaches, but without the convenience or guarantees found in some dedicated functional languages. Accordingly, a JS developer must take special care if they intend to update data without mutation. For example, a Redux reducer "must never mutate its arguments, perform side effects…, [or] call non-pure functions", but Redux itself provides no tools for adhering to those strictures.

This article will not focus on the benefits of immutability, but rather explore how it can be achieved in JS if desired.

What is an Immutable Update

Consider a function which increments the .counter property of an object:


    
const obj1 = { bools: [true, false], counter: 7 }
const obj2 = { bools: [false, true], counter: 3 }

function incrementObjCounter (obj) {
  // naive solution
  const newObj = {
    bools: obj.bools, // same reference
    counter: obj.counter + 1 // updated data
  }
  return newObj
}

const newObj1 = incrementObjCounter(obj1)
const newObj2 = incrementObjCounter(obj2)

console.log(obj1, newObj1) // different objects
console.log(obj2, newObj2) // different objects
console.log(obj1.bools === newObj1.bools) // shared reference
console.log(obj2.bools === newObj2.bools) // shared reference

Rather than modify the original object, we generate a new object with changed data. Note that an even more naive solution might recursively copy all the data in the original object. This is usually referred to as a deep clone, and doubles the amount of memory in use.

If we never intend to mutate the data in our base object, however, it can be safely shared with the new object, as demonstrated with the .bools property above. This structural sharing means that an immutable update can often re-use existing memory.

Unfortunately, the code above is brittle; it uses hard-coded property names even for data not being updated. The function is neither reusable for other object shapes nor easily maintainable.

Difficulties with Immutable Updates

Suppose we have some nested data as follows:



const dino = {
  name: 'Denver',
  type: 'dinosaur',
  friends: [
    {
      name: 'Wally',
      type: 'human',
      pets: [
        {
          name: 'Rocky',
          type: 'dog'
        }
      ]
    },
    {
      name: 'Casey',
      type: 'human'
    }
  ]
}

Perhaps we might want to give Wally a new pet rabbit of the form { name: 'Ears', type: 'rabbit' }. Give it a try; the dino value is in scope in the following editable code block. Unlike in most real-world applications, we have deeply frozen dino so you will know if you accidentally attempt to mutate it – an error will be thrown.


    
const registerTests = require('@runkit/glebec/tape-dispenser/releases/1.0.0')
const test = (actual) => registerTests(t => {
    t.deepEqual(
        actual,
        {
          name: 'Denver',
          type: 'dinosaur',
          friends: [
            {
              name: 'Wally',
              type: 'human',
              pets: [
                {
                  name: 'Rocky',
                  type: 'dog'
                },
                {
                  name: 'Ears',
                  type: 'rabbit'
                }
              ]
            },
            {
              name: 'Casey',
              type: 'human'
            }
          ]
        }
    )
    t.end()
})
function deepFreeze(object) {
  var propNames = Object.getOwnPropertyNames(object);
  for (let name of propNames) {
    let value = object[name];
    object[name] = value;
    if ((typeof value) === 'object') { object[name] = deepFreeze(value) }
  }

return Object.freeze(object);
}
const dino = deepFreeze({
  name: 'Denver',
  type: 'dinosaur',
  friends: [
    {
      name: 'Wally',
      type: 'human',
      pets: [
        {
          name: 'Rocky',
          type: 'dog'
        }
      ]
    },
    {
      name: 'Casey',
      type: 'human'
    }
  ]
})


    
await (function runTestInStrictMode () {
'use strict'; // using functional strict mode because of runkit limitations

// dino is in scope

const updatedDino = undefined; // give Wally a new pet rabbit!

return test(updatedDino);
})()

Did you manage to correctly generate a new dinosaur, without throwing any mutation-related errors? In an actual codebase, what is your confidence that you would have avoided those errors? Keep in mind that frequently, objects like this are not deeply frozen – they will silently accept mutation.

For this challenge, we had you add an object. What about updating a deeply-nested object, or deleting one? Feel free to experiment below, then read on for some review.


    
function deepFreeze(object) {
  var propNames = Object.getOwnPropertyNames(object);
  for (let name of propNames) {
    let value = object[name];
    object[name] = value;
    if ((typeof value) === 'object') { object[name] = deepFreeze(value) }
  }

return Object.freeze(object);
}
const dino = deepFreeze({
  name: 'Denver',
  type: 'dinosaur',
  friends: [
    {
      name: 'Wally',
      type: 'human',
      pets: [
        {
          name: 'Rocky',
          type: 'dog'
        }
      ]
    },
    {
      name: 'Casey',
      type: 'human'
    }
  ]
})


    
(function runTestInStrictMode () {
'use strict'; // using functional strict mode because of runkit limitations

// dino is in scope

const dinoRenamedRocky = undefined // change dino.friends[0].pets[0].name

const dinoRemovedRocky = undefined // remove dino.friends[0].pets[0]

console.log(dino, dinoRenamedRocky, dinoRemovedRocky) // three different values
})()

Review of Vanilla JS Behavior

Primitives are Immutable (but also Re-assignable)

JavaScript primitives (undefined, null, boolean, number, string, and symbol values) are immutable by default, so you are already prevented from permanently altering primitive values themselves.


    
const str = 'hello'
str[0] = 'j'        // silently ignores mutation attempt
console.log(str)    // "hello", not "jello"

Of course, JavaScript does allow re-assignment of shared variables, which is not the same thing as mutation but which presents many of the same issues.


    
let x = 5

badInc = () => { x = x + 1; return x }
badDbl = () => { x = x * 2; return x }

console.log(badInc(x) + badDbl(x)) // neither commutative nor idempotent

Try commuting the terms in the above expression to badDbl(x) + badInc(x) and re-running the code. Because of the statefulness inherent in re-binding the shared x variable, we get different results, betraying our expectation of how addition works.

Objects are Mutable (but also Freezable)

Anything not of the primitive types listed above is considered an object in JS – including arrays and functions. A common beginner misunderstanding with JavaScript is that const declarations will prevent mutation. Not so; const only prevents re-assignment.


    
const obj = {}
const arr = []
const fnc = () => {}

obj.mutated = true
arr.mutated = true
fnc.mutated = true

console.log(obj.mutated, arr.mutated, fnc.mutated) // true x 3

JavaScript does have the static method Object.freeze(obj) to prevent re-assigning properties. In strict mode, attempting to set a property on a frozen object throws a helpful error. Sadly, in non-strict mode the attempt is merely rejected silently. (Note that freeze itself mutates the object.)


    
const obj = { example: 9000 }
obj.example++ // mutates obj

Object.freeze(obj) // mutates obj by freezing it
obj.example++ // silently ignored in non-strict mode (error in strict mode)

console.log(obj.example) // 9001, not 9002

Beware, however – freeze only prevents re-assigning top-level properties, and does not prevent mutating objects referenced in those properties. For that, you need a non-native "deep freeze" algorithm which recursively freezes objects.


    
const obj = { o: { x: 50 } }

Object.freeze(obj)

obj.o.x++ // still allowed
console.log(obj) // inner reference mutated, oops

Freezing objects could help reveal and debug errors by failing early (upon mutation attempt) rather than late (when an unanticipated state yields incorrect behavior), at least in strict mode. In practice however, freezing is not very common, perhaps because:

an author needs to predict that a given object is worth the extra effort of freezing, belying the YAGNI principle
deep freeze algorithms, like deep clone algorithms, have edge cases and pitfalls in JS (e.g. cycles, properly detecting objects)
recursively freezing deeply-nested objects might be a performance concern (valid or not)

Approach 1: Native Immutable Updates

So, what tools does JS provide when hoping to avoid mutation? As primitives are already immutable, and functions are infrequently used as mutable data containers, in practice the question is how to generate new versions of Objects and Arrays. For those, we have several built-in methods.

Spread Syntax

As of ES2015, the spread ... operator has allowed for expanding iterable values into explicit arguments. When used inside new array or object literals, this permits copying the properties of existing values into the new value:


    
const obj1 = { type: 'data' }
const arr1 = [1, 2, 3]

const obj2 = { ...obj1, subtype: 'stuff' } // adds a key-val pair
const arr2 = [ ...arr1, 'cheese' ] // adds an element

// distinct old and new versions
console.log(obj1, obj2)
console.log(arr1, arr2)

With objects in particular, this allows for easy updating of a top-level key:


    
const obj1 = { type: 'data', age: 55 }

const obj2 = { ...obj1, age: obj1.age + 1 } // modified age

console.log(obj1, obj2)

In some environments, object spread syntax may not be supported, but Object.assign (also ES2015) may be available.

Problems with Native Methods

Spread makes it convenient to add new values to an array, add new key-value pairs to an object, or modify a key-value pair on an object. However, deletion of a key-value pair is not as straightforward. There are some tricks using destructuring but they are not convenient when working with nested objects.

When it comes to arrays, removing a specific element can be done via either filtering or sliceing:


    
const arr = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet']
const newArrA = [...arr.slice(0, 2), ...arr.slice(3)]
const newArrB = arr.filter(color => color !== 'yellow')
console.log(arr, newArrA, newArrB)

While updating an array element can be accomplished with slice or map:


    
const arr = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet']
const newArrA = [...arr.slice(0, 2), 'sunshine', ...arr.slice(3)]
const newArrB = arr.map(color => color === 'yellow' ? 'sunshine' : color)
console.log(arr, newArrA, newArrB)

These methods work but are somewhat cumbersome and error-prone. And we are only dealing with shallow data; things become more difficult with nesting. Let's return to the original example from this article, adding a rabbit to Denver's friend Wally's list of pets. Here is one possible solution using vanilla JS:


    
const dino = {
  name: 'Denver',
  type: 'dinosaur',
  friends: [
    {
      name: 'Wally',
      type: 'human',
      pets: [
        {
          name: 'Rocky',
          type: 'dog'
        }
      ]
    },
    {
      name: 'Casey',
      type: 'human'
    }
  ]
}


    
const updatedDino = {
  ...dino,
  friends: [
    {
      ...dino.friends[0],
      pets: [...dino.friends[0].pets, { name: 'Ears', type: 'rabbit' }]
    },
    ...dino.friends.slice(1)
  ]
}
console.log(dino, updatedDino)

This works, but it has some notable downsides:

it is complex and verbose enough to be difficult to read, write, and maintain
- frequent alternation between array and object spread makes it easy to lose track of what's going on
- the deeper into the object one goes, the higher the likelihood that reference chains grow (e.g. pets: [...dino.friends[0].pets ])
- modifying one specific value in an array requires adding map or slice into the mix, increasing noise
- any mistakes in implementation will be silent mutation errors in practice, unless dino is deeply frozen and you are in strict mode
the performance is not ideal
- spread syntax invokes the iteration protocol
- creating a copy of changed objects / arrays (e.g. the pets and friends arrays) is O(n) time complexity

Approach 2: Ramda `lens`

Context

Lenses are an approach to interacting with nested data that originate in Haskell, a lazy (and therefore of necessity pure) functional language with Hindley-Milner inferred static typing. In that language, they are remarkably flexible and general tools that work across myriad data types seamlessly.

Lenses and related tools are a deep topic, and in JavaScript we do not have the type restrictions that make lenses especially valuable in Haskell. However, the core idea is simple and useful enough that it makes an appearance in Ramda, a popular functional JS utility library.

High-Level

Conceptually, a lens is a pair of functions:

a getter for a "focus" element a that can be derived from some "source" data s
a setter which can update a, immutably generating a new s

In terms of implementation, a lens is actually a single function which performs either of the above duties depending on how it is used. A given lens function is not invoked directly on the source; instead, helper functions like view, set, and over are responsible for correctly wielding the lens.



const { view } = require('ramda')
const extractedData = view(someLens, sourceData) // NOT someLens(wrappingData)

Because lenses are individual functions, they can be directly composed together to form new lenses (an example of the combinator pattern).



const { compose } = require('ramda')
const deepLens = compose(outerLens, innerLens)

Demonstration

Most commonly with Ramda, one will not write a lens from scratch but use methods like lensIndex and lensProp to generate correct lenses.


    
const dino = {
  name: 'Denver',
  type: 'dinosaur',
  friends: [
    {
      name: 'Wally',
      type: 'human',
      pets: [
        {
          name: 'Rocky',
          type: 'dog'
        }
      ]
    },
    {
      name: 'Casey',
      type: 'human'
    }
  ]
}


    
const R = require('ramda')

// dino is in scope

// making a lens for the "friends" property
const friendsLens = R.lensProp('friends')

// viewing data using a lens
const friends = R.view(friendsLens, dino)
console.log(friends)

// immutably setting data using a lens
const lonelyDino = R.set(friendsLens, [], dino) // aww, no more friends
console.log(lonelyDino)

// immutably mapping data using a lens
const addEveryone = arr => [...arr, 'everyone']
const popularDino = R.over(friendsLens, addEveryone, dino)
console.log(popularDino)

console.log(dino) // unchanged

The set and over methods generate new data with the desired updates, but like Object/Array spread, the new values also share any non-updated references with the old values.

All of this is well and good, but what about nested data? For that, standard right-to-left function composition can stitch together multiple lenses.


    
const dino = {
  name: 'Denver',
  type: 'dinosaur',
  friends: [
    {
      name: 'Wally',
      type: 'human',
      pets: [
        {
          name: 'Rocky',
          type: 'dog'
        }
      ]
    },
    {
      name: 'Casey',
      type: 'human'
    }
  ]
}


    
const R = require('ramda')

// dino is in scope

// making some lenses
const friendsLens = R.lensProp('friends')
const lens0 = R.lensIndex(0)
const petsLens = R.lensProp('pets')
const nameLens = R.lensProp('name')

// stacking lenses together into a single lens
const frns0pets0name = R.compose(
  friendsLens,  // outermost lens first
  lens0,
  petsLens,
  lens0,
  nameLens      // innermost lens last
)

// viewing data using a lens
console.log(R.view(frns0pets0name, dino))

// immutably setting data using a lens
console.log(R.set(frns0pets0name, 'Spot', dino))

// immutably mapping data using a lens
console.log(R.over(frns0pets0name, (s => s + '!'), dino))

console.log(dino) // unchanged

Compared to our Object/Array spread + map technique, the above is far more concise, declarative, easy, and foolproof. But it gets even easier; composing together lenses to focus on a nested property chain is common, so Ramda provides a convenient lensPath function.


    
const dino = {
  name: 'Denver',
  type: 'dinosaur',
  friends: [
    {
      name: 'Wally',
      type: 'human',
      pets: [
        {
          name: 'Rocky',
          type: 'dog'
        }
      ]
    },
    {
      name: 'Casey',
      type: 'human'
    }
  ]
}


    
const R = require('ramda')

// dino is in scope
const frns0pets0name = R.lensPath(['friends', 0, 'pets', 0, 'name'])

console.log(R.set(frns0pets0name, 'Spot', dino))

console.log(dino) // unchanged

You can use this lens with view and over as well, of course – try for yourself. Ultimately, our final solution has been condensed down to two easy-to-read lines – one constructing the lens from a path, another using the lens to immutably set a deeply-nested property in some data.

All You Need is Lens?

Lenses, being vanilla composable functions with multiple capabilities (read/update/set), are a highly functional solution with all the attendant tricks that implies: partial application, higher-order usage, first-class portability, dynamic behavior etc. However, while Ramda's lens functions make it easy to view, set, and map nested properties, deleting is a little more indirect; you must map over a parent prop using vanilla JS removal techniques:


    
const R = require('ramda')
const obj = { items: ['a', 'b'] }
const removeFirst = arr => arr.slice(1)
const updated = R.over(R.lensProp('items'), removeFirst, obj)

The basic instantiation and usage of lenses via a library like Ramda may be simple enough, but users should be aware that lenses and other "optics"* have some advanced uses and important gotchas. For example, lens-like functions which violate the lens laws can result in odd edge cases.

*(A subset of lenses are isomorphisms, which enable you to operate on data structures as if they were other (equivalent) data structures. There are also prisms, which enable interacting with data that may or may not be of a certain shape, and traversals, which can focus on multiple subparts at a time.)

Approach 3: Immer

Some developers may prefer a more idiomatic approach to immutable updates in JS which doesn't involve importing a larger suite of tools or learning a new API. Michael Westrate's library Immer is purpose-built for just that.

Immer's clever trick is to change what ordinarily-mutating actions mean – intercepting assignment (=), unsafe methods (push), and other cases – in a form of metaprogramming. Specifically, it uses the Proxy constructor to create a "draft" version of your original object. You can mangle this draft at will, even mutating deeply-nested references directly. Instead of allowing those changes to actually occur, Immer transforms them into an aggregate immutable update on the original object.

Demonstration

Immer's core function, produce, has the following signature:



produce(currentState, producer: (draftState) => void): nextState


    
const { produce } = require('immer')

const original = {
  color: 'blue',
  items: [5, 6],
  thing: { x: true },
  shared: {}
}

const updated = produce(original, (draft => {
  draft.color = 'red'
  draft.items.push(917)
  delete draft.thing.x
  draft.thing.y = false
}))

console.log(original, updated) // no mutation
console.log(original.shared === updated.shared) // no naive copying

As the final console.log above shows, Immer is using structural sharing just like our manual spread and Ramda lens solutions. The advantages include:

new properties are automatically frozen in development mode
produce has a curried version for partial application
immer is a small single-purpose library
no need to learn a new API (apart from the one function wrapper)
no need to take special care in most cases, less cognitive overhead

All You Need is Immer?

While Immer is very slick, it is ultimately doing the same Object.assign / spread / map type operations as our previous solutions. So while Immer benefits from structural sharing, some updates on large data may be slow (O(n) to copy an array, for example). Also, by default Immer only works on (certain properties of) plain arrays and objects, not other built-ins such as Map and Set. For other pitfalls, consult the docs.

Approach 4: Immutable.js

The three approaches we have examined so far all focus on essentially the same data structures – nested Objects and Arrays. Native methods, lenses, and immer all "play well with others" in the sense that other libraries and codebases will generally provide and expect such data types.

One disadvantage of those structures, however, is that they were not purposefully designed with immutable updates in mind. To add an item to an array, you have to create a copy of the array with all other elements – an O(n) operation. If you fail to take special care, you can call a native method like sort without realizing it mutates the original data structure.

An alternative approach is to switch to a purely functional data structure (PDF link), or at least a data structure with efficient immutable update operations. Such data structures would expose an API of only pure operations, reducing the chance of error.

Facebook's library Immutable takes advantage of such structures. While they are implemented in vanilla JavaScript, the details are hidden from the user, who now interacts with classes such as List and Map (distinct from the ES2015 class of the same name). For large amounts of data, these entities are now much quicker to modify; for example, Map's set and get functions have O(log32 n) time complexity, and List's push and pop methods are O(1) despite returning a new updated list.

Demonstration

Immutable is a large library with multiple classes, each of which has many methods. We will demonstrate just a small corner of that library, beginning with converting some typical JS data to a nested series of Maps and Lists.


    
const dino = {
  name: 'Denver',
  type: 'dinosaur',
  friends: [
    {
      name: 'Wally',
      type: 'human',
      pets: [
        {
          name: 'Rocky',
          type: 'dog'
        }
      ]
    },
    {
      name: 'Casey',
      type: 'human'
    }
  ]
}


    
const Immutable = require('immutable')

// dino is in scope
const immDino = Immutable.fromJS(dino)

// view nested (perhaps missing!) data
const dogName = immDino.getIn(['friends', 0, 'pets', 0, 'name'])
console.log(dogName)

// change nested data (immutably), perhaps at a brand new path
const immDino2 = immDino.setIn(['friends', 0, 'pets', 0, 'name'], 'Spot')
console.log(immDino2)

Some advantages are not directly demonstrated, but worth pointing out:

if a property doesn't exist, getIn will short-circuit and return undefined rather than throwing a cannot read x of undefined error
if a property doesn't exist, setIn will generate new Map objects along the way
there are many more things we can do with Immutable.js Maps and Lists, such as .map, .push, .sort, etc. – all in a pure, non-destructive way

At the end, if some other library or framework requires a plain JS object or array, we can use .toJS() to convert it back.

All You Need is Immutable?

Performance and safety are the primary reasons to favor using immutable, but as always there are tradeoffs to consider.

Immutable requires developers to learn a new, relatively large API
Debugging immutable values is less ergonomic than plain objects and arrays
Projects using Immutable classes may need to convert to and from simpler datatypes, potentially undoing the performance benefit

I Want it All

Each of the approaches examined has pros and cons, as is often the case in programming. Thankfully, they are not mutually exclusive. For example, Brian Lonsdorf demonstrates using Ramda lenses to blend native objects/arrays with Immutable.js maps/lists in his article Lenses with Immutable.js. Similarly, one might use array spread inside a function passed to Ramda over, or inside a call to Immer's produce function. Knowing multiple approaches allows you to reach for the abstraction that fits your use case.

Tool	Learning Curve	Safety	Performance	Concept	TL;DR
Native	JS devs expected to know it, but takes time to master	Poor, common source of errors	Slow (linear) for large amounts of data	Manually copy nested properties, `map` / `filter` / `slice` to update or delete	Built-in
Ramda (lenses) · (52 kB)	Small number of concepts, but potentially alien to FP newbies	Good, but be careful with paths	Comparable to native	Create lenses for nested data, use them with `view` / `set` / `over`, manipulate via FP techniques (composition, partial application)	Versatile patterns
Immer · (13 kB)	One API method	Good, but has some edge cases	Comparable to native	Use normally-mutating native actions on a draft object, actions instead become immutable updates	Easy API
Immutable · (63 kB)	Larger library with many API methods	Good, but be careful with paths	Excellent per se, but slowed by conversion	Use library's data structures and methods instead of native types, convert where necessary	Faster algos

Addendum: Immutability via Function Encoding

Prof. Dierk König brings up another technique for immutable data: store your data as functions.

// Detect dark theme var iframe = document.getElementById('tweet-1095617645767020544-673'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1095617645767020544&theme=dark" }

The Vireo combinator (as it is named in Raymond Smullyan's famous book, To Mock a Mockingbird) is defined in JavaScript as follows:



const vireo = a => b => f => f(a)(b)

When vireo is applied twice (to two separate pieces of data), it returns a final function which has closed over both data points. The result is conceptually a pair of numbers, stored as a function closure. To access to the stored numbers, a final function argument is provided:


    
const vireo = a => b => f => f(a)(b)


    
const pairOfNums = vireo(5)(8) // f => f(5)(8)

pairOfNums(a => b => console.log(a)) // logs 5
pairOfNums(a => b => console.log(b)) // logs 8

Note that with this example, there is no way to actually modify the values once the pair is generated – the closure acts as a form of privileged data. How can we "update" such a pair? We make a new function which defers to old function:


    
const vireo = a => b => f => f(a)(b)


    
const pairOfNums = vireo(5)(8) // f => f(5)(8)

const fst = a => _ => a
const snd = _ => b => b

const newPairWithSecondNumDoubled = f => {
    const firstNum = pairOfNums(fst)
    const secondNum = pairOfNums(snd)
    return f(firstNum)(secondNum * 2)
}

console.log(
    newPairWithSecondNumDoubled(fst), // 5
    newPairWithSecondNumDoubled(snd)  // 16
)

To make this easier, we could write helper functions for getting, setting, and mapping…


    
const vireo = a => b => f => f(a)(b)


    
const getL  = p => p(l => _ => l)
const getR  = p => p(_ => r => r)
const getLR = p => p(l => r => [l, r])

const setL  = newL => p => vireo(newL)(getR(p))
const setR  = newR => p => vireo(getL(p))(newR)

const mapL  = transform => p => vireo(transform(getL(p)))(getR(p))
const mapR  = transform => p => vireo(getL(p))(transform(getR(p)))

const numPair = vireo(3)(7)

const show = pair => console.log(getLR(pair))

show(numPair) // [3, 7]
show(setL(0)(numPair)) // [0, 7]
show(mapR(x => x * 2)(numPair)) // [3, 14]

Storing data through closures, and creating new functions which defer to old functions, can scale up to more complex data and also be made more idiomatic in JS; this is a large enough topic for its own article, however. If this approach intrigues you, Sandy Maquire's Thinking with Types illustrates a clever method (in Haskell) of encoding Tic-Tac-Toe boards as functions from coordinates to data. Experiment with a JS version below!


    
const emptyBoard = (x, y) => null

const setPos = (atX, atY, newVal, oldBoard) => {
    const oldVal = oldBoard(atX, atY)
    const newBoard = (x, y) => {
        return (x === atX && y === atY)
            ? newVal
            : oldBoard(x, y)
    }
    return newBoard
}

const printBoard = (board, limitX, limitY) => {
    for (let x = 0; x < limitX; x++) {
        for (let y = 0; y < limitY; y++) {
            console.log('pos ' + x + ', ' + y + ' is ' + board(x, y))
        }
    }
}

const b2 = setPos(0, 0, 'x', emptyBoard)
const b3 = setPos(1, 1, 'o', b2)

printBoard(b3, 2, 2)

// NB: if you log a larger board, runkit paginates the results!

Monadic Parser Combinators: an Interactive JS Tutorial (Pt. 1)

Gabriel Lebec — Fri, 02 Nov 2018 18:17:53 +0000

Parsing analyzes serial data into a structural result, and is a key step in static code analysis and compilation. Parsers also demonstrate various functional concepts including purity, composition, and monads.

In this interactive tutorial, we will walk through implementing a simple parser combinator library. Combinators allow programmers to easily build up complex programs through the use of a small number of cooperative utility functions.

const color  = P.either(P.literal('red'), P.literal('blue'))
const animal = P.either(P.literal('zebra'), P.literal('giraffe'))
const spaces = P.many1(P.literal(' '))
const tallTale =
    color .chain(c =>
    spaces.chain(_ =>
    animal.chain(a => P.of(`There was a ${c} ${a}.`))))

The intent is partly to learn about parsing and partly to learn about functional programming. No prior experience in either is assumed.

Motivations

Serial data, e.g. from a file or network payload, often must be analyzed into a result before a program can work with it. For example:

HTML is a string format for page contents. Browsers parse HTML into the DOM, a tree of in-memory nodes that can be queried and manipulated to affect the rendered web page.
JSON is a string format for nested data, often used for configuration files or network payloads. Programs can use JSON.parse to convert a JSON string into a JavaScript Object, which can be easily read and updated during runtime.
ESLint is a static code analysis tool for detecting errors and style deviations. ESLint uses a JavaScript parser (Espree) to read the author's program (a text file) and identify potential problems.

In addition, a class of programs called compilers go one step further, folding a parse tree back down into a converted string format. Compilers thus act as translators between strings in one formal language to strings in another.

const codeES2018 = 'num => num + 1'
const codeES5 = compileToES5(codeES2018)
console.log(codeES5) // 'function (num) { return num + 1 }'

V8 is a JavaScript engine that uses a compiler to translate JavaScript into executable machine code.
Babel compiles JavaScript written in modern and/or domain-specific syntax (e.g. ES2018 + JSX) into older syntax (e.g. ES5).
Prettier compiles JavaScript with non-standard formatting into JavaScript with consistent formatting.

In a typical compiler, parsing is referred to as the front end and code generation is called the back end.

    infix       FE (parser)       +      BE (generator)      postfix
 "2 + 3 * 5"         ->          / \           ->          "2 3 5 * +"
                                2   *
                               / \
                              3   5

However, it is also possible to generate results during the parsing step. In that case, no explicit tree is built, though the parser implicitly follows a tree structure while recursing through the input string.

Parsers

Generally, a parser extracts structure from the beginning of some serial input. The input can be an ordinary string, though some parsers may expect a stream (sequentially consumable source, e.g. generator or observable) of tokens (objects recording both linguistic type and lexical content).

Let's start simple and consider a parser to be a function from string to result.

// parse :: String -> *
const parse = s => ?

This begs the question of what our parser produces. The answer depends on the problem. Many parsers produce tree nodes, but parsers can be written to build any result desired, including raw strings, numbers, functions, whatever.

Dealing With Failure

For now let's just capture the literal string value (or lexeme) that our parser matches. Here is an (incomplete) parser intended to match on and result in the lexeme "Triceratops":

// parseTri :: String -> String
const parseTri = s => "Triceratops"

Sadly, this parser is broken. What if our string contains the wrong dinosaur? Parsing "T. Rex" shouldn't result in "Triceratops". We need a way to signal failure.

How would you address this issue? Come up with your own approach; your parsing function should be able to take the following strings and either result in "Triceratops" or else indicate (somehow) that it failed to parse.


    
// parseTri :: String -> String     // change me
const parseTri = s => 'Triceratops' // change me

// change parseTri so that it can indicate failure

console.log(parseTri('Triceratops'))       // should succeed
console.log(parseTri('Triceratops rules')) // should succeed
console.log(parseTri('I <3 Triceratops'))  // should fail
console.log(parseTri('Pteranodons'))       // should fail
console.log(parseTri('T. Rex'))            // should fail
console.log(parseTri(''))                  // should fail

Signaling Failure: Maybe?

type Parser = String -> Maybe String

An experienced functional programmer would likely reach for a sum type such as the Maybe monad. However, to properly address that concept now would derail this article substantially, so we will circle back to Maybe later on.

Signaling Failure: Array?

type Parser = String -> [String]

Functional parsers commonly represent their results as lists. Failure can thus be represented by the empty list [], and multiple successes (from an ambiguous grammar) can be captured if necessary. Ambiguous grammars lie outside the scope of this article, so we don't strictly need lists.

Signaling Failure: Null

type Parser = String -> String | Null

Both Maybe and lists are good ways of dealing with failure, but for now we will stick with a method JS developers are familiar with: null. The null value, whose inventor Tony Hoare once called his "billion dollar mistake", has serious pitfalls. However, it is idiomatic, approachable, and will suffice for the moment.

Here is our new parser. Try it on some strings and see what happens:


    
// parseTri :: String -> String | Null
const parseTri = s => s.startsWith('Triceratops')
    ? 'Triceratops'
    : null

console.log(parseTri('...try strings here...'))

Dealing with Leftovers

When we parse a result from a string, in most cases we will only consume part of the input. The remainder will have other values we can parse, which means we need to keep track of where to resume. In a mutable setting like JavaScript, one might be tempted to create a shared index value.

let index = 0
const parseTri = s => {
    const remainder = s.slice(index)
    if (remainder.startsWith('Triceratops')) {
        index += 'Triceratops'.length
        return 'Triceratops'
    }
    return null
}

This works fine for parsing a single string:


    
let index = 0
const parseTri = s => {
    const remainder = s.slice(index)
    if (remainder.startsWith('Triceratops')) {
        index += 'Triceratops'.length
        return 'Triceratops'
    }
    return null
}


    
// (index & parseTri are in scope but hidden)
const string = 'TriceratopsTriceratops'
const res1 = parseTri(string) // 'Triceratops'
const res2 = parseTri(string) // 'Triceratops'
const res3 = parseTri(string) // null
console.log(res1, res2, res3)

However, shared mutable state can quickly cause problems. What if we want to subsequently parse a different string?


    
let index = 0
const parseTri = s => {
    const remainder = s.slice(index)
    if (remainder.startsWith('Triceratops')) {
        index += 'Triceratops'.length
        return 'Triceratops'
    }
    return null
}
const string = 'TriceratopsTriceratops'
const res1 = parseTri(string) // 'Triceratops'
const res2 = parseTri(string) // 'Triceratops'
const res3 = parseTri(string) // null


    
// (index, parseTri, and res1–res3 are in scope but hidden)
const string2 = 'Triceratops rules'
const res4 = parseTri(string2)
console.log(res4) // null // oops!

There are solutions, of course. We could create a Parser class whose instances manage internal state, or a higher-order makeParser function which closes over state. Both of those solutions bury state without actually eliminating it; debugging such hidden state is sometimes even more challenging.

Pure Token Consumption

It turns out that for this problem, we don't actually need mutable state. In functional programming, we prefer pure solutions.

Pure functions are stateless deterministic mappings from input to output, with no side effects. In other words, pure functions have output, but neither depend on nor change the external universe. If you can define your function as a (potentially infinite) table of inputs and outputs, it's pure. Try to induce how f1, f2, and f3 below are defined:

f1 in	f1 out	f2 in	f2 out	f3 in	f3 out
`'hi'`	`2`	`[a, b]`	`b`	`0`	`-2`
`'what'`	`4`	`[0, 9, 1]`	`9`	`1`	`-1`
`'pow'`	`3`	`[0]`	`undefined`	`2`	`2`
`'forest'`	`6`	`[]`	`undefined`	`3`	`7`
`'a'`	`1`	`[1, 2, 3]`	`2`	`4`	`14`
`''`	`0`	`[z, y]`	`y`	`5`	`23`
…	…	…	…	…	…

If a parser needs to indicate where the next parse should commence, that implies that the leftover input should itself be a return value. So, our parsers will return two things: a parsed result, and remaining input.

type Parser = String -> String & String

How can you write a function that returns two things? There is more than one viable way; come up with your own approach below, then read on for our take.


    
// parseTri :: String -> String & String
const parseTri = s => s.startsWith('Triceratops')
    ? 'Triceratops' // fix me to also return leftover input
    : null

// should succeed with "" as a remainder
console.log(parseTri('Triceratops'))

// should succeed with " rules" as a remainder
console.log(parseTri('Triceratops rules'))

// should fail
console.log(parseTri('T. Rex'))

Tuples and Friends

Because functional programming involves a lot of data flowing in and out of functions, functional languages often feature a lightweight data structure for packaging values together: the tuple.

-- Haskell
myTuple = ("hello", 99) -- a 2-tuple
str = fst myTuple -- "hello"
num = snd myTuple -- 99

JavaScript doesn't have tuples, but it does have Objects and Arrays (which are actually a type of Object). We can emulate tuples easily enough:

const myTuple = ['hello', 99]
const str = myTuple[0] // 'hello'
const num = myTuple[1] // false

const myTuple = { str: 'hello', num: 99 }
const { str } = myTuple // 'hello'
const { num } = myTuple // false

Arrays are more concise, but Objects are more expressive. You probably used one of these in your solution above; we'll use Objects.


    
// parseTri :: String -> { result: String, remainder: String } | Null
const parseTri = s => s.startsWith('Triceratops')
    ? { result: 'Triceratops', remainder: s.slice(11) }
    : null

console.log(parseTri('Triceratops'))
console.log(parseTri('Triceratops is cool'))
console.log(parseTri('T. Rex'))

Side Note: Isomorphisms

n-Tuples and n-element JS Arrays (when used solely to store data) are actually isomorphic. Sets A and B are isomorphic if you can define a pair of functions a2b and b2a, such that:

a2b maps all values in A to values in B
b2a maps all values in B to values in A
b2a(a2b(a)) = a
a2b(b2a(b)) = b

Isomorphisms are a rich topic with some delightful results, but the upshot is that it is nice to know when two data types are equivalent for a given use case.

Thought puzzle: why might two-valued objects not be isomorphic to 2-el arrays? What information would be lost in translation?

Threading Parsers

Our parser can now report which part of the input was not consumed, but how do we actually use that information? The leftover string from one parse becomes the input to the next parse. Complete the code below.


    
const assert = require('assert')

const parseTri = s => s.startsWith('Triceratops')
    ? { result: 'Triceratops', remainder: s.slice(11) }
    : null

const solution = [
    "const firstParse = parseTri(string)",
    "const secondParse = parseTri(firstParse.remainder)",
    "const thirdParse = parseTri(secondParse.remainder)"
].join('\n')


    
// parseTri :: String -> { result: String, remainder: String } | Null

// parseTri is in scope in this snippet. You can refer back
// to its definition, but you won't need to edit it.

const string = 'TriceratopsTriceratops'

// use parseTri to obtain the three values below:

const firstParse = undefined
const secondParse = undefined
const thirdParse = undefined

// console.log(solution)
assert.deepStrictEqual(firstParse, {
    result: 'Triceratops',
    remainder: 'Triceratops'
}, 'first parse works')
assert.deepStrictEqual(secondParse, {
    result: 'Triceratops',
    remainder: ''
}, 'second parse works')
assert.equal(thirdParse, null, 'third parse works')

To see our solution, you can log the hidden variable solution.

Generalizing

We have a single parser which can parse "Triceratops" – not very interesting. Write a few parsers for other dinosaurs.


    
const registerTests = require('@runkit/glebec/tape-dispenser/releases/1.0.0')

const testParsers = () => registerTests(t => {
    t.deepEqual(
        parseRex('T. Rex'),
        { result: 'T. Rex', remainder: '' },
        'parseRex parses "T. Rex"'
    )
    t.deepEqual(
        parseRex('T. Rex is scary'),
        { result: 'T. Rex', remainder: ' is scary' },
        'parseRex parses "T. Rex is scary"'
    )
    t.equal(
        parseRex('Triceratops'),
        null,
        'parseRex fails to parse "Triceratops"'
    )
    t.deepEqual(
        parseRaptor('Velociraptor'),
        { result: 'Velociraptor', remainder: '' },
        'parseRaptor parses "Velociraptor"'
    )
    t.deepEqual(
        parseRaptor('Velociraptor is scary'),
        { result: 'Velociraptor', remainder: ' is scary' },
        'parseRaptor parses "Velociraptor is scary"'
    )
    t.equal(
        parseRaptor('Triceratops'),
        null,
        'parseRaptor fails to parse "Triceratops"'
    )
    t.end()
})

const solution = [
    "const parseRex = s => s.startsWith('T. Rex')",
    "    ? { result: 'T. Rex', remainder: s.slice(6) }",
    "    : null",
    "",
    "const parseRaptor = s => s.startsWith('Velociraptor')",
    "    ? { result: 'Velociraptor', remainder: s.slice(12) }",
    "    : null"
].join('\n')


    
// parseRex :: String -> { result: String, remainder: String } | Null
const parseRex = undefined // matches "T. Rex"

// parseRaptor :: String -> { result: String, remainder: String } | Null
const parseRaptor = undefined // matches "Velociraptor"

// console.log(solution)
await testParsers()

This is pretty repetitive. Let's generalize and make a parseLiteral function.


    
const registerTests = require('@runkit/glebec/tape-dispenser/releases/1.0.0')

const testParsers = () => registerTests(t => {
    t.deepEqual(
        parseRex('T. Rex'),
        { result: 'T. Rex', remainder: '' },
        'parseRex parses "T. Rex"'
    )
    t.deepEqual(
        parseRex('T. Rex is scary'),
        { result: 'T. Rex', remainder: ' is scary' },
        'parseRex parses "T. Rex is scary"'
    )
    t.equal(
        parseRex('Triceratops'),
        null,
        'parseRex fails to parse "Triceratops"'
    )
    t.deepEqual(
        parseRaptor('Velociraptor'),
        { result: 'Velociraptor', remainder: '' },
        'parseRaptor parses "Velociraptor"'
    )
    t.deepEqual(
        parseRaptor('Velociraptor is scary'),
        { result: 'Velociraptor', remainder: ' is scary' },
        'parseRaptor parses "Velociraptor is scary"'
    )
    t.equal(
        parseRaptor('Triceratops'),
        null,
        'parseRaptor fails to parse "Triceratops"'
    )
    t.end()
})

const solution = [
    "const parseLiteral = literal => s => s.startsWith(literal)",
    "    ? { result: literal, remainder: s.slice(literal.length) }",
    "    : null",
    "",
    "const parseRex = parseLiteral('T. Rex')",
    "",
    "const parseRaptor = parseLiteral('Velociraptor')"
].join('\n')


    
// parseLiteral :: String ->
//     (String -> { result: String, remainder: String } | Null)
const parseLiteral = literal => undefined

// parseRex :: String -> { result: String, remainder: String } | Null
const parseRex = undefined // use parseLiteral

// parseRaptor :: String -> { result: String, remainder: String } | Null
const parseRaptor = undefined // use parseLiteral

// console.log(solution)
await testParsers()

Solving the above demonstrates a common functional technique. Higher-order functions take and/or return functions themselves; parseLiteral does the latter. Instead of hard-coding individual parsers for every string, parseLiteral generalizes, mapping from strings to parsers:

string	`parseLiteral(string)`
`'hi'`	parser for `'hi'`
`'yo'`	parser for `'yo'`
`'wow'`	parser for `'wow'`
…	…

Different Result Types

Parsers match on strings, but they don't have to result in them. Write parsers for digit strings which result in numbers.


    
const registerTests = require('@runkit/glebec/tape-dispenser/releases/1.0.0')

const testParsers = () => registerTests(t => {
    t.deepEqual(
        parseNum0('0'),
        { result: 0, remainder: '' },
        'parseNum0 parses "0"'
    )
    t.deepEqual(
        parseNum0('0 is cool'),
        { result: 0, remainder: ' is cool' },
        'parseNum0 parses "0 is cool"'
    )
    t.equal(
        parseNum0('1'),
        null,
        'parseNum0 fails to parse "1"'
    )
    t.deepEqual(
        parseNum1('1'),
        { result: 1, remainder: '' },
        'parseNum1 parses "1"'
    )
    t.deepEqual(
        parseNum1('1 is cool'),
        { result: 1, remainder: ' is cool' },
        'parseNum1 parses "1 is cool"'
    )
    t.equal(
        parseNum1('0'),
        null,
        'parseNum1 fails to parse "0"'
    )
    t.end()
})

const solution = [
    "const parseNum0 = s => s.startsWith('0')",
    "    ? { result: 0, remainder: s.slice(1) }",
    "    : null",
    "",
    "const parseNum1 = s => s.startsWith('1')",
    "    ? { result: 1, remainder: s.slice(1) }",
    "    : null"
].join('\n')


    
// parseNum0 :: String -> { result: Number, remainder: String } | Null
const parseNum0 = undefined // result should be 0, not '0'

// parseNum1 :: String -> { result: Number, remainder: String } | Null
const parseNum1 = undefined // result should be 1, not '1'

// console.log(solution)
await testParsers()

Once we start using our parsers for practical purposes, it will be convenient to transform raw lexemes into processed results specific to our use case.

Types, Signatures, & Aliases

We now have seen two different kinds of parsers: ones that result in strings, and ones that result in numbers.

parseRex  :: String -> { result: String, remainder: String } | Null
parseNum1 :: String -> { result: Number, remainder: String } | Null

We haven't drawn special attention to these comments yet, preferring to teach by example, but these are examples of type signatures. A type signature documents what set a value belongs to. For example, the Bool type is a set of two values: true and false. You can read the notation :: as "has type" or "is in the set":

true  :: Bool -- `true`  is in the set `Bool`
false :: Bool -- `false` is in the set `Bool`

Functions also belong to types. The ! (or "not") function happens to be in the set of functions which map values in Bool to values in Bool. We signify this as (!) :: Bool -> Bool. Here is the ! function defined:

Bool input	Bool output
`true`	`false`
`false`	`true`

Thought puzzle: there are precisely three other functions of type Bool -> Bool. Can you define all of them? Remember, each function will be a table of two rows.

Functions are mappings from one type to another type (e.g. Int -> Bool, String -> String, or Object -> String). Accordingly, functional languages often emphasize their type system. ML and related languages like OCaml, F#, ReasonML, Miranda, Haskell, PureScript, Idris, and Elm are examples of languages with sophisticated typing, including algebraic data types and complete type inference.

JavaScript has a (sometimes infamous) dynamic type system, and lacks an official type notation. The syntax here is borrowed from Haskell and is similar to the system used by Ramda, a JS utility library. It is explained well by both the Ramda wiki and Fantasy Land docs.

We bring this up now because it is beginning to get cumbersome to write out the entire type of our parsers. The parseRex and parseNum1 type signatures differ at only one location, result:

parseRex  :: String -> { result: String, remainder: String } | Null
parseNum1 :: String -> { result: Number, remainder: String } | Null

Accordingly, from now on we will use Parser a to mean "a parsing function whose result is of type a":

type Parser a = String -> { result: a, remainder: String } | Null

This type alias is just a shorthand we will use for documentation purposes. It will clean up our comments considerably and make it easier to talk about parsers. For example, now we can categorize parseRex and parseNum1 more concisely:

parseRex  :: Parser String
parseNum1 :: Parser Number

Try it yourself. Simplify our parseLiteral signature using the shorthand:


    
const solution = [
    "parseLiteral :: String -> Parser String"
].join('\n')


    
// long version:

// parseLiteral :: String ->
//     (String -> { result: String, remainder: String } | Null)

// short version (fill in):

// parseLiteral :: ???

console.log(solution)

Combinators at Last

What if we want to match on more than one possibility? Implement the following parsers. Existing parsers are in scope, use them in your definition:


    
const registerTests = require('@runkit/glebec/tape-dispenser/releases/1.0.0')

const parseLiteral = literal => s => s.startsWith(literal)
    ? { result: literal, remainder: s.slice(literal.length) }
    : null

const parseTri = parseLiteral('Triceratops')
const parseRex = parseLiteral('T. Rex')
const parseRaptor = parseLiteral('Velociraptor')

const testParsers = () => registerTests(t => {
    t.deepEqual(
        parseCarnivore('T. Rex is scary'),
        { result: 'T. Rex', remainder: ' is scary' },
        'parseCarnivore parses "T. Rex is scary"'
    )
    t.deepEqual(
        parseCarnivore('Velociraptor is fast'),
        { result: 'Velociraptor', remainder: ' is fast' },
        'parseCarnivore parses "Velociraptor is fast"'
    )
    t.equal(
        parseCarnivore('Triceratops eats grass'),
        null,
        'parseCarnivore fails to parse "Triceratops eats grass"'
    )
    t.deepEqual(
        parseBigDino('T. Rex has small arms'),
        { result: 'T. Rex', remainder: ' has small arms' },
        'parseBigDino parses "T. Rex has small arms"'
    )
    t.deepEqual(
        parseBigDino('Triceratops has three horns'),
        { result: 'Triceratops', remainder: ' has three horns' },
        'parseBigDino parses "Triceratops has three horns"'
    )
    t.equal(
        parseBigDino('Velociraptor hunts in packs'),
        null,
        'parseBigDino fails to parse "Velociraptor hunts in packs"'
    )
    t.end()
})

const solution = [
    "// parseCarnivore, parseBigDino :: Parser String",
    "const parseCarnivore = s => parseRex(s) || parseRaptor(s)",
    "const parseBigDino   = s => parseRex(s) || parseTri(s)"
].join('\n')


    
// parseTri    :: Parser String
// parseRex    :: Parser String
// parseRaptor :: Parser String

// parseCarnivore :: Parser String
const parseCarnivore = undefined // match "T. Rex" OR "Velociraptor"

// parseBigDino :: Parser String
const parseBigDino = undefined // match "T. Rex" OR "Triceratops"

// console.log(solution)
await testParsers()

Again, this is getting repetitive. What does the functional programmer do when faced with repetition? Generalize! Write a function either which takes two parsers and returns a new parser that matches either of them.


    
const registerTests = require('@runkit/glebec/tape-dispenser/releases/1.0.0')

const parseLiteral = literal => s => s.startsWith(literal)
    ? { result: literal, remainder: s.slice(literal.length) }
    : null

const parseTri = parseLiteral('Triceratops')
const parseRex = parseLiteral('T. Rex')
const parseRaptor = parseLiteral('Velociraptor')

const testParsers = () => registerTests(t => {
    t.deepEqual(
        parseCarnivore('T. Rex is scary'),
        { result: 'T. Rex', remainder: ' is scary' },
        'parseCarnivore parses "T. Rex is scary"'
    )
    t.deepEqual(
        parseCarnivore('Velociraptor is fast'),
        { result: 'Velociraptor', remainder: ' is fast' },
        'parseCarnivore parses "Velociraptor is fast"'
    )
    t.equal(
        parseCarnivore('Triceratops eats grass'),
        null,
        'parseCarnivore fails to parse "Triceratops eats grass"'
    )
    t.deepEqual(
        parseBigDino('T. Rex has small arms'),
        { result: 'T. Rex', remainder: ' has small arms' },
        'parseBigDino parses "T. Rex has small arms"'
    )
    t.deepEqual(
        parseBigDino('Triceratops has three horns'),
        { result: 'Triceratops', remainder: ' has three horns' },
        'parseBigDino parses "Triceratops has three horns"'
    )
    t.equal(
        parseBigDino('Velociraptor hunts in packs'),
        null,
        'parseBigDino fails to parse "Velociraptor hunts in packs"'
    )
    t.end()
})

const solution = [
    "// either :: (Parser a, Parser b) -> Parser (a | b)",
    "const either = (p1, p2) => s => p1(s) || p2(s)"
].join('\n')


    
// parseLiteral :: String -> Parser String
// parseTri     :: Parser String
// parseRex     :: Parser String
// parseRaptor  :: Parser String

// either :: (Parser a, Parser b) -> Parser (a | b)
const either = (p1, p2) => undefined

// parseCarnivore, parseBigDino :: Parser String
const parseCarnivore = either(parseRex, parseRaptor)
const parseBigDino   = either(parseRex, parseTri)

// console.log(solution)
await testParsers()

Congratulations, you've written a combinator.

Combi-who?

Combinator, like many programming terms, is overloaded – it means different things in different contexts.

Combinatory logic is the study of functions which act on functions. For example, the I combinator (x => x) takes in a function and returns the same function. In this field, "combinator" formally means a function with no free (unbound) variables.
The combinator pattern is a strategy for building flexible libraries, in which a small number of cooperative utility functions build up rich results (which in turn can be new inputs to those same functions).
- For example, CSS "combinators" take in CSS selectors and yield new, more complex selectors. div and h1 are both primitive selectors; using the direct child (>) combinator, you can create the new div > h1 selector.

We will define a parser combinator as a function which takes in one or more parsers, and returns a new parser. Some examples:

either :: (Parser a, Parser b) -> Parser (a | b)
both   :: (Parser a, Parser b) -> Parser [a, b]
any    :: (...Parser *)        -> Parser *
many   ::  Parser a            -> Parser [a]

You've already defined either; take a crack at both and any next. For manual testing, parseLiteral and all of our dino parsers are in scope:


    
const registerTests = require('@runkit/glebec/tape-dispenser/releases/1.0.0')

const parseLiteral = literal => s => s.startsWith(literal)
    ? { result: literal, remainder: s.slice(literal.length) }
    : null

const parseTri = parseLiteral('Triceratops')
const parseRex = parseLiteral('T. Rex')
const parseRaptor = parseLiteral('Velociraptor')

const testTriRexViaBoth = () => registerTests(t => {
    const parseTriRex2 = both(parseTri, parseRex)
    t.deepEqual(
        parseTriRex2('TriceratopsT. Rex'),
        { result: ['Triceratops', 'T. Rex'], remainder: '' },
        'parseTriRex parses "TriceratopsT. Rex"'
    )
    t.deepEqual(
        parseTriRex2('TriceratopsT. Rex!!!'),
        { result: ['Triceratops', 'T. Rex'], remainder: '!!!' },
        'parseTriRex parses "TriceratopsT. Rex!!!"'
    )
    t.equal(
        parseTriRex2('TriceratopsT. Bone'),
        null,
        'parseTriRex fails to parse "TriceratopsT. Bone"'
    )
    t.equal(
        parseTriRex2('Triangles'),
        null,
        'parseTriRex fails to parse "Triangles"'
    )
    t.end()
})

const solution = [
    "const both = (p1, p2) => s => {",
    "    const r1 = p1(s)",
    "    if (!r1) return null",
    "    const r2 = p2(r1.remainder)",
    "    if (!r2) return null",
    "    return {",
    "        result: [r1.result, r2.result],",
    "        remainder: r2.remainder",
    "    }",
    "}"
].join('\n')


    
// both takes in a two parsers, and makes a parser that matches
// the first one and then the second (or fails if EITHER of them
// fails). It packages the two successes into an array.

// both :: (Parser a, Parser b) -> Parser [a, b]
const both = undefined

// parseTriRex :: Parser String
const parseTriRex = both(parseTri, parseRex)
console.log(parseTriRex('TriceratopsT. Rex!')) // succeeds
console.log(parseTriRex('Triceratops & T. Rex')) // fails

// console.log(solution)
await testTriRexViaBoth()

Also, either is in scope if you want it:


    
const registerTests = require('@runkit/glebec/tape-dispenser/releases/1.0.0')

const parseLiteral = literal => s => s.startsWith(literal)
    ? { result: literal, remainder: s.slice(literal.length) }
    : null

const either = (p1, p2) => s => p1(s) || p2(s)

const parseTri = parseLiteral('Triceratops')
const parseRex = parseLiteral('T. Rex')
const parseRaptor = parseLiteral('Velociraptor')

const testDinoViaAny = () => registerTests(t => {
    const parseDino2 = any(parseTri, parseRex, parseRaptor)
    t.deepEqual(
        parseDino2('Velociraptor on the loose'),
        { result: 'Velociraptor', remainder: ' on the loose' },
        'parseDino parses "Velociraptor on the loose"'
    )
    t.deepEqual(
        parseDino2('Triceratops for the win'),
        { result: 'Triceratops', remainder: ' for the win' },
        'parseDino parses "Triceratops for the win"'
    )
    t.deepEqual(
        parseDino2('T. Rex is a king'),
        { result: 'T. Rex', remainder: ' is a king' },
        'parseDino parses "T. Rex is a king"'
    )
    t.equal(
        parseDino2('Wooly mammoths migrate west'),
        null,
        'parseDino fails to parse "Wooly mammoths migrate west"'
    )
    t.end()
})

const solution = [
    "// any :: (...Parser *) -> Parser *",
    "const any = (...parsers) => parsers.reduce(either)",
].join('\n')


    
// either :: (Parser a, Parser b) -> Parser (a | b)

// any takes in a variable number of parsers, and makes a parser
// that matches the first one to match (or fails if they ALL fail).

// any :: (...Parser *) -> Parser *
const any = undefined

// parseDino :: Parser String
const parseDino = any(parseTri, parseRex, parseRaptor)

// console.log(solution)
await testDinoViaAny()

This is a powerful concept. Instead of hand-coding ad-hoc parser functions for every conceivable purpose, we can define a few abstract combinators. Feed simple parsers in, get more powerful parsers out; those new powerful parsers can become, in turn, inputs to the same combinators. We can therefore build up rich behavior from a few easy-to-use tools. This is the essence of composition – construction via combination.


    
const parseLiteral = literal => s => s.startsWith(literal)
    ? { result: literal, remainder: s.slice(literal.length) }
    : null

const parseTri = parseLiteral('Triceratops')
const parseRex = parseLiteral('T. Rex')
const parseRaptor = parseLiteral('Velociraptor')

const either = (p1, p2) => s => p1(s) || p2(s)

const both = (p1, p2) => s => {
    const r1 = p1(s)
    if (!r1) return null
    const r2 = p2(r1.remainder)
    if (!r2) return null
    return {
        result: [r1.result, r2.result],
        remainder: r2.remainder
    }
}

const any = (...parsers) => parsers.reduce(either)


    
const parseDino = any(parseTri, parseRex, parseRaptor)
const parseTwoDinos = both(parseDino, parseDino)
console.log(parseTwoDinos('VelociraptorTriceratopsEtc.')) // succeeds
console.log(parseTwoDinos('T. RexVelociraptor…')) // succeeds
console.log(parseTwoDinos('TriceratopsNope')) // fails

Conclusion to Part 1

Below is the current state of our parser combinator library.

// type Parser a = String -> { result: a, remainder: String } | Null

// parseLiteral :: String -> Parser String
const parseLiteral = literal => s => s.startsWith(literal)
    ? { result: literal, remainder: s.slice(literal.length) }
    : null

// either :: (Parser a, Parser b) -> Parser (a | b)
const either = (p1, p2) => s => p1(s) || p2(s)

// both :: (Parser a, Parser b) -> Parser [a, b]
const both = (p1, p2) => s => {
    const r1 = p1(s)
    if (!r1) return null
    const r2 = p2(r1.remainder)
    if (!r2) return null
    return {
        result: [r1.result, r2.result],
        remainder: r2.remainder
    }
}

// any :: (...Parser *) -> Parser *
const any = (...parsers) => parsers.reduce(either)

In this first installment, we covered:

what parsing is
some use cases for parsers
one (non-functional) way to deal with failure
one (functional) way to eliminate state
function purity
using tuples (or arrays/objects) as return values
threading parser results sequentially
types, signatures, and aliases
basic parser combinators

In an upcoming sequel to this article, we will cover some more challenging issues:

dealing with longer sequences
dealing with choice
functors and monads
simulating infix function notation
formal grammars & parsing theory
recursive descent
laziness

Part 2 will be linked here once published.

About the Author

Gabriel Lebec is an instructor for Fullstack Academy of Code, an intensive web applications development program. He has a B.A. in Mathematics and Studio Art, and too many hobbies, including the art-historical study of antique Japanese swords. You can see more by Gabriel at Medium, YouTube, GitHub, and Twitter.

DEV Community: Gabriel Lebec

When Nesting Promises is Correct

Intro

The Setup

The Problem

Solutions

Library-Specific: Bluebird bind

A+-Compliant, ECMA-Approved: Promise.all

Controlled State, Shared Scope

The Punchline: Nested Promises

Silly Experiment: Formatting Tricks

The Promised Land: Async/Await

Conclusion

The FP Papers: Hughes Lists

A Novel Representation of Lists and its Application to the Function "Reverse"

Mutation?

Purity?

The Paper

Representations

The DList, Defined

Constant Time Append

Reverse

Conclusion

Property Testing with JSVerify · Part III

Part III: Intermediate JSVerify Usage

Using Built-In Arbitraries

Combinators: Deriving New Arbitraries from Existing Arbitraries

Transforming Arbitraries

Defining Custom Arbitraries from Scratch

Deriving Generators

Generator Combinators

Transforming Generators

Dependently-Generated Values

Writing Shrinks

Putting It All Together

Summary

Addendum

Property Testing with JSVerify · Part II

Part II: JSVerify Docs and Details

Type Documentation

Key JSVerify Types

generator a

Deterministic Randomness

shrink a

show

arbitrary a

property

Verification (unofficial)

checkoptions

env / typeEnv / map arbitrary

Property Testing with JSVerify · Part I

Part I: What is Property Testing?

Unit Testing

Ad-Hoc Property Testing via Dynamic Assertions

First-Class Property Testing with JSVerify

Diagnosing the Problem

But Wait, There's More!™ Check Out This One Weird Trick™

Summary & Try It Yourself

Four Ways to Immutability in JavaScript

Abstract

Introduction

What is an Immutable Update

Difficulties with Immutable Updates

Review of Vanilla JS Behavior

Primitives are Immutable (but also Re-assignable)

Objects are Mutable (but also Freezable)

Approach 1: Native Immutable Updates

Spread Syntax

Problems with Native Methods

Approach 2: Ramda lens

Context

High-Level

Demonstration

All You Need is Lens?

Approach 3: Immer

Demonstration

All You Need is Immer?

Approach 4: Immutable.js

Demonstration

All You Need is Immutable?

Library-Specific: Bluebird `bind`

A+-Compliant, ECMA-Approved: `Promise.all`

`generator a`

`shrink a`

`show`

`arbitrary a`

`property`

`checkoptions`

`env` / `typeEnv` / `map arbitrary`

Approach 2: Ramda `lens`