Improve current Free monad implementation

[1Jajen1]

From a slack thread: https://kotlinlang.slack.com/archives/C5UPMM0A0/p1554022508033000
Right now there are several weird things around the Free-monad: (when I refer to Free later on I mean the Free-Monad)

• It requires a monad instance as the target when evaluating (a simple functor and an f-algebra would do)
• There are no good examples around (The ones from haskell are too diffrent and the ones from cats require gadts which are by no means necessary)
• Combining free monads could be better in several ways
  • Coproducts should be made more efficient to make lookups faster
  • Injecting and interpreting from a coproduct can be autogenerated easily to allow use with 0-boilerplate from a user
• There is no FreeT for cases where you'd want an underlying monad (like State or EitherT etc)
• ideas of autoderiving functors (has low priority for me but can definitly be done) (otherwise you can always use Yoneda to get a functor I think)
• Performance: (I don't know how efficient the current format is, definitly better than what the default Free is, but I think it may be worth exploring other encodings for better performance)
  • Church encoding (isomophic to Free and can be used to optimize existing Free's as well) http://hackage.haskell.org/package/free-5.1/docs/Control-Monad-Free-Church.html

Some of these approaches could also directly benefit other parts of arrow, especially auto-deriving stuff (although I think there needs to be a discussion regarding generating code using kapt with reference to multiplatform use before). And also arrow-streams may benefit from it.

Some more in-depth parts:

• Interpreting free with recursion schemes is a good approach to solve the first problem, that only requires an f-algebra, a functor for the adt and a function for the base case Free.Pure. Interpreting to a monad is still easy as an f-algebra doesn't constrain its types.
• Defining an inject function injectL (F) -> CoproductPartialOf<F, G> or injectR (G) -> CoproductPartialOf<F, G> is trivial and going further with nested coproducts also is. We can generate code for something like a FreeMonadContinuation<F, G, ...> that allows calling bind on any Free<F, A> (beforehand for some reasonable depth or maybe in kapt at compile time). Same for interpreters over Coproducts.
• Examples for cats-free usually involve gadts, those are not really usable in kotlin as typesafety goes down the drain. But you can simple model the adt as a functor by passing a as some sort of continuation (the first example I wrote in the slack thread does that) and you instantly get typesafety back all the way. With smart constructors this is also invisible from the user.
• Error handling: We had some discussion about error handling in Free and how it is different from handling errors in arrow (well it can be). I think its only worth focusing on errors that happen within our dsl as errors in the interpreter or the real world don't matter (a normal program would fail here as well). One approach to error handling is to simply explicitly return errors using a concrete type that implements MonadError. That can get you pretty far I think. Another approach if you simply want to short-circuit on error is wrapping Free in EitherT, but that is very limited. Yet another approach is FreeT, now there are other good reasons to use FreeT, but for now I'll focus on errors. With FreeT m simply provide a Monad m that also is a MonadError and delegate error handling to that (at least I think that FreeT is MonadError when m is MonadError
• Performance requires some benchmarks beforehand, otherwise testing wether or not Church encoding is faster is a bit hard. Would love to have some automated benchmarks set up there.

This all really is more of a discussion and task-list, I also think it has little priority for now, but I did not want to loose the opportunity to write this down before the slack thread gets long forgotten :)

I'll probably tackle some of these in the upcoming months, but will explicitly write here when I do, so if anyone is interested in doing part of this feel free to do so!

@i-walker @raulraja I think this covers most of what we were talking about, if not feel free to add stuff here :)

[i-walker]

Ping me If you start working on this @1Jajen1 :)

[raulraja]

excellent thanks, also ping me, interested in the direction this takes

[nomisRev]

@1Jajen1 I'm not sure if you looked at FreeC which is like Free but it also deals with unexpected occurring errors.

@raulraja I am assuming we still want to upgrade this to arrow-free at some point. We discussed once to replace Free with FreeC if this is still the plan than maybe this is the issue where we clean up FreeC and promote it to arrow-free and replace Free.

Thoughts?

[1Jajen1]

I don't really like that tbh. I think that overcomplicates Free and it is not really necessary imo. Baking in error handling in Free looks wrong. Not doing so might also be more performant when thinking about church encoding. Error handling can be done using FreeT or explicitly. Either way FreeC will also directly benefit from a different approach to Free (recursion schemes as foldMap, better coproducts and deriving Functors + docs).

Also can't FreeC be expressed as monad transfomers over Free or other way around by using FreeT? That may be a cleaner approach to free. I'd love to see a direct comparison so I'll do FreeT first and check how that all works out

[nomisRev]

Well, @1Jajen1 FreeC was originally built as a foundation for Stream<F, A>, where this additional power is needed. I'm fine with keeping it internal in arrow-streams but I still think it's valuable to expose for others.

We can also decide to expose both. Having the possibility to move Free to FreeC with the same utilities etc is probably also an advantage.

EDIT: For sure you could express FreeC with FreeT and get MonadError/Concurrent instances but this comes at a perf cost which is not desired for use cases like Stream or similar use cases.

[pamu]

Is anything happening here?