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 b
applyReducer reducer inputList =
let
initialState = initialMachineState inputList
finalState = applyReducerToMachineState reducer initialState
inputList
in
List.reverse finalState.outputList
makeInitialState : List a -> InternalState a
makeInitialState 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 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}
run : (InternalState a -> b) -> List a -> List b
run 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 -> 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
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.

--

--

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