Evaluation of Erlang recursive function (why does this work)

3
votes

I started to learn some Erlang and right now I am stuck with following "problem".

I know how recursion works and I am aware of the basics of HigherOrderFunctions.

So to get more into the whole concept I implemented "lists:all/2" with the usage of fold myself:

fold(_, Start, []) -> Start;
fold(F, Start, [H|T]) -> fold(F, F(H, Start), T).

all(Pred, L) ->
    F = fun(H, ToF) ->
        case Pred(H) of
            true -> ToF;
            false -> false
        end
    end,
    fold(F, true, L).

I know this version does not care about empty lists, but that is not what bothers me. I can't figure out why it works how it does.

When I use my list [1,2,3] and set the Pred to "fun(X) when X == 3 -> true; (_) -> false end" it obviously returns "false". But why? if I work this through on paper as last call before something is returned I get:

fold(F, F(H, Start), T)

Where F is Pred and F(H, Start) returns "true" because the last element is 3 and T is an empty list [].

So when I get this right, the last call should be fold(_, true, []) and should therefore return "true" which it doesn't.

Am I missing something here or do I get anything wrong when it comes to evaluating the last expression? Does this function somehow use logical AND on all the returns of "Pred"?

2
recursionerlangevaluation
Your pred could be fun(X) -> X == 3 end - Isac

2 Answers

4
votes

Basically, you are right about the last call, but when doing your analysis, you've substituted true for Start value, where in fact this value is false:

fold(F, true, [1,2,3])

evaluates to:

fold(F, true, [1|[2,3]]) -> fold(F, F(1, true), [2,3])

which in turns evaluates to:

fold(F, false, [2|3]) -> fold(F, F(2, false) [3])

which in turns evaluates to:

fold(F, false, [3|[]]]) -> fold(F, F(3, false), [])

which evaluates to:

fold(_, false, []) -> false

Because in last call Pred is true, and you are returning ToF, which is false.

2
votes

Try to avoid complex solutions for simple problems (code compactness is one of a benefits of functional languages):

all(_, []) ->
   true;
all(Pred, [H|T]) ->
   case Pred(H) of
      true ->
         all(Pred, T);
      false ->
         false
   end.