[erlang-questions] To name a function

[Jakob Cederlund]

categorize(L, F) when is_list(L), is_function(F, 1) ->

    categorize(L, F, empty).


categorize([], _F, V) ->

    V;

categorize([E | Rest], F, empty) ->

    categorize(Rest, F, F(E));

categorize([E | Rest], F, V) ->

    case F(E) of

        V -> categorize(Rest, F, V);

        _ -> some

    end.

O(N), no building, no double traversing, quite readable too...

2010/12/16 Raimo Niskanen
<raimo+erlang-questions@REDACTED<raimo%2Berlang-questions@REDACTED>
>

> On Thu, Dec 16, 2010 at 09:44:29AM +0100, Morten Krogh wrote:
> > Hi
> >
> > As soon as you have seen both an element that satisfies the condition
> > and one that doesn't, you can return "some", making a full list
> > traversal overkill for many inputs.
>
> To support that idea (regardless of what this thread is about,
> I am just throwing in an observation), if you have to traverse
> a list once - you have linear speed complexity; O(N).
>
> If you instead do it twice this does not change, you just
> get a constant factor speed degradation.
>
> If you (sub- ?) optimize by traversing the list once but do
> more work by building intermediate results of which most
> are uninteresting - you stress the garbage collector
> which makes the speed complexity harder to determine.
> You probably get anything from a large constant factor speed
> degradation to even O(N*log(N)) .. O(N*N).
>
> Therefore it is often a good idea to first traverse the list
> without building garbage to decide if you can skip the term building
> traversal entirely, unless it is obvious this rarely happens.
>
> >
> > Morten.
> >
> > On 12/15/10 6:13 PM, Attila Rajmund Nohl wrote:
> > >2010/12/15, Ryan Zezeski<rzezeski@REDACTED>:
> > >>On Wed, Dec 15, 2010 at 11:06 AM, Attila Rajmund Nohl<
> > >>attila.r.nohl@REDACTED>  wrote:
> > >>
> > >>>Hello!
> > >>>
> > >>>I've found at least places in my code where I'd need a function which
> > >>>decides if all, some or none members of a list have a particular
> > >>>property (the list always has at least one element). How to name this
> > >>>function? The code is something like this:
> > >>>
> > >>>f(_F, []) ->
> > >>>  erlang:error({badarg, []});
> > >>>
> > >>>f(F, L) ->
> > >>>  {Has, Not} =
> > >>>    lists:foldr(
> > >>>      fun(E, {H, N}) ->
> > >>>        case f(E) of
> > >>>          true ->  {H+1, N};
> > >>>          false ->  {H, N+1}
> > >>>        end
> > >>>      end, {0,0}, L),
> > >>>  case {Has, Not} of
> > >>>    {0, _} ->  none;
> > >>>    {_, 0} ->  all;
> > >>>    _ ->  some
> > >>>  end.
> > >>>
> > >>>
> > >>Well, I wouldn't give it any style points but I came up with
> > >>all_some_none.
> > >>  Also, instead of using fold you could make use of lists:all/2 and
> > >>lists:filter/2.
> > >I could, but that would traverse the list twice (with the length()
> > >guard three times). I don't expect the lists I'm using this function
> > >on to have more than 2000 elements, so on contemporary hardware this
> > >difference is probably not noticeable.
> > >
> > >________________________________________________________________
> > >erlang-questions (at) erlang.org mailing list.
> > >See http://www.erlang.org/faq.html
> > >To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
> > >
> >
> >
> > ________________________________________________________________
> > erlang-questions (at) erlang.org mailing list.
> > See http://www.erlang.org/faq.html
> > To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
>
> --
>
> / Raimo Niskanen, Erlang/OTP, Ericsson AB
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
>
>