ekmett/free

Alternative formulation of Free Applicative

Opened this issue · 3 comments

safareli commented

I have seen Control.Applicative.Free.Fast but it has stack issue in strict environments and I guess it would have same issue in Haskell in too, so i'm opening this issue to share my work on this topic.

Also encoding using functions is a bit too tricky and hard to understand. on the other hand implementation i'm proposing has simpler structure and same performance characteristics but is stacksafe but fold is tricky:

data Free f a where
  Pure :: a -> Free f a
  Lift :: f a -> Free f a
  Ap :: Par f (a -> b) -> Free f a -> Free f b

This is the text i have written some time ago:

Recently I have Implemented FreeApplicative (Par in safareli/free#31) which has O(1) complexity on map/ap and O(n) on fold. Also fold is stacksafe, which was not possible with other optimised implementations out there, as they use functions to build up a structure which requires extra stack on fold, leading to stack overflow. here the Free Applicative structure itself is not using any function, and the fold is written so, that function's stack is not used. I think same technique could be applied to other "lazyish" structures to fix stack issue without need for TCO support in environment.

Related issues:

ElvishJerricco commented

Am I correct that this is law breaking? It certainly looks that way.

Can you show an example that isn't "stacksafe" in the existing Haskell implementations, considering Haskell does have TCO support? I think a Cayley representation may be far more straightforward, and it's unclear whether it would have that problem.

safareli commented

Not sure, in Scala and JS we don't have TCO, so Cayley representation does not work here.

I don't know if that's an issue in Haskell (I have not written Haskell at all), just opened this issue so that, in case it's a problem, then it could be ported here too.

safareli commented

Just in case here is implementation of a FreeApplicative in Purescript which is stacksafe with O(1) complexity on map/ap and O(n) on fold ethul/purescript-freeap#13