Erlang: serial implementation of accumulator

Question

I am trying to create a method that takes an associative and commutative operator, as well a list of values, and then returns the answer by applying an operator to the values in the list.

The following two examples represent what the input/output are supposed to look like.

Example 1

Input: sum(fun(A,B) -> A+B end, [2,6,7,10,12]).

Output: 37

Example 2

Input: sum(fun (A,B) -> A++B end , ["C", "D", "E"]).

Output: "CDE"

This is the code I am working with so far.

-module(tester).
-compile(export_all).

sum(Func, Data, Acc) ->
    lists:foldr(Func, Acc, Data).

This code produces the correct result, however, there are two problems I am trying to figure out how to approach answering.

(1) In order for this code to work, it requires an empty list to be included at the end of the command line statements. In other words, if I enter the input above (as in the examples), it will err out, because I did not write it in the following way:

12> tester:sum(fun(X, Acc) -> X+Acc end, [2,6,7,10,12], 0).

How would I implement this without an empty list as in the examples above and get the same result?

(2) Also, how would the code be implemented without the list function, or in an even more serial way?

Answer 1

After working on this for a while, this was my solution. I've left some comments about the general idea of what I did, but there's a lot more to be said.

-module(erlang2).
-compile(export_all).
-export([reduce/2]).

reduce(Func, List) ->
    reduce(root, Func, List).

%When done send results to Parent
reduce(Parent, _, [A]) -> 
    %send to parent 
    Parent ! { self(), A}; 

   %I tried this at first to take care of one el in list, but it didn't work
   %length ([]) ->
   % Parent !   {self(), A};

%get contents of list, apply function and store in Parent
reduce(Parent, Func, List) ->
            { Left, Right } = lists:split(trunc(length(List)/2), List),
            Me = self(),
            %io:format("Splitting in two~n"),
            Pl = spawn(fun() -> reduce(Me, Func, Left) end),
            Pr = spawn(fun() -> reduce(Me, Func, Right) end),
            %merge results in parent and call Func on final left and right halves
            combine(Parent, Func,[Pl, Pr]).

%merge pl and pl and combine in parent
combine(Parent, Func, [Pl, Pr]) ->
    %wait for processes to complete (using receive) and then send to Parent
    receive
        { Pl, Sorted } -> combine(Parent, Func, Pr, Sorted);
        { Pr, Sorted } -> combine(Parent, Func, Pl, Sorted)
    end.

combine(Parent, Func, P, List) ->
    %wait and store in results and then call ! to send
    receive
        { P, Sorted } ->
            Results = Func(Sorted, List),
            case Parent of
                root ->
                    Results;
                %send results to parent
                _ -> Parent ! {self(), Results}
            end
    end.

Answer 2

How would I implement this without an empty list as in the examples above and get the same result?

Assuming the list always has one element (you can't really do it without this assumption), you can extract the first element from the list and pass that as the initial accumulator. You'll need to switch to foldl to do this efficiently. (With foldr you'll essentially need to make a copy of the list to drop the last element.)

sum(Func, [X | Xs]) ->
  lists:foldl(fun (A, B) -> Func(B, A) end, X, Xs).

1> a:sum(fun(A,B) -> A+B end, [2,6,7,10,12]).
37
2> a:sum(fun (A,B) -> A++B end , ["C", "D", "E"]).
"CDE"

Also, how would the code be implemented without the list function, or in an even more serial way?

Here's a simple implementation using recursion and pattern matching:

sum2(Func, [X | Xs]) ->
  sum2(Func, Xs, X).

sum2(Func, [], Acc) ->
  Acc;
sum2(Func, [X | Xs], Acc) ->
  sum2(Func, Xs, Func(Acc, X)).

We define two versions of the function. The first one extracts the head and uses that as the initial accumulator. The second one, with arity 3, does essentially what the fold functions in lists do.