Lists, tuples and ranges

Adding an item to the front of an Elixir list takes the same time whether the list holds 2 items or 2 million, while adding one at the end copies the whole list. Building 20,000 items with ++ in a loop copied 199,990,000 list cells and took nearly a second on the computer that ran it, against a fraction of a millisecond for the fast way.

Below, you will see why from the way lists are stored, build lists the fast way, avoid two surprising list operators, choose between lists and tuples, and write ranges with steps, including empty and descending ones. Each output below comes from Elixir 1.20.4 with Erlang/OTP 29.1.1 underneath.

A list is a chain of cells: the front is near, the end is far

The Elixir guide says it in one line: “Lists are stored in memory as linked lists”. Each cell holds one item and a link to the rest of the list, and that one fact explains every cost below. Try the basic operations in IEx:

from session import shell

# A list in IEx: adding at the front, joining at the end, and what happens to the original.
shell([
    "list = [2, 3]",
    "[1 | list]",
    "list ++ [4]",
    "list",
    "{hd([1, 2, 3]), tl([1, 2, 3])}",
    "length([1, 2, 3])",
    "List.last!([])",
    "System.halt()",
])

$ iex
Erlang/OTP 29 [erts-17.1] [source] [64-bit] [smp:18:18] [ds:18:18:10] [async-threads:1] [jit]

Interactive Elixir (1.20.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> list = [2, 3]
[2, 3]
iex(2)> [1 | list]
[1, 2, 3]
iex(3)> list ++ [4]
[2, 3, 4]
iex(4)> list
[2, 3]
iex(5)> {hd([1, 2, 3]), tl([1, 2, 3])}
{1, [2, 3]}
iex(6)> length([1, 2, 3])
3
iex(7)> List.last!([])
** (ArgumentError) attempted to get the last element of an empty list
    (elixir 1.20.4) lib/list.ex:381: List.last!/1
    iex:7: (file)
iex(7)> System.halt()

[1 | list] put 1 in front of [2, 3], and list ++ [4] added 4 at the end, yet list was still [2, 3] afterwards: list operators “never modify the existing list”, in the guide’s words, they return a new one. hd/1 gave the headhead and tail: The first item of a list and the list of every item after it: in [1, 2, 3] the head is 1 and the tail is [2, 3]. [x | list] builds a list from a head and a tail., the first item, and tl/1 the tail, the list of the items after it. Step through what each of those lines did to the cells:

The figure shows the two costs to remember. Prepending makes one cell and shares the rest, so it costs the same for any length. Anything that needs the end of a list walks every cell: length/1, List.last/1, and ++, which also copies every cell of its left list. The guide’s naming rule helps here: a function is called size when it takes constant time and length when it is linear, which is why lists have length/1 and tuples tuple_size/1.

Build a list by prepending, then reverse it once

Because ++ copies its left list, appending items one at a time copies the list again and again. This program builds the same list of n items in two ways, prepending each item and reversing once at the end, or appending each with ++, and times both:

# Building a list of n items two ways: prepending and reversing once, or appending with ++ each time.
defmodule Build do
  # Prepend each item, then reverse once at the end: n new cells, then n more for the reverse.
  def by_prepend(n), do: Enum.reverse(prepend(1, n, []))

  defp prepend(i, n, acc) when i > n, do: acc
  defp prepend(i, n, acc), do: prepend(i + 1, n, [i | acc])

  # Append each item with ++, which copies the whole list built so far, every time.
  def by_append(n), do: append(1, n, [])

  defp append(i, n, acc) when i > n, do: acc
  defp append(i, n, acc), do: append(i + 1, n, acc ++ [i])
end

defmodule Main do
  def run do
    IO.puts("      n  cells copied by ++  prepend and reverse     ++ in a loop  same list")

    for n <- [5_000, 10_000, 20_000] do
      {fast_us, fast} = :timer.tc(fn -> Build.by_prepend(n) end)
      {slow_us, slow} = :timer.tc(fn -> Build.by_append(n) end)
      # The k-th ++ copies the k - 1 cells built before it: 0 + 1 + ... + (n - 1) in all.
      copied = div(n * (n - 1), 2)

      IO.puts(
        String.pad_leading(Integer.to_string(n), 7) <>
          String.pad_leading(Integer.to_string(copied), 20) <>
          String.pad_leading(ms(fast_us), 21) <>
          String.pad_leading(ms(slow_us), 17) <>
          String.pad_leading(Atom.to_string(fast == slow), 11)
      )
    end
  end

  defp ms(us), do: :erlang.float_to_binary(us / 1000, decimals: 2) <> " ms"
end

Main.run()

from session import run

run("""
elixir build_order.exs
""")

$ elixir build_order.exs
      n  cells copied by ++  prepend and reverse     ++ in a loop  same list
   5000            12497500              0.09 ms         45.91 ms       true
  10000            49995000              0.08 ms        205.88 ms       true
  20000           199990000              0.20 ms        988.65 ms       true

Both ways built the same list, as the last column says. The count of copied cells explains the times: the k-th ++ copies the k − 1 cells built before it, so n appends copy 0 + 1 + … + (n − 1) = n(n − 1)/2 cells. Doubling n from 10,000 to 20,000 multiplied the copies by about four, from 49,995,000 to 199,990,000, and the time of the ++ loop grew in step, while prepending and reversing, about 2n cell operations, stayed well under a millisecond.

Erlang’s Efficiency Guide gives the same advice: attach new elements to the beginning of the list, and when the order matters, “build the list in reverse order and reverse the list when you are done”. Enum.reverse/1 is one pass over the list, so the fast way costs two passes in all, however long the list is.

Subtracting removes first matches only, and a list can end in a non-list

Two list operators behave in ways that surprise people coming from other languages:

from session import shell

# Two list operators that surprise: -- removes the first match only, and ++ with a non-list on the right,
# then the one place where a list that ends in a non-list is normal: IO data.
shell([
    "[1, 2, 2, 3] -- [2]",
    "[1, 2, 2, 3, 2] -- [2, 2]",
    "[1 | 2]",
    'is_list(["a", "b"] ++ "c")',
    'length(["a", "b"] ++ "c")',
    'IO.iodata_to_binary(["tea for " | "two"])',
    "System.halt()",
])

$ iex
Erlang/OTP 29 [erts-17.1] [source] [64-bit] [smp:18:18] [ds:18:18:10] [async-threads:1] [jit]

Interactive Elixir (1.20.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> [1, 2, 2, 3] -- [2]
[1, 2, 3]
iex(2)> [1, 2, 2, 3, 2] -- [2, 2]
[1, 3, 2]
iex(3)> [1 | 2]
[1 | 2]
iex(4)> is_list(["a", "b"] ++ "c")
true
iex(5)> length(["a", "b"] ++ "c")
** (ArgumentError) errors were found at the given arguments:

  * 1st argument: not a list

    :erlang.length(["a", "b" | "c"])
    iex:5: (file)
iex(5)> IO.iodata_to_binary(["tea for " | "two"])
"tea for two"
iex(6)> System.halt()

-- removes, for each item on its right, the first match on its left, and no more: [1, 2, 2, 3] -- [2] kept the second 2, and [1, 2, 2, 3, 2] -- [2, 2] removed two 2s and kept the third. To remove every copy of a value, filter the list instead, with Enum.reject/2, which the collections module of this track teaches.

The other surprise is the improper listimproper list: A list whose last link is not the empty list, such as [1 | 2]. It is legal and appears in IO data, but length/1 and most Enum functions reject it.. A list’s last cell normally links to the empty list, but [1 | 2] links to the number 2 instead, and ["a", "b"] ++ "c" made the same shape, because ++ copies its left list and attaches whatever is on its right as the last link. The result is still a list to is_list/1, yet length/1 raised ArgumentError, and most functions of Enum fail on it too. Improper lists are legal on purpose: IO data, the nested lists of strings and bytes that I/O functions accept, may end in a string instead of the empty list, and IO.iodata_to_binary(["tea for " | "two"]) joined one into “tea for two”. In ordinary code an improper list is nearly always a mistake: an item that should have been wrapped in a list, ++ ["c"].

A tuple is a fixed group: quick to read, copied to change

A tupletuple: A fixed-size group of values stored side by side, written {:ok, 42}. Reading a value by position is quick, but changing one builds a new tuple. keeps a fixed number of values side by side. The guide says that tuples “store elements contiguously in memory”, which makes reading by position fast and changing expensive:

from session import shell

# A tuple: a fixed group of values, read by position, copied to change, and used as a tagged result.
shell([
    't = {:ok, "hello", 42}',
    "elem(t, 1)",
    'put_elem(t, 1, "world")',
    "t",
    "tuple_size(t)",
    'File.read("no_such_file.txt")',
    "System.halt()",
])

$ iex
Erlang/OTP 29 [erts-17.1] [source] [64-bit] [smp:18:18] [ds:18:18:10] [async-threads:1] [jit]

Interactive Elixir (1.20.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> t = {:ok, "hello", 42}
{:ok, "hello", 42}
iex(2)> elem(t, 1)
"hello"
iex(3)> put_elem(t, 1, "world")
{:ok, "world", 42}
iex(4)> t
{:ok, "hello", 42}
iex(5)> tuple_size(t)
3
iex(6)> File.read("no_such_file.txt")
{:error, :enoent}
iex(7)> System.halt()

elem(t, 1) read the second value, counting from 0, in one step, and tuple_size/1 gave 3 just as quickly. put_elem/3 returned a new tuple and left t as it was: tuples are immutable too, so changing one value means a new tuple, although the guide notes that “all entries are shared between the old and the new tuple, except for the entry that has been replaced”. The last line shows the most common tuple of all, a tagged tupletagged tuple: A tuple whose first element is an atom naming what it holds, such as {:ok, value} or {:error, reason}, the usual shape of a result that may fail.: File.read/1 returned {:error, :enoent} for a missing file, and returns {:ok, contents} when it can read one. The atom first says which case you have.

The rule of thumb follows from the costs. A list suits a collection whose number of items varies and which you go through in order; a tuple suits a fixed group of a few values read by position, such as a result, a point {x, y} or an Erlang date, {year, month, day}. Answer the two questions in the table to see the choice for your own data:

Most code needs both: a list of tuples, such as [{:ok, 1}, {:error, :enoent}], is a varying collection of fixed results. When the values have names rather than positions, the next lesson’s maps are the better fit.

Ranges are three numbers with a step

A rangerange: A sequence of integers written first..last//step, such as 1..10//3. It stores only those three numbers, so 1..1_000_000 holds no list of a million values. stands for a sequence of integers without storing them. It is written first..last, or first..last//step with a step:

from session import shell

# Ranges with a step, empty and descending ranges, and the warning for a range written backwards.
shell([
    "Enum.to_list(1..10//3)",
    "Enum.to_list(10..1//-3)",
    "Enum.to_list(1..0//1)",
    "5..1",
    "n = 0",
    "Enum.to_list(1..n)",
    "Enum.to_list(1..n//1)",
    "Range.size(1..10//3)",
    "5 in 1..10",
    "Enum.count(1..1_000_000)",
    "Map.from_struct(1..1_000_000)",
    "Enum.sum(1..100)",
    "System.halt()",
])

$ iex
Erlang/OTP 29 [erts-17.1] [source] [64-bit] [smp:18:18] [ds:18:18:10] [async-threads:1] [jit]

Interactive Elixir (1.20.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> Enum.to_list(1..10//3)
[1, 4, 7, 10]
iex(2)> Enum.to_list(10..1//-3)
[10, 7, 4, 1]
iex(3)> Enum.to_list(1..0//1)
[]
iex(4)> 5..1
warning: 5..1 has a default step of -1, please write 5..1//-1 instead
  iex:4: (file)

5..1//-1
iex(5)> n = 0
0
iex(6)> Enum.to_list(1..n)
warning: Range.new/2 and first..last default to a step of -1 when last < first. Use Range.new(first, last, -1) or first..last//-1, or pass 1 if that was your intention
  (elixir 1.20.4) src/elixir.erl:382: :elixir.eval_external_handler/3
  (stdlib 8.1) erl_eval.erl:1048: :erl_eval.do_apply/7
  (stdlib 8.1) erl_eval.erl:1664: :erl_eval.expr_list/7
  (stdlib 8.1) erl_eval.erl:1660: :erl_eval.expr_list/5
  (stdlib 8.1) erl_eval.erl:754: :erl_eval.expr/6

[1, 0]
iex(7)> Enum.to_list(1..n//1)
[]
iex(8)> Range.size(1..10//3)
4
iex(9)> 5 in 1..10
true
iex(10)> Enum.count(1..1_000_000)
1000000
iex(11)> Map.from_struct(1..1_000_000)
%{first: 1, last: 1000000, step: 1}
iex(12)> Enum.sum(1..100)
5050
iex(13)> System.halt()

1..10//3 gave 1, 4, 7 and 10, and a negative step counts down: 10..1//-3 gave 10, 7, 4 and 1. Ranges include both ends whenever the step lands on them. 1..0//1 is empty, because no number is at least 1 and at most 0, and an empty range is a normal value. Writing 5..1 still works, but IEx printed the warning “5..1 has a default step of -1, please write 5..1//-1 instead”: the Range documentation says implicit decreasing ranges are deprecated. The next three lines show why. With n = 0, 1..n counted down and gave [1, 0], with a warning that came only as it ran, while 1..n//1 was the empty range that a loop over “1 to n” means.

Map.from_struct/1 shows what a range really is: a struct of three integers, first, last and step. So 1..1_000_000 takes no more memory than 1..3, and in, Range.size/1 and Enum.count/1 answer from the three numbers. Enum.sum(1..100) gave 5,050.

Practise: rotate a list

Write Rotate.left/2 and Rotate.right/2. left(list, n) moves the first n items to the end, so left([1, 2, 3, 4, 5], 2) is [3, 4, 5, 1, 2], and right(list, n) moves the last n items to the front. Any whole n must work: one larger than the list goes round more than once, and a negative one turns the other way. Copy the two files into an empty folder:

defmodule Rotate do
  @moduledoc "Rotates lists: the items that fall off one end come back at the other."

  @doc "Moves the first n items to the end. Any whole n works: larger than the list, or negative."
  def left(list, _n) do
    # Drop the underscore once you use the argument.
    list
  end

  @doc "Moves the last n items to the front. right(list, n) is the same as left(list, -n)."
  def right(list, _n) do
    list
  end
end

Code.require_file("rotate.ex", __DIR__)
ExUnit.start(seed: 0)

defmodule RotateTest do
  use ExUnit.Case

  test "left moves the first n items to the end" do
    assert Rotate.left([1, 2, 3, 4, 5], 2) == [3, 4, 5, 1, 2]
  end

  test "right moves the last n items to the front" do
    assert Rotate.right([1, 2, 3, 4, 5], 2) == [4, 5, 1, 2, 3]
  end

  test "n larger than the list goes round more than once" do
    assert Rotate.left([1, 2, 3], 4) == [2, 3, 1]
    assert Rotate.right([1, 2, 3], 7) == [3, 1, 2]
  end

  test "a negative n turns the other way" do
    assert Rotate.left([1, 2, 3], -1) == [3, 1, 2]
  end

  test "an empty list stays empty" do
    assert Rotate.left([], 3) == []
    assert Rotate.right([], 3) == []
  end
end

Run elixir rotate_test.exs. The starter returns every list as it was, so only the test of the empty list passes:

from session import run

# The tests against the starter, which returns every list unchanged.
run("""
cd practice
!elixir rotate_test.exs
""")

$ cd practice
$ elixir rotate_test.exs
Running ExUnit with seed: 0, max_cases: 36



  1) test left moves the first n items to the end (RotateTest)
     rotate_test.exs:7
     Assertion with == failed
     code:  assert Rotate.left([1, 2, 3, 4, 5], 2) == [3, 4, 5, 1, 2]
     left:  [1, 2, 3, 4, 5]
     right: [3, 4, 5, 1, 2]
     stacktrace:
       rotate_test.exs:8: (test)



  2) test right moves the last n items to the front (RotateTest)
     rotate_test.exs:11
     Assertion with == failed
     code:  assert Rotate.right([1, 2, 3, 4, 5], 2) == [4, 5, 1, 2, 3]
     left:  [1, 2, 3, 4, 5]
     right: [4, 5, 1, 2, 3]
     stacktrace:
       rotate_test.exs:12: (test)



  3) test n larger than the list goes round more than once (RotateTest)
     rotate_test.exs:15
     Assertion with == failed
     code:  assert Rotate.left([1, 2, 3], 4) == [2, 3, 1]
     left:  [1, 2, 3]
     right: [2, 3, 1]
     stacktrace:
       rotate_test.exs:16: (test)



  4) test a negative n turns the other way (RotateTest)
     rotate_test.exs:20
     Assertion with == failed
     code:  assert Rotate.left([1, 2, 3], -1) == [3, 1, 2]
     left:  [1, 2, 3]
     right: [3, 1, 2]
     stacktrace:
       rotate_test.exs:21: (test)

.
Finished in 0.02 seconds (0.02s on load, 0.00s async, 0.00s sync)

Result: 1/5 passed
Failed: 4 tests
[exit status 2]

Two functions do the work: Integer.mod/2, from the first lesson of this module, and Enum.split/2. Integer.mod(n, length(list)) turns any n, negative or too large, into a position from 0 up to the length of the list. Enum.split(list, k) returns a tuple of the first k items and the rest, {front, back}, and back ++ front joins them, once, so the whole rotation is a couple of passes over the list. An empty list needs a check of its own, because Integer.mod/2 cannot divide by a length of 0. A finished version passes all five tests:

from session import run

# The same tests against finished left/2 and right/2.
run("""
cd finished
cp ../practice/rotate_test.exs .
elixir rotate_test.exs
""")

$ cd finished
$ cp ../practice/rotate_test.exs .
$ elixir rotate_test.exs
Running ExUnit with seed: 0, max_cases: 36

.....
Finished in 0.01 seconds (0.01s on load, 0.00s async, 0.00s sync)

Result: 5 passed

Then try the self-check: it covers lists, building them, the two surprising operators, tuples and ranges, asks about whichever you know least first, and explains each answer as soon as you give it:

Interview questions

Warm-up: when do you use a tuple and when a list in Elixir?

Use a list for a collection whose number of items varies, which you go through in order or build up as you go, and a tuple for a fixed group of a few values, read by position. The costs decide it. A list is a chain of linked cells: prepending is instant and shares the rest, but length/1, reading item i and ++ walk the list. A tuple stores its values side by side: elem/2 and tuple_size/1 are instant, but changing a value with put_elem/3 builds a new tuple. That is why functions return tagged tuples, such as {:ok, contents} or {:error, :enoent} from File.read/1: always two values, the first an atom that names the case. And it is why a list of tuples, such as a list of results, is so common.

Two questions about building and queueing lists:

Key takeaways

• A list is a chain of linked cells: [x | list] adds one cell and shares the rest, while length/1, List.last/1 and ++ walk the list, and ++ copies its whole left list.
• Build lists by prepending and reversing once: 20,000 appends with ++ copied 199,990,000 cells, while prepending and reversing took a fraction of a millisecond.
• -- removes only the first match for each item on its right, and ++ with a non-list on the right makes an improper list that length/1 rejects.
• A tuple is a fixed group of values side by side, read in one step with elem/2 and copied by put_elem/3; tagged tuples such as {:ok, value} and {:error, reason} are how functions report results.
• A range is a struct of three integers, first..last//step: it holds no list, an empty range is normal, and a descending range needs its negative step written.
• New in 1.20, List.first!/1 and List.last!/1 raise for an empty list instead of returning nil.