elm-community / list-extra

Convenience functions for working with List.
http://package.elm-lang.org/packages/elm-community/list-extra/latest
MIT License
135 stars 58 forks source link

Simpler implementation of the "cycle" function #126

Closed flsantos0101 closed 4 years ago

flsantos0101 commented 4 years ago

I've updated the "cycle" function. The change consists of a more straightforward application (it has been tested on both Ellie and localhost).

pzp1997 commented 4 years ago

Interesting implementation! The current implementation of cycle was written to be stack safe and performant, see #80. At the time, I tried several implementations and that was the best one I found, however, I do not believe I tried a "doubling" implementation like the one you are proposing. As per the contribution guidelines, we need benchmarks that demonstrate performance gains over the current implementation to proceed.

pzp1997 commented 4 years ago

Going off intuition, I think you should avoid recomputing the length of the list for each recursive call since that results in many extra traversals of the list. Instead, you can compute the length of the list once, pass that as an argument to a recursive helper function, and add it to itself (double it) for each recursive call.

Another change that I expect would improve perf is to stop the recursion right before the length of the list is larger than c to avoid extra allocations.