[erlang-questions] List comprehension puzzler

Raimo Niskanen <>
Wed Sep 21 08:30:33 CEST 2016


On Tue, Sep 20, 2016 at 03:53:55PM -0700, Kenneth Lakin wrote:
> On 09/20/2016 08:00 AM, Raimo Niskanen wrote:
> > Note that length(ISBN) will be called twice on this maybe very long list,
> > and that in itself may be bad since length/1 is O(N).
> 
> That seems easy enough to fix:
> 
> when length(I) =< 13 andalso (length(I) == 10 orelse length(I) == 13)

Sorry about being unclear.  I should have written "... *called* (twice) ..."
since there is little greater harm in calling it twice than calling it once.
It is still O(N) if you call it a constant number of times, and the
subsequent times it is likely that data is in the processor's cache
so they may be faster.

The harm is in calling length/1 even once on a possibly very long list.

We have had a suggestion to add a guard length(List, Max)
or max_length(List, Max) that would stop traversal after Max elements.

This would be O(min(length(List), Max)),
which is O(Max),
which for a constant Max is O(1).

But we never got to it...

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB


More information about the erlang-questions mailing list