Discussion: effect stack-aware composition methods

[anatoliykmetyuk]

Transformer Effect Types composition methods family

flatMap, map, semiflatMap, subflatMap, right etc etc. Their names are clearly a cartesian product. For EitherT: (left, bi, <empty>) x ((semi, sub) x flat), traverse, <empty>) x (map, empty). However, this fact is not abstracted in any way. The lack of abstraction leaves "holes" in the namespace (as per Cats 1.5.0):

• No leftSubflatMap, though there is leftSemiflatMap.
• No biSubflatMap, though there is biSemiflatMap.
• No leftTraverse, though there is biTraverse.

Effect Type Stack Abstraction

Consider a stack of effect types: FT[GT[HT[...[S, ?], ?], ?], A] (later – FT :: GT :: HT :: ... :: S for convenience; and XT[A] means XT[..., A], where ... is the "tail" – the effects following XT in the stack). Assume XT are of the kind (* -> *) -> * -> *, X – of the kind, * -> *, A, B, C are * and ... indicates stack going deeply in a similar fashion.

What if we want to do e.g. A => HT[B] or A => GT[B] or A => S[B] or H[A] => GT[B]? Currently, we can't do so because the transformer effect types are not aware of the other possible nested effect types. We do not have an abstraction for a stack of effect types.

Currently, we only have type classes for F[_] types, and not the transformer effect types (* -> * vs (* -> *) -> * -> *). All of the semi- and sub- methods come from the transformer effect types themselves (EitherT, OptionT). It would be nice to have these methods separated in their own type class.

However, if such a type class is to be defined, it will need the type-level information about the entire stack of effects involved. E.g. FT :: GT :: HT :: S is a Monad: it has a flatMap that works on a function A => (FT :: GT :: HT :: S)[B]. However, the monad type class treats FT :: GT :: HT :: S as * -> * kind, it is not aware of the structure of the effect type stack. This information along won't give semiflatMap etc.

Ideally, the end user should just provide the type classes for X-kind types and get the XT :: ...-kind methods out of the box (e.g. EitherT :: IO requires Monad[Either], Monad[IO] etc to provide semiflatMap etc).

Questions

• What are conceivable effect stack structures and methods for their composition? What about the different arity and even non-stack structures? What would be a reasonably doable subset to discuss?
• What information about the structures above is needed to derive the methods above?
• What programming language capabilities do we need to make automatic derivation of such methods happen? Can we do it with the current Scala technology (implicits, Shapeless, macros)?