[erlang-questions] Additions to lists module

Richard O'Keefe ok@REDACTED
Thu Nov 27 04:57:49 CET 2008

On 27 Nov 2008, at 4:08 pm, Serge Aleynikov wrote:
> On the other hand returning a value of length(L)+1 means that you  
> would need to traverse the list twice - once to figure out the  
> "unsuccessful" return value, and the second one to find the actual  
> index of an element.  Doesn't it sound like an unnecessary piece of  
> work to compute length(L)+1?

Um, no.  Any time you are doing positional indexing into a list,
you had _better_ be remembering how long the list is.
More accurately,
  (1) it doesn't require any more effort to *compute* length(L)+1
      in order to return it (you have it right there in an argument)
  (2) in *isolation* it *would* require two traversals, but
  (3) in most plausible contexts it would not.

In particular, if you have things like "delete the nth element if there
is one" or "insert this after n-1 elements", then length(L)+1 is
_exactly_ what you want.

I used this convention in a string library and it worked beautifully.
(More precisely, I used "how many leading elements that do not match"
as the definition, so length(L) was the failure result.)
>> Summary: I recommend adopting/adapting the Haskell names,
>> and there's a choice between
>> Index|absent, Index|0, Index|length+1, {present,Index}|absent
>> for the result.
> My preference is Index|absent or Index|0.

I would hope that we could find a better reason for a choice
than someone's preferences, mine included.
> Though I agree with your reasoning, the only counter argument I can  
> come up with is that all functions in the lists module don't have  
> separators,

There has been a lot of chatter in this mailing list about
revising the libraries.  Consistent and readable naming conventions
are obviously a goal of such a revision, if/when it happens.  I for
one do not find the names in the current lists module acceptable.

> so if we choose to respect the naming style in that module, we'd  
> need to drop the underscore.
> On the other hand in the string module we find co-existing names  
> like substr/2 and sub_string/2...
>> Something like
>>    foldl_prefix(Stepper, Acc0, [X|Xs]) ->
>>        case Stepper(X, Acc0)
>>          of {continue,Acc} -> foldl_prefix(Stepper, Acc, Xs)
>>           ; {stop,Result}  -> Result
>>        end;
>>    foldl_prefix(S, Acc, []) when is_function(S, 2) ->
>>        Acc.
>> which _does_ at least fold a prefix, might be less confusing.
>> The function results are now completely unambiguous, there
>> is no mention of any 'predicate' (because there is none),
>> and while the name doesn't completely describe the function,
>> everything it says is true.  The Stepper function here is closer
>> to being the Fun of a fold than the Pred of a takewhile.
>> I'm sure someone else can think of a better name.
>> I am rather concerned that the final value of a logically
>> empty list (one for which it is not the case that the list
>> has an element and the stepper function says to continue)
>> has its result derived in two different ways:
>> - if the list is physically empty ([]), Acc0 is the result
>> - if the list is logically but not physically empty ([X|_]),
>>   Acc1 is the result where {stop,Acc1} = Stepper(X, Acc0).
>> Somehow this just doesn't feel right.
> Why is the second case a concern?  Wouldn't it be at the discretion  
> of the Stepper function to make the determination of when to stop  
> and return the accumulator whatever it wants one to be?

I don't understand your question.  The point is that there are two
*DIFFERENT* ways for a logically empty list to terminate and so the
same logical situation gets two *DIFFERENT* ways to determine quite
possibly different final results.

Of course it's at the discretion of the Stepper to decide when
to stop.  That's what it's _for_.  But not always!  When the list
comes to an end things stop without the Stepper being asked or even
told.  TWO ways to stop, both representing the same abstract
situation ('while' has found all the elements we want) but TWO
different final values.

get t
> Serge

More information about the erlang-questions mailing list