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

Serge Aleynikov serge@REDACTED
Fri Apr 26 16:17:25 CEST 2013


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