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

groupsOf and friends can exceed maximum call stack size #164

Open jmbromley opened 2 years ago

jmbromley commented 2 years ago

groupsOf and friends are not truly tail recursive because they use List.take from elm/core. But the core implementation of List.take only switches to a (slightly slower) tail recursive implementation after it has processed 1000 elements. This means that if groupsOf has a large number of recursions then it can build up an excessive call stack from repeated calls to List.take (each of which could have a stack of up to 1000 calls).

A realword of example of this causing "maximum call stack size exceeded" errors is billstclair/elm-crypto-string#10.

Chadtech commented 2 years ago

This is really interesting. I appreciate your code too. In your PR you ask if this is too much of a corner case to worry about. Yeah, it might be. I am always torn because, it is great to document these trade offs and discover these optimizations for people to find. On the other hand its not good to include them as general or "go to" functions for people to use.

I wonder if we should make a new module called like List.Extra.TailRec for these functions?

I guess before we would even want to look into that we should measure the exact performance trade off for full stack safety.