[erlang-patches] Add lists:init/1 - got tired of implementing it

Serge Aleynikov serge@REDACTED
Fri Apr 26 17:46:27 CEST 2013


Apologies, the recommended name should be lists:drop_last/1 (rather than
what I wrote in the email below).

On 4/26/2013 10:17 AM, Serge Aleynikov wrote:
> The name of this function seems to be misleading though.  Since init/1
> usually refers to initialization of something (e.g. gen behaviors),
> perhaps a better choice of the name would be: drop_tail/1.
> 
> 
> On 4/26/2013 9:41 AM, Fred Hebert wrote:
>> Ah yeah, the version that reverses twice is more likely to be fast due
>> to the fact that lists:reverse/1 calls lists:reverse/2, which is now a
>> NIF. Thus the traversal and building is gonna be made in C rather than
>> in Erlang. Testing with a 'homemade' lists:reverse/2 tends to bring
>> things back to the more expected N vs. 2N for traversals.
>>
>> Regards,
>> Fred.
>>
>> On 04/26, Hans Svensson wrote:
>>> You are absolutely right about the 'badarg', it is better to have a
>>> consistent failure!
>>>
>>> However on performance, the suggested implementation is somewhat
>>> surprisingly the best option (I admit, I did measure before writing
>>> the patch ;-) ) For lists up to 3000 elements, it is on average
>>> ~x1.8 faster than a (tail-)recursive implementation!
>>>
>>> So a better version would probably be:
>>> init([]) -> error(badarg);
>>> init(List = [_ | _]) ->
>>>   lists:reverse(tl(lists:reverse(List)));
>>> init(_) -> error(badarg).
>>>
>>> /Hans
>>>
>>> On 2013-04-25 18:18, Fred Hebert wrote:
>>>> I don't think there's any benefit in tail-recursion when you're
>>>> rebuilding an entirely new list. Given the limited number of arguments,
>>>> the list you're creating by not being tail-recursive is in all points
>>>> similar to the one you would have to maintain on the stack through tail
>>>> recursions. Maybe a bit larger, but given you don't have to trash it,
>>>> you're likely to avoid GC costs by doing it that way.
>>>>
>>>> See http://erlang.2086793.n4.nabble.com/Efficiency-of-a-list-construction-td3538122.html#a3538379
>>>> and http://ferd.ca/erlang-s-tail-recursion-is-not-a-silver-bullet.html
>>>> for more information.
>>>>
>>>> What I would worry about in my implementation is adding a clause
>>>> of 'init([]) -> error(badarg)' to be consequent in failures with the rest
>>>> of the lists module, and not get a 'function_clause' error there when
>>>> someone passes in an empty list.
>>>>
>>>> On 04/25, Yurii Rashkovskii wrote:
>>>>> What about non-tail-recursiveness, though?
>>>>>
>>>>>
>>>>> On Thu, Apr 25, 2013 at 8:54 AM, Fred Hebert <mononcqc@REDACTED> wrote:
>>>>>
>>>>>> Sounds to me like it would have been better implemented as something like:
>>>>>>
>>>>>> init([_]) -> [];
>>>>>> init([H|T]) -> [H|init(T)].
>>>>>>
>>>>>> As this would avoid re-building the list twice, once on each reversal.
>>>>>>
>>>>>> Regards,
>>>>>> Fred.
>>>>>>
>>>>>>
>>>>>> On Thu, Apr 25, 2013 at 11:12 AM, Hans Svensson <hanssv@REDACTED> wrote:
>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>> Yesterday I implemented, for the umpteenth time, the init-function. (I
>>>>>>> guess being taught Haskell at one point could be blamed partly for the
>>>>>>> coding style requiring this function...) It is a trivial function that I
>>>>>>> think should be part of the standard lists module. This patch adds the
>>>>>>> function, tests in lists_SUITE, and documentation of the function.
>>>>>>>
>>>>>>> The implementation is trivial: reverse(tl(reverse(List))).
>>>>>>>
>>>>>>> If I've missed some religious reason for not having this function feel
>>>>>>> free to drop the patch ;-)
>>>>>>>
>>>>>>> Cheers,
>>>>>>> Hans
>>>>>>>
>>>>>>> git fetch git://github.com/hanssv/otp.**git<http://github.com/hanssv/otp.git>add_init_to_lists
>>>>>>>
>>>>>>> https://github.com/hanssv/otp/**compare/erlang:maint...add_**
>>>>>>> init_to_lists<https://github.com/hanssv/otp/compare/erlang:maint...add_init_to_lists>
>>>>>>> https://github.com/hanssv/otp/**compare/erlang:maint...add_**
>>>>>>> init_to_lists.patch<https://github.com/hanssv/otp/compare/erlang:maint...add_init_to_lists.patch>
>>>>>>> ______________________________**_________________
>>>>>>> erlang-patches mailing list
>>>>>>> erlang-patches@REDACTED
>>>>>>> http://erlang.org/mailman/**listinfo/erlang-patches<http://erlang.org/mailman/listinfo/erlang-patches>
>>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> erlang-patches mailing list
>>>>>> erlang-patches@REDACTED
>>>>>> http://erlang.org/mailman/listinfo/erlang-patches
>>>>>>
>>>>>>
>>>>> _______________________________________________
>>>>> erlang-patches mailing list
>>>>> erlang-patches@REDACTED
>>>>> http://erlang.org/mailman/listinfo/erlang-patches
>>>> _______________________________________________
>>>> erlang-patches mailing list
>>>> erlang-patches@REDACTED
>>>> http://erlang.org/mailman/listinfo/erlang-patches
>>>
>> _______________________________________________
>> erlang-patches mailing list
>> erlang-patches@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-patches
>>



More information about the erlang-patches mailing list