Choice and Alternative traits refactor

[louthy]

Two new traits have been added:

Choice<F>

public interface Choice<F> : Applicative<F>, SemigroupK<F>
    where F : Choice<F>
{
    static abstract K<F, A> Choose<A>(K<F, A> fa, K<F, A> fb);
    
    static K<F, A> SemigroupK<F>.Combine<A>(K<F, A> fa, K<F, A> fb) => 
        F.Choose(fa, fb);
}

Choice<F> allows for propagation of 'failure' and 'choice' (in some appropriate sense, depending on the type).

Choice is a SemigroupK, but has a Choose method, rather than relying on the SemigroupK.Combine method, (which now has a default implementation of invoking Choose). That creates a new semantic meaning for Choose, which is about choice propagation rather than the broader meaning of Combine. It also allows for Choose and Combine to have separate implementations depending on the type.

The way to think about Choose and the inherited SemigroupK.Combine methods is:

• Choose is the failure/choice propagation operator: |
• Combine is the concatenation/combination/addition operator: +

Any type that supports the Choice trait should also implement the | operator, to enable easy choice/failure propagation. If there is a different implementation of Combine (rather than accepting the default), then the type should also implement the + operator.

ChoiceLaw can help you test your implementation:

choose(Pure(a),   Pure(b))  = Pure(a)
choose(Fail,      Pure(b))  = Pure(b)
choose(Pure(a),   Fail)     = Pure(a)
choose(Fail [1],  Fail [2]) = Fail [2]

It also tests the Applicative and Functor laws.

Types that implement the Choice trait:

• Arr<A>
• HashSet<A>
• Iterable<A>
• Lst<A>
• Seq<A>
• Either<L, R>
• EitherT<L, M, R>
• Eff<A>
• Eff<RT, A>
• IO<A>
• Fin<A>
• FinT<M, A>
• Option<A>
• OptionT<M, A>
• Try<A>
• TryT<M, A>
• Validation<F, A>
• Validation<F, M, A>
• Identity<A>
• IdentityT<M, A>
• Reader<E, A>
• ReaderT<E, M, A>
• RWST<R, W, S, M, A>
• State<S, A>
• StateT<S, M, A>
• Writer<A>
• WriterT<M, A>

NOTE: Some of those types don't have a natural failure value. For the monad-transformers (like ReaderT, WriterT, ...) they add a Choice constraint on the M monad that is lifted into the transformer. That allows for the Choice and Combine behaviour to flow down the transformer until it finds a monad that has a way of handling the request.

For example:

var mx = ReaderT<Unit, Seq, int>.Lift(Seq(1, 2, 3, 4, 5));
var my = ReaderT<Unit, Seq, int>.Lift(Seq(6, 7, 8, 9, 10));
var mr = mx + my;

ReaderT can't handle the + (Combine) request, so it gets passed down the transformer stack, where the Seq handles it. Resulting in:

ReaderT(Seq(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))

Similarly for |:

var mx = ReaderT<Unit, Option, int>.Lift(Option<int>.None);
var my = ReaderT<Unit, Option, int>.Lift(Option<int>.Some(100));
var mr = mx | my;

The Option knows how to handle | (Choose) and propagates the failure until it gets a Some value, resulting in:

ReaderT(Some(100))

This is quite elegant I think, but it requires all monads in a stack to implement Choice. So, a good sensible default (for regular monads without a failure state), is to simply return the first argument (because it always succeeds). That allows all monads to be used in a transformer stack. This isn't ideal, but it's pragmatic and opens up a powerful set of features.

Alternative<F>

Alternative is a Choice with an additional MonoidK. That augments Choice with Empty and allows for a default empty state.

AlternativeLaw can help you test your implementation:

choose(Pure(a), Pure(b)) = Pure(a)
choose(Empty  , Pure(b)) = Pure(b)
choose(Pure(a), Empty  ) = Pure(a)
choose(Empty  , Empty  ) = Empty

It also tests the Applicative and Functor laws.

Types that implement the Alternative trait:

• Arr<A>
• HashSet<A>
• Iterable<A>
• Lst<A>
• Seq<A>
• Eff<A>
• Eff<RT, A>
• IO<A>
• Fin<A>
• FinT<M, A>
• Option<A>
• OptionT<M, A>
• Try<A>
• TryT<M, A>
• Validation<F, A>
• Validation<F, M, A>

Thanks to @hermanda19 for advocating for the return of the Alternative trait, I think I'd gotten a little too close to the code-base and couldn't see the wood for the trees when I removed it a few weeks back. The suggestion to make the trait have a semantically different method name (Choose) re-awoke my brain I think! :D

Any thoughts or comments, please let me know below.

---

This discussion was created from the release Choice and Alternative traits refactor.