Comprehensions

Mix.install([
  {:kino, github: "livebook-dev/kino", override: true},
  {:kino_lab, "~> 0.1.0-dev", github: "jonatanklosko/kino_lab"},
  {:vega_lite, "~> 0.1.4"},
  {:kino_vega_lite, "~> 0.1.1"},
  {:benchee, "~> 0.1"},
  {:ecto, "~> 3.7"},
  {:math, "~> 0.7.0"},
  {:faker, "~> 0.17.0"},
  {:utils, path: "#{__DIR__}/../utils"}
])

Navigation

Return Home Report An Issue

Setup

Ensure you type the ea keyboard shortcut to evaluate all Elixir cells before starting. Alternatively you can evaluate the Elixir cells as you read.

Comprehensions

Let’s try to comprehend comprehensions (we’re sorry).

But in all seriousness, you might mistake a comprehension for a for loop if you’re coming from another programming language. This is not the case! Notice below that the comprehension returns a list.

for each <- 1..100 do
  each * 2
end

Since the comprehension has a return value, it can be bound to a variable and used elsewhere.

my_comprehension =
  for each <- 1..10 do
    each * 2
  end

List.to_tuple(my_comprehension)

A comprehension can even be piped into another function.

for each <- 1..10 do
  each * 2
end
|> List.to_tuple()

In an OOP language without immutability, it’s common to use for loops to mutate some variable. We don’t do that in Elixir! Notice below that sum is still 0.

sum = 0

for each <- 1..100 do
  sum = sum + each
  sum
end

sum

So what are comprehensions for? Currently, we can accomplish the same behavior with the Enum module.

Enum.map(1..100, fn each -> each * 2 end)

A comprehension is syntax sugar. That means that while it may look cleaner, it does not provide any additional behavior. The Enum module and comprehensions can accomplish the same behavior.

A comprehension is broken down into three parts: generators, filters, and collectables.

Generators

In the following example, the generator is n <- 1..100 which defines the collection to enumerate over.

for n <- 1..100 do
  n
end

We can also use pattern matching in the generator to ignore non-matching values.

for {:keep, value} <- [keep: 1, keep: 2, filter: 1, filter: 3] do
  value
end

Here’s where comprehensions get cool and stop looking like for loops. You can use multiple comma-separate generators in a single comprehension.

The comprehension treats each additional generator like a nested loop. For each element in the first loop, it will enumerate through every element in the second loop.

for a <- 1..3, b <- 4..6 do
  {a, b}
end

flowchart
  subgraph D[generator 2]
    4a[4]
    5a[5]
    6a[6]
  end
  subgraph C[generator 2]
    4b[4]
    5b[5]
    6b[6]
  end
  subgraph B[generator 2]
    4c[4]
    5c[5]
    6c[6]
  end
  subgraph A[generator 1]
    1 --> B
    2 --> C
    3 --> D
  end

We can even use elements from one generator in the next generator.

for a <- 1..3, b <- a..0 do
  {a, b}
end

flowchart
  subgraph D[generator 2]
    1a[1]
    0a[0]
  end
  subgraph C[generator 2]
    2b[2]
    1b[1]
    0b[0]
  end
  subgraph B[generator 2]
    3c[3]
    2c[2]
    1c[1]
    0c[0]
  end
  subgraph A[generator 1]
    1 --> D
    2 --> C
    3 --> B
  end

There’s no real limit to the number of generators that you can use, but each generator creates another nested loop and therefore has a significant performance impact.

That means generally, a comprehension with a single generator will have linear complexity $O(n)$. A comprehension with two generators will have polynomial time $O(n^2)$. A comprehension with three generators will also have polynomial time but $O(n^3)$.

So the performance follows Big $On^g$ where $g$ is the number of generators that you use.

Utils.graph(:comprehension_big_o)

Your Turn

In the Elixir cell below, use a comprehension to create a list of even integers from 2 to 100.

Hint Remember that ranges can have steps! e.g. 1..10//3

Filters

We can use filters in a comprehension to filter out elements from the generator. For example, we could omit all values divisible by 3.

The comprehension will filter out all values that do not return true for the filter function.

for n <- 1..100, rem(n, 3) === 0 do
  n
end

We can use multiple comma-separated filters.

for a <- 1..100, rem(a, 3) === 0, rem(a, 5) === 0 do
  a
end

We can also use multiple comma-separated filters and generators. Filters and generators can go in any order. However, it’s likely more clear to group filters together after the generators.

for a <- 1..45, b <- 1..5, rem(a, 5) === 0, rem(b, 5) === 0 do
  [a, b]
end

That said, you can put the generators and filters in alternating order.

for a <- 1..45, rem(a, 5) === 0, b <- 1..5, rem(b, 5) === 0 do
  [a, b]
end

The generators must go in the order you want to nest them, otherwise, you change the behavior. The filters must also go after any generator whose variable they rely on. For example, b has not yet been defined here.

for a <- 1..45, rem(a, 5) === 0, rem(b, 5) === 0, b <- 1..5 do
  [a, b]
end

Your Turn

In the Elixir cell below, create a comprehension with a filter that generates every combination of 2 numbers up to 6 that equal 7.

flowchart
1 --- 6
2 --- 5
3 --- 4
4b[4] --- 3b[3]
5b[5] --- 2b[2]
6b[6] --- 1b[1]

[{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}]

Collectables

By default, the comprehension returns a list. However, we can accumulate the elements into any value with the :into option. Into works with any collection that you’re used to using with the Enum module.

Even without the :into option, we can create a comprehension that returns a keyword list by using tuples with an atom as the first element and any value as the second element.

for n <- 1..5 do
  {:"key_#{n}", n}
end

Now, since both maps and keyword lists are key-value tuples underneath, we can specify the :into option to instead return a map.

for n <- 1..5, into: %{} do
  {:"key_#{n}", n}
end

This map could have default values.

for n <- 1..5, into: %{default: "hello!"} do
  {:"key_#{n}", n}
end

And instead of a map, it can be any data type that implements the Collectable protocol.

This includes strings!

for n <- 1..10, do: "#{n}", into: ""

Your Turn

In the Elixir cell below, create a comprehension that returns a map of letters abcd and their code points.

%{"a" => 97, "b" => 98, "c" => 99, "d" => 100}

Hint You can use :binary.first/1 to convert a variable bound to a string to a codepoint.

Why Use A Comprehension?

In general, you should probably lean on the Enum module more often than comprehensions. The Enum module can accomplish all of the same functionality with map and reduce as a comprehension.

This is especially true if you’re coming from an OOP background and feel tempted to use comprehensions because they feel like for loops.

Instead, consider using comprehensions to refactor (improve) your code after you’ve already written it.

For example, in the creation of the graph for how nested generators have $O(n^g)$ performance where $g$ is the number of generators, we originally wrote the following code to display $O(n^2)$ complexity.

Enum.map(init..max, fn number_of_elements ->
  %{"number of elements": number_of_elements, time: number_of_elements ** 2, type: "2"}
end)

But then while writing, realized we could refactor it into a one-line statement using comprehensions.

What do you think? Is this more clear or not?

for n <- init..max, do: %{"number of elements": n, time: n ** 2, type: "2"}

Your Turn

In the Elixir cell below, convert the following Enum.map into a comprehension.

Enum.map(1...5, fn each -> each * 2 end)
[2, 4, 6, 8, 10]

In the Elixir cell below, convert the following Enum.reduce into a comprehension.

Enum.reduce(["a", "b", "c"], fn each, acc -> acc <> each end)
"abc"

In the Elixir cell below, convert the following nested Enum.map into a comprehension with three generators.

Enum.map(1..3, fn a -> Enum.map(1..3, fn b -> {a, b} end) end)
[[{1, 1}, {1, 2}, {1, 3}], [{2, 1}, {2, 2}, {2, 3}], [{3, 1}, {3, 2}, {3, 3}]]

Commit Your Progress

Run the following in your command line from the project folder to track and save your progress in a Git commit.

$ git add .
$ git commit -m "finish comprehensions section"