Alternative formulation of Free Applicative

[safareli]

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:

• scalaz consider another implementation of FreeAp scalaz/scalaz#1301
• cats Make FreeApplicative stack safe typelevel/cats#1151 (WIP PR)
• purescript Initial sketch of a free applicative implementation ethul/purescript-freeap#9

[ElvishJerricco]

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]

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]

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