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.

Figure 1: Representing a layout as a graph

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:

  1. Create a new train state with the new position after moving, as before.
  2. 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.

Figure 2: Adjusting the train position

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.