Make schemes stack-safe using Eval

[DavidGregory084]

Makes the schemes in this project stack safe using the awesome idea from this gist by @Baccata.

Things I still need to do:

• Add stack-safety tests for some of the schemes
• Try to unpick the tangled logic of some of the more obscure schemes (e.g. histo)

Questions I still have:

• How much slower is it?!?!! :stuck_out_tongue:
• How much of a problem is it in practice to have the more restrictive Traverse constraint
• Can I rewrite the monadic schemes to use tailRecM?
• What are the laws for prepro and postpro? I have fiddled with the implementations and want to make sure the transformations happen in the right place - I can probably look in one of the other recursion schemes libraries for this
• Is it more efficient to add stack-safety using the approach described here, using a type class which decomposes the data structure rather than relying on Eval to make traverse stack-safe?

[Baccata]

@DavidGregory084, ha, I had completely forgotten about this. After many thoughts, I think I had come to the realisation that the use of Eval there was just a specific use of hyloM, and had elected to use the generic hyloM(which requires a Traverse anyway) combined with whatever stack safe monad was best suited to the code I was writing (which may or may not have been Eval)

How much of a problem is it in practice to have the more restrictive Traverse constraint

Theoretically, I think it becomes a problem if your pattern functor has lazy/by-name components to it. I don't think this is a very common case but a library should tread lightly with this kind of decision.

Can I rewrite the monadic schemes to use tailRecM

I don't think it's possible to achieve generically, as the pattern-functor is the structure that "knows" when recursion stops and when to start producing Bs. Without intricate runtime typechecks, it's likely impossible.

[DavidGregory084]

Yeah, that totally makes sense, I considered removing the non-monadic schemes from the library. I can see how it wouldn't be possible to use tailRecM due to the type class instances handling all of the recursion. I think I might have to go down the rabbit hole of the "Dissectible" type class. 😆