fix RangeError of iterate

[m-shaka]

iterate raises RangeError: Maximum call stack size exceeded when recursive function is called too many time(example bellow). Now I use tail recursive optimization to avoid this sort of error.

f n = if n == 100000 then Nothing else Just (n + 1)

iterate f 1

[Chadtech]

Awesome!

Before merging this, would you mind doing a benchmark so we can see that this doesnt come at any great trade off with performance? Here is an out of date example of such a benchmark we did for another PR: https://ellie-app.com/t6xMfYpdNwa1 . There is some info about benchmarking in the README.md

[m-shaka]

I'm so sorry not to read the contribution guide.

In fact, my first implementation cause performance degradation. But current implementation is rather faster.

https://ellie-app.com/8dGJwQbwxZpa1

[pzp1997]

Wow, you made it tail-recursive and also made it faster! Nice work. I find the performance win quite surprising, as from what I've seen, a non-tail-recursive implementation is nearly always more performant than a tail-recursive implementation with a reverse at the end. But you can't argue with solid benchmarks.

Also, with regards to the changes you made between your original implementation and your current one, I noticed a while ago that top-level helper functions perform better than those nested in a let... in.... (Again, I'm not really sure why this is the case, but perhaps this has to do with closure allocation.) I think we should keep this tip in mind for all the functions in List.Extra.

[harrysarson]

When I run these benchmarks I see it getting slightly slower:

These are small changes though so is probably okay.

[m-shaka]

@harrysarson You use Firefox or Safari, I guess. On Chrome it performs about 2 times faster. I'm not sure what causes this difference... :cry:

[harrysarson]

firefox!

[harrysarson]

I had a play with the ellie on firefox but could not match the performance of the non tail recursive version unfortunately.

[pzp1997]

I ran the benchmark in various browsers on my laptop and I'm seeing wins pretty much across the board. Of the browsers I tested, Firefox had the worst absolute performance and the wins there were also smaller. The only times when the original version was faster was with 10 recursive calls on Firefox and Safari. I think that slowdown is acceptable given all the other positives of the proposed implementation.

Chrome 80.0.3987.132

Firefox 73.0.1

Safari 11.1.2

Opera 67.0.3575.53

[Chadtech]

Awesome! This all looks good to me. The benefits in most cases seem to outweigh the possible costs in some cases.

Great job @m-shaka !