Seq<A> refactor

I have refactored the Seq<A> to have similar performance characteristics to the .NET List<T> type (under most circumstances).

It works in almost the same way as List<T> internally: which is that it is an array which doubles in size when it needs more space. This has a number of benefits for Seq<A>:

• The items in the sequence are contiguous in memory. This has massive performance benefits when iterating the sequence, because it gives the cache on the CPU a chance to page in as much of the sequence as it can.
• There is now an Add and Concat which has very similar performance characteristics as Cons. And so the sequence can grow in either direction without incuring a performance cost. This is particularly useful if you're using the mconcat or mappend with the MSeq monoid.
• When not doubling in size the Cons and Add operations are almost as fast as setting an item in an array.
• Seq<A> now gains an index accessor for O(1) access to items in the non-lazy sequence. A lazy sequence is O(n) where n are the number of items that need to be streamed to get to the index. Obviously after that the sequence becomes non-lazy.

Other Seq<A> features

Seq<A> now has a deconstructor that can extract the head item and the tail:

    var (head, tail) = seq;

Note, this will throw for empty sequences.

Lazy sequences can be forced to load all of their items with:

seq = seq.Strict();

What are the problems?

• Complexity

The Seq type is internally a lot more complex now, even if the surface API is the same. That's why I'm releasing this as a beta. @StefanBertels @michael-wolfenden @bender2k14 @faeriedust @colethecoder @StanJav @OlduwanSteve - you guys tend to be very good at spotting issues, so an extra set of eyes on this would be good.

Unit tests-wise I think we're pretty good, as my initial tests showed that half of the unit tests failed from the initial bugs (because Seq is used so much). Those same tests going reassuringly green gave a reasonable amount of confidence in the approach. But if anyone wants to add more, that would be always appreciated.

Tradeoffs

As with any immutable data structure, there are some trade-offs when it comes to creating mutated versions.

With the new Seq<A> the tradeoff comes when calling multiple Cons or Add operations from the same Seq<A>. Because internally the structure is an array, it is only one dimensional. It can only grow left (Cons) or grow right (Add). The vast majority of add and cons operations will be working in that single dimension, and so doing an add or cons will have similar performance characteristics to setting an element in an array.

But when multiple cons or adds are done from the same Seq<A> you add additional dimensions to the sequence.

    A -> A -> A -> A ->  A -> 
                     \
                      -> A ->  A -> ...

There are then multiple dimensions that want to expand into the same single dimensional array. So, in these circumstances the routing node gets a flag set after the first Cons, which any subsequent Cons will see and, instead of just expanding into the array, will clone the whole Seq.
If this happens relatively infrequently, or your sequence is small, then it's not a big deal. But if you have a million item list, that you keep just consing a single item onto then you're going to be doing a lot of array copying.

So, just to be clear, this is fine:

   var xs = Seq(Range(1, 10000000));
   var nxs = 1.Cons(2.Cons(3.Cons(xs)));

This has the biggest cost:

   var xs = Seq(Range(1, 10000000));

   var nxs1 = 1.Cons(xs);  // This is free
   var nxs2 = 2.Cons(xs);  // This is expensive
   var nxs3 = 3.Cons(xs);  // This is expensive
   var nwb = 4.Cons(nxs3); // This is free

Thankfully I don't think this is a very likely or common use-case for Seq and the most common use-cases are now going to be significantly more efficient. Note: Once a Seq has branched into multiple dimensions the individual dimensions are free to grow as though they were singly dimensional, and so it's only the branch which causes copying.

Record type attributes

The attributes for opting out of various Record features have been bothering me. They're pretty ugly naming-wise, so I have deprecated the old ones and added a few more:

Old attribute	New attribute
OptOutOfEq	[NonEq]
OptOutOfOrd	[NonOrd]
OptOutOfToString	[NonShow]
OptOutOfHashCode	[NonHash]
OptOutOfSerialization	[NonSerializable]

One thing that was bugging me was that if I wanted a field or property to be completely ignored by the Record system then I'd have to use:

[OptOutOfEq, OptOutOfHashCode, OptOutOfOrd, OptOutOfSerialization, OptOutOfToString]

Which is crazy. And so now you can just use:

[NonRecord]

It makes the field or property invisible to the Record system.

You can also use:

[NonStructural]

Which is the equivalent of [NonEq, NonOrd, NonHash] to remove the field or property from structural equality and ordering.

Conclusion

I welcome feedback on these changes. This is a beta release because it's feature complete, but risky. And so I will be taking soundings for a few weeks.

Minor breaking change to:

Func<A> memo<A>(Func<A> f);

This previously used Lazy<T> internally to lazily load the value and support at most once evaluation. But because Lazy<T> memoises exceptions, which I believe is undesirable, I have decided to change this to a bespoke implementation that doesn't memoise exceptions.

The Task<A> extension methods have been moved from the global namespace into the LanguageExt namespace, so please make sure you're using LanguageExt with the latest release.

Some additional helper functions in Try, TryOption, TryAsync, TryOptionAsyncto help convert toEitherandValidation. You can now provide your own mapping function to map between Exception` and whatever error type you want. i.e.

    var ma = tryValue.ToEither(ex => Error.New(ex.Message));

It's still usually best to provide bespoke extensions to do this mapping, but this should make the job a bit simpler.

There is also an additional BindLeft function on Either, EitherUnsafe, and EitherAsync types.

I have decided to relent and break the Rx related functionality out of the LanguageExt.Core project. I did so for a few reasons:

• I kept being asked. And after a time one realises that there must be an issue.
• I decided that the Observable Prelude functionality wasn't important enough to keep in the Prelude type (which was one of the key reasons to keep it together before)
• There has been some odd versioning going on with Rx where I've seen issues in other projects that have required manual assembly version matching
• Having zero dependencies for the Core is nice.

The new LanguageExt.Rx project only supports net46+ and netstandard 2, this is because I set the project to have a dependency on System.Reactive version *, which in theory should allow any version to be included, but it seems to have locked it to 4.* (slightly annoying, but it's better than locking it to an older version I suppose) - if anyone has information on how to make the wildcard work for all versions please get in touch via the github Issues.

Today I have decided to release version 3 of lang-ext, this has been running along as a beta for many months now and has been stable for all of that period and so although there was much more stuff I wanted to put into the release, I feel it's probably a good idea to get, what's been done so far, live.

The big change is a major refactor to the async types and behaviours - lots of bug fixes and a project to standardise the Async types and methods. Because of this standardisation project (which is ongoing) you may see some compilation errors due to changes in method names or arguments (when using named arguments).

In practice this will mean some manual fix ups, but once done you shouldn't see any problems from the changes in behaviour.

There are lots of bug fixes in the async types, but also in general, so if you're one of those people that couldn't use the beta for whatever reason, I would highly recommend that you migrate to v3.0.0 - I've been using much of this in production for many months.

The kind of compilation issue you may see is:

    Match(Some, None)

Becoming variously:

    Match(SomeAsync, None)
    Match(Some, NoneAsync)
    Match(SomeAsync, NoneAsync)

This is to reduce the chance of compiler misunderstanding when using the many variants of each type of Match, Map, Bind etc.

Also, some functions may have changed from say Match to MatchAsync and vice versa depending on the context.

The scale of improvements in the async story can't be understated, there are many bug fixes, but also a huge increase in the amount of async functionality added. Not least from new types like EitherAsync, FunctorAsync, BiFunctorAsync, ApplicativeAsync, MonadAsync

I am now leveraging the type-class/class-instance system and splitting the synchronous and asynchronous types - this puts a very powerful type-safe story in place for the core types and their class instances. But this has also lead to an enormous amount of typing as the fall-out from this means essentially creating an Async type for each synchronous type (Option and OptionAsync for example). The end goal is a very happy place where there's a mathematical relationship between sync and async, and powerful features that fall out of it by default (like benefits in the higher-kinds system which allows pairs of monads to be composed into a single type).

This will be worked on over the next 6 months or so and will gradually improve.

A similar project has begun to create a type-safe way of describing safe and unsafe types. Unsafe types are those that will hold and/or return null. This is in an earlier stage than the async updates - but will have similarly profound effects for the standardisation of the core types and the relationship between safe and unsafe types (i.e. a safe type can become unsafe, but not the other way around).

A quick run down of what I could see from the commit notes. This is not an exhaustive list by any means:

• Improvements in the type-class discovery system for Record equality, ordering, etc.
• Additional class instances that derive from the Eq, Ord, Functor, Applicative, and Monad type-classes
• Seq and Map various fixes and performance improvements
• Significant improvements to OptionNone
• Addition of EitherLeft<L> and EitherRight<R> to make type inference easier with Either<L, R>
• IgnoreBaseAttribute for Record types - stops the base type fields being used for any Record operations
• Minor performance improvements for Record types
• Bug fixes in Result and OptionalResult
• Try has partition, succs, and fails like Either's partition, lefts, and `rights.
• Tuple<,,> and ValueTuple<,,> Sum fixes
• Additional constructors and Prelude functions for the Writer monad
• Massive improvements to the Higher Kinds feature to have more reliable binding operations which mean more robust pairing of monadic types. Also understand the pairings between async types and async and non-async types, which removes the chance of the .Result being called on an async type just to make it compatible in the HKT system. NOTE: This may mean some of the functions for the HKT types disappear - causing compilation errors. This is a good thing, they didn't do what you thought they did and you'll need to come up with a better solution yourself
• Sequence and Traverse added for Writer, Reader, State, and RWS monads when they're paired with enumerable monads like Seq, Lst, IEnumerable, etc.

There's probably lots more, if you have a few days you can check the merge; it's probably not that fun to read.

Thanks to all contributors who helped put this release together. This is the first part of the bigger picture where async and unsafe become distinct typed concepts, rather than just suffixes on method names and types. Watch this space 👍

I don't normally do release notes for 'minor' releases, but even though this is a smallish change, it will have quite a profound effect on those of you using the Either, EitherUnsafe, and Option types.

Up until now the standard way to construct an Either would be to use one of the two constructor functions:

    var either = Left<string, int>("Failed");
    var either = Right<string, int>(100);

Typing those generic arguments in every time due to C#'s terrible type inference system is definitely one of the point points of this library (and C# in general).

Well, now I've solved it. You can now construct your Either types like so:

    var either = Left("failed");
    var either = Right(100);

Cue the collective sigh of relief!

I haven't managed to cheat C#, it still has its limitations: I have used a similar technique to None (which removes the need to use Option<int>.None (for example). None is a field in the Prelude which is of type OptionNone. The Option<A> type has implicit conversion operators to make use of it relatively seamless (which mostly removes the need to type in the generic argument type).

There are now two new types EitherRight<R> and EitherLeft<L> that work in a similar way to OptionNone. The main difference is that they both implement the subset of functions that are appropriate for the state they represent and you can use them in LINQ expressions without the type-system complaining.

For example:

   var r =from x in Right(2)
          from y in Right(123)
          from z in Right(5)
          select x + y + z;

The value r here is a EitherRight<R>.

With the example below there are both Either and EitherRight values in the LINQ expression.

    Either<string, int> either = Right(2);

    var r = from z in either
            from x in Right(123)
            from y in Right(5)
            select x + y + z;

The value r here is an Either<L, R>.

You can use any combination:

    Either<string, int> either = Right(2);

    var r = from x in Right(123)
            from y in Right(5)
            from z in either
            select x + y + z;

One thing to be wary of is when using Left(x) - because the R type can't be inferred it will always have a bound value of Unit:

    from x in Right(2)
    from y in Left("error")
    from z in Right(5)
    select x + y + z;

Here y is Unit and so you'll get a compile time error. This is unlikely to be a big issue in practice, but you can Bind the EitherLeft into an Either like so:

    from x in Right(2)
    from y in Left("error").Bind<int>()
    from z in Right(5)
    select x + y + z;

The reason that Bind doesn't take a function for its argument is that it would never run (because it's following the rules of the Either monad). So, you can consider Bind to simply be a cast operation for the R value that doesn't exist.

EitherRight has five Bind functions:

        Either<L, R> Bind<L>();
        EitherRight<B> Bind<B>(Func<R, EitherRight<B>> f);
        Either<L, R> Bind<L>(Func<R, EitherLeft<L>> f); 
        Either<L, B> Bind<L, B>(Func<R, Either<L, B>> f);
        EitherUnsafe<L, B> Bind<L, B>(Func<R, EitherUnsafe<L, B>> f);

The first allows for casting of the unknown L type, the next one allows for the Bind to continue on the Right branch, the next switches the state to Left (and in the process gives us enough information to construct an Either), the next two are the 'classic' bind operations that you'd see in `Either.

OptionNone has also been gifted with a new interface that supports the subset of behaviour that's appropriate for an Option in a None state (which, is very limited, obviously). But it also supports the Bind function to cast the type.

Note

• All existing constructor functions will continue to work as-is, so this should have zero effect on any existing code.
• I will be bringing this technique to the other types that have multiple type arguments soon

This has definitely been one of my biggest gripes over the years, so I hope you enjoy the release as much as I know I'm going to 👍

This is a minor release to bump the previous version up to beta, as it appears pretty stable. This may allow a few more people to use the new async features (and prepare for the breaking changes).

There are a few improvements and bug fixes here:

• Traverse and Sequence now works for sequences of Reader, Writer, State, and RWS monads

These extensions are manually added rather than auto-implemented by the HKT system. So, the implementations of each are as optimal as possible, but because of the amount of typing - not all combinations are done. However, you should find that the combination of the monads listed above with Seq, Lst, Arr, [], HashSet, Set, Stck, and IEnumerable are all supported.

NOTE: The reverse operation isn't current implemented. I felt that the most useful operation would be to turn sequences of readers/writers/states, into a reader/writer/state where the bound value is a sequence (following the rules of the readers/writers/state monad). The other direction is clearly less useful (although will be implemented at some point I'm sure).

static Writer<MSeq<string>, Seq<string>, int> writer(int value, Seq<string> output) => () =>
    (value, output, false);

static Writer<MSeq<string>, Seq<string>, Seq<int>> multWithLog(Seq<int> input) =>
    from _ in writer(0, SeqOne("Start"))
    let c = input.Map(i => writer(i * 10, SeqOne($"Number: {i}")))
    from r in c.Sequence()
    select r;

/ Run the writer
var res = multWithLog(Seq(1, 2, 3)).Run();

// res.Value.IfNoneOrFail(Seq<int>()) == Seq(10, 20, 30);
// res.Output == Seq("Start", "Number: 1", "Number: 2", "Number: 3");

• Fix for: Result<>.Bottom.IsBottom is false - https://github.com/louthy/language-ext/issues/341
• Various minor improvements

On nu-get now

This is an alpha release of the initial phase of the async overhaul of language-ext.

• New type-classes for asynchronous types: MonadAsync, ApplicativeAsync, FunctorAsync, FoldableAsync, BiFoldableAsync
• Improved implementations of the class-instances for asynchronous types: MTask, ApplTask, FTask, MTryAsync, ApplTryAsync, FTryAsync, MTryOptionAsync, ApplTryOptionAsync, FTryOptionAsync, MOptionAsync, ApplOptionAsync, FOptionAsync,
• New asynchronous EitherAsync type with associated MEitherAsync, ApplEitherAsync, FEitherAsync implementations.
• Overhauled transformer extensions for nested monads so only behaviours that can run without forcing asynchronous monads to run synchronously are available.
• Constructor functions for asynchronous types now work with Task rather than Func

All existing unit-tests pass although some tests had to be updated due to the breaking changes.

The main breaking changes you will see are:

• Constructor functions for asynchronous types won't accept plain Funcs any more - they must return Tasks
• Some extension methods in the transformer system now return Task<A> where they previously forced synchronous return value of A
• To reduce the problems of method resolution a large number of methods have been renamed to have Async suffixes - so if your function doesn't exist anymore then check if there is an methodNameAsync variant.
• The async functionality previously attached to the synchronous class instances has now gone (so FoldAsync isn't on MOption any more for example)

The RWS (Reader Writer State) monad has returned and has been fully implemented with the type-class system. Thanks to @gwintering Greg Wintering for the hard work on this. It's certainly not an easy type to formulate.

There have been many bugs fixed over the past few versions where I didn't publish release notes, so it's probably a good idea to get the info out:

• Try.IfFailThrow not throws when faulted - https://github.com/louthy/language-ext/issues/264
• memo of enumerable is not lazy - https://github.com/louthy/language-ext/issues/265
• Trouble with Lst - SetItem(index, value) - https://github.com/louthy/language-ext/issues/272
• Traversing Lst<TryAsync> returns empty - https://github.com/louthy/language-ext/issues/279
• static properties cause Record::Equals to crash - https://github.com/louthy/language-ext/issues/281
• Removing an item from a list throws Argument exception when value does not implement IComparable -
  https://github.com/louthy/language-ext/issues/284
• Stackoverflow in Arr<Arr>.Equals - https://github.com/louthy/language-ext/issues/286
• Exception didn't keep after converting from Try to TryOption - https://github.com/louthy/language-ext/issues/295
• Ambiguous type in List/Seq.foldX() when ListItem type T and State Type S are same types - https://github.com/louthy/language-ext/issues/304
• Task<Option<>>.BiIterAsync() takes wrong route when None - https://github.com/louthy/language-ext/issues/299

Thanks to everyone who reported issues. Especially those that committed pull requests with fixes - it massively helps! Also thanks to those who submitted other improvements - everything helps 👍

I was going to hold off on this for as long as possible, but the limitations of netstandard 1.3 are getting in the way of improvements to lang-ext and has been blocking fixes I'd like to make. Unfortunately nu-get doesn't seem to support netstandard 1.3 and netstandard 2.0 in the same package, so I have dropped support for netstandard 1.3 (you can still build a netstandard 1.3 project from source using the COREFX13 preprocessor directive).

Fixes for netstandard 2.0 and net451:

• Record types use guaranteed field and property ordering for comparison/ord operations. https://github.com/louthy/language-ext/issues/262

Fixes for netstandard 2.0:

• When defining a default Eq type-class that will work with records, lang-ext can now search the entire project assembly list for candidate instances.
• raiseapp function in Prelude is now available - raises an ApplicationException

All on nu-get now.

Firstly, if you're using the Records or NewTypes feature and you're relying on the fact they derive from ISerializable, then note that now they do not.

Since adding the Records feature last week I have been using them heavily (along with the new serialisable NewTypes), unfortunately because Record<A> and NewType<...> derive from ISerializable JSON.NET forces you to implement the deserialisation constructor: ctor(SerializationInfo info, StreamingContext ctx) which I am finding to be reeeeally tedious when JSON.NET has a decent fall-back option of matching field and property names to constructor arguments and working it out itself.

The side-effect of this is that if you're using any other mechanism for serialisation that relies on the type inheriting ISerializable then you'll need to add that to your definitions yourself. I feel that's probably the most pragmatic approach as at least this way you can opt-in, whereas previously you couldn't opt-out.

Whilst I was in there I added a new feature to find the default class-instance for a type-class. If you don't know what type-classes or class-instances are then please see the Ad-hoc Polymorphism section in the README.

A quick example of this is finding the default equality instance for string:

    Class<Eq<string>>.Default.Equals(x, y);

This will do a one time search of the loaded assemblies for a type called EqString that derives from Eq<string>. This is very similar to how Haskell resolves class-instances for type-classes, and makes the system 'less ad-hoc' and more concrete.

At the moment it only works for simple types, so this isn't possible yet:

    Class<Monad<Option<A>, A>>.Default.Return(...);

It will be possible when I have some more time!

The main benefit of this right now is that I have updated the NewType<..> and Record<A> types to look for Eq and Ord classes when building the IL for their equality, ordering, and hash-code implementations.

This means you can provide ad-hoc equality and ordering classes that will just work with Records and NewTypes:

This is a Record type that has a field with a type of JObject, which is owned by Json.NET and can't be modified.

    public class TestEqJObject : Record<TestEqJObject>
    {
        public readonly JObject Value;

        public TestEqJObject(JObject value) => 
            Value = value;
    }

By default the equality operators won't be much use. But by implementing a class-instance for JObject equality, they are:

    public struct EqJObject : Eq<JObject>
    {
        public bool Equals(JObject x, JObject y) =>
            JObject.DeepEquals(x, y);

        public int GetHashCode(JObject x) =>
            x.GetHashCode();
    }

Example:

JObject a = (JObject)JsonConvert.DeserializeObject(JsonConvert.SerializeObject(new { A = "Hello", B = "World" }));
JObject b = (JObject)JsonConvert.DeserializeObject(JsonConvert.SerializeObject(new { A = "Hello", B = "World" }));
JObject c = (JObject)JsonConvert.DeserializeObject(JsonConvert.SerializeObject(new { A = "Different", B = "World" }));

var i = new TestEqJObject(a);
var j = new TestEqJObject(b);
var k = new TestEqJObject(c);

var x = i == j;    // true
var y = i == k;   // false
var z = j == k;   // false

NOTE: If you're using .NETStandard/NETCore then you will need to register the assemblies that have the class-instances in.

    ClassInstancesAssembly.Register(typeof(EqJObject).GetTypeInfo().Assembly);

Unfortunately NETStandard 1.3 has most of the reflection API missing, so you need to add them manually. NETStandard 2.0 has just been released, so I'm sure I'll be moving to that in the coming months and this won't be necessary.

Finally

Finally the EqDefault and OrdDefault types have been updated to use this resolution system. And so all the types that use EqDefault<A> and OrdDefault<A> will benefit from discovery of equality an ordering instances. So for example Map<K, V> can now discover the ordering operators for its key, or the standard == operators for all the core types like Option, Either, etc. There have always been specialised Equals and Compare functions to allow you to provide your own Eq or Ord class, but now the default behaviour is much more robust than just calling EqualityComparer<A>.Default.Equals(x, y) or Comparer<A>.Default.Equals(x, y)

These a super powers for C# devs, which will become even more powerful once I have made them work for the more complex types too.

This covers the past 6 minor version number updates. Mostly the minor release have been finding the edge cases with the Record<A> system:

Updates

• Symmetric equality added
• Validation types now support serialisation/deserialisation

Fixes

• Edge case bugs in equality and ordering fixed
• ToString edge cases fixed
• Property names are prettified when serialised (they were using the backing field name, which is ugly)

All in all the record system should be stable now. If you find any edge cases that cause exceptions please let me know. If you downloaded version 2.1.0 to 2.1.9 and you want to use records then you should upgrade to this release.

Some minor fixes to yesterdays release, but some additional features too:

• Record<A> derived types now gain a default ToString() implementation

So for a type like this:

    public class TestClass : Record<TestClass>
    {
        public readonly int X;
        public readonly string Y;
        public readonly Guid Z;

        public TestClass(int x, string y, Guid z)
        {
            X = x;
            Y = y;
            Z = z;
        }
    }

You would get a return from ToString of:

"TestClass(1, Hello, 2ba1ec03-8309-46f6-a93e-5d6aada3a43c)"

• Record<A> derived types now implement ISerializable and provide a default GetObjectData and deserialisation constructor.
• The are new Attributes for opting fields out of the equality testing, ordering comparisons, hash-code generation, stringification (ToString), and serialisation:
  • Equals() - OptOutOfEq
  • CompareTo() - OptOutOfOrd
  • GetHashCode() - OptOutOfHashCode
  • ToString() - OptOutOfToString
  • Serialization - OptOutOfSerialization (can also use NonSerializable)

For example, here's a record type that opts out of various default behaviours:

    public class TestClass2 : Record<TestClass2>
    {
        [OptOutOfEq]
        public readonly int X;

        [OptOutOfHashCode]
        public readonly string Y;

        [OptOutOfToString]
        public readonly Guid Z;

        public TestClass2(int x, string y, Guid z)
        {
            X = x;
            Y = y;
            Z = z;
        }
    }

And some unit tests showing the result:

[Fact]
public void OptOutOfEqTest()
{
    var x = new TestClass2(1, "Hello", Guid.Empty);
    var y = new TestClass2(1, "Hello", Guid.Empty);
    var z = new TestClass2(2, "Hello", Guid.Empty);

    Assert.True(x == y);
    Assert.True(x == z);
}

[Fact]
public void OptOutOfHashCodeTest()
{
    var x = new TestClass2(1, "Hello", Guid.Empty);
    var y = new TestClass2(1, "Hello32543534", Guid.Empty);
    var z = new TestClass2(1, "Hello", Guid.Empty);

    Assert.True(x.GetHashCode() == y.GetHashCode());
    Assert.True(x.GetHashCode() == z.GetHashCode());
}

[Fact]
public void OptOutOfToString()
{
    var x = new TestClass2(1, "Hello", Guid.Empty);
    var y = new TestClass2(1, "Hello", Guid.NewGuid());

    Assert.True(x.ToString() == y.ToString());
}

For context here are yesterday's release notes

The latest release of language-ext offers support for building 'record types' in C#.

It's no secret that implementing immutable record types, with structural equality, structural ordering, and efficient hashing solutions is a real manual head-ache of implementing Equals, GetHashCode, deriving from IEquatable<A>, IComparable<A>, and implementing the operators: ==, !=, <, <=, >, >=. It is a constant maintenance headache of making sure they're kept up to date when new fields are added to the type - with no compilation errors if you forget to do it.

Record<A>

This can now be achieved simply by deriving your type from Record<A> where A is the type you want to have structural equality and ordering. i.e.

    public sealed class TestClass : Record<TestClass>
    {
        public readonly int W;
        public readonly string X;
        public readonly Guid Y;
        public AnotherType Z { get; set; }

        public TestClass(int w, string x, Guid y, AnotherType z)
        {
            W = w;
            X = x;
            Y = y;
            Z = z;
        }
    }

This gives you Equals, IEquatable.Equals, IComparable.CompareTo, GetHashCode, operator==, operator!=, operator >, operator >=, operator <, and operator <= implemented by default. As well as a default ToString implementation and an ISerializable implementation.

Note that only fields or field backed properties are used in the structural comparisons and hash-code building. So if you want to use properties then they must not have any code in their getters or setters.

No reflection is used to achieve this result, the Record type builds the IL directly, and so it's as efficient as writing the code by hand.

There are some unit tests to see this in action.

Opting out

It's possible to opt various fields and properties out of the default behaviours using the following attributes:

• Equals() - OptOutOfEq
• CompareTo() - OptOutOfOrd
• GetHashCode() - OptOutOfHashCode
• ToString() - OptOutOfToString
• Serialization - OptOutOfSerialization (can also use NonSerializable)

For example, here's a record type that opts out of various default behaviours:

    public sealed class TestClass2 : Record<TestClass2>
    {
        [OptOutOfEq]
        public readonly int X;

        [OptOutOfHashCode]
        public readonly string Y;

        [OptOutOfToString]
        public readonly Guid Z;

        public TestClass2(int x, string y, Guid z)
        {
            X = x;
            Y = y;
            Z = z;
        }
    }

And some unit tests showing the result:

public void OptOutOfEqTest()
{
    var x = new TestClass2(1, "Hello", Guid.Empty);
    var y = new TestClass2(1, "Hello", Guid.Empty);
    var z = new TestClass2(2, "Hello", Guid.Empty);

    Assert.True(x == y);
    Assert.True(x == z);
}

RecordType<A>

You can also use the 'toolkit' that Record<A> uses to build this functionality in your own bespoke types (perhaps if you want to use this for struct comparisons or if you can't derive directly from Record<A>, or maybe you just want some of the functionality for ad-hoc behaviour):

The toolkit is composed of seven functions:

    RecordType<A>.Hash(record);

This will provide the hash-code for the record of type A provided. It can be used for your default GetHashCode() implementation.

    RecordType<A>.Equality(record, obj);

This provides structural equality with the record of type A and the record of type object. The types must match for the equality to pass. It can be used for your default Equals(object) implementation.

    RecordType<A>.EqualityTyped(record1, record2);

This provides structural equality with the record of type A and another record of type A. It can be used for your default Equals(a, b) method for the IEquatable<A> implementation.

    RecordType<A>.Compare(record1, record2);

This provides a structural ordering comparison with the record of type A and another record the record of type A. It can be used for your default CompareTo(a, b) method for the IComparable<A> implementation.

    RecordType<A>.ToString(record);

A default ToString provider.

    RecordType<A>.SetObjectData(record, serializationInfo);

Populates the fields of the record from the SerializationInfo structure provided.

    RecordType<A>.GetObjectData(record, serializationInfo);

Populates the SerializationInfo structure from the fields of the record.

Below is the toolkit in use, it's used to build a struct type that has structural equality, ordering, and hash-code implementation.

    public class TestStruct : IEquatable<TestStruct>, IComparable<TestStruct>, ISerializable
    {
        public readonly int X;
        public readonly string Y;
        public readonly Guid Z;

        public TestStruct(int x, string y, Guid z)
        {
            X = x;
            Y = y;
            Z = z;
        }

        TestStruct(SerializationInfo info, StreamingContext context) =>
            RecordType<TestStruct>.SetObjectData(this, info);

        public void GetObjectData(SerializationInfo info, StreamingContext context) =>
            RecordType<TestStruct>.GetObjectData(this, info);

        public override int GetHashCode() =>
            RecordType<TestStruct>.Hash(this);

        public override bool Equals(object obj) =>
            RecordType<TestStruct>.Equality(this, obj);

        public int CompareTo(TestStruct other) =>
            RecordType<TestStruct>.Compare(this, other);

        public bool Equals(TestStruct other) =>
            RecordType<TestStruct>.EqualityTyped(this, other);
    }

Type-classes

For anybody using the type-class and class-instance features of language-ext there are two new class instances to support record equality and ordering:

• EqRecord<A>
• OrdRecord<A>

So for example if you have two functions constrained to take Eq<A> or Ord<A> types:

public bool GenericEquals<EqA, A>(A x, A y) where EqA : struct, Eq<A> =>
    default(EqA).Equals(x, y);

public int GenericCompare<OrdA, A>(A x, A y) where OrdA : struct, Ord<A> =>
    default(OrdA).Compare(x, y);

Then you can call them with any record type:

var x = new TestClass(1, "Hello", Guid.Empty);
var y = new TestClass(1, "Hello", Guid.Empty);

var res1 = GenericEquals<EqRecord<TestClass>,TestClass>(x, y);
var res2 = GenericCompare<OrdRecord<TestClass>, TestClass>(x, y);

All on nu-get:

• LanguageExt.Core
• LanguageExt.FSharp
• LanguageExt.Parsec

Either updates

• Partition to use ValueTuple
• Partition/Lefts/Rights Seq variants
• Moved Typeclass attribute to LanguageExt.Attributes

All on nu-get:

• LanguageExt.Core
• LanguageExt.FSharp
• LanguageExt.Parsec

The Func extension methods Compose and BackCompose have been flipped. I felt they were the wrong way around, and that in this situation where the Prelude function compose works one way:

    static Func<int, float>  f = x => x * 3.0f;
    static Func<float, bool> g = x => x > 4.0f;

    var h = compose(f, g);

That the extension method should also go the same way:

   var h = f.Compose(g);

It would also feel more natural when composing multiple functions:

   var x = a.Compose(b).Compose(c).Compose(d);

So if you use the Compose and BackCompose extensions, then you need to flip them in your code.

Version 2 Release Notes

Version 2.0 of Language-Ext is now in released, I was going to wait until I had time to rewrite the README docs, but I think that will take some time, and so I think it's best to get this live.

This is a major overhaul of every type in the system. I have also broken out the LanguageExt.Process actor system into its own repo, it is now named Echo, so if you're using that you should head over to the repo and follow that. It's still in alpha - it's feature complete, it just needs more testing - so it's lagging behind at the moment. If you're using both lang-ext Core and the Echo Process system then wait until the Echo Process system is released before migrating to the new Core.

Version 2.0 of Language-Ext actually just started out as a branch where I was trying out a new technique for doing ad-hoc polymorphism in C# (think somewhere between Haskell typeclasses and Scala implicits).

I didn't expect it to lead to an entire re-write. So a word of warning, there are many areas that I know will be breaking changes, but some I don't. Breaking changes will 99% of the time be compile time errors (rather than changes in behaviour that silently affect your code). So although I don't expect any major issues, For any large projects I would put aside an afternoon to fix up any compilation breakages.

Often the breakages are for things like rectifying naming inconsistencies (for example some bi-map functions were named Map, some named BiMap, they're all now BiMap), another example is that all collection types (Lst, Map, etc.) are now structs. So any code that does this will fail to compile:

    Map<int, string> x = null;

The transformer extensions have been overhauled too (they provided overloads for nested monadic types, Option<Lst<A>> for example). If you were cheating trying to get directly at values by calling Lift or LiftUnsafe, well, now you can't. It was a bad idea that was primarily to make the old transformer types work. So they're gone.

The overloads of Select and SelectMany are more restricted now, because combining different monadic types could lead to some type resolution issues with the compiler. You will now need to lift your types into the context of the LINQ expression (there are now lots of extensions to do that: ToOption, ToTry, etc.)

For the problems you will inevitablity have with upgrading to language-ext 2.0, you will also have an enormous amount of new benefits and possibilities.
My overriding goal with this library is to try and provide a safer environment in which to write C#. Version 1 was mostly trying to protect the programmer from null and mutable state. Version 2 is very much focussed on improving our lot when implementing abstract types.

Inheritance based polymorphism is pretty much accepted to be the worst performer in the polymorphic world. Our other option is parametric polymorphism (generics). With this release I have facilitated ad-hoc polymorphism with a little known technique in C#.

So for the first time it's possible to write numeric methods once for all numeric types or do structural equality testing that you can rely on.

Also there is support for the much more difficult higher-order polymorphic types like Monad<MA, A>. LanguageExt 2.0 provides a fully type-safe and efficient approach to working with higher order types. So yes, you can now write functions that take monads, or functors, or applicatives, and return specialised values (rather than abstract or dynamic values). Instead of writing a function that takes an Option<A>, you can write one that takes any monadic type, bind them, join them, map them, and return the concrete type that you pushed in.

Of course without compiler or runtime support for higher-order generics some hoops need to be jumped through (and I'm sure there will be some Haskell purist losing their shit over the approach). But at no point is the integrity of your types affected. Often the technique requires quite a large amount of generic argument typing, but if you want to write the super generic code, it's now possible. I don't know of any other library that provides this functionality.

This has allowed the transformer extensions to become more powerful too (because the code generator that emits them can now use the type-class/instance system). The Writer monad can now work with any output type (as long as it has a Monoid instance), so it's not limited to telling its output to an IEnumerable, it can be a Lst, a string, an int, or whatever Monoid you specify.

Personally I find this very elegant and exciting. It has so much potential, but many will be put off by the amount of generic args typing they need to do. If anybody from the Rosyln team is reading this, please for the love of god help out with the issues around constraints and excessive specifying of generic arguments. The power is here, but needs more support.

Scroll down to the section on Ad-hoc polymorphism for more details.

Documentation

Full API documentation can be found here

Bug fixes

• Fix for Lst.RemoveAt(index) - certain tree arrangements caused this function to fail
• Fix for HSet (now HashSet) constructor bug - constructing with an enumerable always failed
• Map, Lst, Set, Option, Either, etc. All have serialisers that work with Json.NET (finally).

Examples: https://github.com/louthy/language-ext/blob/type-classes/LanguageExt.Tests/SerialisationTests.cs

New features - LanguageExt.Core

New collection types:

Type	Description
Seq<A>	Cons-like, singly-linked list
HashSet<A>	Ordering is done by GetHashCode(). Existence testing is with EqualityComparer<A>.Default.Equals(a,b)
HashMap<A, B>	Ordering is done by GetHashCode(). Existence testing is with EqualityComparer<A>.Default.Equals(a,b)
HashSet<EqA, A> where EqA : struct, Eq<A>	Ordering is done by GetHashCode(). Existence testing is with default(EqA).Equals(a,b)
HashMap<EqA, A, B>	Ordering is done by GetHashCode(). Existence testing is with default(EqA).Equals(a,b)
Set<OrdA, A> where OrdA : struct, Ord<A>	Ordering is done by default(OrdA).Compare(a,b). Existence testing is with default(OrdA).Equals(a,b)
Map<EqA, A, B>	Ordering is done by default(OrdA).Compare(a,b). Existence testing is with default(OrdA).Equals(a,b)
Arr<A>	Immutable array. Has the same access speed as the built-in array type, but with immutable cells. Modification is expensive, due to the entire array being copied per operation (although for very small arrays this would be more efficient than Lst<T> or Set<T>).
Lst<PredList, A> where PredList : struct, Pred<ListInfo>	This allows lists to run a predicate on the Count property of the list after construction.
Lst<PredList, PredItem, A> where PredItem : struct, Pred<A>	This allows lists to run a predicate on the Count property of the list after construction and on items as they're being added to the list.

As you can see above there are new type-safe key versions of Set, HashSet, Map, and HashMap. Imagine you want to sort the value of a set of strings in a case-insensitive way (without losing information by calling value.ToLower()).

    var map = Set<TStringOrdinalIgnoreCase, string>(...)

The resulting type would be incompatible with:

    Set<TString, string>, or Set<TStringOrdinal, string>

And is therefore more type-safe than just using Set. Examples

The two new predicate versions of Lst allow for properties of the list to travel with the type. So for example this shows how you can enforce a list to be non-empty:

    public int Product(Lst<NonEmpty, int> list) =>
        list.Fold(1, (s, x) => s * x);

There are implicit conversion operators between Lst<A> and Lst<PredList, A>, and between Lst<A> and Lst<PredList, PredItem, A>. They don't need to reallocate the collection, but converting to a more constrained type will cause the validation to run. This is very light for constructing Lst<PredList, A>, but will cause every item in the list to be validated for Lst<PredList, PredItem, A>.

And so it's possible to do this:

    Lst<int> list = List<int>();

    var res = Product(list);  // ArgumentOutOfRangeException

That will throw an ArgumentOutOfRangeException because the list is empty. Whereas this is fine:

    Lst<int> list = List<int>(1, 2, 3, 4, 5);

    var res = Product(list); // 120

To construct the predicate list types directly, call:

    Lst<NonEmpty, int> list = List<NonEmpty, int>(1, 2, 3, 4, 5);

The second type of predicate Lst is Lst<PredList, PredItem, A>. PredItem is a predicate that's run against every item being added to the list. Once the item is in the list it won't be checked again (because it's an immutable list).

For example, this is a Lst that can't be empty and won't accept null items.

    var x = List<NonEmpty, NonNullItems<string>, string>("1", "2", "3");

Obviously declaring types like this gets quite bulky quite quickly. So only using them for method arguments is definitely a good approach:

    public string Divify(Lst<NonEmpty, NonNullItems<string>, string> items) =>
        String.Join(items.Map(x => $"<div>{x}</div>"));

Then Divify can be invoked thus:

    var res = Divify(List("1", "2", "3")); 

    // "<div>1</div><div>2</div><div>3</div>"

But as mentioned above, the implicit conversion from Lst<string> to Lst<NonEmpty, NonNullItems<string>, string> will run the NonNullItems<string> predicate for each item in the Lst.

Built-in are some standard Pred<ListInfo> implementations:

• AnySize - Always succeeds
• CountRange<MIN, MAX> - Limits the Count to be >= MIN and <= MAX
• MaxCount<MAX> - As above but with no lower bound
• NonEmpty - List must have at least one item

And by default there are lots of Pred<A> implementations. See the NewType discussion later.

Seq<A>

A new feature is the type Seq<A> which derives from ISeq<A>, which in turn is an IEnumerable<A>.

It works very much like cons in functional languages (although not a real cons, as that's not a workable solution in C#). It's a singly-linked list, with two key properties: Head which is the item at the head of the sequence, and Tail which is the rest of the sequence. You can convert any existing collection type (as well as IEnumerable types) to a Seq<A> by calling the Seq constructor:

    var seq1 = Seq(List(1, 2, 3, 4, 5));    // Lst<A> -> Seq<A>
    var seq2 = Seq(Arr(1, 2, 3, 4, 5));     // Arr<A> -> Seq<A>
    var seq3 = Seq(new [] {1, 2, 3, 4, 5}); // A[] -> Seq<A>
    ...    

As well as construct them directly:

    var seq1 = Seq(1, 2, 3, 4, 5);

    var seq2 = 1.Cons(2.Cons(3.Cons(4.Cons(5.Cons(Empty)))));

In practice if you're using Cons you don't need to provide Empty:

    var seq = 1.Cons();   // Creates a sequence with one item in

The primary benefits are:

• Immutable
• Thread-safe
• Much lighter weight than using Lst<A> (although Lst<A> is very efficient, it is still an AVL tree behind the scenes)
• Maintains the original type for Lst<A>, Arr<A>, and arrays. So if you construct a Seq from one of those types, the Seq then gains extra powers for random lookups (Skip), and length queries (Count).
• If you construct a Seq with an IEnumerable then it maintains its laziness, but also guarantees that each item in the original IEnumerable is only ever enumerated once.
• Obviously easier to type Seq than IEnumerable!
• Count works by default for all non-IEnumerable sources. If you construct with an IEnumerable then Count will only cause a single evaluation of the underlying IEnumerable (and subsequent access to the seq for anything else doesn't cause additional evaluation)
• Efficient pattern matching on the Seq, which again doesn't cause multiple evaluations of the underling collection.

Seq has a bigger interface than IEnumerable which allows for various bespoke optimisations depending on the underlying collection; which is especially powerful for the LINQ operators like Skip, Take, TakeWhile,

    public interface ISeq<A> : 
        IEnumerable<A>, 
        IEquatable<ISeq<A>>, 
        IComparable<ISeq<A>>
    {
        /// <summary>
        /// Head of the sequence
        /// </summary>
        A Head { get; }

        /// <summary>
        /// Head of the sequence
        /// </summary>
        Option<A> HeadOrNone();

        /// <summary>
        /// Tail of the sequence
        /// </summary>
        Seq<A> Tail { get; }

        /// <summary>
        /// True if this cons node is the Empty node
        /// </summary>
        bool IsEmpty { get; }

        /// <summary>
        /// Returns the number of items in the sequence
        /// </summary>
        /// <returns>Number of items in the sequence</returns>
        int Count { get; }

        /// <summary>
        /// Match empty sequence, or multi-item sequence
        /// </summary>
        /// <typeparam name="B">Return value type</typeparam>
        /// <param name="Empty">Match for an empty list</param>
        /// <param name="Tail">Match for a non-empty</param>
        /// <returns>Result of match function invoked</returns>
        B Match<B>(
            Func<B> Empty,
            Func<A, Seq<A>, B> Tail);

        /// <summary>
        /// Match empty sequence, or one item sequence, or multi-item sequence
        /// </summary>
        /// <typeparam name="B">Return value type</typeparam>
        /// <param name="Empty">Match for an empty list</param>
        /// <param name="Tail">Match for a non-empty</param>
        /// <returns>Result of match function invoked</returns>
        B Match<B>(
            Func<B> Empty,
            Func<A, B> Head,
            Func<A, Seq<A>, B> Tail);

        /// <summary>
        /// Match empty sequence, or multi-item sequence
        /// </summary>
        /// <typeparam name="B">Return value type</typeparam>
        /// <param name="Empty">Match for an empty list</param>
        /// <param name="Seq">Match for a non-empty</param>
        /// <returns>Result of match function invoked</returns>
        B Match<B>(
            Func<B> Empty,
            Func<Seq<A>, B> Seq);

        /// <summary>
        /// Match empty sequence, or one item sequence, or multi-item sequence
        /// </summary>
        /// <typeparam name="B">Return value type</typeparam>
        /// <param name="Empty">Match for an empty list</param>
        /// <param name="Tail">Match for a non-empty</param>
        /// <returns>Result of match function invoked</returns>
        B Match<B>(
            Func<B> Empty,
            Func<A, B> Head,
            Func<Seq<A>, B> Tail);

        /// <summary>
        /// Map the sequence using the function provided
        /// </summary>
        /// <typeparam name="B"></typeparam>
        /// <param name="f">Mapping function</param>
        /// <returns>Mapped sequence</returns>
        Seq<B> Map<B>(Func<A, B> f);

        /// <summary>
        /// Map the sequence using the function provided
        /// </summary>
        /// <typeparam name="B"></typeparam>
        /// <param name="f">Mapping function</param>
        /// <returns>Mapped sequence</returns>
        Seq<B> Select<B>(Func<A, B> f);

        /// <summary>
        /// Filter the items in the sequence
        /// </summary>
        /// <param name="f">Predicate to apply to the items</param>
        /// <returns>Filtered sequence</returns>
        Seq<A> Filter(Func<A, bool> f);

        /// <summary>
        /// Filter the items in the sequence
        /// </summary>
        /// <param name="f">Predicate to apply to the items</param>
        /// <returns>Filtered sequence</returns>
        Seq<A> Where(Func<A, bool> f);

        /// <summary>
        /// Monadic bind (flatmap) of the sequence
        /// </summary>
        /// <typeparam name="B">Bound return value type</typeparam>
        /// <param name="f">Bind function</param>
        /// <returns>Flatmapped sequence</returns>
        Seq<B> Bind<B>(Func<A, Seq<B>> f);

        /// <summary>
        /// Monadic bind (flatmap) of the sequence
        /// </summary>
        /// <typeparam name="B">Bound return value type</typeparam>
        /// <param name="bind">Bind function</param>
        /// <returns>Flatmapped sequence</returns>
        Seq<C> SelectMany<B, C>(Func<A, Seq<B>> bind, Func<A, B, C> project);

        /// <summary>
        /// Fold the sequence from the first item to the last
        /// </summary>
        /// <typeparam name="S">State type</typeparam>
        /// <param name="state">Initial state</param>
        /// <param name="f">Fold function</param>
        /// <returns>Aggregated state</returns>
        S Fold<S>(S state, Func<S, A, S> f);

        /// <summary>
        /// Fold the sequence from the last item to the first
        /// </summary>
        /// <typeparam name="S">State type</typeparam>
        /// <param name="state">Initial state</param>
        /// <param name="f">Fold function</param>
        /// <returns>Aggregated state</returns>
        S FoldBack<S>(S state, Func<S, A, S> f);

        /// <summary>
        /// Returns true if the supplied predicate returns true for any
        /// item in the sequence.  False otherwise.
        /// </summary>
        /// <param name="f">Predicate to apply</param>
        /// <returns>True if the supplied predicate returns true for any
        /// item in the sequence.  False otherwise.</returns>
        bool Exists(Func<A, bool> f);

        /// <summary>
        /// Returns true if the supplied predicate returns true for all
        /// items in the sequence.  False otherwise.  If there is an 
        /// empty sequence then true is returned.
        /// </summary>
        /// <param name="f">Predicate to apply</param>
        /// <returns>True if the supplied predicate returns true for all
        /// items in the sequence.  False otherwise.  If there is an 
        /// empty sequence then true is returned.</returns>
        bool ForAll(Func<A, bool> f);

        /// <summary>
        /// Skip count items
        /// </summary>
        Seq<A> Skip(int count);

        /// <summary>
        /// Take count items
        /// </summary>
        Seq<A> Take(int count);

        /// <summary>
        /// Iterate the sequence, yielding items if they match the predicate 
        /// provided, and stopping as soon as one doesn't
        /// </summary>
        /// <returns>A new sequence with the first items that match the 
        /// predicate</returns>
        Seq<A> TakeWhile(Func<A, bool> pred);

        /// <summary>
        /// Iterate the sequence, yielding items if they match the predicate 
        /// provided, and stopping as soon as one doesn't.  An index value is 
        /// also provided to the predicate function.
        /// </summary>
        /// <returns>A new sequence with the first items that match the 
        /// predicate</returns>
        Seq<A> TakeWhile(Func<A, int, bool> pred);
    }

Breaking changes

• Previously there were functions in the Prelude called seq which took many types and turned them into IEnumerable<A>. Now they're constructing Seq<A> I have renamed them to Seq in line with other constructor functions.
• Where sensible in the rest of the API I have changed AsEnumerable() to return a Seq<A>. This is for types which are unlikely to have large sequences (like Option, Either, Try, etc.); You may find casting issues in those situations, but the types returned are obviously more useful, so it feels like a win. Let me know if you have issues (All the major types have a ToSeq() method where appropriate, for convenience).
• In LanguageExt.Parsec any parsers that previously returned IEnumerable<A> now return Seq<A>; I noticed when using the Parsec library extensively that I would often use ToArray() or Freeze() to force strict evaluation of a IEnumerable result. Now you don't have to, but you may see some casting issues.
• Match and match for IEnumerable previously allowed for matching up to six items in six separate lambdas. They're now gone because I doubt anybody uses them, and they're slightly unwieldy. Now they use Seq behind the scenes to remove any multiple evaluations during the matching process:

        static int Sum(Seq<int> seq) =>
            seq.Match(
                ()      => 0,
                x       => x,
                (x, xs) => x + Sum(xs));

Non-nullable types:

In the ongoing quest to make it safer to write C# code, these types are all now structs and therefore can't be null:

    Stck<A>, 
    Que<A>, 
    Lst<A>, 
    Map<A, B>, 
    Map<Ord, A, B>, 
    HashMap<A, B>, 
    HashMap<Eq, A, B>, 
    Set<A>, 
    Set<Ord, A>
    HashSet<A, B>, 
    HashSet<Eq, A, B>, 
    Que<A>, 
    Arr<A>

This means you can create a member field and not initialise it and everything will 'just work':

    static class Test
    {
        public static Map<string, int> Foo;
    }

    Assert.True(Test.Foo == Map.empty<string, int>());
    Assert.True(Test.Foo == default(Map<string, int>);

Lazy Option<A> and OptionUnsafe<A>

Option<A> and OptionUnsafe<A> have until now been strict types. They can now support both strict and lazy behaviour in the same type.

For example:

    var option = from w in Some(_ => 5)
                 from x in Some(_ => 10)
                 from y in Some(_ => 15)
                 from z in Some(_ => 20)
                 select w + x + y + z;

    // At this point the w + x + y + z expression hasn't run

Any function that returns a concrete non-Option type will force the expression to be evaluated:

    var result = option.IfNone(0);   // 50

The result is memoised and therefore subsequent calls to Match or similar won't re-evaluate the expression. The strict behaviour is unaltered:

    var option = from w in Some(5)
                 from x in Some(10)
                 from y in Some(15)
                 from z in Some(20)
                 select w + x + y + z;

    // At this point the w + x + y + z expression *has* run

If strict and lazy Options are combined, then the whole expression becomes lazy:

    var option = from w in Some(5)
                 from x in Some(_ => 10)  // lazy expression
                 from y in Some(15)
                 from z in Some(20)
                 select w + x + y + z;

    // At this point the w + x + y + z expression hasn't run

Note if you want to write functions that return lazy options, then you will need to wrap them in Optional or Some:

    Option<int> LazyOptionFoo() => Optional(_ => ... );

Either and EitherUnsafe will have lazy functionality soon

NewType

NewType has gained an extra generic argument. So this:

    class Metres : NewType<double> { ... }

Becomes:

    class Metres : NewType<Metres, double>  { ... } 

That makes lots of functionality more type-safe for NewType derived types. For example monadic and functor operators like Select, Map, Bind, SelectMany can now return Metres rather than NewType<double>. Which is very important for the integrity of the type.

There is a variant that takes an additional generic argument PRED. Which is constrained to be a struct of Pred<A>. This is called in the base constructor:

    if (!default(PRED).True(value)) 
        throw new ArgumentOutOfRangeException(nameof(value), value);

So you should be able to see that this allows validation to be embedded into the type. Here's an example from the new Process system client code:

    public class ClientConnectionId : NewType<ClientConnectionId, string, StrLen<I10, I100>>
    {
        public ClientConnectionId(string value) : base(value)
        { }
    }

ClientConnectionId is like a session token, and StrLen<I10, I100> means the string must be 10 to 100 chars long. It is defined thus:

    public struct StrLen<NMin, NMax> : Pred<string>
            where NMin : struct, Const<int>
            where NMax : struct, Const<int>
    {
        [Pure]
        public bool True(string value) =>
            Range<int, TInt, NMin, NMax>.Is.True(value?.Length ?? 0);
    }

NMin and NMax are constrained to be Const<int>, and from the example above are I10 and I100. They're defined as:

    public struct I10 : Const<int> { public int Value => 10; }
    public struct I100 : Const<int> { public int Value => 100; }

You can define your own struct type that derives from Pred<A> to provide any common validation primatives that you like. And defined constants by deriving from Const<A>.

These are the built in predicate types:

• True<A> - Always succeeds, no matter what's passed
• False<A> - Always fails, no matter what's passed
• Equal<A, EQ, CONST> - Value A must be equal to CONST. EQ is a Eq<A> instance
• Exists<A, Term1, ..., Term5> - Term1 - Term5 are predicates. The test passes if A is true when applied to any of the terms.
• ForAll<A, Term1, ..., Term5> - Term1 - Term5 are predicates. The test passes if A is true when applied to all of the terms.
• GreaterThan<A, ORD, CONST> - Value A must be greater than CONST. ORD is an Ord<A> instance.
• GreaterOrEq<A, ORD, CONST> - Value A must be greater than or equal to CONST. ORD is an Ord<A> instance.
• LessThan<A, ORD, CONST> - Value A must be less than CONST. ORD is an Ord<A> instance.
• LessOrEq<A, ORD, CONST> - Value A must be less than or equal to CONST. ORD is an Ord<A> instance.
• Range<A, ORD, MIN, MAX> - Value A must be in the range MIN to MAX. ORD is an Ord<A> instance.

Constants are in the LanguageExt.ClassInstances.Const namespace. Integers are prefixed with I; the most commonly used are already created: 0 to 256, then powers of two and hundreds, thousands, etc. Double constants are prefixed with D. Only D0, D1, and DNeg1 exist. Char constants are 'A'- 'Z', 'a' - 'z', '0' - '9', ChSpace, ChTab, ChCR, ChLF.

By embedding the validation into the type, there is no 'get out of jail free' cards where a loophole can be found in the type (or sub-type). And it also becomes fundamentally a different type to (for example) NewType<ClientConnectionId, string, StrLen<I0, I10>> (See the <I0, I10> at the end); so any function that wants to work with a client connection token must accept either ClientConnectionId or its base type of NewType<ClientConnectionId, string, StrLen<I10, I100>>. It gives a small glimpse into the world of dependently typed languages, I think this is a pretty powerful concept for improving the safety of C# types in general (with no runtime costs), and takes the original NewType idea to the next level.

There is now an explicit cast operator. So for the Metres example above:

    Metres m = Metres.New(100);
    double x = (double)m * 2.0;

NumType

With the new type-classes and class-instances (see later), it's now possible to write generic code for numeric-types. And so I have created a variant of NewType called NumType. Numeric types like int are the kind of types that are very commonly made into NewType derived types (along with string), but previously there wasn't a good story for doing arithmetic on those types. Now with the NumType it is possible. They work in exactly the same way as NewTypes, but you must specify a Num<A> class-instance (below it's TDouble):

    public class Metres : NumType<Metres, TDouble, double> { 
        public Metres(double x) : base(x) {}
    }

That gives you these extras over NewType:

    operator+
    operator*
    operator/
    operator-
    Product()
    Divide()
    Plus()
    Subtract()
    Abs()
    Signum()
    Min()
    Max()
    Sum()

As with NewType you can also use a predicate:

    public class Age : NumType<Age, TInt, int, Range<int, TInt, I0, I120>> 
    { 
        public Age(int x) : base(x)  {}
    }

FloatType

Even more specialised than NumType and NewType in that it only accepts class-instances from the type-class Floating<A>. It adds functionality that are only useful with floating-point number types (along with the functionality from NumType and NewType):

 Exp(), Sqrt(), Log(), Pow(A exp), LogBase(A y), Sin(), Cos(), Asin(), Acos(), Atan(), Sinh()
 Cosh(), Tanh(), Asinh(), Acosh(), Atanh()

ValueTuple and Tuple

A new feature of C# 7 is syntax for tuples. Instead of:

    Tuple.Create(a, b)

You can now:

    (a, b)

You can also give them names:

    (K Key, V Value)

So wherever in lang-ext tuples are used, they now accept ValueTuple. ValueTuple is the struct version of Tuple that C# is using to back the new syntax.

This is particularly nice for Map:

    var map = Map(
        (1, "Paul"), 
        (2, "Steve"), 
        (3, "Stan"), 
        (4, "Tanzeel"), 
        (5, "Dan"), 
        (6, "Andreas"));

Also Map now derives from IEnumerable<(K Key, V Value)>.

Tuples look like they're going to be a lot more important in C# going forwards, so I have created extension methods and Prelude functions for Tuple and ValueTuple with up to 7 items.

    // Add an item to a tuple
    var (a,b,c)   = (1, 2).Add(3);
    var (a,b,c,d) = (1, 2).Add(3).Add("Hello");

If your tuple contains Semigroups (like Lst and int for example) then you can call Append:

    var (a, b) = append<TLst<int>, TInt, Lst<int>, int>(
                    (List(1,2,3), 3),
                    (List(4,5,6,7), 4));

    // ([1,2,3,4,5,6,7], 7)

Or:

    var list = append<TLst<int>, Lst<int>>( (List(1,2,3), List(4,5,6,7)) );

    // [1,2,3,4,5,6,7]

Head and Tail:

    var a  = ("a", 123, true).Head();   // "a"
    var bc = ("a", 123, true).Tail();   // (123, true)

Sum and Product:

    var a = (100, 200, 300).Sum<TInt, int>();  // 600
    var b = (10, 10, 10).Product<TInt, int>(); // 1000

Contains:

    var a = (1,2,3,4,5).Contains<EqInt, int>(3);  // true

Mapping:

    x = x.Map( tuple => tuple );
    
    x = x.BiMap(a  => a * 2, b => b * 3);
    x = x.TriMap(a  => a * 2, b => b * 3, c => c + " add");
    x = x.QuadMap(a  => a * 2, b => b * 3, c => "over", d => "ride");
    // etc.

    x = x.MapFirst(a => a * 2);  // just maps the first item and leaves the rest alone
    x = x.MapSecond(b => b * 3);  
    x = x.MapThird(c => c + " add");
    x = x.MapFourth(d => "change");  
    // etc.

    var (a, b) = (100, "text").MapFirst(x => x * 2); // (200, "text")

Also:

    Iter, Fold, BiFold, BiFoldBack, TriFold, TriFoldBack, etc.

Cond<A>

Cond allows for building conditional expressions that can be used fluently. It also seamlessly steps between synchronous and asynchronous behaviour without any need for ceremony.

Here's a simple example:

var cond = Cond<int>(x => x == 4)
               .Then(true)
               .Else(false);

That can be run like so:

bool result = cond(4); // True
bool result = cond(0); // False

Or,

bool result = 4.Apply(cond); // True
bool result = 0.Apply(cond); // False

Here's a slightly more complex example:

    var vowels = Subj<char>().Map(Char.ToLower)
                             .Any(x => x == 'a', x => x == 'e', x => x == 'i', x => x == 'o', x => x == 'u')
                             .Then("Is a vowel")
                             .Else("Is a consonant");

    var x = vowels('a'); // "Is a vowel"

This can then be tagged onto anything that returns a char or a Task<char>:

    var res = GetCharFromRemoteServer().Apply(vowels);   // Task<string>

See the pull request for the discussion that led to this feature. Thanks to @ncthbrt for the suggestion and initial implementation.

Range

Continuing the super generic theme, there is now a new Range type that can handle any type (as long as they have Monoid and Ord instances):

    public class Range<SELF, MonoidOrdA, A> : IEnumerable<A>
        where SELF : Range<SELF, MonoidOrdA, A>
        where MonoidOrdA : struct, Monoid<A>, Ord<A>, Arithmetic<A>
    {
        ...
    }

As with NewType, FloatType, and NumType, anything that derives from it should provide itself as the first generic argument. This is the definition of IntegerRange:

    public class IntegerRange : Range<IntegerRange, TInt, int>
    {
        IntegerRange(int min, int max, int step) : base(min, max, step) { }
    }

Everything else is handled in the base class, so it's trivial to add your own. As before they implement IEnumerable<A>, and are lazy. They now support Overlaps(SELF range) and InRange(A x). There are two constructor functions: Range.FromMinMax(min, max, step) and Range.FromCount(min, count, step). There are several provided implementations: BigIntegerRange, CharRange, DecimalRange, DoubleRange, FloatRange, IntegerRange, LongRange, ShortRange.

Try<A> and TryOption<A>

Try and TryOption (the lazy monads that catch exceptions) have been improved to memoise everything they do. So once you run a Try, running the same reference again won't re-invoke the computation, it will just return the previously cached value. This can be useful in LINQ expressions especially.

TryAsync<A>

There is a new monadic type called TryAsync which, as you may have guessed, is an asynchronous version of Try. Try and TryAsync are delegate types that are invoked when you call extension methods like Match on them. By default the TryAsync evaluation extension methods will wrap the invocation in a Task and will catch any exceptions thrown.

    TryAsync<int> LongRunningOp() => TryAsync(() => 10);

    int x = await LongRunningOp().Match(
                Succ: y  => y * 2,
                Fail: ex => 0
                );

Unfortunately you must wrap the operation in a TryAsync(() => ...) because the compiler can't infer the result-type like it can with Try. However you can promote a Try to a TryAsync:

    Try<int> LongRunningOp() => () => 10;

    int x = await LongRunningOp().ToAsync().Match(
                Succ: y  => y * 2,
                Fail: ex => 0
                );

Or use any of the new Async extension methods added to Try:

    Try<int> LongRunningOp() => () => 10;

    int x = await LongRunningOp().MatchAsync(
                Succ: y  => y * 2,
                Fail: ex => 0
                );

Every single method of Try now has an Async variant. Also any method of Try or TryAsync that takes a Func (for example Map(Try<A> x, Func<A, B> f)), now has a variant that allows a Task to be returned instead. For Try methods this will either promote the result to be a TryAsync (as is the case with Map), or a Task (as is the case with Fold). This makes it trivial to deal with asynchronous results, as the Try or TryAsync will automatically perform the correct synchronisation required to extract a valid result.

For functions where operations could run in parallel then the type will again handle that automatically. For example if you use the new Applicative functionality, this is possible:

// Placeholder functions.  Imagine they're doing some work to get some remote
// data lists.
TryAsync<Lst<int>> GetListOneFromRemote() => TryAsync(List(1, 2, 3));
TryAsync<Lst<int>> GetListTwoFromRemote() => TryAsync(List(4, 5, 6));

// Combines two lists and sorts them. 
public static IEnumerable<int> CombineAndOrder(Lst<int> x, Lst<int> y) =>
    from item in (x + y)
    orderby item
    select item;

// Uses the fact that TryAsync is an applicative, and therefore has the 
// apply function available.  The apply function will run all three parts
// of the applicative asynchronously, will handle errors from any term,
// and will then apply them to the CombineAndOrder function.
public TryAsync<IEnumerable<int>> GetRemoteListsAndCombine() =>
    apply(
        CombineAndOrder,
        GetListOneFromRemote(),
        GetListTwoFromRemote());

[Fact]
public async void ListCombineTest()
{
    var res = await GetRemoteListsAndCombine().IfFail(Enumerable.Empty<int>());

    var arr = res.ToArray();

    Assert.True(arr[0] == 1);
    Assert.True(arr[1] == 2);
    Assert.True(arr[2] == 3);
    Assert.True(arr[3] == 4);
    Assert.True(arr[4] == 5);
    Assert.True(arr[5] == 6);
}

TryOptionAsync<A>

As Try has got its TryAsync pairing, so has TryOption now got TryOptionAsync. The interface is almost exactly the same as TryAsync. Here are some quick examples:

    // Some example method prototypes
    public TryOptionAsync<int> LongRunningAsyncTaskOp() => TryOptionAsync(10);
    public Task<TryOption<int>> LongRunningAsyncOp()    => Task.FromResult(TryOption(10));
    public TryOption<int> LongRunningOp()               => TryOption(10);
    public Task<int> MapToTask(int x)                   => Task.FromResult(x * 2);
    public int MapTo(int x)                             => x * 2;

    public async void Test()
    {
        TryOptionAsync<int> j = LongRunningOp().ToAsync();
        TryOptionAsync<int> k = LongRunningAsyncOp().ToAsync();

        // These run synchronously
        int a = LongRunningOp().IfNoneOrFail(0);
        TryOption<int> b = LongRunningOp().Map(MapTo);

        // These run asynchronously
        int u = await LongRunningAsyncTaskOp().IfNoneOrFail(0);
        int v = await LongRunningAsyncOp().IfNoneOrFail(0);
        int x = await LongRunningOp().IfNoneOrFailAsync(0);
        TryOptionAsync<int> y1 = LongRunningOp().MapAsync(MapTo);
        TryOptionAsync<int> y2 = LongRunningOp().MapAsync(MapToTask);
        int z1 = await y1.IfNoneOrFail(0);
        int z2 = await y2.IfNoneOrFail(0);
    }

Ad-hoc polymorphism

Ad-hoc polymorphism has long been believed to not be possible in C#. However with some cunning it is. Ad-hoc polymorphism allows programmers to add traits to a type later. For example in C# it would be amazing if we had an interface called INumeric for numeric types like int, long, double, etc. The reason this doesn't exist is if you write a function like:

    INumeric Add(INumeric x, INumeric y) => x + y;

Then it would cause boxing. Which is slow (well, slower). I can only assume that's why it wasn't added by the BCL team. Anyway, it's possible to create a numeric type, very much like a type-class in Haskell, and ad-hoc instances of the numeric type-class that allow for generic numeric operations without boxing.

From now on I will call them type-classes and class-instances, or just instances. This is not exactly the same as Haskell's type-classes. If anything it's closer to Scala's implicits. However to make it easier to discuss them I will steal from Haskell's lexicon.

Num<A>

So for example, this is how to create a number type-class:

    public interface Num<A>
    {
        A Add(A x, A b);
        A Subtract(A x, A b);
        ...
    }

Notice how there are two arguments to Add and Subtract. Normally if I was going to implement this interface the left-hand-side of the Add and Subtract would be this. I will implement the ad-hoc class-instance to demonstrate why that is:

    public struct TInt : Num<int>
    {
        public int Add(int x, int b) => x + y;
        public int Subtract(int x, int b) => x + y;
        ...
    }

See how TInt is a struct? Structs have a useful property in C# in that they can't be null. So we can invoke the operations like so:

    int r = default(TInt).Add(10, 20);

The important thing to note is that default(TInt) gets optimisied out in a release build, so there's no cost to the invocation of Add. The Add and Subtract methods both take int and return int. So therefore there's no boxing at all.

If we now implement TFloat:

    public struct TFloat : Num<float>
    {
        public float Add(float x, float b) => x + y;
        public float Subtract(float x, float b) => x + y;
        ...
    }

Then we can see how a general function could be written to take any numeric type:

    public A DoubleIt<NumA, A>(A x) where NumA : struct, Num<A> =>
        default(NumA).Add(x, x);

The important bit is the NumA generic argument, and the constraint of struct, Num<A>. That allows us to call default(NumA) to get the type-class instance and invoke Add.

And so this can now be called by:

    int a    = DoubleIt<TInt, int>(5);        // 10
    double b = DoubleIt<TFloat, float>(5.25); // 10.5

By expanding the amount of operations that the Num<A> type-class can do, you can perform any numeric operation you like. If you like you can add new numeric types (say for complex numbers, or whatever), where the rules of the type are kept in the ad-hoc instance.

Luckily you don't need to do that, because I have created the Num<A> type (in the LanguageExt.TypeClasses namespace), as well as Floating<A> (with all of the operations from Math; like Sin, Cos, Exp, etc.). Num<A> also has a base-type of Arithmetic<A> which supports Plus, Subtract, Product, Negate. This is for types which don't need the full spec of the Num<A> type. I have also mapped all of the core numeric types to instances: TInt, TShort, TLong, TFloat, TDouble, TDecimal, TBigInt, etc. So it's possible to write truly generic numeric code once.

There's no getting around the fact that providing the class-instance in the generic arguments list is annoying (and later you'll see how annoying). The Roslyn team are looking into a type-classes like feature for a future version of C# (variously named: 'Concepts' or 'Shapes'). So this will I'm sure be rectified, and when it is, it will be implemented exactly as I am using them here.

Until then the pain of providing the generic arguments must continue. You do however get a super-powered C# in the mean-time.

The need to write this kind of super-generic code is rare; but when you need it, you need it - and right now this is simply the most powerful way.

Eq<A>

Next up is Eq<A>. Equality testing in C# is an absolute nightmare. From the different semantics of Eqauls and ==, to IEqualityComparer, and the enormous hack which is EqualityComparer.Default (which doesn't blow up at compile-time if your code is wrong).

The Eq<A> type-class looks like this:

    public interface Eq<A>
    {
        bool Equals(A x, A y);
        int GetHashCode(A x);
    }

There are Eq prefixed instances for all common types (EqInt, EqString, EqGuid etc.), as well as for all of the types in this library (EqLst, EqSet, EqTry, etc). All of the numeric types (TInt, TDouble, etc.) also implement Eq<A>.

To make it slightly prettier to use in code, you can use the Prelude equals function:

    bool x = equals<EqInt>(1, 1); // True

Or use default as shown before:

    bool x = default(EqInt).Equals(1, 1); // True

One final way is:

    bool x = EqInt.Inst.Equals(1, 1);

Inst is defined on all of the instances in lang-ext, but it's not an 'official feature'. Anybody could implement an ad-hoc implementation of Eq<A> and not provide an Inst.

For example you may call this directly:

    bool x = EqLst.Inst.Equals(List(1,2,3), List(1,2,3)); // true

Because you may be concerned about calling:

    bool x = List(1,2,3) == List(1,2,3); // ?

... as all C# programmers are at some point, because we have no idea most of the time whether == does what we think it should.

Just FYI List(1,2,3) == List(1,2,3) does work properly! As do all types in language-ext.

There are two variants of the immutable HashSet in language-ext:

    HashSet<A>
    HashSet<EqA, A> where EqA : struct, Eq<A>

What's interesting about the second one is that the equality definition is baked into the type. So this:

    HashSet<EqString, string> 

Is not compatible with:

    HashSet<EqStringOrdinalIgnoreCase, string> 

And if you think about that, it's right. The strings that are used as keys in the HashSet<EqString, string> do not have the same properties as the strings in HashSet<EqStringOrdinalIgnoreCase, string>. So even though they're both strings, they have different semantics (which cause wildly different behaviour for things like set intersection, unions, etc.)

Now compare that to HashSet<T> in the BCL, or ImmutableHashSet<T> in System.Collections.Immutable, where two different sets with different IEqualityComparer types injected will cause undefined results when used together.

That's hopefully a small glimpse into the potential for improving type-safeness in C#.

Ord<A>

Ord is for ordering. i.e. a IComparable replacement. By the way, these names Eq, Ord, Num, are all lifted from Haskell. I much prefer the short concise names that still convey meaning than the bulky and often clumsy names of the BCL.

This is Ord<A>, it derives from Eq<A>

    public interface Ord<A> : Eq<A>
    {
        int Compare(A x, A y);
    }

Usage should be self-explanatory now, but the important thing to note here is that because 'type classes' are just interfaces, they can also have an inheritance hierarchy.

This is a slightly more complex example:

    public struct OrdArray<ORD, A> : Ord<A[]>
        where ORD : struct, Ord<A>
    {
        public int Compare(A[] mx, A[] my)
        {
            if (ReferenceEquals(mx, my)) return 0;
            if (ReferenceEquals(mx, null)) return -1;
            if (ReferenceEquals(my, null)) return 1;

            var cmp = mx.Length.CompareTo(my.Length);
            if (cmp == 0)
            {
                for(var i = 0; i < mx.Length; i++)
                {
                    cmp = default(ORD).Compare(mx[i], my[i]);
                    if (cmp != 0) return cmp;
                }
                return 0;
            }
            else
            {
                return cmp;
            }
        }

        public bool Equals(A[] x, A[] y) =>
            default(EqArray<ORD, A>).Equals(x, y);

        public int GetHashCode(A[] x) =>
            hash(x);
    }

The OrdArray which is an Ord<A[]>, does itself also take an ORD generic argument, which allows the contents of the array to be compared:

    int x = OrdArray<TInt, int>.Inst.Compare(Array(1,2), Array(1,2)); // 0

Semigroup<A>

This is where we start going a little more abstract. Semigroups are a feature of category theory, which is soooo not important for this discussion. They represent an associative binary operation, which can be invoked by calling Append.

    public interface Semigroup<A>
    {
        A Append(A x, A y);
    }

Positive numbers (for example) form a semigroup. I won't dwell on it too long, because although the Append function is super-useful, nearly everything that falls into the Semigroup category is also a Monoid...

Monoid<A>

A monoid has something that a semigroup doesn't, and that's the concept of identity (often meaning 'empty' or 'zero'). It looks like this:

    public interface Monoid<A> : Semigroup<A>
    {
        A Empty();
    }

This comes with some helper functions in LanguageExt.TypeClass:

    public static partial class TypeClass
    {
        public static A mempty<MONOID, A>() where MONOID : struct, Monoid<A> =>
            default(MONOID).Empty();

        public static A mconcat<MONOID, A>(IEnumerable<A> xs) where MONOID : struct, Monoid<A> =>
            xs.Fold(mempty<MONOID, A>(), (s, x) => append<MONOID, A>(s, x));

        public static A mconcat<MONOID, A>(params A[] xs) where MONOID : struct, Monoid<A> =>
            xs.Fold(mempty<MONOID, A>(), (s, x) => append<MONOID, A>(s, x));
    }

Now the semigroup Append comes to life. Examples of monoids are: TInt, MLst, TString, etc. i.e.

    var x = mconcat<TString, string>("Hello", " ", "World");   // "Hello World"
    var y = mconcat<TLst<int>, Lst<int>>(List(1), List(2, 3)); // [1,2,3]
    var z = mconcat<TInt, int>(1, 2, 3, 4, 5);                 // 15

The Empty() function is what provides the identity value for the concat operations. So for string it's "", for Lst<T> it's [] and for int it's 0. So a monoid is a semigroup with a zero.

It's surprising how much stuff just starts working when you know your type is a monoid. For example in language-ext version 1 there is a monadic type called Writer<W, T>. The writer monad collects a log as well as returning the bound value. In version 1 the log had to be an IEnumerable<W>, which isn't super flexible. In language-ext version 2 the type looks like this:

    public class Writer<MonoidW, W, A> where MonoidW : struct, Monoid<W>
    {
        ...
    }

So now it can be a running numeric total, or a Lst<W>, or a Set<W>, or whatever monoid you dream up.

Higher-kinds

Higher-order polymorphism would allow us to define a type like so:

    public interface MyType<M<A>>
    {
        M<B> Foo<B>(M<A> ma);
    }

Where not only is the A parametric, but so it M. So for example if I wanted to implement MyType for Option<A> I could do:

    public class MyOptionType<A> : MyType<Option<A>>
    {
        public Option<B> Foo<B>(Option<A> ma) => ...;
    }

It would be soooo nice if C# (well, the immutable CLR) would support this. But it doesn't. So we need to find ways around it. The way I am using for language-ext is:

    public interface MyType<MA, A>
    {
        MB Foo<MB, B>(MA ma);
    }

    public class MyOptionType<A> : MyType<Option<A>, A>
    {
        public MB Foo<MB, B>(Option<A> ma) => ...;
    }

Monad

This is where some of the difficulties come in. How do we return an MB if we don't know what it is? This is a problem for the Monad type. This is a simplified version:

    public interface Monad<MA, A>
    {
        MB Bind<MB, B>(MA ma, Func<B, MB> bind);
        MA Return(A a);
        MA Fail(Exception e = null);
    }

Looking at the prototype for Bind it seems at first glance that the bind argument will give us the MB value we want. But an Option might be in a None state, in which case it shouldn't run bind.

    public MB Bind<MB, B>(Option<A> ma, Func<A, MB> bind) =>
        ma.IsSome
            ? bind(ma.Value)
            : ??? ; // What do we return here?

The key is to use constraints. But it also requires an extra generic paramter for Bind:

    public interface Monad<MA, A>
    {
        MB Bind<MonadB, MB, B>(MA ma, Func<B, MB> bind) 
            where MonadB : struct, Monad<MB, B>;

        MA Return(A a);
        MA Fail(Exception e = null);
    }

So we now know that MonadB is a class-instance of the Monad<MB, B> type-class. So we can now do this:

    public MB Bind<MB, B>(Option<A> ma, Func<A, MB> f) 
        where MonadB : struct, Monad<MB, B> =>
            ma.IsSome
                ? f(ma.Value)
                : default(MonadB).Fail();

The eagle eyed reader will notice that this actually allows binding to any resulting monad (not just Option<B>). I'm not an academic, but I'm sure there will be someone throwing their toys out of their prams at this point. However, it works, it's type-safe, and it's efficient.

The actual definition of Monad is more complex than this, in order to unify monadic types that take arguments (Reader and State) and monads that carry internal state (Writer and State), as well as to support asynchronous monads (TryAsync and TryOption). I won't muddy the waters too much right now, but unified and type-safe they are. There are no hacks.

You should see that the Return and Fail functions are trivial to implement:

    public Option<A> Return(A a) =>
        Optional(a);

    public Option<A> Fail(Exception e = null) =>
        None;

What that means is that any function that has been constrained by a monad instance can create new instances of them:

    public M CreateNewIntegerMonad<MonadInt, M, int>(int x) 
        where MonadInt : struct, Monad<M, int> =>
            default(MonadInt).Return(x);

This is one of the key breakthroughs. Imagine trying to create a Monad type the old way:

    public interface Monad<A>
    {
        Monad<B> Bind<B>(Func<A, Monad<B>> bind);
    }

    public class Option<A> : Monad<A>
    {
        public Monad<B> Bind<B>(Monad<A> ma, Func<A, Monad<B>> bind) =>
            IsSome
                ? bind(Value)
                : None;
    }

    public Monad<int> CreateNewIntegerMonad(int x) =>
        ????; // How?

Maybe we could parameterise it?

    public Monad<int> CreateNewIntegerMonad<M>(int x) where M : Monad<int> =>
        ????; // We still can't call new M(x)

But that doesn't work either because we still can't call new M(x). Being able to paramterise generic functions at the point where you know the concrete types (and therefore know the concrete class-instance) means that the generic functions can invoke the instance functions to create the concrete types.

Here's a super generic example of a function that takes two monad arguments, they're both of the same type, and their bound values are Num<A>.

    public static MA Add<MonadA, MA, NumA, A>(MA ma, MA mb)
        where MonadA  : struct, Monad<MA, A>
        where NumA    : struct, Num<A> =>
            default(MonadA).Bind<MonadA, MA, A>(ma, a =>
            default(MonadA).Bind<MonadA, MA, A>(mb, b =>
            default(MonadA).Return(default(NumA).Plus(a, b))));

You may notice that the two Bind calls followed by the Return are basically a much less attractive version of this:

        from a in ma
        from b in mb
        select default(NumA).Plus(a, b);

And so I can now add two options:

    var x = Some(10);
    var y = Some(20);
    var z = Option<int>.None;

    var r1 = Add<MOption<int>, Option<int>, TInt, int>(x, y); // Some(30)
    var r2 = Add<MOption<int>, Option<int>, TInt, int>(x, z); // None

    Assert.True(r1 == Some(30));
    Assert.True(r2 == None);

Or two lists:

    var x = List(1, 2, 3);
    var y = List(4, 5, 6);
    var z = List<int>();

    var r1 = Add<MLst<int>, Lst<int>, TInt, int>(x, y);
    var r2 = Add<MLst<int>, Lst<int>, TInt, int>(x, z);

    Assert.True(r1 == List(5, 6, 7,  6, 7, 8,  7, 8, 9));
    Assert.True(r2 == z);

Or any two monads. They will follow the built in rules for the type, and produce concrete values efficiently and without any boxing or dynamic casting.

Transformer types

Because using the super-generic stuff is hard, and most of the time not needed. I have kept the transformer types, but they're now implemented in terms of the instance types. There is a new MonadTrans type-class and a default instance called Trans.

For every pair of nested monads: Lst<Option<A>>, Try<Either<L, A>>, etc. there are the following extension methods (this is for Arr<Lst<A>>):

A SumT<NumA, A>(this Arr<Lst<A>> ma);

int CountT<A>(this Arr<Lst<A>> ma);

Arr<Lst<B>> BindT<A, B>(this Arr<Lst<A>> ma, Func<A, Lst<B>> f);

Lst<Arr<B>> Traverse<A, B>(this Arr<Lst<A>> ma, Func<A, B> f);

Lst<Arr<A>> Sequence<A>(this Arr<Lst<A>> ma);

Arr<Lst<B>> MapT<A, B>(this Arr<Lst<A>> ma, Func<A, B> f);

S FoldT<S, A>(this Arr<Lst<A>> ma, S state, Func<S, A, S> f);

S FoldBackT<S, A>(this Arr<Lst<A>> ma, S state, Func<S, A, S> f);

bool ExistsT<A>(this Arr<Lst<A>> ma, Func<A, bool> f);

bool ForAllT<A>(this Arr<Lst<A>> ma, Func<A, bool> f);

Unit IterT<A>(this Arr<Lst<A>> ma, Action<A> f);

Arr<Lst<A>> FilterT< A>(this Arr<Lst<A>> ma, Func<A, bool> pred);

Arr<Lst<A>> Where<A>(this Arr<Lst<A>> ma, Func<A, bool> pred);

Arr<Lst<A>> Select<A, B>(this Arr<Lst<A>> ma, Func<A, B> f);

Arr<Lst<C>> SelectMany<A, B, C>(
        this Arr<Lst<A>> ma,
        Func<A, Lst<B>> bind,
        Func<A, B, C> project);

Arr<Lst<A>> PlusT<NUM, A>(this Arr<Lst<A>> x, Arr<Lst<A>> y) where NUM : struct, Num<A>;

Arr<Lst<A>> SubtractT<NUM, A>(this Arr<Lst<A>> x, Arr<Lst<A>> y) where NUM : struct, Num<A>;

Arr<Lst<A>> ProductT<NUM, A>(this Arr<Lst<A>> x, Arr<Lst<A>> y) where NUM : struct, Num<A> =>
        ApplyT(default(NUM).Product, x, y);

Arr<Lst<A>> DivideT<NUM, A>(this Arr<Lst<A>> x, Arr<Lst<A>> y) where NUM : struct, Num<A>;

AppendT<SEMI, A>(this Arr<Lst<A>> x, Arr<Lst<A>> y) where SEMI : struct, Semigroup<A>;

int CompareT<ORD, A>(this Arr<Lst<A>> x, Arr<Lst<A>> y) where ORD : struct, Ord<A>;

bool EqualsT<EQ, A>(this Arr<Lst<A>> x, Arr<Lst<A>> y) where EQ : struct, Eq<A>;

Arr<Lst<A>> ApplyT<A, B>(this Func<A, B> fab, Arr<Lst<A>> fa);

Arr<Lst<C>> ApplyT<A, B, C>(this Func<A, B, C> fabc, Arr<Lst<A>> fa, Arr<Lst<A>> fb);

The number of functions has increased dramatically. Some of the special ones are Traverse and Sequence which flips the inner and outer types. So for example:

    Lst<Option<int>> x = List(Some(1), Some(2), Some(3), Some(4), Some(5));
    Option<Lst<int>> y = x.Sequence();

    Assert.True(y == Some(List(1, 2, 3, 4, 5)));

As you can see, the list is now inside the option.

    Lst<Option<int>> x = List(Some(1), Some(2), Some(3), None, Some(5));
    Option<Lst<int>> y = x.Sequence();

    Assert.True(y == None);

In this case there is a None in the Lst so when the Lst<Option<>> becomes a Option<Lst<>> the rules of the Option take over, and one None means all None.

This can be quite useful for Either:

    var x = List<Either<string, int>>(1, 2, 3, 4, "error");

    var y = x.Sequence();

    Assert.True(y.IsLeft && y == "error");

This collects the first error it finds, or returns Right if there is no error.

Traverse is the same as Sequence except it applies a mapping function to each bound value as it's transforming the types. Here's an example that runs 6 tasks in parallel, and collects their results:

    var start = DateTime.UtcNow;

    var f1 = Task.Run(() => { Thread.Sleep(3000); return 1; });
    var f2 = Task.Run(() => { Thread.Sleep(3000); return 2; });
    var f3 = Task.Run(() => { Thread.Sleep(3000); return 3; });
    var f4 = Task.Run(() => { Thread.Sleep(3000); return 4; });
    var f5 = Task.Run(() => { Thread.Sleep(3000); return 5; });
    var f6 = Task.Run(() => { Thread.Sleep(3000); return 6; });

    var res = await List(f1, f2, f3, f4, f5, f6).Traverse(x => x * 2);

    Assert.True(toSet(res) == Set(2, 4, 6, 8, 10, 12));

    var ms = (int)(DateTime.UtcNow - start).TotalMilliseconds;
    Assert.True(ms < 3500, $"Took {ms} ticks");

So there is a List of Tasks that becomes a single awaitable Task of List.

As well as the extensions, there are also static classes for the transformer types. There is one for each type of monad. So for example, Option has a LanguageExt.OptionT type. Whenever you have a pair of nested monads, and Option is the inner monad, then you would use OptionT:

    var ma = List(Some(1),Some(2),Some(3),Some(4),Some(5));

    var total = OptionT.foldT(ma, 0, (s, x) => s + x); // 15
    var total = OptionT.sumT<TInt, int>(ma); // 15
    var mb    = OptionT.filterT(ma, x > 3); // List(Some(3), Some(4))

I could go on endlessly about the new types. There are so many. But for the release notes I think I should wrap it up. It's worth taking a look at the API documentation for the type-classes and the instances

IL.Ctor

Although this doesn't really fit with the core message of the library, it is something used internally in the project, and because it's super useful, I've decided to make it public rather than private. There are 4 functions for building a Func<...,R> which invokes the constructor for a type.

    var ticks = new DateTime(2017, 1, 1).Ticks;

    // Builds a delegate to call new DateTime(long);
    var ctor = IL.Ctor<long, DateTime>();

    DateTime res = ctor(ticks);

    Assert.True(res.Ticks == ticks);

The generated delegate doesn't use reflection, IL is emitted directly. So invocation is as fast as calling new DateTime(ticks). The four Ctor functions are for up to four arguments.

The NewType system uses it to build a fast strongly-typed factory function:

    public abstract class NewType<NEWTYPE, A, PRED> :
        IEquatable<NEWTYPE>,
        IComparable<NEWTYPE>
        where PRED    : struct, Pred<A>
        where NEWTYPE : NewType<NEWTYPE, A, PRED>
    {
        protected readonly A Value;

        /// <summary>
        /// Constructor function
        /// </summary>
        public static readonly Func<A, NEWTYPE> New = IL.Ctor<A, NEWTYPE>();

        ...
    }

As you can see, it would be impossible to call new NEWTYPE(x) from the NewType base-class.

So for example:

   class Metres : NewType<Metres, float> 
   { 
       public Metres(float x) : base(x) {} 
   }

   var ms = Metres.New(100);

Nuget

• LanguageExt.Core
• LanguageExt.Parsec
• LanguageExt.FSharp