Why Enum.reduce fun arguments are x, acc instead of acc, x?

I always thought that it follows the order of the arguments to Enum.reduce itself - first the collection, then the accumulator, so in the reducer you get the element first and the accumulator second.

Probably to give you a chance to utilise tail-call recursion in the passed closure function, which only works if the accumulator is the last parameter (unless I am horribly misremembering this).

Interesting. This would make sense. Thanks for the info.

That is incorrect.

A simple implementation of reduce() looks somewhat like this:

def reduce([], acc, _fun) do
  acc 
end

def reduce([h|t], acc, fun) do
  reduce(t, fun.(h, acc), fun)
end

Tail recursion is happening for invocations of reduce() itself, the details of the function fun don’t matter.

I think you’re remembering that foldl is easier to tco than foldr.

defmodule Fold do
  # reduce _is_ foldl
  # foldl [a] -> b -> (a -> b -> b) -> b
  def foldl([], acc, _),
    do: acc

  def foldl([x | xs], acc, f),
    do: foldl(xs, f.(x, acc), f)

  # foldr [a] -> b -> (a -> b -> b) -> b
  def foldr([], acc, _),
    do: acc

  def foldr([x | xs], acc, f),
    do: f.(x, foldr(xs, acc, f))
end

list = [1, 2, 3]
f = &[&1 | &2]

IO.inspect(Fold.foldl(list, [], f)) # [3,2,1]
IO.inspect(Fold.foldr(list, [], f)) # [1,2,3]

Folding (reducing) emerged from “folding lists” - the most common list operation is cons-ing:

f = &[&1 | &2]

Note how the parameter order isn’t “unhandy”. One could argue that the unhandy-ness is a result of the preferred parameter order in Elixir due to pipelining. In a curried language the opposite order (the thing that changes should be last) would be preferred.

Note also that Elixir inherited the order from Erlang (1986):

and Erlang has no pipelining.

FYI:

Haskell (1990):

Prelude.foldl: (a -> b -> a) -> a -> [b] -> a
Prelude.foldr: (a -> b -> b) -> b -> [a] -> b

OCaml (1996):

fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

Interestingly for “fold left” it’s (acc, elem -> acc) while for “fold right” it’s (elem, acc -> acc)

Hypothesis:

• (acc, elem -> acc) for “fold left” accumulator is built from the list left-to-right (left associative)
• (elem, acc -> acc) for “fold right” accumulator is built from the list right-to-left (right associative)

LISP (1958)

(reduce (lambda (x y) (+ (* x 10) y)) '(1 2 3 4)) => 1234

iex(1)> Enum.reduce([1,2,3,4], & &2 * 10 + &1)
1234

Again LISP used (acc, elem -> acc) for reduce/fold left.

So why would Erlang use (elem, acc -> acc)?

Hypothesis:

• Conceptually general “folding” refers to foldr because it preserves the order within a list - hence (elem, acc -> acc).

defmodule X do
  def map_1(list, f),
    do: :lists.foldr(&[f.(&1) | &2], [], list)

  def map_2(list, f) do
    (&[f.(&1) | &2])
    |> :lists.foldl([], list)
    |> :lists.reverse()
  end

  def scan_1(list, init, f) do
    fun = fn x, g ->
      fn y ->
        value = f.(x, y)
        [value | g.(value)]
      end
    end

    acc = fn _ -> [] end
    lazy = :lists.foldr(fun, acc, list)
    lazy.(init)
  end

  def scan_2(list, init, f) do
    fn
      x, [y | _] = acc ->
        [f.(x, y) | acc]

      x, [] ->
        [f.(x, init)]
    end
    |> :lists.foldl([], list)
    |> :lists.reverse()
  end
end

list = [1, 2, 3]
f = &(&1 * 2)
g = &Kernel.+/2

IO.inspect(X.map_1(list, f))     # [2, 4, 6]
IO.inspect(X.map_2(list, f))     # [2, 4, 6]
IO.inspect(X.scan_1(list, 2, g)) # [3, 5, 8]
IO.inspect(X.scan_2(list, 2, g)) # [3, 5, 8]

From a performance standpoint foldl is preferred for long lists but requires reversal if order is relevant. But for pragmatic reasons sticking to the same function type (elem, acc -> acc) makes a function usable for both foldr and foldl.

Yeah, that was it and thanks for correction.

Don’t know the answer, but FWIW I also think that passing the acc first, collection element second would be more intuitive, and I frequently find myself flipping these two args in reduce.

Yup. Generally having the arguments in the current order is less ergonomic. But I suppose I’ll have to wait for elixir 2.0 before it’s made consistent.

My guess is that this change will never happen, but who knows

Many other languages agree with you (though initially I found the swap between foldl (i.e. acc, elem -> acc) and foldr (i.e. elem, acc -> acc) a bit confusing).

for comprehensions side step the issue:

iex(1)> for x <- [1,2,3,4], reduce: %MapSet{} do
...(1)>   acc -> MapSet.put(acc,x)
...(1)> end
#MapSet<[1, 2, 3, 4]>
iex(2)> 

https://github.com/erlang/otp/blob/master/lib/stdlib/src/lists.erl#L1253-L1277

foldl(F, Accu, [Hd|Tail]) ->
    foldl(F, F(Hd, Accu), Tail);

% ...

foldr(F, Accu, [Hd|Tail]) ->
    F(Hd, foldr(F, Accu, Tail));