An approach for short circuiting folds - awesome or harmful?

Feedback
#1

The other day @natefaubion mentioned an idea that popped into his head for an approach to using normal folds to create short circuiting folds. I though it was really interesting so I decided to go ahead and try to implement it. Here is the result
https://github.com/ursi/purescript-return

Return introduces a new data type

data Return a
  = Cont a
  | Return a

and a function

mkReturnable :: ∀ a. ((Return a -> a) -> a) -> a

Using mkReturnable you can create functions that “return” values early in a way that you normally would have to use explicit recursion to accomplish.

For example:

foldl' :: ∀ a b f. Foldable f => (b -> a -> Return b) -> b -> f a -> b
foldl' f init as = mkReturnable \return -> foldl (\b a -> return $ f b a) init as

This is nice because it allows for you to define, for fee, folds that can exit early for anything that already has a Foldable instance, instead of having to use recursion to handle each differently.

However, I don’t know what to think of this. On one hand, the API to create short circuiting functions just feels a little off to me. I think it’s because you’re using the FFI to make an abstraction that can’t be made within PS itself (afaict). But on the other hand, I think it’s type safe and I would guess that any function you can create with this could also be created without it. It also allows for potentially more performant code without doing an entire implementation via the FFI.

So, can you think of any way this can be misused? Is there a better way to accomplish this? Is this something worth accomplishing? What are your thoughts?

  • Awesome!
  • Yuck!
  • I don’t care

0 voters

2 Likes
#2

As a connoisseur and purveyor of terrible ideas, I voted for “yuck”, but I don’t think it’s necessarily harmful. It’s yucky because it’s a hack, albeit a neat one. I personally love publishing hack libraries. Hacks come about because of necessity. In this case, we have a large ecosystem for Foldable, but sometimes you need to short-circuit, and this lets you utilize the existing ecosystem with a new capability. I wouldn’t recommend someone use this unless they were really desperate, kind of like purescript-call-by-name. Foldable is something that works well in Haskell, but has significant deficiencies in a strict language, so maybe we can use this as a point of discussion in improving the situation.

2 Likes
#3

This is one of the typical examples used to motivate delimited continuations/effect systems. There’s a cool tutorial on the upcoming system for OCaml here: https://github.com/ocamllabs/ocaml-effects-tutorial

The Generators from Iterators chapter basically matches what you’re trying to do here. (It’s possible you can implement this with JS generators, but I haven’t tried).

Not that that’s a solution we can “just” adopt in PureScript since we don’t have a runtime where we could implement delimited continuations, but I thought it might still be interesting to you.

1 Like