# 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