Stack-safe default foldr?

Change Proposals
#1

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 CatLists 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.

2 Likes
#2

I think both stack-safe foldr and foldl can be defined in terms of foldMap by using an unbalanced binary tree, reassociating as you go when unconsing/unsnocing. This is equivalent to the foldl/reverse implementation of foldr for Lists (The tree is just fully left associatve). You don’t specifically need a CatList. I’ve defined the equivalent ad-hoc in lots of libraries, and I absolutely think we should make the default implementations stack-safe.

data FreeSemigroup a = Node a | Append (FreeSemigroup a) (FreeSemigroup a)
uncons :: FreeSemigroup a -> Tuple a (Maybe (FreeSemigroup a))
unsnoc :: FreeSemigroup a -> Tuple (Maybe (FreeSemigroup a)) a

See things like:

1 Like
#3

I’m playing around with this idea, and I think I can implement a foldl in terms of foldMap that’s going to be stack-safe, but I’m not sure my foldl performance stays O(n). I’m doing this for uncons:

uncons :: ∀ a. FreeSemigroup a -> Tuple a (Maybe (FreeSemigroup a))
uncons i = go i Nothing
  where 
  go :: FreeSemigroup a -> Maybe (FreeSemigroup a) -> Tuple a (Maybe (FreeSemigroup a))
  go lhs rhs = case lhs, rhs of
    Node a, _ -> Tuple a rhs
    Append (Node a) ys, Nothing -> Tuple a $ Just ys
    Append (Node a) ys, Just r -> Tuple a $ Just $ Append ys r
    Append xs ys, Nothing -> go xs $ Just ys
    Append xs ys, Just r -> go xs $ Just $ Append ys r

That’s a bit of a roundabout implementation just to make sure that it’s tail recursive so that it’s stack-safe, but wouldn’t the performance be O(log(n)), and hence foldl would be O(n*log(n))? Don’t I need a constant-time uncons in order to get a O(n) foldl?

#4

You don’t have to make it strictly a semigroup. You can add an empty case. To clean it up a bit you could do something like:


data FreeMonoid a = Mempty | Append (FreeMonoid a) (FreeMonoid a) | Node a

data UnconsView a = UnconsMore a (FreeMonoid a) | Done

uncons :: forall a. FreeMonoid a -> UnconsView a
uncons =
  case _ of
    Empty -> Done
    Node a -> UnconsMore a Empty
    Append l r -> go l r
  where
  go l r = case l of
    Empty -> go r Empty
    Node a -> UnconsMore a r
    Append l' r' -> go l' (Append r' r)

This is amortized O(1), exactly the same as CatList. That is, each time you uncons it makes progress in flattening it out. You aren’t repeating all the work you did in previous steps, so it all evens out. For example, if the tree is totally left-associated, the first uncons would have to reverse the entire tree (equivalent to List.reverse at the end of the foldr implementation for lists). But it never does that work again as long as you continue to productively uncons. This is exactly equivalent to the existing Endo approach, except that uses the programming language stack as it’s data structure as it builds a tree of closures, rather than the heap and data nodes, and is consequently unsafe.

It’s only roundabout because you have to implement this ad-hoc :laughing: If you were able to just use CatList, it wouldn’t feel that way, would it? :smile:

I suggest using something like UnconsView because there’s less allocation and indirection. In large folds, this can make a significant difference to the constants (half the allocations, half the garbage).

1 Like
#5

Thanks! Yeah I was building a

newtype FreeMonoid a = FreeMonoid (Maybe (FreeSemigroup a))

without thinking about the extra allocations and GC. I’m really glad to hear that it’s an amortized O(1). I didn’t recognize that it make progress towards flattening like that. That’s cool! I was able to get it up and running with a modification of this FreeMonoid with the UnconsView, and the benchmarks got much better. Thanks for the perf tips!