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

[Fred Hebert]

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
>