Hybrid free monad / free applicative

[bqm]

Hello,

I am new to the cats project & open source in general - cats is a great project & I learnt a lot from it :)

I've been exploring free monads recently & my understanding is that we can't express parallel operations with them. Free applicatives on the other hand, allow us to express parallelism but we can't express sequential operations.

It seems that it could be interesting to have a data structure that could support both use cases - sequential & parallel operations. For instance, we may want to implement a key value store DSL and be able to write a program like "do these 2 put operations in parallel and if they succeeded, do these 2 get operations in parallel".

I've made a naive implementation of such a structure to show what I mean (naive implementation because I lose a few interesting properties like the tail recursive interpreters for instance) & wrote a simple client code example.

Naive implementation: https://gist.github.com/bqm/bee72c18fa4baa708f7cf2b146bbc872
Simple client code: https://gist.github.com/bqm/e8e28c06311be8d76071729dcaf5b836

What do you think of having an hybrid structure like that in cats?

[adelbertc]

So the interesting thing is that it allows you to control the ap behavior - in Haxl this is leveraged to give you "implicit parallelism" when using Applicative operations like traverse. However it introduces the danger of having inconsistent ap-bind behavior. For instance, accumulating errors (e.g. Validated) vs. fail fast (e.g. Xor). One could argue that having the Applicative being parallel and Monad being sequential is inconsistent, but you could also argue it's not observable or not worth caring about.

I am unsure about this because of the dangers of ap-bind consistency.. but I could also see this being useful.

[ceedubs]

@adelbertc It only introduces danger of having inconsistent ap-bind behavior if the data structure you are interpreting it into already has inconsistent ap-bind behavior. So I'm not sure that's a big concern.

There is the question of whether certain execution semantics (such as ap running computations in parallel while flatMap runs them sequentially) qualify as inconsistencies. Originally I was of the opinion that these do qualify as inconsistencies. However, I'm increasingly open to the idea that this distinction isn't worth worrying about. It is really a hassle to not be able to do parallel computations when using the free monad without some pretty invasive workarounds (such as adding a Parallel item to your algebra or something). In particular, I thought that this comment was pretty convincing.

[ceedubs]

Oh and by the way, thanks for bringing this up @bqm :). This is something that I've thought about and discussed with several people, but I don't think it ever made itself into a GitHub issue.

[adelbertc]

Can this use case be solved by newtype-ing (wrapping in a value class/tagged types) and overriding the ap behavior?

[ceedubs]

@adelbertc I think only if you reify an Ap constructor into Free as done in this example. If you just have GoSub, then you don't have a way of representing things that can run in parallel.

[bqm]

@ceedubs Thanks :)

As @ceedubs mentioned, I believe that we need Ap and the case classes defined by Free in order to materialize parallelism in our new data structure.

What would be the best next steps - should we wait for more opinions before doing a PR?

[adelbertc]

Probably waiting on this as well #990

[ghost]

What would be the best next steps - should we wait for more opinions before doing a PR?

I think we could benefit from a proof-of-concept PR now that #990 is merged, perhaps taking your experiments as a starting point @bqm?

[weihsiu]

just a heads up on this video which, towards the end, combines both Free and FreeApplicative using Coproduct. i couldn't find the source code for the example though.

[bqm]

@weihsiu Thanks for the link, nice keynote! This is an interesting encoding which is I believe is close to Free[FreeApplicative[MyADT, ?], A] (i.e coproduct left case can be seen as a free applicative with only one element).

@dialelo Cool! I will work on a proof of concept PR.

[raulraja]

Found the code and slides for @markus1189 presentation that @weihsiu mentioned above in case anyone was looking for those: https://github.com/markus1189/flatmap-oslo-2016

[safareli]

I think you might need to take a look at haskell-free-concurrent written by @srijs and my improgress port of it to JS safareli/free#31, this allows to mix Free(Seq) and FreeAp(Par) structures in Concurrent structure which could be then interpreted using one monad, one Applicative and isomorphism between this two

[safareli]

Also the Free[CoProduct[F, FreeAp[F[_]]], ?], A] from @markus1189 is basically same as Free[FreeAp[F[_]], A] (SeqPar) From @jdegoes. Difference between the SeqPar and Concurrent is discussed here

P.S. to not i'm not familiar with scala and type signatures might not be correct

[jdegoes]

Free[FreeAp[F, ?], A] is a sequential composition of parallel fragments in F. It requires 2 constructors and levels of wrapping to lift an F[A], 1 constructor and one level of wrapping to lift an FreeAp[F, A], and 1 foldMaping to retool a Free[F, A] to a Free[FreeAp[F, ?], A] (with each F operation wrapped one level in a FreeAp constructor).

Contrast with Free[Coproduct[F, FreeAp[F, ?]], A], which has one additional level of wrapping and one additional level of construction/deconstruction (in some cases) due to Coproduct.

Also relevant is my Post-Free talk at Winter Retreat which will be a fresh treatment on this subject matter (& beyond).

[markus1189]

Yeah indeed Free[Coproduct[F,FreeAp[F[_]], ?], A] is isomorphic to Free[FreeAp[F, ?], A], so you can get rid of the Coproduct 👍

@jdegoes the post-free talk sounds more like a workshop, is there any chance to get a recording or maybe a write-up afterwards? :D

[safareli]

Can't wait to read/watch that :p

[jdegoes]

Hopefully it will be recorded. 😄 If not, I will write up in a blog.

[peterneyens]

For those interested, I tried to translate @jdegoes ' SeqPar gist to Scala using Cats (see gist).

[jdegoes]

@peterneyens Cool! 😄

[ugoenyioha]

https://gist.github.com/ugoenyioha/cb6df372561d70bea6630df699408b27

[edmundnoble]

For those interested, this has been implemented in typelevel Eff for some time now. https://github.com/atnos-org/eff/

[deusaquilus]

Markus's talk is also on youtube: https://www.youtube.com/watch?v=C2hCOGYRxP0