Functional programming with Elm, part 2
In the first part of this series, I have talked a little about the functional programming paradigm, and I have shown what a simple simulation of a train moving on an infinite straight track looks like in Elm. But in reality, tracks are not infinite. The branch off each other and merge, and they end somewhere. In this part, I will explore a functional implementation of a train moving from one track to the next.
First, we need to look at the problem like a mathematician would. The concept in mathematics to describe connections is called a graph. The edges of the graph represent the individual pieces of railroad track, and the vertices represent the points where the tracks meet.
First, we need to add a graph library to the project. This simply tells the package manager that we are going to use this particular add-on library.
> elm install drathier/elm-graph
Here is my plan:
Add:
drathier/elm-graph 4.0.0
elm/random 1.0.0
elm-community/list-extra 8.2.4
elm-community/maybe-extra 5.2.0
elm-community/random-extra 3.1.0
elm-explorations/test 1.2.2
owanturist/elm-union-find 1.0.0
Would you like me to update your elm.json accordingly? [Y/n]:
Success!
We need to define what we actually mean by a track. We will ignore curves, inclines, and other complications for now and stick to straight tracks, but with a certain, finite length.
type alias Track = { length : Float } -- in m
We can now use a graph to represent the connections between the tracks. I will call this data structure Layout
.
import Graph exposing (Graph)
type alias Layout =
Graph Int () Track
The import statement will not look too strange if you know your various script languages. The type alias means that we can use Layout
as a shorthand for the specific type of graph we need.
Graph is actually a generic type that could hold all sorts of data. For our purpose, we want a graph that uses Int
as keys for its vertices, that carries no extra data on the vertices, hence the ()
, and that uses Track
to hold additional data about the edges. The ()
syntax is a tuple with zero elements, or Elm’s idea of “nothing particular.” As the connections in our layout do not have any additional information associated with them apart from just being there, we don’t need an additional type here–but we will need that later when we get to switching between different branch lines.
As an aside, if you wonder about what is going on in the “declaration” of the Graph above: Graph
refers to a function that returns a type, which is then assigned to the name Layout
. That function takes three parameters, which are themselves types; in our case Int
, Track
, and ()
. A function like that is called a type constructor. Elm is somewhat limited in how you can work with types this way, e.g. I think you cannot have a list of type constructors [Graph a b c, Tree a, Weird a]
and apply a certain type to them all at once. But that’s okay. In full-blown functional programming languages like Haskell, this is a major source of Power.
You may have heard that functional programming uses λ (lambda) calculus. A system that can construct types this way through functions is called Fω (F-omega) calculus. If you are curious, there is even one more level to achieve beyond that, the Calculus of Constructions, λC. But then, in mathematics there is always another level.
Moving on
We need to amend the train state with the track the train is currently on. Each track is identified by the two vertices it connects. I will define a new record type for the train location that contains the position of the train on the current track, the two vertex numbers for the current track, and, for convenience, the track information itself.
type alias TrainState =
{ name : String
, length : Float -- in m
, speed : Float -- in m/s
, location : Maybe TrainLocation
}
type alias TrainLocation =
{ edge : ( Int, Int ) -- The vertices
, pos : Float -- The position on the track in m from the first vertex
, track : Track -- The track information for convenience
}
The train location is a Maybe TrainLocation
. This is a neat trick in Elm and other programming languages to say there could be none. Maybe
is actually a type, and it allows type-safe code without null pointer exceptions. See the Elm Guide for more information about this. For now, let me say that a variable of type Maybe someType
can contain either Nothing
or Just something
, where something
will be of the type someType
we specified earlier. In other words, a Maybe Int
could be either Nothing
or Just 5
or Just -37
or any other integer wrapped in a Just
. We can use this to implement null-pointer-safe code, as we will see later.
Now, let’s reconsider what the move
function did: It simply calculated the new position of a train based on its previous position on the track, depending on its speed and the elapsed time. Now, we need to check if the train is leaving the current track and entering the next one, and handle this transition. In order to do that, we pass the layout into the function, so that we can decide what the next track actually is.
move : Layout -> Int -> TrainState -> TrainState
move layout millis trainState =
To implement the function, I will write it down in a semi-mathematical way:
- Create a new train state with the new position after moving, as before.
- Pass the new state into a function that will normalize the position by checking if the train is still on the track, and adjusting if necessary.
Here is the code:
case trainState.location of
Nothing ->
-- If the train has no location, no need to move.
trainState
Just loc ->
-- Create a new train state ...
{ trainState
-- ... but replace the location with a new location ...
| location =
-- ... based on the old location but with an updated position ...
{ loc | pos = loc.pos + trainState.speed * toFloat millis / 1000.0 }
-- and finally "normalize" the location in case we are on a different track now.
|> normalizeLocation layout
}
The case ... of
statement with its two branches Nothing ->
and Just loc ->
handles the case that the train may not have a valid location. In this case, we are returning the previous train state. If there is a valid location, then we create a new train state based on the previous one.
The |>
means “pass the result on into the next function.”
This is the implementation of normalizePosition
, the function that fixes things when the train enters a new track:
normalizeLocation : Layout -> TrainLocation -> Maybe TrainLocation
normalizeLocation layout loc =
-- If the position is beyond the end of the current track ...
if loc.pos > trackLength loc.track then
-- ... get the next track.
case nextTrack loc.edge layout of
Nothing ->
-- If there is no next track, return.
Nothing
Just ( otherEdge, otherTrack ) ->
-- Calculate the new position.
{ loc
-- Subtract the current track length from the position.
| pos = loc.pos - trackLength loc.track
-- Set the edge ...
, edge = otherEdge
-- ... and track info for the new location.
, track = otherTrack
}
-- ... and repeat until done.
|> normalizeLocation layout
else
-- We are within the track bounds, so return.
Just loc
If you look closely, it requires a nextTrack
function that returns the next track the train will move on. It will retrieve the next track from the layout graph. The graph library provides some convenient functions, such as outgoing
which gives us a set of edges outgoing from a specific vertex.
nextTrack : ( Int, Int ) -> Layout -> Maybe ( ( Int, Int ), Track )
nextTrack ( fromId, toId ) layout =
Graph.outgoing toId layout
|> Set.toList
-- Arbitrarily select the first track on the list for now.
|> List.head
-- If the list was empty, head will return Nothing.
-- andThen only applies the next function if the input exists.
-- In this case, create the edge.
|> andThen (\otherId -> Just ( toId, otherId ))
-- If we are good so far ...
|> andThen
-- ... take the edge we created earlier, ...
(\edge ->
-- ... and get the Track for this edge.
case Graph.Pair.getEdgeData edge layout of
Nothing ->
-- If we don't have track information, return.
Nothing
Just track ->
-- If we have it, return the new edge and the Track.
Just ( edge, track )
)
Next
We have glossed over the topic of more complex layouts with lines branching off and merging into the mainline. Before we address that, we should first implement curved tracks, so we can add more realism instead of having only a view of what is connected where.
Here is again a simple visualization of the transition from one track to the next, marked in blue and green. Note also the track change in the debug output below.