Elm – Recursive Functions

In one of the Elm For Beginners exercises I have to update a player record’s name field with the modified player name and all I have is the playerId to search on.

Here are the Elm type alias for the Model and the Player

type alias Model =
    { players : List Player
    , name : String
    , playerId : Maybe Int
    }

type alias Player =
    { id : Int
    , name : String
    , points : Int
    }

If I were writing this in C# I’d probably have the Player objects stored in a generic List. To modify PlayerId’s name I’d probably use a foreach statement to iterate through the list. When I found the Player object who’s id matched PlayerId, I’d change the player’s name.

public int PlayerId;
public string Name;
public List<Player> Players;

public class Player
{
    public int Id { get; set; }
    public string Name { get; set; }
    public int Points { get; set; }
}

// 1. Code to create Players list and populate with Players
// 2. Code to set Name to player's new name
// 3. Code to set PlayerId of player whose name you want to update

foreach (Player p in Players)
{
    if p.Id = PlayerId {
        p.Name = Name;
    }
}

But Elm doesn’t have control structures like for, foreach, while, or do-while. So how do I iterate over the record elements in the list below and modify the one player record that meets the criteria?

[ { id = 2, name = "Robin Maya", points = 0 }
  , id = 1, name = "Katie Maya", points = 0 }
  , id = 0, name = "Bill Maya", points = 0 } ] 

From working with Clojure and reading Functional Programming for the Object-Oriented Programmer I knew that is was possible to extract the items in a list. Elm provides you with head function to extract the first element of a list.

head : List a -> Maybe a
head [1, 2, 3] == Just 1
head [] == Nothing

And a tail function to extract the rest of the list.

tail : List a -> Maybe (List a)
tail [1, 2, 3] == Just [2, 3]
tail [] == Nothing

The type annotation before the head and tail examples is an Elm convention that makes is easier at a glance to determine a function’s inputs and outputs and also easier to debug compiler warnings.

Both functions take a list (“List a”) as input and output a single element of that list (“Maybe a” for head) or the remainder of the list (“Maybe (List a) for tail”).

The “Maybe” in this type annotation indicates that in certain situations, like when an empty list is passed as a parameter, nothing might be returned (in fact, Nothing is returned).

Since Elm doesn’t support null values it uses the union types of Maybe, Just, and Nothing to handle situations like this (I’ll probably do a blog post about these types at a later date as I try to understand them better).

So using head and tail I could systematically extract the values of a list for review. If I take the example Elm list with the three Player records in it that I showed previously and applied successive head and tail functions to it I would get this:

#1
head == { id = 2, name = "Robin Maya", points = 0 }
tail == [ { id = 1, name = "Katie Maya", points = 0 }
          , id = 0, name = "Bill Maya", points = 0 } ]

#2
head == { id = 1, name = "Katie Maya", points = 0 }
tail == [ { id = 1, name = "Bill Maya", points = 0 } ]

#3
head == { id = 1, name = "Bill Maya", points = 0 }
tail == []

So I can extract individual list elements but one question remains–what mechanism do I use to leapfrog my way through the list since Elm doesn’t provide foreach or do-while control structures?

Some thinking and googling lead me to this page which explained how to create recursive functions in Elm.

To explain how a recursive function works here’s an example of how to calculate the factorial of a number using recursion. In mathematics, the factorial n! of a non-negative number n is the product of all positive integers less than or equal to n. For example,

5! = 5 x 4 x 3 x 2 x 1 = 120

The Elm function to calculate the factorial of a number would be:

import Html exposing (..)

main = Html.text (toString (factorial 5))

factorial : Int -> Int
factorial int =
    case int of
        0 ->
            1
        _ ->
            int * factorial (int - 1)

The factorial function type annotation (line 5) indicates that this function takes an Int as a parameter and returns an Int. The case statement in the body of the function (lines 6-10) uses pattern matching to determine what to do with the parameter value passed into the function:

  • If the value of int is zero the functions returns a value of one
  • Otherwise, for any other value (“_” acts as a wildcard) the function calls itself again, subtracting one from the current value of int. The value returned from this function call is multiplied by the original value of int.

In the example above, calling the factorial function with the parameter of 5 makes five recursive function calls.

factorial 5
    5 * factorial 4
        4 * factorial 3
            3 * factorial 2
                2 * factorial 1
                    1 * factorial 0
                        1

Which yields the value of 120.

Back to my original problem–I have to update one of the records in the list using the player’s id.

[ { id = 2, name = "Robin Maya", points = 0 }
  , id = 1, name = "Katie Maya", points = 0 }
  , id = 0, name = "Bill Maya", points = 0 } ] 

So I wrote a recursive updatePlayer function to do that.

updatePlayer : Player -> List Player -> List Player
updatePlayer player players =
    case players of
        [] ->
            []
        x :: xs ->
            if x.id == player.id then
                { x | name = player.name } :: xs
            else
                updatePlayer player xs

The function takes two parameters–the first is a single player object containing the id of the player to update and their new name. The second is a list of current players. The function returns a list of updated players.

The case statement uses pattern matching to determine what to do with the list that’s passed as a parameter into the function. If the list is empty, it simply returns and empty list (lines 4-5).

The pattern on line 6 splits the list into a head and a tail. The head (a record) is assigned to x and the tail (a list) is assigned to xs. If the id of the head record is equal to the id in the player record a new player record is created with an updated player name (obtained from the player record) using the following format:

newRecordName =
    { oldRecordName | fieldName1 = newFieldValue1
                    , filedName2 = newFieldValue2
                    ...
    }

Rather than assigning this newly created record (Elm data is immutable) I simply it after using the cons statement (::) to add it to the front of the list stored in xs

If the id of the head record is not equal to the id in the player record then I recursively call the updatePlayer function again, passing in the player object and the tail stored in xs as the list.

This first attempt of updatePlayer has an error in it. When passing in the Before list the function returned the After list. The player’s name was updated from “Katie” to “Kathleen” but I lost one of my records. Rather than retaining a record that didn’t match the player id the function appeared to be throwing it away until if found a match.

Before:
[ { id = 2, name = "Robin Maya", points = 0 }
  , id = 1, name = "Katie Maya", points = 0 }
  , id = 0, name = "Bill Maya", points = 0 } ]

After:
[ { id = 1, name = "Kathleen Maya", points = 0 }
  , id = 0, name = "Bill Maya", points = 0 } ]

I spent some time trying to figure out why this was happening but ran up against my limited knowledge of Elm and my unfamiliarity with functional programming. I thought about also passing in an empty list as one of the parameters and using it to store head records as I iterated through the list but that seemed kludgy.

So I did the next best thing–I decided to sleep on it and return to the problem the next day.

Fifteen minutes after sitting down at the keyboard the next morning I discovered my omission.

-- Original
updatePlayer : Player -> List Player -> List Player
updatePlayer player players =
    case players of
        [] ->
            []
        x :: xs ->
            if x.id == player.id then
                { x | name = player.name } :: xs
            else
                updatePlayer player xs

-- Modified
updatePlayer : Player -> List Player -> List Player
updatePlayer player players =
    case players of
        [] ->
            []
        x :: xs ->
            if x.id == player.id then
                { x | name = player.name } :: xs
            else
                x :: updatePlayer player xs

Compare the recursive function call on lines 11 and 23. Line 11 discards the unmatched head record when calling updatePlayer again while line 23 uses the cons (::) function to “stitch” the unmatched head record to the whatever results are returned by subsequent calls to updatePlayer.

I was quite pleased with myself for about fifteen minutes. Not only had I figured out how to iterate through a list using Elm pattern matching but I was also one step closer to grokking the immutable nature of data in Elm.

But then I reviewed the lesson’s answer to see the instructor’s solution and discovered another way to accomplish the same thing using two new Elm functions and no recursion. It was a bit humbling. I’ll write about it in my next post.

Helpful links

This entry was posted in Software Development and tagged , , . Bookmark the permalink.