Othello Kata: The Iterator Pattern in JavaScript/TypeScript Functional Programming
This article is part of a series about functional programming concepts demonstrated on well-known kata in TypeScript. See FizzBuzz Kata: An Exploration With Functors!
Othello (a.k.a. Reversi)
In addition to being a famous tragedy by William Shakespeare, Othello is a strategy board game for two players played on an 8×8 board. It is told to require “a minute to learn, [and] a lifetime to master”. Indeed, it is not unusual to see dramatic reversals of advantage up to the end of the play. If you’re not familiar with this game and want to learn, you can give it a try online.
In this kata, we’ll try and implement the feature of telling where a player can play:
Now we choose to model the play board as an array of arrays:
At some point, this kata requires to iterate over the play board and determine for each cell if placing a disk allows to capture disks of the opponent’s color. With an array of arrays, this means looping over the lines (1 to 8) and for each line to loop over the columns (A to H).
But that’s implementation details, and one could expect to loop over the play board without knowing how this actually happens. That’s where the iterator pattern pops up!
The Iterator pattern
Iterating over an array seems pretty obvious, you just loop over all its items. But how do you iterate over a tree? Depth-first traversal and breadth-first traversal are the most useful and common approaches, although other ones could be envisioned. In any case, the corresponding implementation details are not the concern of the client code.
Refactoring Guru states:
Iterator is a behavioural design pattern that lets you traverse elements of a collection without exposing its underlying representation.
In JavaScript, the iterator protocol specifies the interface an object must implement in order to be iterable in a for...of statement. Concretely, an object is an iterator when it implements a next() method that returns an object with the following two properties:
done:falseif the iterator is able to produce a next value in the collection;trueif the iterator has completed its sequence.value: ifdoneisfalse, the next JavaScript value that is part of the collection. Otherwise this property is not defined.
This is very handy but not much suited to a functional style of programming, which favours declarations over imperative statements (see Declarative Programming on Wikipedia). In practice, this means that one would prefer to iterate over the data structure using a map or reduce function rather than a for...of loop.
As a consequence, the iterator pattern needs to be adapted.
Iterating over arrays
With arrays, iteration is typically achieved through the reduce function, which has the following signature:
Array.prototype.reduce(callback(accumulator, currentValue[, index[, array]]) {
...
}[, initialValue]);A common use case of the reduce function is adding all an array’s numbers:
By the way, the reduce function is fundamental because the map and filter functions derive from it, as suggested by these alternative implementations:
Now, inspired by arrays, we’re going define a reduce function with a similar signature in order to iterate over the play board.
A suggested implementation
First let’s define the generic interface of an collection over which we can iterate with a reduce function:
Now we can define an iterable play board as follows:
And implement the actual looping over the play board. The board’s reduce function relies on the reduce functions of the underlying arrays:
Thanks to the above, it has finally become possible to iterate over the play board via a reduce function. In plain English, we iterate over the board and collect the coordinates of playable cells in an array:
Final thoughts
Via a concrete example, this article illustrates the fact that many object-oriented programming patterns remain valid in the functional programming world, assuming a few adaptations.
Transposing a pattern from one programming style to the other requires to refer to the original problem the pattern intended to solve, e.g. here iterating over a data structure without knowing about the specifics of it.
Comments are welcomed. Thanks for reading!
