Language-ext: Help requested: unit tests for `Traverse`

[louthy]

An ongoing thorn in my side has been the behaviour of Traverse and Sequence for certain pairs of monadic types (when nested). These issues document some of the problems:

https://github.com/louthy/language-ext/issues/552
https://github.com/louthy/language-ext/issues/651

The Traverse and Sequence functions were previously auto-generated by a T4 template, because for 25 monads that's 25 * 25 * 2 = 1250 functions to write. In practice it's a bit less than that, because not all nested monads should have a Traverse and Sequence function, but it is in the many hundreds of functions.

Because the same issue kept popping up I decided to bite the bullet and write them all by hand. This has a number of benefits:

• The odd rules of various monads when paired can have bespoke code that makes more sense than any auto-generated T4 template could ever build. This fixes the bugs that keep being reported and removes the surprising nature of Traverse and Sequence working most of the time, but not in all cases.
• I'm able to hand-optimise each function based on what's most efficient for the monad pairing. This is especially powerful for working with Traverse and Sequence on list/sequence types. The generic T4 code-gen had to create singleton sequences and the concat them, which was super inefficient and could cause stack overflows. Often now I can pre-allocate an array and use a much faster imperative implementation with sequential memory access. Where possible I've tried to avoid nesting lambdas, again in the quest for performance but also to reduce the amount of GC objects created. I expect a major performance boost from these changes.
• The lazy stream types Seq and IEnumerable when paired with async types like Task, OptionAsync, etc. can now have bespoke behaviour to better handle the concurrency requirements (These types now have TraverseSerial and SequenceSerial which process tasks in a sequence one-at-a-time, and TraverseParallel and SequenceParallel which processes tasks in a sequence concurrently with a _window_ of running tasks - that means it's possible to stop the Traverse or Sequence operation from thrashing the scheduler.

Help

Those are all lovely things, but the problem with writing several hundred functions manually is that there's gonna be bugs in there, especially as I've implemented them in the most imperative way I can to get the max performance out of them.

I have just spent the past three days writing these functions, and frankly, it was pretty soul destroying experience - the idea of writing several thousand unit tests fills me with dread; and so if any of you lovely people would like to jump in and help build some unit tests then I would be eternally grateful.

Sharing the load on this one would make sense. If you've never contributed to an open-source project before then this is a really good place to start!

I have...

• Released the updates in 3.4.14-beta - so if you have unit tests that use Traverse and Sequence then any feedback on the stability of your tests would be really helpful.
• Created a github project for managing the cards of each file that needs unit tests. It's the first time using this, so not sure of its capabilities yet, but it would be great to assign a card to someone so work doesn't end up being doubled up.
• The code is in the hand-written-traverse branch.
• The folder with all the functions is transformers/traverse

Things to know

• Traverse and Sequence take a nested monadic type of the form MonadOuter<MonadInner<A>> and flips it so the result is MonadInner<MonadOuter<A>>
• If the outer-type is in a fail state then usually the inner value's fail state is returned. i.e. Try<Option<A>> would return Option<Try<A>>.None if the outer Try was in a Fail state.
• If the inner-type is in a fail state then usually that short-cuts any operation. For example Seq<Option<A>> would return an Option<Seq<A>>.None if any of the Options in the Seq were None.
• Where possible I've tried to rescue a fail value where the old system returned Bottom. For example: Either<Error, Try<A>>. The new system now knows that the language-ext Error type contains an Exception and can therefore be used when constructing Try<Either<Error, A>>
• All async pairings are eagerly consumed, even when using Seq or IEnumerable. Seq and IEnumerable do have windows for throttling the consumption though.
• Option combined with other types that have an error value (like Option<Try<A>>, Option<Either<L, R>>, etc.) will put None into the resulting type (Try<Option<A>>(None), Either<L, Option<A>>(None) if the outer type is None - this is because there is no error value to construct an Exception or L value - and so the only option is to either return Bottom or a success value with None in it, which I think is slightly more useful. This behaviour is different from the old system. _This decision is up for debate, and I'm happy to have it - the choices are: remove the pairing altogether (so there is no Traverse or Sequence for those types) or return None as described above_

Obviously, it helps if you understand this code, what it does and how it should work. I'll make some initial tests over the next few days as guidance.

[louthy]

Latest beta is up.

Some example unit tests

[iamim]

Hi,
I'd love to help! Pretty sure I could carve out a couple of hours in my weekend. Is it possible to assign monads so that there's no overlap between different contributors?

[louthy]

@iamim Are you able to see the project cards? https://github.com/louthy/language-ext/projects/1

Pick one from there, if you can move it to In Progress, that's great, if not just put the name of the monad here.

The jobs are listed by _inner monad_. i.e. M<INNER<A>>, so Seq means Try<Seq<A>>, Option<Seq<A>>, Identity<Seq<A>>, etc...

[louthy]

v3.4.16-beta available now.

Option, OptionUnsafe, Either, EitherUnsafe, and Try now fully tested as the inner monad for:

Arr, HashSet, IEnumerable, Lst, Que, Seq, Set, Stck, Either, EitherUnsafe, Identity, Option, OptionUnsafe, Try, TryOption, Validation.

247 unit tests for the traverse functions so far, about 1/5th of the way through. I've had to make some minor bug fixes along the way, but it's mostly looking pretty good.

[harrhp]

taking SeqT card (can't move it to in progress)
https://github.com/louthy/language-ext/projects/1#card-34099493

[iamim]

I started on Lst

[iamim]

Is it common to consider the empty state for collection types a success case? I'm not sure this is intuitive to me:

[Fact]
public void EmptyArrIsSomeEmptyArr()
{
    Arr<Option<int>> ma = Empty;

    var mb = ma.Sequence();

    Assert.True(mb == Some(Arr<int>.Empty));
}

[iamim]

Some thoughts out loud: I'm not aware of such a rule, but it makes sense for Sequence between Out<In<T>> and In<Out<T>> to be inverses of each other, e.g. result in the same value when composed. In the case above, staring with Option<Arr<int>>.None and chaining Sequence twice we end up with Some.
Again, I'm not 100% sure whether this concern is legit but it feels very "category theory"-y.

[louthy]

Is it common to consider the empty state for collection types a success case? I'm not sure this is intuitive to me

Yep, I was going to change that, and had already done it for some of the other types. My original thought was to try and maintain a value where a 'zero state' looked usable, but as you say it's not always intuitive.

A crude imaginary generic C# way to think about this would be:

```c#
MY> Traverse(MX> ma, Func f) =>
ma == MX>.Zero
? MY>.Zero
: reduce(ma.Head(), ma.Tail(), (state, x) => from a in state
from b in x
select MY>.PlusT(a, b));

> `Head` and `Tail` are just ways of showing that we can somehow iterate all of the items in the transformer type.  

So for your example, the starting state for an empty `Arr<Option<A>>` would be `Option<Arr<B>>.Zero`.  For a non-empty `Arr<Option<A>>` would use the head value and fold using the standard binding rules of the outer option to apply.  So, as long as the values with the `Arr` were `Some` then the result will be `Some`, otherwise `None`.

> Some thoughts out loud: I'm not aware of such a rule, but it makes sense for Sequence between Out<In<T>> and In<Out<T>> to be inverses of each other, e.g. result in the same value when composed.

That's just not always possible, because some operations are destructive (non-injective surjection).  A collection of `None` will turn into a None, the size of the original collection can't survive that.

Even if we maintained an inner value, what would those values be? 
```c#
    Seq(None, None, None) -> Some(Seq(?, ? ?))

The behaviour of Sequence and Traverse has always been to apply the rules of the monad over and over for each item, and so anything where the values collapse will not be bijective, so there's no realistic expectation for them to be isomorphic.

[louthy]

One thing to think about though is whether MX<MY<A>>.Zero should be effectively MX<MY<A>>.ZeroT - i.e. a new zero for each pairing. zero doesn't work for Either for example, it is bottom, because there's no way to construct a L or R value when one doesn't exist. However, Either<L, Seq<R>> has a usable zero: Right(Seq.Empty). This is what I've done so far, but I'm not 100% sure it's the best approach.

The options are:

• Accept the outer monad's version of zero - which would cause bottom values for empty sequences with Eithers or Validations
• Accept there should be a transformer-type zero, which is unique to each pairing, that would give you Right(Seq.Empty) (this is what we have now)
• Remove the function where bottom could be returned, but that leads to a real loss of useful functionality

[louthy]

Thinking more about it, I think the current way is probably right. The pseudo code would be:
```c#
MY> Traverse(MX> ma, Func f) =>
ma.FoldT(MY>.ZeroT, ma, (state, x) =>
from a in state
from b in x
select MY>.PlusT(a, f(b)));

The only question when a transformer-type would have two valid `zero` states (as in your example):
```c#
    Option<Arr<A>>.None
    Option<Arr<A>>.Some(Arr.Empty)

Which one would be the correct choice? If it's consistent with Either, then Some(Empty) would be the way to go.

I will fire up some tests in Haskell, in case this is way off, but I think it makes sense.

[louthy]

Ok, so in Haskell (the arrows -----> represent the sequence operation):

    [] :: [Maybe Int]  ----->  Just []
    [] :: [Either String Int]  ----->  Right []

So, empty outer-lists always become success values. In C# it would be:
```c#
Seq>(Empty) -----> Some(Seq.Empty)
Seq>(Empty) -----> Right(Seq.Empty)

So, this _is_ how lang-ext traverse works now.

When there are fail values in the sequence:
```haskell
    [Just 1, None]  ----->  Nothing
    [Right 1, Left "fail"]  ----->  Left "fail"

This _is_ how the lang-ext versions work.

When the sequence is inner and the outer is a fail:

    Nothing :: Maybe [Int]  ----->  [Nothing]
    Left "fail" :: Either String [Int]  ----->  [Left "fail"]

So, the fail value is in a singleton sequence afterwards. This is not how the lang-ext ones work at the moment, they return an empty sequence. So, I'll update those.

[louthy]

A couple of updates:

• All types that have a fail state when they're the outer monad will now create a singleton collection with the failed value in it when the inner type is a collection (the last example in the Haskell comparison above)
• Nested collections (like Lst<Seq<A>>) now find all combinations of the sequences and return those. This was the previous functionality, but I'd got my hand-written ones wrong and had essentially just done a functor map.

3.4.17-beta on nu-get now.

[louthy]

@iamim @harrhp I have added unit tests for HashSet which should be a good reference for Seq and Lst.

[harrhp]

taking ArrT
https://github.com/louthy/language-ext/projects/1#card-34099377

[louthy]

@harrhp @iamim NOTE: Some changes have just gone in that might affect what you're doing (shouldn't, but it's worth resyncing if you haven't for a while). Mostly, it's just finishing the job of where ma is in a failed state, it should always return Return(ma.Fail). Again, this is to align it with the behaviour in Haskell.

[iamim]

starting on Set

[iamim]

Started getting lots of System.ArgumentException: At least one object must implement IComparable. Could you point me to where I should look to fix it?
It happens while traversing Outer<Set<T>> and adding Outer<T> to the new Set.

[louthy]

@iamim > Started getting lots of System.ArgumentException: At least one object must implement IComparable. Could you point me to where I should look to fix it?

When you get that, you can't do the test because OrdDefault can't find the default ordering type.

What I've done is to write the desired tests and then comment them out with a TODO message:

https://github.com/louthy/language-ext/blob/hand-written-traverse/LanguageExt.Tests/Transformer/Traverse/HashSet/Collections/Set.cs#L24

These functions wouldn't have worked on the old system either. It is desirable to have this working, but it's a much larger job, so I'd prefer to keep it focussed for now.

[iamim]

Ok, will do that too.

[dancrn]

@louthy might it be possible to generate tests with T4? not quite sure how that'd work in practise, especially if there is some specialised behaviour..

also, i think me and some of my colleagues owe you a beer or two (we use LanguageExt a _lot_) - we're just outside of the city by old street!

[louthy]

might it be possible to generate tests with T4

I think there's a fair amount of common code for sure, but it's pretty awkward building T4 templates for this (if you look at the current T4 templates for generating the HKTs they're pretty damn ugly, and although they could be better, I wouldn't fell particularly confident that the tests were good if I used T4).

This change to the hand-written Traverse functions has definitely been painful, but building the tests by hand is giving me much more confidence that parity between lang-ext Traverse and Sequence and the traverse and sequence in Haskell is there. It's also highlighting some missing stuff from the rest of the library so it's nice to fill all that in.

also, i think me and some of my colleagues owe you a beer or two (we use LanguageExt a lot) - we're just outside of the city by old street!

I'll take you up on that! My office is at New Broad Street by Liverpool St. Station. Probs won't be in town for a bit though, so towards the end of the month/early next month would work, drop me an email [email protected] 👍

Funnily enough, I was going to suggest everybody who uses language-ext was going to owe me a beer after this week ;-)

[louthy]

@iamim @harrhp Heads up re: HashSet - I have fixed the @iamim 's HashSet<Lst<>> test, and left a comment.

HashSet ordering can never be guaranteed, so sorting the results is what _should_ be done. If the hashing algorithm changes in future, then any assumptions on ordering would cause the tests to fail.

There does seem to be some non-deterministic behaviour in .NET Framework though - so I will need to investigate why that is after the tests have been built. If it's deterministic within the process then it's nothing to worry about, but if not then there could be real problems for HashSet equality, ordering, etc.

[louthy]

@harrhp Well spotted. I was going to optimise that a bit more anyway, so I'll stick it on the list.

@iamim @harrhp Don't take any of the Async types yet. I'm working on a new equality system that will allow for asynchronous nested equality, i.e.
```c#
var ma = SomeAsync(TryAsync(1));
var mb = SomeAsync(TryAsync(1));

var mr = await (ma == mb);  // True

```
I'm trying to generalise it so that any level of nested async types will work and also allow the inner type to be a synchronous type. That should make it much easier to build the Async tests, but also be a really nice feature.

[harrhp]

taking QueT
https://github.com/louthy/language-ext/projects/1#card-34099474

[harrhp]

taking IEnumerableT
https://github.com/louthy/language-ext/projects/1#card-34099422

[harrhp]

hit some bug when comparing Seq<IEnumerable<T>> or constructing HashSet<IEnumerable<T>>

System.NullReferenceException : Object reference not set to an instance of an object.
   at LanguageExt.ClassInstances.EqDefault`1.Equals(A a, A b) in C:\Users\Skobka\Documents\git\language-ext\LanguageExt.Core\ClassInstances\Eq\EqDefault.cs:line 38
   at LanguageExt.Seq`1.Equals[EqA](Seq`1 rhs) in C:\Users\Skobka\Documents\git\language-ext\LanguageExt.Core\DataTypes\Seq\Seq.cs:line 817
   at LanguageExt.Tests.Transformer.Traverse.IEnumerableT.Collections.IEnumerableIEnumerable.IEnumerableIEnumerableCrossProduct() in C:\Users\Skobka\Documents\git\language-ext\LanguageExt.Tests\Transformer\Traverse\IEnumerable\Collections\IEnumerable.cs:line 41

source exception

at LanguageExt.ClassInstances.ClassFunctions.GetTypeInfo[A]() in C:\Users\Skobka\Documents\git\language-ext\LanguageExt.Core\ClassInstances\ClassFunctions\ClassFunctions.cs:line 31

because typeA.BaseType returns null for typeA=IEnumerable

[louthy]

hit some bug when comparing Seq> or constructing HashSet>

Fixed.

[louthy]

The first async type now has unit tests (OptionAsync), which can be used as a template for the rest.

It was pretty painful updating the Hashable, Eq, and Ord system to support asynchrony but it's massively worth it.

Being able to await equality of two nested async types is pretty fabulous functionality and really takes the functionality of language-ext beyond the inheritance model of IEquatable and overridden Equals:
```c#
var ma = TryAsync(SomeAsync(1234));
var mb = ma.Sequence();
var mc = SomeAsync(TryAsync(1234));

var mr = await (mb == mc);

It will also work when a synchronous type is nested within an `async` type:
```c#
    var ma = Some(SomeAsync(1234));
    var mb = ma.Sequence();
    var mc = SomeAsync(Some(1234));

    var mr = await (mb == mc);

Along with the significant improvement in the resolution of EqDefault, OrdDefault, HashableDefault (and the new EqDefaultAsync, OrdDefaultAsync, HashableDefaultAsync) means major improvements for structural equality of records and unions, it also allows the commented out/skipped HashSet and Set unit-tests to be re-added, because EqSet<A>, OrdSet<A>, EqHashSet<A>, and OrdHashSet<A> can now be resolved.

Finally, the resolvers look for more than HashableX when resolving a type. For Hashable it looks for HashableX, then EqX, then OrdX as they all support GetHashCode.

[louthy]

3.4.18-beta on nu-get now

[iamim]

This is awesome! I'll try to finish the inner types that I started with Async<Sync<T>> as soon as I can and pick up some leftover cases if any are left.
By the way, is there a wiki or something where I can read more about the automatic type-class resolution?

[louthy]

wiki

Not yet, no. I was thinking of putting something together before the full release. There’s a few more things I’d like to improve (to generalise it for all type-classes), that I’ll start on once the traverse work is complete.

[iamim]

I guess Async<Sync<T>> is not that useful to turn inside-out and that's why it doesn't have Traverse?

[louthy]

Sorry, yep I should have picked up on that when you mentioned it earlier. If there was an async value inside a sync value then all access to the inside value would be via the sync value's non-async methods. Which would force the evaluation of the asynchronous values (through Task.Result), and that's bad.

If the sync types had async methods that might be a different story, but that would get messy very quickly and all of the sync methods would have time-bombs/potential deadlocks in. So, it's best to not do it at all.

Sync can become async (via x.AsTask()), but not the other way around.

[louthy]

3.4.19-beta released

[iamim]

It's been a busy week. I hope to get back to it this weekend.

[louthy]

@iamim No worries, it has been for me too, I've definitely been slowing down as I run out of energy somewhat - although that's probably more to do with my coffee machine breaking this week ;-)

Thanks for the support! 👍

[louthy]

3.4.20-beta released

[harrhp]

taking TryOptionT
https://github.com/louthy/language-ext/projects/1#card-34099531

[blakeSaucier]

Hi - hope everyone is staying in good health. I have some extra time these days and would be happy to help. I'll start with Identity. Doesn't look like I can move the card.

[louthy]

Thanks @blakeSaucier , card assigned 👍

[blakeSaucier]

Working on Traverse tests for Validation

[blakeSaucier]

Question for Either Validation Traverse implementation:

My understanding is the Traverse will wrap the Left in a success:
```C#
var ma = Left>(Error.New("alt"));
var mb = ma.Sequence();
var mc = Success>(Left(Error.New("alt")));
Assert.Equal(mc, mb);

The above test fails but the following will pass:
```C#
        var ma = Left<Error, Validation<Error, int>>(Error.New("alt"));
        var mb = ma.Sequence();
        var mc = Fail<Error, Either<Error, int>>(Error.New("alt"));
        Assert.Equal(mc, mb);

Is this correct? It seems inconsistent with the other Traverse implementations I'm looking at.

Thanks

[louthy]

If it’s inconsistent, it’s wrong.

The hand written implementations were done very quickly, hence the need for the tests :) So, expect inconsistencies and look to other similar implementations to fix.