Image for post
Image for post

Making Functional Machines with Elm

I recently encountered a little text processing problem in an app I was working on (see LaTeX in the Browser). Here is a version of the problem. Suppose given a list of a list of strings, say

The task is to join the strings to form good prose. The following is not the way to do it:

What is needed is a rule that looks at a string and and the string following it, and then joins them either with a space or no space, depending on some rule. We may want to produce the “join” directly, e.g.,

Or we may wish to first annotate the list of strings for further processing, like this:

The symbol S means “join to the following string with a space, N means join with no space, and P means the end of a paragraph — so add two blank lines if there is text following.

A More General Problem

This little problem leads to a more general one. Suppose that we have a list of things a_1, a_2, a_3, ... that we want to turn into a list b_1, b2, b3, ... The rule for computing b_k is a function of a_(k-1), a_k , and a_(k+1) — the current element, the element before, and the element after. Let’s try to solve the general problem, and then apply the solution to some special cases.

We can imagine our computation as being carried out by a machine that accepts an input tape, reads from it, and, consulting its internal state at each step, adds an element to an output tape. As a simple test case, our input tape will be a list of integers, as will be the output tape. See if you can guess the rule:

Each element of the output list is the sum of the corresponding element of the input list and its left and right neighbors. Look at the number 6 in the output list. It has position 2 (counting from 0, as computer scientists do). The number in position 2 in the input list is 2; the sum of this number and its two neighbors is 6.

What we want is a general solution to the general problem. That way we can test it on special cases like the one just described, then go on to confidently apply it in harder cases. All we have to do is verify the rule for computing output values.

This is what typed functional languages like Elm and Haskell allow us to do — capture a “pattern of computation.”

A List Processing Machine: Designing the Main Types

We will design a ListMachine module which exports just two things: a function called run and a type, InternalState. The first implements a way of transforming a list of a's into a list of b's. The second defines the internal state of the machine, and has type signature

The InternalState is what is needed to capture the idea of a “tape” of values where there is a value that is “currently being read” and where the machine has access to the values immediately to the left and right of the current on. We call these values “before” (left), “current”, and “after” (right). The Maybe values are needed because, for example, internalState.before may not be defined before the first cell of the tape is read.

To define an actual machine, one needs a function that computes a value of type b in terms of the internal state. Such a function has type

The function that “runs” the tape through the machine has type

Here is the output function for the example above:

If all goes well, we can do this:

Building the Machine

To build the machine, we need to capture not only the InternalState, with its input tape and three “registers,” before, current, and after, but also the current value of the output tape, whose elements are constructed one-by-one as the elements of the input tape are “read.” Here is the type of the full machine state:

The machine will process its tape using a foldl function, transforming an initial MachineState into a final one, where the final one carries the computed result in its outputList field. The type signature of foldl is

Let’s now compare types, assuming that the value produced by foldl is Machine a b. Then we must set v = Machine a b, and we must set u = a, since the input tape has type List a. The foldl we use in this context must therefore have the signature

This type alias is a bit long, so let’s agree on the following definitions. First, a generic Reducer (something consumed by foldl) has type alias u -> v -> v. Second, a ListMachine.Reducer is

Then our foldl type alias can be written as

This looks right: a reducer is used with an initial machine state and a list of inputs of type a to produce a final machine state. That final state holds an output list of elements of type b. From the type analysis, we deduce the function definition. In fact, given the types and given the fact that we use foldl, the only possible definition is the following one:

Computing the initial state

Suppose that we have a function initialMachineState inputList that builds a MachineState from an inputList. Then we can define a function applyReducer that takes a reducer and a list of a's and transforms it into a list of b's:

We compute the initial state, run the reducer, then extract the output list from the final state. To set up the initial state, we first set up the initial internal state

To set up the initial machine state, define an empty output list:

Computing the next internal state

To compute the next internal state, we use the function definition below. Note that the next internal state is a function of only one argument: the previous internal state. Put in other terms, this operation involves only reading from the input tape.

Reducing the input

We are almost finished. The penultimate step is to design a function for making reducers of type a b from functions of type InternalState a -> b. This is accomplished by the function makeReducer. It takes a single argument, an output function f : InternalState a -> b.

Once we have makeReducer, we can define ListMachine.run:

At long last we have a simple API. To define a ListMachine, we need only define an outputFunction of type InternalState a -> b. To run the resulting machine, execute

Example 1: the sumState machine

Recall the output function for lists of numbers:

It sums up the values of the the before, current, and after fields of the internalState. Here the computation we did at the beginning of this article

Example 2: String processing

Let’s go back to the string list example. Define a new output function:

We can run it to get an annotated list:

Example 3: a variant of String processing

Here is a slightly different output function:

And here is the result:

Conclusion

Elm’s type system is a powerful mechanism for abstraction. Once the underlying pattern of computation for a problem is extracted and given form with suitable type signatures and functions, it is often possible to give quite general solution with a simple API that hides a fair amount of complexity. The ListMachine package exemplifies this philosophy.

Reference: GitHub Repo for ListMachines or this Ellie.

Written by

jxxcarlson on elm slack, http://jxxcarlson.github.io

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store