Accumulators and Foldl in declarative languages

Using accumulators in declarative programming is common. Basically it is possible to convert not tail recursive functions into tail recursive ones using an accumulator.
Consider a very simple procedure: sum numbers in a list. The naive implementation is:

naive_sum([]) -> 0;
naive_sum([H|T]) ->
    H + naive_sum(T).

This one is not tail recursive. Every time the second clause matches, naive_sum is called and the return value of the recursive call is needed in order to compute the result. The standard way to write this one is:

standard_sum(L) ->
    standard_sum(L, 0).
standard_sum([], Acc) -> Acc;
standard_sum([H|T], Acc) ->
    standard_sum(T, Acc+H).

Notice that this way the last operation of each recursive calling clause is the recursive clause. This means that the new call can take the place of the old one. Simple. It’s so simple (and the pattern is so common), that it has a name foldl.

.
sum(L) ->
    lists:foldl(fun(X, Y) -> X + Y end, 0, L).

Basically, it's one of the primitives of functional languages. For example, in Haskell, it would be:

mysum lst = foldl (+) 0 lst

However, an Haskell programmer would write. This trasformation is known as eta-reduction.

mysum = foldl (+) 0

In Prolog, the naive and the "standard"sum becomes:

naive_sum([], 0).
naive_sum([H|T], Res) :-
    naive_sum(T, Res1),
    Res is Res1 + H.
standard_sum(L, Res) :-
    standard_sum(L, 0, Res).
standard_sum([], Acc, Acc).
standard_sum([H|T], Acc, Res) :-
    Acc1 is H * Acc,
standard_sum(T, Acc1, Res).

Since Prolog clauses can't return a value (because they are not functions, of course!), we need an extra argument which unifies with the result. Besides, in the Prolog version it is quite explicit that naive_sum can't be tail recursive. The difference between the naive and the tail recursive version is that the first one uses linear (O(N)) space and the latter uses constant (O(1)) space. Both are O(n) in terms of running time.
Another typical example on accumulators use is the "revert list" in Prolog. This is the naive version:

naive_revert([], []).
naive_revert([H|T], L1) :-
    naive_revert(T, T1),
append(T1, [H], L1). 

This is both not tail recursive and has a worse than expected running time: indeed it is O(N^2) while it should be O(N).
The first solution is using the built-in reverse predicate. It is even the right thing to do in production, but it is not useful to learn. :)
Let’s examine the following code:

standard_reverse(Xs, Ys) :- standard_reverse(Xs, [], Ys).
standard_reverse([X|Xs], Acc, Ys) :-
    standard_reverse(Xs, [X| Acc], Ys).
standard_reverse([], Ys, Ys).

Once again, we got tail recursion (using an accumulator). Basically we read the first element in the first list and we push it in the accumulator. When we take another element this one is pushed again (and the former is after this one). Then, when we finish the list, we unify the accumulator with the last value. This version is O(n) in time and space.
The Erlang version is extremely similar (and slightly more readable):

standard_revert(L) ->
    standard_revert(L, []).
standard_revert([X|Xs], Acc) ->
    standard_revert(Xs, [X|Acc]);
standard_revert([], Acc) -> Acc.

We can explore this definition further:

rev(_Op, [], Acc) -> Acc;
rev(Op, [H|T], Acc) ->
    rev(Op, T, Op(Acc, H)).
strange_revert(L) ->
    rev(fun(A, B) -> [B|A] end, L, []).

Here, instead of using the [X|Xs] constructor explicitly, we moved it in anonymous function. Notice that we also reverted the parameters. That is to say we don’t have a cons function:

Cons = fun(H, T) -> [H|T] end

but a :

Flipped_Cons = fun(T, H) -> [H|T] end

This is not unexpected. Let’s consider the definition of the foldl function itself:

foldl(_F, Acc, []) ->
    Acc;
foldl(F, Acc, [H|T]) ->
foldl(F, F(Acc, H), T).

They look very similar. Indeed they have almost the very same shape. We just have to flip a couple of parameters (foldl has the accumulator as the second parameter, not as the third one). We must notice that the foldl above is not akin Erlang foldl. In Haskell the type of foldl is:

Hugs> :type foldl
foldl :: (a -> b -> a) -> a -> [b] -> a

The binary operation has the accumulator as the first parameter (here it has type a), which is the same convention we adopted for the handmade foldl written above (from now on our:foldl). Erlang standard foldl follows another convention, the binary function has the accumulator as the second parameter.

foldl(Fun, Acc0, List) -> Acc1
Types  Fun = fun(Elem, AccIn) -> AccOut
Elem = term()
Acc0 = Acc1 = AccIn = AccOut = term()
List = [term()]

If we want to use foldl to build the reverse function we must chose which foldl to use. our:foldl needs the Flip (Flip_Cons) operation, while the standard Erlang foldl is fine with a Cons operation.

foldl_revert(L) ->
    lists:foldl(fun(H,T) -> [H|T] end, [], L).
foldl_revert2(L) ->
    our:foldl(fun(T,H) -> [H|T] end, [], L).

And here we are foldling in Prolog:

foldl(Functor, Acc, [H|T], Foldled) :-
call(Functor, Acc, H, Acc1),
foldl(Functor, Acc1, T, Foldled).
foldl(_Functor, Acc, [], Acc).
cons(T, H, [H|T]) :- !.