Constrained context functors

[bielr]

I was trying to write an effect like this

data ReplicateM m k = forall a. ReplicateM (m a) (NonEmpty a -> m k)

instance HFunctor ReplicateM where
    hmap f (ReplicateM m k) = ReplicateM (f m) (f . k)

instance Effect ReplicateM where
    handle state handler (ReplicateM m k) = 
        ReplicateM (handler (m <$ state)) (handler . fmap k . sequenceA)

The real scenario is a Distributed effect with a more complicated API where there is an interpreter-defined number of workers and a job m is computed in parallel (or sequentially). I believe that there is no escape in requiring f in the Effect instance to be an Applicative (actually, just Apply from semigroupoids because I require at least one execution with NonEmpty).

Do you think it is possible to define some hierarchy of Effect instances for different constraints on f? In my opinion the Apply case is quite reasonable, as it would allow weaving the state of Either e or Reader r but not State s (unless s is a Semigroup!). The downside is that I can't see an easy (and flexible) fix for this:

• Hardcoding a hierarchy would limit use cases (i.e. how granular should the hierarchy be?), but should be easy to implement: just add one or two superclasses to Effect.
• Allowing arbitrary constraints (parameterizing the Effect class by f?) would change the API and all Carrier instances. However, this would allow interesting use cases, like serializing the monadic context or any other black magic the user may come up with (I haven't toyed with other classes to be honest).

What do you think? Is it worth it?

[bielr]

I did a prototype of the second idea (class Effect f sig) in my fork (bielr/fused-effects@65adf6f) if you are interested.

After that, I guess I could rename it to class Weaves f sig (name taken from polysemy) and then use -XQuantifiedConstraints to recover the current definition plus more:

• Effect sig ~ forall f. Functor f => Weaves f sig
• Effects1 sig ~ forall f. Apply f => Weaves f sig
• Effects sig ~ forall f. Applicative f => Weaves f sig
• ...

[robrix]

This is something we’ve definitely talked about a bit, e.g. #194 discusses Traversable. We’ve also run into it in other contexts that I couldn’t find issues for, e.g. we’d need Applicative (IIRC) to implement an All effect collecting the results of nondeterministic branches:

data All m k = forall a . All (m a) ([a] -> k)

In fact, we (long ago) weakened the superclass constraint on Carrier from Effect to HFunctor specifically to accommodate effects using scoped actions producing fixed types, e.g.:

data Boolean value (m :: * -> *) k
  = Boolean Bool (value -> m k)
  | AsBool value (Bool -> m k)

So in a sense, this hierarchy already exists, it’s just currently limited to HFunctor > Effect.

I do think it’s worth exploring this space more, with a couple of caveats:

1. I’d like to avoid dropping support for 8.2 and 8.4 until we absolutely have to (cf ghc backwards-compatibility #185), which means -XQuantifiedConstraints.

2. I’m also extremely reluctant to use CPP, altho I am willing to re-evaluate that position if we’ve got a particularly compelling reason to go for it.

3. I’d prefer not to pull in a dependency on semigroupoids if at all possible; keeping fused-effects’ dependencies minimal has been pretty valuable thus far.

Parameterizing Effect by f is definitely interesting! Maybe this is something we should explore more in diffused-effects to get a feel for it in practice. Alternatively, a PR against fused-effects would be welcome, tho I’ll say right now that I’m very unlikely to want to ship this in 1.0 since that milestone has grown quite large. Either way, I definitely think it’s worth exploring to see if we can address some of the challenges 👍

[bielr]

I've been thinking a bit more about Effect f sig. First, some notes:

• The Effect f sig approach seems to have the best gains for the tradeoff
• HFunctor could be aliased to Effect Identity, one less class to implement! Nevermind. Works in theory, too ugly in practice
• If you want to tighten the superclass constraint of Carrier to HFunctor + Effect of the state of the carrier, then there needs to be a type family or functional dependency for it
• Otherwise delegating Carriers can be a bit ugly because you need to manually specify the required Effect instance for the inner monad in the new instance context (this is why I had to export BinaryTree in my fork)

I completely agree with your points. I don't think the semigroupoids dependency is worth it, I was simply mentioning Apply because it's being particularly useful for my project.

I have limited free time, but I am willing to help if I can, either by opening a PR based on my prototype or by submitting it to diffused-effects if you want. I'm also a bit worried that if this doesn't make it to 1.0 then it will be hard to include afterwards because it's an extensive breaking change (although updates are quite mechanical).

[robrix]

Effect is gone as of #361, but I’m still noodling with approaches to constrain the context functor.

[bielr]

As a side note, I had some free time today to play with this on the relatively new Effect-less Algebra class and the update to my previous attempt is at https://github.com/bielr/fused-effects/tree/parameterized-distributive-algebras (my updates have been quick and dirty! no docs changes and I blindly applied many GHC suggested fixes, but all tests run successfully)

Main changes:

• Algebra sig m becomes Algebra ctx m, and sig is moved to an associated type family Sig m (it was too cumbersome otherwise).
• ThreadAlgebra ctx1 ctx2 m is basically an utility alias to Algebra (Compose ...) when a datatype is used in alg to thread the new context using thread. This simplifies many type signatures.
• Algebra1 c m is an alias to (Monad m, forall ctx. c ctx => Algebra ctx m), so that the examples in the README stay clean and with no mentions to StateC and ReaderC (the current Algebra becomes Algebra1 Functor). GHC 8.10 is out there, so according to the N-2 versions policy it is now okay to ask for QuantifiedConstraints, right?
• Algebra can still be derived, but it requires StandaloneDeriving.