Reduce (fold)

In previous sections we discussed many methods for iterating over data and transforming it. In this section we'll discuss another higher order function that is arguably one of the most powerful. It is a concept recognized across enough programming languages to get its own wikipedia article. Most popular languages call it reduce, although some languages will call it fold or inject. Here's the parameters it takes, and although the order of the parameters may be different in other languages the functionality and output will be the same.

reduce(list, fn, starting_value)

Like with map() and filter(), it takes a list you want to transform and a function (fn) to do the transformation. The transformation function behaves like a recursive loop like seen in the last section. Here's a function that takes a list of numbers and gives you the total sum of those numbers.

local list = {23, 63, 12, 48, 3}

local sum_fn = function(accumulator, current_number)
  return accumulator + current_number
end


local total_sum = reduce(list, sum_fn, 0)

We pass reduce a starting number of 0. What happens is sum_fn is invoked with the first parameter, the accumulator being the starting number 0 and current_number being the first number in the list. Whatever value the function returns becomes the new value for accumulator next loop around.

Lua doesn't have a reduce function built in so we'll implement our own here with a detailed description of all the parameters. Try not to get too hung up on the actual reduce function's implementation at the top, but rather focus below that on how it works. There will be several more examples. Once you understand how to use it, go back to the top and look at the actual reduce function's implementation. Copy all this code into the text editor window on the REPL and run it:

-- Applies fn on two arguments cumulative to the items of the array t,
-- from left to right, so as to reduce the array to a single value. If
-- a first value is specified the accumulator is initialized to this,
-- otherwise the first value in the array is used.
-- @param {table} t - a table to reduce
-- @param {function} fn - the reducer for comparing the two values
--   @param {*} acc - The accumulator accumulates the callback's return
--     values; It is the accumulated value previously returned in the
--     last invocation of the callback, or `first_value`, if supplied.
--   @param {*} current_value - The current element being processed in the list.
--   @param {number} current_index - The index of the current element
--     being processed in the list, starting at 1.
-- @param {*} first_value - The initial value of the accumulation. If the array is
--   empty, the first_value will also be the returned value. If the array is empty
--   and no first value is specified an error is raised.
-- @example
--   -- returns 'zxy'
--   reduce(
--     { 'x', 'y' },
--     function(a, b) return a + b end,
--     'z'
--    )
local function reduce(t, fn, first)
  local acc = first
  local starting_value = first ~= nil
  for i, v in ipairs(t) do
    -- No starting value, start on
    -- the first element in the list
    if starting_value then
      acc = fn(acc, v, i, t)
    else
      acc = v
      starting_value = true
    end
  end
  assert(
    starting_value,
    'Attempted to reduce an empty table with no first value.'
  )
  return acc
end

local list = {23, 63, 12, 48, 3}
local sum_fn = function(accumulator, current_number)
  print(accumulator)
  return accumulator + current_number
end

local total_sum = reduce(list, sum_fn, 0)
print('The total sum is:', total_sum)

Following the print statement inside of sum_fn, we can see that the accumulator starts out with the 0 we pass in. We add current_number to accumulator and it begins to accumulate all the values as it goes.

0
23
86
98
146
The total sum is:   149

If we don't pass in a starting number, the accumulator will begin right away with the first number in the list:

local sum_fn = function(accumulator, current_number)
  print(accumulator)
  return accumulator + current_number
end

local total_sum = reduce(list, sum_fn)

23
86
98
146
The total sum is:   149

If you've used javascript, you may be starting to see the uncanny resemblance it bears to javascript's reduce function. Both languages are very similar syntactically, and given the ubiquity of javascript this Lua implementation follows much of the same behavior.

Let's look at some more examples to better understand how to reduce and what situations doing so could prove useful. The reduce function is omitted in the following examples, but you can copy and paste the function in the REPL alongside the examples to run the code yourself.

-- Concatenate a list of words
local list = {'this', 'is', 'a', 'sentence'}

local sentence = reduce(list, function(acc, word, index, list)
  -- Add a period if this is the last word
  if index == #list then
    word = word .. '.'
  end
  -- Otherwise add a space between the words
  return acc .. ' ' .. word
end)

print(sentence)

this is a sentence.

-- Only keep odd numbers
local list = {23, 63, 12, 48, 3}
local odd_numbers = reduce(list, function(acc, current_number)
  if current_number % 2 == 0 then
    return acc
  end
  acc[#acc + 1] = current_number
  return acc
end, {})

for key, value in ipairs(odd_numbers) do
  print(value)
end

23
63
3

This looks similar to what we might do with the filter function previously covered in 3.3 - Map and filter. In fact, we can compose filter and map from reduce. Take a look at the same code refactored out:

local filter = function(list, predicate_fn)
  return reduce(list, function(acc, val, i, t)
    if predicate_fn(val, i, t) then
      acc[#acc + 1] = val
      return acc
    end
    return acc
  end, {})
end


-- Only keep odd numbers
local list = {23, 63, 12, 48, 3}
local odd_numbers = filter(list, function(current_number)
  return current_number % 2 ~= 0
end)

for key, value in ipairs(odd_numbers) do
  print(value)
end

An example of wrapping reduce with a new map function won't be explained here, but rather left up to the reader as an exercise at the end of this section.

Here's one more example that is a bit more complex, a function called compose that creates a pipeline for passing data through. It accomplishes this by passing any functions you give it through to reduce as a list:

-- Function that allows you to compose other functions
-- together to form a pipeline. The resulting pipeline
-- is a function that you can pass your intended data through.
local compose = function(...)
  -- "..." and "arg" are special keywords in Lua.
  -- See: https://www.lua.org/pil/5.2.html
  local fns = arg
  return function(x)
    return reduce(fns, function(acc, v)
      return v(acc)
    end, x)
  end
end

-- Some example composable functions
local add = function(x)
  return function(y)
    return y + x
  end
end
local multiply = function(x)
  return function(y)
    return y * x
  end
end
local subtract = function(x)
  return function(y)
    return y - x
  end
end


local number_pipeline = compose(add(12), multiply(2), subtract(9))
print(number_pipeline(3))
print(number_pipeline(2))

Alternative reduce implementations

Iterating tables

Let's go back to the implementation of reduce for a moment. Take a look at the implementation of it given above. Notice the iteration inside is using ipairs which expects an array/list-type table. If we wanted to reduce a non-list table we could modify reduce to first check if the table is an array and do appropriate iteration over the table whether or not it is. Let's test that:

local function reduce(t, fn, first)
  local get_iterator = function(t)
    if type(t) == 'table' then
      -- If property of 1 is empty then
      -- iterate as a regular keyed table
      if t[1] == nil then
        return pairs(t)
      end
      return ipairs(t)
    end
    error('Expected table, got ' .. tostring(t))
  end
  local acc = first
  local starting_value = first ~= nil
  -- Whether we do ipairs or pairs is conditional
  for i, v in get_iterator(t) do
    -- No starting value, start on
    -- the first element in the list
    if starting_value then
      acc = fn(acc, v, i, t)
    else
      acc = v
      starting_value = true
    end
  end
  assert(
    starting_value,
    'Attempted to reduce an empty table with no first value.'
  )
  return acc
end


local list = {
  monday = 23,
  tuesday = 63,
  wednesday = 12,
  thursday = 48,
  friday = 3
}
local total_sum = reduce(list, function(acc, current_number, key)
  print(key .. ': ' .. current_number)
  return acc + current_number
end)

print('total sum: ' .. total_sum)

This should print something like this:

wednesday: 12
friday: 3
thursday: 48
monday: 23
total sum: 149

Note that the order the keys are iterated in are not guaranteed. Also "tuesday" wasn't printed out because it was the starting number, but it was still included in the total. Passing an extra argument of 0 to reduce would have caused all the days to be passed through our reducer function and printed out.

Break early

Ok, here's another example that seems tricky at first glance; Let's say you implemented some search functionality on top of reduce like this:

local list = {23, 63, 12, 48, 3}

local find = function(list, predicate_fn)
  return reduce(list, function(acc, v, i, t)
    if predicate_fn(v, a, t) then
      return v
    end
    return acc
  end)
end

print(find(list, function(val)
  return val > 50
end))
print(find(list, function(val)
  return val % 8 == 0
end))

Which prints out the expected results:

63
48

But do you see what's problematic about this? If we find the results we want, the reduce function will keep running through the entire list unnecessarily. Typically when doing a search you only want the first item you find anyway, but the above implementation will return the last item found if more than one match is made. Do you remember how the reduce function passes in the table as the last argument to the reducer function? We can take control of iterator via the table and kill the iteration prematurely. This involved mutating the table:

local list = {23, 63, 12, 48, 3}

local find = function(list, predicate_fn)
  return reduce(list, function(acc, v, i, t)
    if predicate_fn(v, a, t) then
      -- If a result was found, destroy the next item in the list
      -- to prevent the iteration from going any further.
      t[i + 1] = nil
      return v
    end
    return acc
  end)
end

print(find(list, function(val)
  return val > 1
end))

This returns the correct result:

But if we loop over the table afterwards we can see we've messed with the original data which can lead to unexpected consequences in a real application. If your data is coming from an immutable source, meaning something is generating a new copy each time you use it then this wouldn't be a problem:

local generate_list = function()
  return {23, 63, 12, 48, 3}
end

reduce(generate_list(), function()
  ...
  ...

However we could fix all of this if we are willing to add another parameter to our reduce implementation.

local function reduce(t, fn, first)
  local get_iterator = function(t)
    if type(t) == 'table' then
      -- If property of 1 is empty then
      -- iterate as a regular keyed table
      if t[1] == nil then
        return pairs(t)
      end
      return ipairs(t)
    end
    error('Expected table, got ' .. tostring(t))
  end
  local acc = first
  local starting_value = first ~= nil
  for i, v in get_iterator(t) do
    -- Exit the loop when true
    local should_break = false
    -- No starting value, start on
    -- the first element in the list
    if starting_value then
      acc, should_break = fn(acc, v, i, t)
      if should_break then
        break
      end
    else
      acc = v
      starting_value = true
    end
  end
  assert(
    starting_value,
    'Attempted to reduce an empty table with no first value.'
  )
  return acc
end

Now if we pass true as a second return parameter then we will get the first number we are looking for instead of the last. Loop through and print out the list afterward to make sure we haven't mutated it unexpectedly.

local list = {23, 63, 12, 48, 3}

local find = function(list, predicate_fn)
  return reduce(list, function(acc, v, i, t)
    if predicate_fn(v, a, t) then
      return v, true
    end
    return acc
  end, false)
end

print(find(list, function(val)
  return val > 1
end))

for idx, val in ipairs(list) do
  print(idx, val)
end

reduce_right

Another possible change you would want to make is to replace the iterator with a custom-made one to transform data in a specific order or pattern. Taken from lua-users.org's Iteration Tutorial is this reverse-ipairs (ripairs) implementation that allows you to iterate over a table from right to left. This modified version of reduce is typically called reduce_right.

local function reduce_right(t, fn, first)
  local ripairs = function(t)
    local max = 1
    while t[max] ~= nil do
      max = max + 1
    end
    local function ripairs_it(t, i)
      i = i-1
      local v = t[i]
      if v ~= nil then
        return i,v
      else
        return nil
      end
    end
    return ripairs_it, t, max
  end
  local acc = first
  local starting_value = first ~= nil
  for i, v in ripairs(t) do
    -- Exit the loop when true
    local should_break = false
    -- No starting value, start on
    -- the first element in the list
    if starting_value then
      acc, should_break = fn(acc, v, i, t)
      if should_break then
        break
      end
    else
      acc = v
      starting_value = true
    end
  end
  assert(
    starting_value,
    'Attempted to reduce an empty table with no first value.'
  )
  return acc
end

Then swap out reduce for reduce_right in the places you want to use it:

local list = {23, 63, 12, 48, 3}

local find = function(list, predicate_fn)
  return reduce_right(list, function(acc, v, i, t)
    if predicate_fn(v, a, t) then
      return v, true
    end
    return acc
  end, false)
end

print(find(list, function(val)
  return val > 1
end))

Recursive

Since we talked about recursion in the last section, let's try a recursive implementation of reduce. Although with Lua there's no practical reason to choose a recursive implementation over a for-loop or while-loop implementation, doing recursion is fun.

local function reduce(t, fn, acc, key)
  -- Check for starting value
  if key == nil and acc == nil then
    key = next(t, key)
    acc = t[key]
  end
  -- Begin next iteration. Next is a Lua built-in function
  -- that fetches the next key in a table after the given key.
  -- See: https://www.lua.org/pil/7.3.html
  key = next(t, key)
  -- Return acc if we've iterated all keys
  if key == nil then
    return acc
  end
  local break_early = false
  -- Collect new accumulator from predicate function
  acc, break_early = fn(acc, t[key], key, t)
  -- Check to see if the predicate wants to end early
  if break_early then
    return acc
  end
  -- Recur
  return reduce(t, fn, acc, key, acc)
end


-- Test it by getting the total sum from a table like before
local list = {
  monday = 23,
  tuesday = 63,
  wednesday = 12,
  thursday = 48,
  friday = 3
}
local total_sum = reduce(list, function(acc, current_number, key)
  print(key .. ': ' .. current_number)
  return acc + current_number
end, 0)

print('total sum: ' .. total_sum)

This supports breaking early like the two previous implementations.

Exercises

Create a count function that counts up the number of items in a list that match the predicate and returns the total. It should work like this:

local count = function(list, predicate_fn)
  ????
end

local list = {23, 63, 12, 48, 3}
-- Print number of items evenly divisible by 3 (should return 4)
print(count(list, function(v)
  return v % 3 == 0
end))

Go back to the map section in 3.3 and see if you can reimplement the map function on top of reduce.

3.05 - Reduce