search

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 59 forks source link

Refactor (update|set|remove|swap|split)At for efficiency #55

Closed pzp1997 closed 7 years ago

pzp1997 commented 7 years ago

I refactored updateAt, setAt, removeAt, swapAt, and splitAt to make them more efficient. All of the functions are now tail-recursive. In the case of success (i.e. the index is in range), the functions perform two passes over the elements from the start of the list up to and including the given index (and in the case of swapAt the larger index). In the case of failure, the functions require only a single pass over the list.

Closes #1 and the second part of #30. I also have a fast implementation for the proposed insertAt function that uses the atHelper, which would close the rest of #30 and #43. I also have another version of the code that changes the return types of updateAt, setAt, and swapAt in accordance with #32 and #36. Just let me know what you need and I can submit additional PRs or add to this one.

pzp1997 commented 7 years ago

@cbenz Made an interesting point in #36 regarding this PR. Although in theory, these implementations should be faster than the current ones, performance and optimization are a bit tricky in practice. Before we proceed, we should really benchmark the functions so we can truly assess if I was successful. I will try to do this soon. I have also read elm-lang/core#668 about optimizing List.take, which has me wondering if we should take a similar approach. I'm going to close this for now, and re-open it once I have the benchmarks.