Generalised Partition for all Fallible monads

In this release there are now generalised Partition, Succs, and Fails methods (and their equivalent Prelude functions: partition, succs, and fails) that work with any Foldable of Fallible monads.

This is the main Partition extension:

  public static K<M, (Seq<Error> Fails, Seq<A> Succs)> Partition<F, M, A>(
      this K<F, K<M, A>> fma)
      where M : Monad<M>, Fallible<M>
      where F : Foldable<F> =>
      fma.Fold(M.Pure((Fails: Seq.empty<Error>(), Succs: Seq.empty<A>())),
               ma => ms => ms.Bind(
                         s => ma.Bind(a => M.Pure((s.Fails, s.Succs.Add(a))))
                                .Catch(e => M.Pure((s.Fails.Add(e), s.Succs)))));

So, if your F is a Iterable and your M is an IO (so Iterable<IO<A>>), then you can run Partition on that to get a IO<(Seq<Error> Fails, Seq<A> Succs)>. Obviously this will work with any Foldable types you have made too (as well as all the built-in ones: Arr, Lst, Iterable, Seq, Set, HashSet, etc.) -- with any effect type as long as its Fallible and a Monad. Including Fallible types with a bespoke E error value (but you will have to specify the generics as it can't infer from the arguments alone).

For those who know the extensions Partition, Some, Rights, etc. from v4, this generalises the idea completely.

I have also added a Partition extension and partition prelude function that works with any Foldable structure. Unlike the Partition function that works with Fallible types (which partitions on success or failure), this one takes a predicate which is used to partition based on the true / false return. It's like Filter but instead of throwing away the false values, it keeps them and returns a True sequence and False sequence:

public static (Seq<A> True, Seq<A> False) Partition<T, A>(this K<T, A> ta, Func<A, bool> f)
    where T : Foldable<T> =>
    T.Partition(f, ta);

All foldables get a default implementation, but it's possible to override in the trait-implementation (for performance reasons mostly).

Finally, I've added unit-tests for the Foldable default-implementations. Anybody who's been following along will know that the Foldable trait only has two methods that need implementing and over 50 default implementations that we get for free. So, the unit test makes sure they work! (which should guarantee they work for all foldables as long as the two required method-implementations are correct).

I'm considering how I can refactor those unit-tests into a FoldableLaw type that will work like MonadLaw, FunctorLaw, etc. But that's not there yet.

IO monad applicative error collecting

I have added support for the IO<A> monad to collect multiple errors during an applicative Apply call. That also means anything that lifts the IO monad (i.e. transformer stacks or the Eff monad) also get this behaviour. So, you get Validation-like error collection.

Also, bug/missing-feature fixes:

• #1403
• #1398

Choice and Alternative traits refactor

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.

Pipes factored out + EnvIO.FromToken + Applicative Zip

The Pipes functionality that is based on the Haskell Pipes library has been factored out to its own library: LanguageExt.Pipes. This is so I can add more functionality to it (based on the supplementary libraries in the Haskell ecosystem). It also creates a clear demarcation: stating that it's not an 'essential'. I think this makes sense because Pipes is quite advanced and currently not the easiest thing to use for those new to FP in C#.

I have also added EnvIO.FromToken, which allows you to construct an EnvIO that subscribes to the token provided. This is useful if you need to use IO within an existing async workflow, rather than at the edge. -- as I was writing this, I realised there was a better way using the existing EnvIO.New, so this has gone already!

The various bespoke zip functions and extensions have now been generalised to work with any applicative. So zips all round!

`Sys.IO` improvements / Triaged issues + fixes release

Sys.IO improvement

The Sys.IO functions were generalised to support any monad that has the correct Has traits. However, this added a burden to any users of Eff and Aff from v4 of language-ext.

For example, this in v4:

    Console<RT>.writeLine(text)

Would become this in v5:

    Console<Eff<RT>, RT>.writeLine(text)

That works well when you're write entirely generalised IO code, like you see in the Newsletter sample project.

Writing this:

    Console<M, RT>.writeLine(text)

Is clearly not much worse than before. And adds lots of possibilities for writing your IO functions once and have them work with all IO based monads. But, this Console<Eff<RT>, RT>.writeLine(text) is quite ugly to look at in my humble opinion. There's too much clutter and it shows up on every line of IO you write, which doesn't feel good.

So, as Eff<RT, A> is an important type for doing dependecy-injection based IO, I have added Eff specific versions for every static class in the Sys library.

So, for example, as well as Console<M, RT>, there is also a Console<RT> which only works with the Eff<RT, A> monad. This allows existing code that uses Eff<RT, A> to work without a change.

I'm not a huge fan of doubling up the work like this, but I think this is a pragmatic solution that works without much drama.

Fixes and Updates:

• Unit made into a Monoid
• Option<A> made into a Monoid
• The ToEnumerable extension for Foldable has been renamed to ToIterable (it was missed on the previous refactor)
• StreamT internals made lazy
  • Allows the removal of bespoke types that deal only with IEnumerable and IAsyncEnumerable
• HeadUnsafe removed from StreamT
  • HeadOrFail extension to StreamT added. Only works with Fallible monads.
• Fix for FileIO move missing? #1174
• Removed MemoryFS, replaced with use of /tmp as a virtual file-system. Fixes:
  • #1297
  • #1298

Additions, but not ready for primetime

• Source<A> - a source of events that can be subscribed to. Subscriptions yield a StreamT
  • There's an outstanding bug that needs resolving
  • You can see how it will work in the Streams sample

RWST monad transformer

The new RWST<R, W, S, M, A> monad-transformer is now fully-featured and ready for real-world use.

For the uninitiated, the RWST monad-transformer combines all of the effects of the Reader, Writer, State, and M monads into a single monad. You could imagine a type like this:

    ReaderT<R, WriterT<W, StateT<S, M>>, A> 

Which stacks three monad-transformers and the monad M into one type. The problem with that is too much transformer stacking leads to lots of nested lambdas. The RWST monad-transformer smushes the Reader/Writer/State into a single layer making it more performant.

You can use Unit for any of the type parameters if you only need two of the three capabilities. For example, if you only need reader and state effects:

    RWST<R, Unit, S, M, A>

Or, reader and writer effects, but not state:

    RWST<R, W, Unit, M, A>

etc.

There's next to no overhead for doing so.

It's also worth noting that RWST is a very common mega-monad for constructing domain-specific monads for applications. And so, even though it's generics heavy, you would normally wrap it up in a type that reduces the generics overhead.

Let's say we wanted to create an App monad-transformer. Something that carries app-config, app-state, but can also lift other monads into it.

First, create some records to hold the config and the state:

public record AppConfig(int X, int Y);

public record AppState(int Value)
{
    public AppState SetValue(int value) =>
        this with { Value = value };
}

Then create your App monad-transformer type. It is simply a record that contains a RWST monad-transformer:

public readonly record struct App<M, A>(RWST<AppConfig, Unit, AppState, M, A> runApp) : K<App<M>, A>
    where M : Monad<M>, SemigroupK<M>
{
    // Your application monad implementation
}

Then add some extensions to convert from the K type to the concrete type and to Run the App monad-transformer:

public static class App
{
    public static App<M, A> As<M, A>(this K<App<M>, A> ma)
        where M : Monad<M>, SemigroupK<M> =>
        (App<M, A>)ma;
    
    public static K<M, (A Value, AppState State)> Run<M, A>(this K<App<M>, A> ma, AppConfig config, AppState state)
        where M : Monad<M>, SemigroupK<M> =>
        ma.As().runApp.Run(config, state).Map(
            ma => ma switch
                  {
                      var (value, _, newState) => (value, newState)
                  });
}

This also drops the Unit output from the RWST.

Then implement the traits for App<M>. It should be a MonadT because it's a monad-transformer; a Readable because it's got an AppConfig we can read with ask; and Stateful because it's got an AppState that we get, gets, modify, and put:

public class App<M> : 
    MonadT<App<M>, M>,
    Readable<App<M>, AppConfig>,
    Stateful<App<M>, AppState>
    where M : Monad<M>, SemigroupK<M>
{
    public static K<App<M>, B> Bind<A, B>(K<App<M>, A> ma, Func<A, K<App<M>, B>> f) =>
        new App<M, B>(ma.As().runApp.Bind(x => f(x).As().runApp));

    public static K<App<M>, B> Map<A, B>(Func<A, B> f, K<App<M>, A> ma) => 
        new App<M, B>(ma.As().runApp.Map(f));

    public static K<App<M>, A> Pure<A>(A value) => 
        new App<M, A>(RWST<AppConfig, Unit, AppState, M, A>.Pure(value));

    public static K<App<M>, B> Apply<A, B>(K<App<M>, Func<A, B>> mf, K<App<M>, A> ma) => 
        new App<M, B>(mf.As().runApp.Apply(ma.As().runApp));

    public static K<App<M>, A> Lift<A>(K<M, A> ma) => 
        new App<M, A>(RWST<AppConfig, Unit, AppState, M, A>.Lift(ma));

    public static K<App<M>, A> Asks<A>(Func<AppConfig, A> f) => 
        new App<M, A>(RWST<AppConfig, Unit, AppState, M, A>.Asks(f));

    public static K<App<M>, A> Local<A>(Func<AppConfig, AppConfig> f, K<App<M>, A> ma) => 
        new App<M, A>(ma.As().runApp.Local(f));

    public static K<App<M>, Unit> Put(AppState value) => 
        new App<M, Unit>(RWST<AppConfig, Unit, AppState, M, Unit>.Put(value));

    public static K<App<M>, Unit> Modify(Func<AppState, AppState> modify) => 
        new App<M, Unit>(RWST<AppConfig, Unit, AppState, M, Unit>.Modify(modify));

    public static K<App<M>, A> Gets<A>(Func<AppState, A> f) => 
        new App<M, A>(RWST<AppConfig, Unit, AppState, M, A>.Gets(f));
}

Every member is simply a wrapper that calls the underlying RWST monad-transformer (which does all the hard work).

Then we can use our new App monad-transformer:

var app = from config in Readable.ask<App<IO>, AppConfig>()
          from value  in App<IO>.Pure(config.X * config.Y)
          from _1     in Stateful.modify<App<IO>, AppState>(s => s.SetValue(value)) 
          from _2     in writeLine(value) 
          select unit;

This leverages the Readable trait to get at the AppConfig, the leverages the Stateful trait to modify the AppState, and finally does some IO (the lifted M monad), by calling writeLine.

That's great and everything, but we want to make the underlying type disappear completely. So, if we then wrap up the Readable.ask and Stateful.modify in App specific functions:

public static App<M, AppConfig> config<M>() 
    where M : Monad<M>, SemigroupK<M> =>
    Readable.ask<App<M>, AppConfig>().As();

public static App<M, Unit> modify<M>(Func<AppState, AppState> f) 
    where M : Monad<M>, SemigroupK<M> =>
    Stateful.modify<App<M>, AppState>(f).As();

Then we can make the resulting code completely App-centric:

var app = from config in App.config<IO>()
          from value  in App<IO>.Pure(config.X * config.Y)
          from _1     in App.modify<IO>(s => s.SetValue(value)) 
          from _2     in writeLine(value) 
          select unit;

So, by simply wrapping up the RWST monad-transformer you can gain a ton of functionality without worrying how to propagate state, log changes (if you use the Writer part of RWST), or manage configuration. Very cool.

Just for completeness, this is what writeLine looks like:

static IO<Unit> writeLine(object value) =>
    IO.lift(() => Console.WriteLine(value));

I'll cover this topic in more detail in the next article of my Higher Kinds series on my blog.

Law testing + Traits update + RWST

Laws testing

Functors, applicatives, and monads all have laws that make them what they are. Some think that Map just means the same as Map in mathematics, when in fact functors are more constrained and are structure-preserving.

The full set of laws are:

Functors

• Identity law
• Composition law
• Structure preservation law

Applicatives

• Identity law
• Composition law
• Homomorphism law
• Interchange law
• Applicative-functor law

Monads

• Left-identity law
• Right-identity law
• Associativity law

When you write your own functors/applicatives/monads you are expected to honour these laws. In reality it's pretty hard to go wrong if you just follow the type-signatures and implement the traits in the most obvious way, but still, it is possible to make a mistake and some of the guarantees of the traits start to fail.

assert

The type-system isn't able to enforce many of the laws above, so we need to do it ourselves. I have now made that process much easier. If you implement a monadic type (using the new traits system) then can simply call:

MonadLaw<M>.assert();

Where M is your monad trait implementation type.

For example, this tests that Option complies with all of the laws listed above.

MonadLaw<Option>.assert();

If your type isn't a monad, but is an applicative, then you can call:

ApplicativeLaw<M>.assert();

And if your type isn't an applicative, but is a functor, then you can call:

var mx = M.Pure(123);
FunctorLaw<M>.assert(mx);

Functors don't know how to instantiate new functors (unlike applicatives and monads), so you must provide an instance to the assert function.

Note that, if your type is a monad and you call MonadLaw<M>.assert, you do not need to call ApplicativeLaw<M>.assert or FunctorLaw<M>.assert. Those will be tested automatically.

validate

The assert functions listed above are perfect for unit-tests, but you can call validate instead. It will return a Validation<Error, Unit> which will collect a set of failures for any failing laws.

var result = MonadLaw<Option>.validate();

Equality

The functions that test that the laws hold need to be able to test equality of functor/monad/applicative values. Unfortunately, not all functors/applicatives/monads support equality. Types like Reader, for example, are computations (not values), and so must be evaluated to extract a concrete value. The generic traits don't know how to evaluate them to extract the values.

And so, for types that have no valid Equals implementation, you must provide an equality function to assert and validate.

Here's an example for Eff<int>:

  bool eq(K<Eff, int> vx, K<Eff, int> vy) => 
      vx.Run().Equals(vy.Run());
  
  MonadLaw<Eff>.assert(eq);

It's pretty simple, it just runs the effect and compares the result.

Examples

You can look at the unit-tests for all of the functor/applicative/monad types in language-ext:

• Functors
• Applicatives
• Monads

Future

• More laws tested for more traits!
• Potentially add these assertions to a Roslyn analyzer (if anyone wants to try, please do!)

Removal of Alternative and SemiAlternative

I have removed Alternative and SemiAlternative traits. I really disliked the name SemiAlternative (which was a combination of SemigroupK and Applicative. I was OK with Alternative (MonoidK and Applicative) but it doesn't make sense without its semigroup partner. So, for now, we will only have SemigroupK and MonoidK (semigroup and monoid that work for K<F, A> rather than A).

I'm still refining the types and am not 100% happy with this, but am short of ideas for better names or approaches. Feel free to let me know what you think.

Pure to pure

The computation types: Reader, ReaderT, State, StateT, Writer, and WriterT have all had their module Pure function renamed to pure -- as it's not strictly a constructor, it simply lifts a pure value into those computations.

RWST

Reader/Write/State monad-transformer. This is still WIP but it should be usable. It just doesn't have all the bells and whistles yet.

Map and Apply standardisation

Now that language-ext has Functor and Applicative traits, there are a number of extension methods[1][2] and module functions[3][4] that work with those traits.

Those all return the abstract K<F, A> type rather than the more specialised types that derive from K<F, A>. So, to get over that, I had previously added bespoke extensions for types like Either, Option, etc. that would call the generic behaviours and then cast back to the specialised type.

Unfortunately, over the years there's been an inconsistent application of these extension methods to the various functor/applicative types. So, I have now made all functors/applicatives support the exact same set of Map, Apply, Action extensions as well as the exact same set of map, apply, action functions in the Prelude.

That means for some types you may have lost some extensions/functions and for some they have gained. But, they are now all consistent, so going forward at least there's no second guessing.

One big change is that the multiple operand Apply has gone, so you can't do this now:

var mf = Some((int x, int y) => x + y);
var mx = Some(100);
var my = Some(100);

var mr = mf.Apply(mx, my);

You must fluently chain calls to Apply (which is just what it did behind the scenes anyway):

var mr = mf.Apply(mx).Apply(my);

The variants of Map and Apply that took multi-argument Func delegates as their first argument are now all only available as generic extensions and only accept a single operand, e.g:

 public static K<AF, Func<B,Func<C, D>>> Apply<AF, A, B, C, D>(
    this K<AF, Func<A, B, C, D>> mf, 
    K<AF, A> ma)
    where AF : Applicative<AF> =>
    AF.Apply(AF.Map(curry, mf), ma);

public static K<AF, Func<B,Func<C, Func<D, E>>>> Apply<AF, A, B, C, D, E>(
    this K<AF, Func<A, B, C, D, E>> mf, 
    K<AF, A> ma)
    where AF : Applicative<AF> =>
    AF.Apply(AF.Map(curry, mf), ma);

// ... etc.  up to 10 parameter Func delegates

Note, how the multi-parameter Func delegates turn into single parameter curried Func results.

What that means is each bespoke extension method (say, for Option, like below) just needs to handle Func<A, B> and not all variants of n-argument function. All chained Apply calls will eventually bake down to a concrete type being returned, removing the need to call .As() afterwards.

public static Option<B> Apply<A, B>(this Option<Func<A, B>> mf, K<Option, A> ma) =>
    Applicative.apply(mf, ma).As();

public static Option<B> Apply<A, B>(this K<Option, Func<A, B>> mf, K<Option, A> ma) =>
    Applicative.apply(mf, ma).As();

The Prelude now has map, apply, and action functions for all applicatives. I think it's worth pointing out that map is particularly useful in making the use of applicatives a bit easier. Previously, if you needed to lift up an anonymous lambda, you'd need to call fun(x => ...) to make the delegate available:

var mr = fun((int x, int y) => x + y)
             .Map(mx)
             .Apply(my);

Now, with the map overrides, you can avoid the initial lifting of the function and perform the lift and map all in one:

var mr = map((int x, int y) => x + y, mx)
             .Apply(my);

Of course, the tuple-based approach is also available for all applicatives:

var mr = (mx, my).Apply((x, y) => x + y);

This however returns the generic K<F, A> and needs .As() to make it concrete.

Error and catching updates

Based on this discussion the Error type has had a few changes:

• The bespoke Equals operators have been removed. Meaning that all Error types use the built-in record structural equality.
• Is<E>() where E : Exception, the test for an exceptional error contained within the Error, has been renamed to HasException<E>().
• IsType<E>() where E : Error has been added to test if this contains an E. It's like this is E, but because this might contain many-errors, it checks for the existence of any Error of type E.

The Catch extensions and the @catch combinators have been updated:

• To fix some obvious bugs!
• To flip the operands when matching, so the predicate argument is on the left-hand-side where appropriate.
• Added support for error-codes in Catch (previously missing)

Previous releases:

I did some minor releases that didn't get release notes, so here's a quick summary:

• notFollowedBy in Parsec reports the correct position
• Explicit (useAsync) and implicit (via use) support for IAsyncDisposable resources
• SomeRun overrides for Eff weren't disposing of the EnvIO properly
• Fin.Apply matching fix
• LiftM support for StreamT:
  • Previously we could Lift(IAsyncEnumerable<A>) or Lift(IEnumerable<A>) to return a StreamT<M, A>
  • Now we can LiftM(IAsyncEnumerable<K<M, A>>) and LiftM(IEnumerable<K<M, A>>) to also return a StreamT<M, A>

IO eagerness fix

The recent IO refactor allowed for eager evaluation of pure lifted values, this causes stack-overflows and other side-issues with StreamT and other infinite recursion techniques. This minor release fixes that.