Powered by AppSignal & Oban Pro
Would you like to see your link here? Contact us

Reduce

reading/reduce.livemd

Reduce

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

Navigation

Home Report An Issue Comprehension Product SearchNumber Finder

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)
Enum.reduce(Integer.digits(1234321), %{}, fn num, map_accumulator -> 
  Map.update(map_accumulator, num, 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.

Commit Your Progress

DockYard Academy now recommends you use the latest Release rather than forking or cloning our repository.

Run git status to ensure there are no undesirable changes. Then run the following in your command line from the curriculum folder to commit your progress.

$ git add .
$ git commit -m "finish Reduce reading"
$ git push

We’re proud to offer our open-source curriculum free of charge for anyone to learn from at their own pace.

We also offer a paid course where you can learn from an instructor alongside a cohort of your peers. We will accept applications for the June-August 2023 cohort soon.

Navigation

Home Report An Issue Comprehension Product SearchNumber Finder