Would it be a good idea to make a stack-safe alternative to foldrDefault
/foldlDefault
, or perhaps alter foldrDefault
/foldlDefault
to be stack-safe?
For background, I was trying to benchmark the performance of CatList
, and Array.fromFoldable
started blowing the stack for CatList
s of several thousand elements. This is because Array.fromFoldable
(and fromFoldable
for both list types that matter) use foldr
, and while CatList
has a stack-safe foldl
and foldMap
implementation, it’s foldr
is just foldrDefault
, which isn’t stack-safe. So really any Foldable
collection can’t be safely converted to an array or list or lazy list without its own custom stack-safe implementation of foldr
.
It’s easy enough to define a stack-safe foldr
out of foldl
(assuming foldl
is stack-safe), e.g., by using FFI (or maybe ST?) to build an array, and then using the stack-safe foldr
implementation for arrays. This would be slower than the existing implementation, but still O(n). There’s probably a smarter way to do it than that besides. As far as precedence, both Lists define a foldr
that’s significantly slower than other implementations in order to preserve stack-safety.
(I don’t know of a way to define a stack-safe foldr
using foldMap
that stays O(n) though, but maybe smarter people than me can figure it out. It seems like you’d need a CatList
, or something else with O(1) append
to be available inside Data.Foldable
. Maybe that’s a reason why we can’t just alter the existing foldrDefault
/foldlDefault
functions and would need alternative functions.)
To me it seems like a pretty big pitfall when collections can only be safely folded one direction (which isn’t even always clear in the docs), and can’t be safely converted to other stack-safe collections. Is it worthwhile to try to work on getting every collection’s folding to be stack safe in both directions? Is it worthwhile to try to make the default folding functions stack-safe, which would probably solve most of the problems? A lot of collections like CatList
and Seq
probably don’t even make sense to use unless you’re working with enough elements that you could blow the stack.