Making Functional Machines with Elm

`["He", "said", "," , "Hi", "there", "!"] `
`> String.join " " ["He", "said", "," , "Hi", "there", "!"]"He said , Hi there !"`
`"He said, Hi there!"`
`[("He", S), ("said", N), (",", S) , ("Hi", S),     ("there", N), ("!", P)]`

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.

`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]`

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 }`
`InternalState a -> b`
`run : (InternalState a -> b) -> List a -> List b`
`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`
`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}`
`List.foldl : (u -> v -> v) -> v -> List u -> v`
`(a -> (Machine a b) -> (Machine a b)) -> (Machine a b) -> List a -> Machine a b`
`type alias Reducer a b = a -> MachineState a b -> MachineState a b`
`ApplyReducerToMachine : Reducer a b -> (Machine a b) -> List a -> Machine a b`
`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 bapplyReducer reducer inputList =   let    initialState = initialMachineState inputList     finalState = applyReducerToMachineState reducer initialState                        inputList  in    List.reverse finalState.outputList`
`makeInitialState : List a -> InternalState amakeInitialState inputList =   {before = Nothing   , current = List.head inputList    , after = List.head (List.drop 1 inputList)   , inputList = inputList   }`
`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 anextInternalState 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 bmakeReducer 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}`
`run : (InternalState a -> b) -> List a -> List brun outputFunction inputList =   applyReducer (makeReducer outputFunction) inputList`
`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`
`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 | EndParagraphstringJoiner : 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)`
`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 -> StringstringJoiner2 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`
`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.

--

--

More from James Carlson

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

Love podcasts or audiobooks? Learn on the go with our new app.