JavaScript à la ML
I just finished reading An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson. Towards the end, the author teaches some SML and Lisp. I came across a handful of short functions that took advantage of SML’s structure pattern matching syntax and recursion, two very important functional features which you may also see in more broadly used FP languages like Erlang, Haskell, Rust, F#, to name a few. I thought, why not JavaScript? While JavaScript has no native pattern matching support, there’ve been some valiant attempts to do so via userland libraries such as:
However, I didn’t think they really brought much value. Other projects seemed really stale. The best would be, of course, to bring pattern matching natively to JavaScript as outlined in the following proposal:
I urge you to support this stage-0 project as it definitely gets the conversation going and the attention it deserves. Nevertheless, JavaScript has come a long way with destructuring support, which you can think as a very elementary pattern match and a good starting point for this new proposal.
So, I decided to use JavaScript to see if I could mimic the expressiveness in SML to approach some trivial functions in this functional manner.
First, a little about the SML syntax you’ll see, if you’re not familiar. SML is a statically typed language, so an integer i is declared as i: int, a list of strings t as t: string list. Lastly, the infix :: concatenation operator that will return a new list with the first object in head position and the other in tail position, e.g. 0::[1,2,3] -> [0,1,2,3] . For the exercises posted here, this is the extent to which you ’ll use SML syntax.
I’ll need to find JavaScript counterparts to these language features. Like I said before, destructuring allows me to easily decompose an array into head and tail using [h, … tail]as a substitute for [h::t]. This will make recursive solutions much easier. As far as types is concerned, I used Flow. With Flow, a number i is declared as i: number and a sequence of strings t as t: Array<string>. To get closer to SML, I’ll declare a Flow type alias:
type list<E> = Array<E>And that’s about it, really! Let’s work our way there:
Example 1: functions of two case clauses
These examples showcase simple recursive algorithms with a two case-style pattern match: a base and a recursive step. Keep in mind, under the hood, pattern matching is nothing more than the top-bottom conditional branching matching the structure and shape of the provided arguments. When a match is found, the function executes the expression on the right. In SML, this would look like:
fun length [] = 0 |
length (_::(t:int list)) = 1 + (length t);There are 2 case style expressions. If you call length with an empty array, zero is returned. Otherwise, check the next case clause (separated by |) which would match a non-empty array. In this case, the head is matched with a wildcard character _ and discarded, finally the recursive call computes 1 plus the length of the tail of the list.
Now, pretend there’s no Array.prototype.length property in JavaScript for a moment, we could express this as:
const length = ([h, ...tail]: list<number>): number =>
isNil(h) ? 0
: 1 + length(tail)assert.equal(length([]), 0)
assert.equal(length([1,2,3]), 3)
Structurally, I feel this function retains that same expressiveness of the pattern match clause on the left with the return value on the right. Think of each ternary operator a ? b : c as piping together the case clauses — match a, if true execute b, otherwise execute c. Aside from readability, I especially like that it pushes us to use tail recursion and immutability!
In the same vein, we can create other little programs with the same pattern:
Sum elements in a list:
const sum = ([h, ...tail]: list<number>): number =>
isNil(h) ? 0
: h + sum(tail)assert.equal(sum([]), 0)
assert.equal(sum([1,2,3]), 6)
Print the first n cubes starting at 0:
const cubes = (n: number): list<number> =>
!n ? [0]
: cubes(n - 1).concat([n * n * n])assert.deepEqual(cubes(0), [0])
assert.deepEqual(cubes(3), [0, 1, 8, 27])
So, that’s all fun and good, but does this pattern break with > 2 case clauses?
Example 2: functions of three case clauses
I’ll implement a function that finds the ith element in string list. In SML:
fun sifind _ [] = "can't find it" |
sifind 0 ((h:string)::_) = h |
sifind (i:int) (_::(t:string list)) = sifind (i - 1) t;This is the beauty and power of pattern matching in that it’s so declarative that you can read the algorithm off the screen: try to find any position in an empty list and get an error; or try to find the first string in the list then you get the head of the list; lastly, continue to look in the rest of the list.
Let’s implement this in JavaScript so that it reads the same way. I’ve taken the liberty to add a bit more flare and declare a function find that would find the ith element in a list of objects mixed. The return type is an Either to better represent both the failure and the success states.
const find = (i: number, [h, ...tail]: list<mixed>): Either<string, number>
=>
isNil(h) ? Either.Left(`Element not found at ${i}`)
: i === 0 ? Either.Right(h)
: find(i - 1, tail)assert.isTrue(find(0, []).isLeft)
assert.isTrue(find(1, [0]).isLeft)
assert.isTrue(find(2, ['a', 'b', 'c']).isRight) assert.equal(find(2, ['a', 'b', 'c']).fold(null, identity), 'c')
Let’s add another 3-case clause example. This time, I’ll write a function to replace the ith element of a list with another element. You should start to see a pattern in these:
const replace = (i: number, e: mixed, [h, ...tail]: list<mixed>):
list<mixed>
=>
isNil(h) ? []
: i === 0 ? [e, ...tail]
: [h].concat(replace(i - 1, e, tail))
assert.deepEqual(replace(2, 'Jo',
['Chris', 'Jean', 'Les', 'Pat', 'Phil']),
['Chris', 'Jean', 'Jo', 'Pat', 'Phil']
)
Hopefully, you’ve noticed another functional quality if all of these programs — immutability. In this particular case, replacing a value never changes the original array.
Let’s look at one last example, a general purpose list insertion function:
const insert = (e: any, [h, ...tail]: list<any>): list<mixed> =>
isNil(h) ? [e]
: e < h ? [e, h, ...tail]
: [h].concat(insert(e, tail))assert.deepEqual(insert('Jo',
['Chris', 'Jean', 'Les', 'Pat', 'Phil']),
['Chris', 'Jean', 'Jo', 'Les', 'Pat', 'Phil']
)
assert.deepEqual(insert('Jo', []), ['Jo'])
In this case I decided to use a list of any so that the overloaded comparison operator e < h works , just as in untyped JS.
Of course, I’d much rather see a more declarative pattern matching syntax rather than having to use if then else, but if you think about it, behind the scenes that’s kind of how it works.
That’s all I wanted to share. I thought it was really great that we can reason about and express code in this way using JavaScript. It’s a testament to how malleable the language is. I think it’s definitely headed in the right direction and we should continue pushing for these FP-oriented proposals as much as possible.
Thanks for reading!
P.S. If you have an example of a > 3 case “pattern matching” function in JS, please feel free to drop a comment :-)
Resources
- An Introduction to Functional Programming Through Lambda Calculus, Greg Michaelson
