Hybrid free monad / free applicative

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?

Start by reviewing the naive implementation and simple client example linked in the issue, then compare their sequential and parallel use cases with existing Cats abstractions. A complete outcome would require a resolved design for a hybrid structure and agreement that its trade-offs, including the noted interpreter limitations, are acceptable for Cats.