3.16

List

So far we have only seen how to store a single value in a data structure. To store multiple values, we can use one of the following collections Elm provides: List, Array, Tuple, or Record. This section covers list. The rest will be covered in successive sections.

Creating a List

In Elm, a list is a data structure for storing multiple values of the same kind. List is one of the most used data structures in Elm. A list is created with square bracket literals. Each element in a list must be separated by a comma. Here are some examples:

> [ 1, 2, 3 ]
[1,2,3] : List number

> [ 'a', 'b', 'c' ]
['a','b','c'] : List Char

> [ "Tobias", "Gob", "George Michael" ]
["Tobias","Gob","George Michael"] : List String

Elm style guide recommends using a space after [ and a space before ]. But when the repl prints a list, it doesn’t include those spaces because the style guide is created to improve the readability of code for humans.

What happens when we try to put values of different kind in a list?

> [ 1, 'a' ]

-------------- TYPE MISMATCH --------------------------
The 1st and 2nd elements are different types of values.

7|   [1, 'a']
         ^^^
The 1st element has this type:

    number

But the 2nd is:

    Char

Elm doesn’t like that. We can also create a numeric list by specifying a range.

> List.range 1 5
[1,2,3,4,5]

Like String, the List module is also loaded automatically by the repl. Therefore, we don’t need to explicitly import it before using the functions included in it.

A range is created by specifying the first and last numbers in a sequence. It’s a nice shortcut that prevents you from having to type out a long list of numbers. As of this writing, Elm can only use a range to create a list of numbers, not other types like characters or strings.

> List.range 'a' 'z'

--------------------- TYPE MISMATCH -----------------------
The 1st argument to function `range` is causing a mismatch.

3|   List.range 'a' 'z'
                ^^^
Function `range` is expecting the 1st argument to be:

    Int

But it is:

    Char

Like String and Regex modules, the Elm Platform comes pre-loaded with the List module too. It provides a variety of functions to work with lists. Let’s go through some of them.

Checking Membership

The member function determines whether or not an item is present in a given list.

> List.member "Jayne" [ "Kaylee", "Jayne", "Malcolm" ]
True

> List.member "Inara" [ "Kaylee", "Jayne", "Malcolm" ]
False

Checking Length

The isEmpty function determines whether or not a list is empty whereas the length function returns the number of elements in a list.

> List.isEmpty []
True

> List.isEmpty [ "Dolores", "Teddy", "Elsie" ]
False

> List.length []
0

> List.length [ 1, 2, 3 ]
3

> List.length [ "Daenerys", "Tyrion", "Arya", "Khal Drogo" ]
4

Reversing a List

> List.reverse [ 1, 2, 3 ]
[3,2,1]

> List.reverse [ "Stark", "Tully", "Arryn" ]
["Arryn","Tully","Stark"]

reverse returns a new list that contains elements from the original list in reverse order.

Combining Lists

The List module provides multiple functions for putting lists together. Let’s start with something we’re already familiar with: ++ operator.

> [ 1, 2, 3 ] ++ [ 4, 5, 6 ]
[1,2,3,4,5,6]

> [ "Donna", "Eric" ] ++ [ "Fez", "Hyde", "Kelso" ]
["Donna","Eric","Fez","Hyde","Kelso"]

We can also combine more than two lists with ++ operator.

> [ "Donna", "Eric" ] ++ [ "Fez", "Hyde", "Kelso" ] ++ [ "Jackie", "Kitty" ]
["Donna","Eric","Fez","Hyde","Kelso","Jackie","Kitty"]

Like String.append, the List module also provides the append function that lets us combine two lists.

> List.append [ 1, 2 ] [ 3, 4 ]
[1,2,3,4]

Combining more than two lists with append is a bit tedious though.

> List.append (List.append [ 1, 2 ] [ 3, 4 ]) [ 5, 6 ]
[1,2,3,4,5,6]

If we have a bunch of lists buried inside another list, we can use the concat function to flatten it like this:

> List.concat [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ] ]
[1,2,3,4,5,6]

Finally, we can add an element to the front of a list using :: (pronounced cons) operator.

> 1 :: []
[1]

> 1 :: [ 2, 3 ]
[1,2,3]

Splitting a List

Partitioning a List

Unlike strings, we can’t use a separator to split a list. But what we can do is partition a list based on some criteria. The elements that satisfy the criteria will be put into one list and the ones that don’t into another. A predicate function is the perfect place to store our criteria. As a reminder, a predicate is a function that takes a value as an input and returns a boolean as an output. Here’s an example that partitions a list using an anonymous function as a predicate.

> List.partition (\x -> x < 4) [ 1, 2, 3, 4, 5, 6 ]
([1,2,3],[4,5,6])

Here’s another example that uses a normal function as a predicate to partition a list.

> isEvil name = List.member name [ "Joffrey", "Ramsay", "Cersei" ]
<function>

> List.partition isEvil [ "Samwell", "Cersei", "Hodor", "Joffrey", "Meera", "Ramsay" ]
(["Cersei","Joffrey","Ramsay"],["Samwell","Hodor","Meera"])

The elements that satisfy the predicate are placed into the first list, the rest go into the second list. Notice how partition returns a tuple containing the partitioned lists?

A tuple is a container like list, but we can put values of different kinds into it, e.g. (1, "Sobchak", ['t', 'd']). Tuples are quite useful for returning multiple results from a function. We will cover it in much more detail in the Tuple section.

You might be wondering why the partition function didn’t return a list instead of a tuple. After all a list can hold multiple lists inside it too. That’s because lists must contain values of the same kind, but tuples don’t have to. In the future, if partition decides to also return the number of elements in each list like this: (3, [1,2,3], 3, [4,5,6]), it won’t be able to do that with a list. Tuples on the other hand are perfect for situations like this.

Unzipping a List

Let’s say we have a list of tuples each containing two elements.

[ ( "Andy", True ), ( "Hadley", False ), ( "Red", True ) ]

How can we split it into two lists? We can use the unzip function to accomplish that.

> List.unzip [ ( "Andy", True ), ( "Hadley", False ), ( "Red", True ) ]
(["Andy","Hadley","Red"],[True,False,True])

The first list contains the first item from each tuple in the original list and the second list contains the second item. Notice that unzip also returns a tuple instead of a list. You will see this pattern of functions returning multiple values in a tuple in most Elm code.

Sorting a List

Ascending order

Below is a list of top seven highest scores from regular season games in NBA history.

[ 316, 320, 312, 370, 337, 318, 314 ]

But they aren’t sorted in any particular order. How can we sort them in ascending order? By using the sort function.

> List.sort [ 316, 320, 312, 370, 337, 318, 314 ]
[312,314,316,318,320,337,370]

Descending order

The sort function sorts a list only in ascending array. It doesn’t allow us to pass an argument specifying in what order we want the list to be sorted. What a let-down. If we want to sort a list in descending order, Elm makes us jump through a couple of hoops. Let’s try the next example in Playground.elm file as it’s a bit too long to type in the repl. Define a function called descending right above main.

descending a b =
    case compare a b of
        LT ->
            GT

        GT ->
            LT

        EQ ->
            EQ


main =
    ...

Now change main to this:

main =
    [ 316, 320, 312, 370, 337, 318, 314 ]
        |> List.sortWith descending
        |> toString
        |> Html.text

If you don’t have elm-reactor running already, run it from the beginning-elm directory in the terminal. Go to http://localhost:8000/elm-examples/Playground.elm on your browser and you should see the original list sorted in descending order:

[370,337,320,318,316,314,312]

Let’s go through the code step by step. Not sure if you noticed, but in main we used the sortWith function instead of our stubborn friend sort to sort the list of scores in descending order. sortWith accepts two arguments: a comparison function and a list that needs sorting.

Given two values, a comparison function tells us whether the first value is equal, less than, or greater than the second value. As it happens, Elm provides a function called compare that does just that. If the first value is less than the second, compare returns LT. But if the first value is greater, it returns GT. And if they both are equal, it returns EQ.

> compare 1 2
LT

> compare 2 1
GT

> compare 1 1
EQ

compare is defined in the Basics module. As mentioned earlier, Elm puts generic values and functions that can operate on different types of data such as strings, lists, records, etc. into the Basics module. Like String and List, the Basics module is also loaded automatically by the repl. That’s why we don’t need to explicitly import it.

We can also compare strings with the compare function.

> compare "Blade" "Dragonetti"
LT

> compare "Dragonetti" "Blade"
GT

> compare "Blade" "Blade"
EQ

Strings are compared based on alphabetical order. This is how words are ordered in an English dictionary. For example, the word “Thomas” is considered less than “Thompson” because the letter ‘a’ comes before the letter ‘p’ in the alphabet.

> compare "Thomas" "Thompson"
LT

When we want to sort a list in descending order, we need the compare function to behave in opposite manner. How can we make it do that? By creating another function that pulls a switcheroo on compare like this:

descending a b =
    case compare a b of
        LT ->
            GT

        GT ->
            LT

        EQ ->
            EQ

descending returns GT when compare actually meant LT and LT when it meant GT. Now we can give this function to sortWith and our list will get sorted in descending order.

List.sortWith descending [ 316, 320, 312, 370, 337, 318, 314 ]

The sorted list gets passed to the toString function which generates a string representation of the list. Finally, the Html.text function renders it on browser.

toString is also defined in the Basics module because it’s a generic function for converting different kinds of values into a string.

We could have also written the main function like this:

main =
    Html.text (toString (List.sortWith descending [ 316, 320, 312, 370, 337, 318, 314 ]))

However, our original main function using |> was a bit more readable. Here it is again for comparison:

main =
    [ 316, 320, 312, 370, 337, 318, 314 ]
        |> List.sortWith descending
        |> toString
        |> Html.text

Arbitrary order

sortWith actually opens a door for comparing values using any order we want not just ascending or descending. Let’s say we want to sort certain characters from Game of Thrones based on how evil they are. Add the following function definition right above main in Playground.elm.

evilometer character1 character2 =
    case ( character1, character2 ) of
        ( "Joffrey", "Ramsay" ) ->
            LT

        ( "Joffrey", "Night King" ) ->
            LT

        ( "Ramsay", "Joffrey" ) ->
            GT

        ( "Ramsay", "Night King" ) ->
            LT

        ( "Night King", "Joffrey" ) ->
            GT

        ( "Night King", "Ramsay" ) ->
            GT

        _ ->
            GT


main =
    ...

Now let’s use evilometer in main to sort a list of evil characters.

main =
    [ "Night King", "Joffrey", "Ramsay" ]
        |> List.sortWith evilometer
        |> toString
        |> Html.text

If you refresh the page at http://localhost:8000/elm-examples/Playground.elm, you should see:

["Joffrey","Ramsay","Night King"]

All sortWith expects from a comparing function is one of these values: LT, GT, or EQ. It doesn’t care how those values are computed. As it turns out, the sort function is a specialized case of sortWith. Internally, it just calls the compare function directly to compare values. So if we write sortWith like this, we get the behavior of sort function:

> List.sortWith compare [ 316, 320, 312, 370, 337, 318, 314 ]
[312,314,316,318,320,337,370]

Filtering a List

Like String.filter function, List.filter also takes a predicate and a list of items. It then creates a new list containing all items from the original list that pass the test implemented by the predicate. Here are some examples:

> isOdd number = if number % 2 == 0 then False else True
<function>

> List.filter isOdd [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
[1,3,5,7,9]

> isHost name = List.member name [ "Dolores", "Teddy", "Maeve" ]
<function>

> List.filter isHost [ "William", "Bernard", "Dolores", "Teddy" ]
["Dolores","Teddy"]

isOdd function is a predicate that determines whether a given number is odd. We divide the number by 2 and check if the remainder is 0. If yes, it’s not an odd number.

The modulus operator (%) divides the value of one expression by the value of another and returns the remainder.

isHost function is also a predicate that determines whether someone is a host from the ever fascinating Westworld. It uses the List.member function we used earlier to determine whether a given name is in a list of hosts.

Mapping a List

Programming is all about data transformation. We take an input data, apply functions to it in sequence until we have arrived at the result we can return as an output. Let’s say we have a list of strings:

> guardians = [ "Star-lord", "Groot", "Gamora", "Drax", "Rocket" ]
["Star-lord","Groot","Gamora","Drax","Rocket"]

And we want to find out how many strings have lengths less than six. How can we accomplish that? Well, first we need to find out a length of each string in the list. How about we generate another list that contains just lengths, but not the strings themselves? We can do that easily with map function.

> lengths = List.map String.length guardians
[9,5,6,4,6]

map creates a new list with the results of applying a given function on every element in the original list. Here we gave it String.length which takes a string and returns its length. Next we need to remove lengths that are greater than or equal to 6. We already know a function that knows how to do it: filter.

> List.filter (\x -> x < 6) lengths
[5,4]

And we have our answer.

Let’s work through one more problem to solidify our understanding of map. Let’s say we want to find out whether any of the guardians have hyphen in their name. We can use String.contains to check for a hyphen like this:

> List.map (\x -> String.contains "-" x) guardians
[True, False, False, False, False]

After a while, typing an anonymous function starts to get a little tiresome. What if we apply map like this instead:

> List.map (String.contains "-") guardians
[True, False, False, False, False]

Whoa! That works too. Previously, we applied String.contains with both arguments ("-" and x) it needed to return a boolean. However, if we call it without the second argument (x), we get back a partially applied function instead of a boolean value. List.map then passes each string from the guardians list, one at a time, to this partially applied function as the last argument. This results in a boolean value.

An anonymous function like (\param -> someFunction x param) can always be rewritten as (someFunction x) as long as param is the last argument. Here’s one more example that checks if a guardian’s name starts with Dr.

> List.map (\x -> String.startsWith "Dr" x) guardians
[False,False,False,True,False]

> List.map (String.startsWith "Dr") guardians
[False,False,False,True,False]

The partial application technique also works with operators. Let’s rewrite one of our earlier examples that contained an operator using the partial application technique.

> List.filter (\x -> x < 6) lengths
[5,4]

> List.filter ((>) 6) lengths
[5,4]

Notice that we had to flip the < operator in order to achieve the same result. That’s because the partial application technique requires us to use operators in infix style, which places an operator before the operands. If we hadn’t flipped the < operator, we would have gotten a list of numbers that are greater than 6.

> List.filter ((<) 6) lengths
[9]

Folding a List

We have created numerous lists with numbers in them, but we haven’t tried to add all the elements up yet. Let’s do that.

> List.foldl (\x a -> x + a) 0 [ 1, 2, 3, 4 ]
10

What we have done here is fold (or reduce) a list into a number that represents the sum of all elements in the list. The foldl function takes three arguments: combining function, initial value, and a list. The combining function in turn takes two arguments: an element from the list and an accumulator.

After the first application, foldl passes the accumulator (sum thus far) back to the combining function as the second argument repeatedly until there are no more elements left in the list. The figure below shows step-by-step application of the combining function.

Since we are calculating a sum here, we used the + operator inside our combining function. But if we were calculating a product, our combining function would use the * operator instead.

> List.foldl (\x a -> x * a) 0 [ 1, 2, 3, 4 ]
0

Why is it returning zero as the product? Oops… We forgot to change the initial value. foldl passes the initial value (zero in our case) as the first argument to the combining function. The result of multiplying a number by zero is zero. If we change the initial value to 1, we get the expected result.

> List.foldl (\x a -> x * a) 1 [ 1, 2, 3, 4 ]
24

Remember, + and * operators are also functions. And all foldl expects is a function as the first argument. It doesn’t care whether it’s an anonymous function or a normal function or an operator. Therefore, we can re-write the above examples in a much more succinct way like this:

> List.foldl (+) 0 [ 1, 2, 3, 4 ]
10

> List.foldl (*) 1 [ 1, 2, 3, 4 ]
24

In case of addition and multiplication, you can think of replacing the commas in the list with the + and * operators respectively. foldl is capable of reducing a list in many different ways, but if all you want to do is calculate sum or product, Elm already provides those functions as a convenience.

> List.sum [ 1, 2, 3, 4 ]
10

> List.product [ 1, 2, 3, 4 ]
24

That was pretty anticlimactic, wasn’t it? I showed you in detail how to use foldl to calculate sum and product of a list only to find out later there already exist functions to do exactly that much more easily. To make it up to you, I’ll show you one more example that’s actually useful. Let’s say we want to calculate the total number of characters in this list:

> guardians = [ "Star-lord", "Groot", "Gamora", "Drax", "Rocket" ]
["Star-lord","Groot","Gamora","Drax","Rocket"]

We can use foldl to easily reduce this entire list of strings to a single number.

> List.foldl (\x a -> (String.length x) + a) 0 guardians
30

Folding from right

foldl folds a list from left as its name indicates. What that means is it begins its operation starting from the beginning of the list. But, sometimes we need to fold a list starting from the end. The List module provides another function called foldr for that.

> List.foldr (\x a -> x + a) 0 [ 1, 2, 3, 4 ]
10

> List.foldr (\x a -> x * a) 1 [ 1, 2, 3, 4 ]
24

For sum and product it doesn’t matter whether we start from the beginning or end of a list. But there are operators that produce different results depending on where we start. Let’s use one that we are already familiar with: power operator (^). Earlier, we learned that ^ is right-associative whereas + and * are left-associative. What that means is if we write an expression as shown below, ^ will start evaluating it from the right.

> 4 ^ 2 ^ 3
65536

-- (2 ^ 3) = 8
-- (4 ^ 8) = 65536

There are two reasons why ^ is right-associative in Elm:

  1. ^ is also right-associative in mathematics and Elm tries to follow the rules defined in mathematics as much as possible.

  2. If ^ was left-associative, then the end result could simply be computed by just multiplying the exponents. Let’s see some examples to understand what this means.

> (4 ^ 2) ^ 3
4096

> 4 ^ (2 * 3)
4096

> (((2 ^ 3) ^ 4) ^ 5)
1152921504606847000

> 2 ^ (3 * 4 * 5)
1152921504606847000

We applied parentheses to force ^ to evaluate from left. We were then able to simply multiply all the exponents on the right and use ^ only once to get the same result. Therefore, to make the ^ operator more meaningful, we need to evaluate an expression from the right. Now let’s see how foldr behaves with ^.

> List.foldr (\x a -> x ^ a) 1 [ 4, 2, 3 ]
65536

It’s hard to know what’s going on just by looking at the code here. Hopefully, the following diagrams will make things a bit clearer.

What happens if we use ^ with foldl? It starts applying the ^ operator from the left resulting in a different value which is not what we want.

> List.foldl (\x a -> x ^ a) 1 [ 4, 2, 3 ]
43046721
Here’s how we arrived at the final result in the example above:
(4 ^ 1) = 4
(2 ^ 4) = 16
(3 ^ 16) = 43046721

Lastly, we can re-write the above expressions more succinctly just by specifying the operator.

> List.foldr (^) 1 [ 4, 2, 3 ]
65536

> List.foldl (^) 1 [ 4, 2, 3 ]
43046721

Are they all evil?

Earlier we partitioned a list containing characters from Game of Thrones into two lists. The first list was infested with evil people whereas the second list was full of kind souls.

> gotCharacters = [ "Samwell", "Cersei", "Hodor", "Joffrey", "Meera", "Ramsay" ]
["Samwell","Cersei","Hodor","Joffrey","Meera","Ramsay"]

> isEvil name = List.member name [ "Joffrey", "Ramsay", "Cersei" ]
<function>

> List.partition isEvil gotCharacters
(["Cersei","Joffrey","Ramsay"],["Samwell","Hodor","Meera"])

What if we want to find out if any one of the characters is evil? The any function is designed to do just that.

> List.any isEvil gotCharacters
True

There’s certainly evil lurking in that list. Like the partition function, any takes a predicate that tells whether a given character is evil or not. We can also find out if all characters are evil by using the all function instead.

> List.all isEvil gotCharacters
False

How can Hodor be evil, right? If you think about it, any and all are actually folding a list too. They both reduce a list to a single boolean value. There are a few more of these functions that perform a special kind of fold. You can learn all about them here.

Take it or Drop it

Remember those annoying bouncers at famous night clubs who tend to let only good looking people in? If those bouncers were Elm programmers, they’d love the drop function.

> List.drop 2 [ "Smeagol", "Edna", "Freddy", "Daenerys", "Jacob" ]
["Freddy","Daenerys","Jacob"]

The drop function drops the specified number of elements from the beginning of a list and returns a new list with remaining elements. Once in a while, we get a nice bouncer who lets people on a first come first serve basis. They would definitely prefer take over drop.

> List.take 2 [ "Freddy", "Daenerys", "Driver" ]
["Freddy","Daenerys"]

Watch out! The bouncer just let Freddy into the club. take returns a new list containing the specified number of elements from the beginning of a list.

Head or Tail?

Conceptually, a list is divided into two parts: head and tail. The first element is called the head and tail represents the rest of the elements.

The List module even provides functions to get the head and tail of a list.

> List.head [ 1, 2, 3, 4, 5 ]
Just 1

> List.tail [ 1, 2, 3, 4, 5 ]
Just [2,3,4,5]

> List.head []
Nothing

> List.tail []
Nothing

When Elm cannot guarantee a value, it returns a data structure called Maybe. If the value is present, it’s wrapped inside Just, otherwise Nothing is returned. Just and Nothing are members of the Maybe type. This simple concept is at the heart of writing incredibly robust applications in Elm. We will find out how to extract a value from Just later. For now you can ignore it. The next chapter will cover Maybe in much more detail. Until then you can think of Maybe as a container just like List that can hold at most one value.

In the example above, Elm cannot guarantee that it can return a value when asked for the head (or tail) of a list. If the list is empty there is no value to return. Therefore, it returns a Maybe.

How List is Implemented

List is sometimes also called a linked list as it is a linear collection of data elements, each pointing to the next element. An element in a list is called Node.

Even if there is no data in it, the last (empty) node does exist. If you don’t believe me check this out:

> []
[]

> 9 :: []
[9]

> 31 :: [ 9 ]
[31,9]

> 5 :: [ 31, 9 ]
[5,31,9]

> 16 :: [ 5, 31, 9 ]
[16,5,31,9]

We started with an empty list and added 9 in-front of it using the cons (::) operator. We then continued to add the rest of the elements to that list one at a time. When we create a list in this way, it starts to look like a recursive data structure meaning a list consists of nodes which themselves are lists. Because a node isn’t required to contain a value, an empty node is also considered a list.

In fact, behind the scenes List in Elm is actually defined as a recursive data structure. In chapter 4, we will create our own implementation of a linked list that will work similarly to Elm’s implementation of List to better understand how a recursive data structure works.

We covered quite a few functions from the List module in this section, but there are still more included in that module. You can learn all about them here.

Back to top

New chapters are coming soon!

Sign up for the Elm Programming newsletter to get notified!

* indicates required
Close