Evaluation of Erlang recursive function (why does this work)

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"?

Answers


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.


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.

Need Your Help

Core data only storing last object of JSON feed

iphone objective-c xcode json core-data

I´m using Core Data as local storage in my app. I´ve set it up properly and made subclasses of NSManagedObject for each entity. However, when I´m trying to insert values into my store, it only inse...

Javascript printing a variable

javascript variables printing echo

I want to print a variable auth in the flashplayer.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.