Reduce

Mix.install([
  {:jason, "~> 1.4"},
  {:kino, "~> 0.8.0", override: true},
  {:youtube, github: "brooklinjazz/youtube"},
  {:hidden_cell, github: "brooklinjazz/hidden_cell"},
  {:smart_animation, github: "brooklinjazz/smart_animation"},
  {:visual, github: "brooklinjazz/visual"}
])

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.

Review Questions

• When should we use map vs filter vs reduce?
• How can we build an accumulated value using reduce?

Overview

Reduce is an incredibly powerful tool you can leverage in a wide variety of circumstances.

> Reduce (sometimes called fold) is a basic building block in functional programming. Almost all of the functions in the Enum module can be implemented on top of reduce. Those functions often rely on other operations, such as Enum.reverse/1, which are optimized by the runtime. > > * HexDocs

If you’d like to learn more about reduce, there’s an excellent video by Paul Fioravanti.

YouTube.new("https://www.youtube.com/watch?v=OQrfedclHfk")

Input -> Output

As we’ve seen, other Enum functions such as Enum.map/2 or Enum.filter/2 take in a collection as input and produce a list as output.

flowchart LR
C1[Collection] --> Enum.map/2 --> L1[List]
C2[Collection] --> Enum.filter/2 --> L2[List]

Reduce allows you to take any collection and produce any output. That’s powerful.

flowchart LR
C1[Collection] --> Enum.reduce/3 --> ANYTHING!!!

Anytime you have a collection, and want to produce a non-list output, Enum.reduce/3 might be the right tool for the job.

Building the Accumulator

Enum.reduce/3 works by enumerating over the collection and building up an accumulator. Instead of applying a change to each element in the collection, we transform the accumulator by applying a callback function on every element.

For example, we can simply return 0 in the body of the callback function to return this value as the accumulator.

Enum.reduce(1..3, 0, fn _integer, _acc -> 0 end)

With each step in Enum.reduce/3 we create a new acculumator of 0.

flowchart TB
  subgraph Accumulator
  direction TB
    A1 --> A2 --> A3
  end
  subgraph Element
    direction TB
    1 --> 2 --> 3
  end
  A1[0]
  A2[0]
  A3[0]

Anagrams

Let’s look at a more practical example of taking a collection, and returning a non-list output.

In the Anagram exercise you previously completed, you built an Anagram.anagram?/2 function to determine if two strings are anagrams. One solution to the problem is to build a map storing the character counts of two strings.

For example, to determine if "state" and "taste" are anagrams of each other, we can convert them into the following maps with a count of each character, and check if they are equal. Remember that order in maps does not matter.

%{"s" => 1, "t" => 2, "a" => 1, "e" => 1} == %{"t" => 2, "a" => 1, "s" => 1, "e" => 1}

We can use Enum.reduce/3 to convert a string into a map of character counts. For each character in the string, we’ll build a new map with an updated key.

Here’s how we would build the accumulator for the string "aba".

flowchart TB
  A1["%{''a'' => 1}"]
  A2["%{''a'' => 1, ''b'' => 1}"]
  A3["%{''a'' => 2, ''b'' => 1}"]

  subgraph Accumulator
    direction TB
    A1 --> A2 --> A3
  end
  subgraph Element
    direction TB
    a1[a] --> b --> a2[a]
  end

We can initialize or update a value in a map using Map.update/4. If there is no existing key, it initializes the map key with the default value provided.

updated_map = Map.update(%{}, :key, "default value", fn current -> "updated: #{current}" end)

If there is an existing key, then it can update the map key using the existing value.

Map.update(updated_map, :key, "default value", fn current -> "updated: #{current}" end)

When converting a string to a map of character counts, If there is no key, the value will be 1. If there is an existing key in the map, the value will be the current value incremented by 1. Here are the steps we want to accomplish for our Enum.reduce/3 function.

initial_accumulator = %{}

step1 = Map.update(initial_accumulator, "a", 1, fn current_value -> current_value + 1 end)

step2 = Map.update(step1, "b", 1, fn current_value -> current_value + 1 end)

step3 = Map.update(step2, "a", 1, fn current_value -> current_value + 1 end)

Putting this all together, here’s the Enum.reduce/3 function that let’s us convert a string into a map with character counts. Note that we have to split the string into a list of characters first to make it enumerable.

split_string = String.split("aba", "", trim: true)

Enum.reduce(split_string, %{}, fn char, map_accumulator ->
  Map.update(map_accumulator, char, 1, fn current -> current + 1 end)
end)

Your Turn

Use Enum.reduce/3 to convert the integer 1234321 into a map of digit counts.

%{1 => 2, 2 => 2, 3 => 2, 4 => 1}

Example Solution

digits = Integer.digits(1_234_321)

Enum.reduce(digits, %{}, fn integer, acc ->
  Map.update(acc, integer, 1, fn current -> current + 1 end)
end)

Multiple Accumulators

One trick for reduce is to use a collection data-type to simulate having multiple accumulators.

Here’s an example of separating a range into even and odd numbers.

Enum.reduce(1..10, {[], []}, fn integer, {evens, odds} ->
  if rem(integer, 2) == 0 do
    {[integer | evens], odds}
  else
    {evens, [integer | odds]}
  end
end)

Technically, there is only one actual accumulator, our tuple with two lists. However, this functions as a way to track multiple values with each enumeration in the reduce operation.

Further Reading

Consider the following resource(s) to deepen your understanding of the topic.

• Elixir Schools: Reduce
• Enum.reduce/2
• Enum.reduce/3

Mark As Completed

file_name = Path.basename(Regex.replace(~r/#.+/, __ENV__.file, ""), ".livemd")

save_name =
  case Path.basename(__DIR__) do
    "reading" -> "reduce_reading"
    "exercises" -> "reduce_exercise"
  end

progress_path = __DIR__ <> "/../progress.json"
existing_progress = File.read!(progress_path) |> Jason.decode!()

default = Map.get(existing_progress, save_name, false)

form =
  Kino.Control.form(
    [
      completed: input = Kino.Input.checkbox("Mark As Completed", default: default)
    ],
    report_changes: true
  )

Task.async(fn ->
  for %{data: %{completed: completed}} <- Kino.Control.stream(form) do
    File.write!(
      progress_path,
      Jason.encode!(Map.put(existing_progress, save_name, completed), pretty: true)
    )
  end
end)

form

Commit Your Progress

Run the following in your command line from the curriculum folder to track and save your progress in a Git commit. Ensure that you do not already have undesired or unrelated changes by running git status or by checking the source control tab in Visual Studio Code.

$ git checkout -b reduce-reading
$ git add .
$ git commit -m "finish reduce reading"
$ git push origin reduce-reading

Create a pull request from your reduce-reading branch to your solutions branch. Please do not create a pull request to the DockYard Academy repository as this will spam our PR tracker.

DockYard Academy Students Only:

Notify your teacher by including @BrooklinJazz in your PR description to get feedback. You (or your teacher) may merge your PR into your solutions branch after review.

If you are interested in joining the next academy cohort, sign up here to receive more news when it is available.

Up Next