[erlang-questions] To name a function

[Raimo Niskanen]

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