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

["He", "said", "," , "Hi", "there", "!"] 

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

> String.join " " ["He", "said", "," , "Hi", "there", "!"]
"He said , Hi there !"

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.,

"He said, Hi there!"

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

[("He", S), ("said", N), (",", S) , ("Hi", S), 
    ("there", N), ("!", P)]

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:

Step 0:  Input = [0, 1, 2, 3, 4]  Output = [ ]
Step 1:  Input = [1, 2, 3, 4]     Output = [1]
Step 2:  Input = [2, 3, 4]        Output = [1, 3]
Step 3:  Input = [3, 4]           Output = [1, 3, 6]
Step 4:  Input = [4]              Output = [1, 3, 6, 9]
Step 5:  Input = [ ]              Output = [1, 3, 6, 9, 7]

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

type alias InternalState a = 
   { before: Maybe a, 
     current: Maybe a, 
     after: Maybe a, 
     inputList: List a }

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

InternalState a -> b

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

run : (InternalState a -> b) -> List a -> List b

Here is the output function for the example above:

sumState : InternalState Int -> Int 
sumState internalState = 
  let
    a = internalState.before  |> Maybe.withDefault 0 
    b = internalState.current |> Maybe.withDefault 0 
    c = internalState.after   |> Maybe.withDefault 0 
  in  
    a + b + c

If all goes well, we can do this:

ListMachine.run sumState [1,2,3,4]
==> [1, 3, 6, 9, 7]

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:

MachineState a b = 
    {internalState: InternalState a, outputList: List b}

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

List.foldl : (u -> v -> v) -> v -> List u -> v

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

(a -> (Machine a b) -> (Machine a b)) -> (Machine a b) -> List a -> Machine a b

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

type alias Reducer a b = a -> MachineState a b -> MachineState a b

Then our foldl type alias can be written as

ApplyReducerToMachine : Reducer a b -> (Machine a b) -> List a -> Machine a b

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:

applyReducerToMachineState : Reducer a b -> MachineState a b 
                             -> List a -> MachineState a b applyReducerToMachineState reducer initialState inputList =      
         List.foldl reducer initialState inputList

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:

applyReducer : Reducer a b -> List a -> List b
applyReducer reducer inputList = 
  let
    initialState = initialMachineState inputList 
    finalState = applyReducerToMachineState reducer initialState     
                   inputList
  in
    List.reverse finalState.outputList

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

makeInitialState : List a -> InternalState a
makeInitialState inputList = 
  {before = Nothing
   , current = List.head inputList 
   , after = List.head (List.drop 1 inputList)
   , inputList = inputList
   }

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

initialMachineState inputList = 
  {internalState =  makeInitialState inputList, outputList = []}

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.

nextInternalState : InternalState a -> InternalState a
nextInternalState internalState_ = 
  let 
     nextInputList_ = List.drop 1 internalState_.inputList
  in
  {  
    before = internalState_.current
   , current = internalState_.after 
   , after = List.head (List.drop 1 nextInputList_)
   , inputList = nextInputList_
  }

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.

makeReducer : (InternalState a -> b) -> Reducer a b
makeReducer computeOutput input machineState =
  let 
    nextInputList = List.drop 1 machineState.state.inputList  
    nextInternalState_ = nextInternalState machineState.state
    newOutput = computeOutput machineState.state
    outputList = newOutput::machineState.outputList 
  in
    {internalState = nextInternalState_, outputList = outputList}

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

run : (InternalState a -> b) -> List a -> List b
run outputFunction inputList =
   applyReducer (makeReducer outputFunction) inputList

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

run theOutputFunction theInputList

Example 1: the sumState machine

Recall the output function for lists of numbers:

sumState : InternalState Int -> Int 
sumState internalState = 
  let
    a = internalState.before  |> Maybe.withDefault 0 
    b = internalState.current |> Maybe.withDefault 0 
    c = internalState.after   |> Maybe.withDefault 0 
  in  
    a + b + c

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

ListMachine.run sumState [0, 1, 2, 3, 4]
=> [1, 3, 6, 9, 7].

Example 2: String processing

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

type SpacingSymbol = Space | NoSpace | EndParagraph
stringJoiner : InternalState String -> (String, SpacingSymbol)
stringJoiner internalState =
  let 
    b = internalState.current |> Maybe.withDefault ""
    c = internalState.after   |> Maybe.withDefault "" 
    symbol = if internalState.after == Nothing then 
          EndParagraph
       else if List.member (String.left 1 c) 
          [",", ";", ".", ":", "?", "!"] then 
          NoSpace 
       else 
          Space
  in 
    (b, symbol)

We can run it to get an annotated list:

ListMachine.run stringJoiner ["He", "said", ",", "Wow", "!"]
==> [("He",Space),("said",NoSpace),(",",Space),("Wow",NoSpace),("!",EndParagraph)]

Example 3: a variant of String processing

Here is a slightly different output function:

stringJoiner2 : InternalState String -> String
stringJoiner2 internalState =
  let 
    b = internalState.current |> Maybe.withDefault ""
    c = internalState.after   |> Maybe.withDefault "" 
    output =  if internalState.after == Nothing then 
                  b ++ "\n\n"
              else if List.member (String.left 1 c) 
                  [",", ";", ".", ":", "?", "!"] then 
                  b 
              else 
                  b ++ " "
  in 
    output

And here is the result:

ListMachine.run stringJoiner2b ["He", "said", ",", "Wow", "!"]
==> ["He ","said",", ","Wow","!\n\n"]

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.