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):
http://erlang.org/doc/man/lists.html#foldl-3
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.
