[erlang-questions] Can I do the same with a fold easily

ok <>
Mon Oct 19 04:34:01 CEST 2015


"Roelof Wobben" <> wrote:

> I have this two functions :
>
> filter(List, Filter) ->
>      lists:filter(Filter, List).

I see what you did there, you swapped the argument order.
But doing that and keeping the same name is confusing; it
is so easy for people to see what they KNOW must be there
for 'filter' and so hard to see what IS there.

> split2(List) ->
>      { filter(List, fun(X) -> math_functions:odd(X)  end),
>        filter(List, fun(X) -> math_functions:even(X) end) }.
>
> which produces both {[1,3],[2,4]}


Since I'm not familiar with the math_functions: module,
I would prefer to see

split2(Integers) ->
    { [X || X <- Integers, X band 1 =:= 1]
    , [X || X <- Integers, X band 1 =:= 0]
    }.

But your code is fine.

> Could I this also do with a fold or is this the best solution.

It all depends on what 'best' means.
List comprehensions could be implemented more efficient;y
than they currently are, which could make the direct list
comprehension version the fastest and most space efficient.

A function that traverses a list in a single pass is a nice
thing to have because it can be fused with a function that
generates a list (either by the compiler, as in Haskell, or
by you, as in Erlang) to eliminate the intermediate list.
If you are interested, look up 'deforestation' in the context
of functional programming languages.

Let's consider two folds.

(1) Work from left to right building up answers as we go.
    E := O := []
    for X in Integers do
        if odd(X) then O := [X|O] else E := [X|E]
    oops, the answers are back to front.
    {reverse(O), reverse(E)}.

    Since an Erlang function has only one result, we have
    to pack E and O together into a single term.

    OE := {[],[]}
    for X in Integers do
        OE := if odd(X) then {[X|O0],E0} else {O0,[X|E0]}
              where {O0,E0} = OE
    {reverse(O0),reverse(E0)} where {O0,E0} = OE

    Now _that_ is a (left) fold with a cleanup step at the end:

    split3(Integers) ->
        {O,E} = lists:foldl(fun (X, {O0,E0}) ->
                    case X band 1
                      of 1 -> {[X|O0], E0}
                       ; 0 -> {O0, [X|E0]}
                    end end, {[], []}, Integers),
        {reverse(O), reverse(E)}.

(2) We can avoid the reversing by working from right to left.

    split4(Integers) ->
        lists:foldr(fun (X, {O0,E0)) ->
            case X band 1
              of 1 -> {[X|O0], E0}
               ; 0 -> {O0, [X|E0]}
            end end, {[], []}, Integers),


(3) You could expand the foldr/3 version out by hand.  If an
    Erlang function could return two values, like a Lisp or
    Mesa function or a Prolog predicate, doing so could eliminate
    the tuples.  Since an Erlang function _can't_ do that,
    we're stuck with turning over N tuples given N integers,
    in addition to the one tuple we really want.  (A really good
    compiler could in fact eliminate the extra N tuples; whether
    the Erlang compiler is that good yet I don't know.)

    odds_and_evens(Integers) ->
        odds_and_evens(Integers, [], []).

    odds_and_evens([X|Xs], O0, E0) ->
        {O1,E1} = odds_and_evens(Xs, O0, E0),
        case X band 1
          of 1 -> {[X|O1], E1}
           ; 0 -> {O1, [X|E1]}
        end;
    odds_and_evens([], O, E) ->
        {O, E}.

(4) Alternatively, you could read the documentation for
    the lists: module where you will find lists:partition/2.

    split5(Integers) ->
        lists:partition(fun (X) -> X band 1 =:= 1 end, Integers).

I think (4) has the edge in readability.





More information about the erlang-questions mailing list