lefts and rights helpers for Either

[Profpatsch]

I am direly missing these functions from Haskell (http://hackage.haskell.org/package/base-4.8.1.0/docs/src/Data.Either.html#lefts).

I’m not sure how to implement them here, since Haskell uses some kind of partial pattern match magic predicates.

I’m generally not too convinced by the asymmetry of Either. In particular the IfLeft/IfRight functions are preferring Right so much that there is practically no chance to extract a left value. Maybe I’m missing the obvious way of doing it.

The following is as far as I came; it doesn’t compile though, because lout might not be instanced (as far as the compiler is concerned).

        public static class EitherExtensions<L, R>
        {
            private static IEnumerable<L> Lefts(this IEnumerable<Either<L, R>> eis)
            {
                return eis.Filter(ei => ei.IsLeft).Map(ei =>
                {
                    L lout;
                    ei.Match(
                        Right: r => { return; },
                        Left: l => { lout = l; });
                    return lout;
                });
            }
        }

[fazouane-marouane]

Hi,

So I just happen to pass by this awesome project and saw your issue. It's actually quite simple to solve. You can first transform your IEnumerable<Either<L,R>> into a IEnumerable<IEnumerable<L>> then join the bits to get a single IEnumerable<L>

Here are two possible working implementations

    public static class EitherExtensions
    {

        private static IEnumerable<L> Lefts<L, R>(this IEnumerable<Either<L, R>> eis)
        {
            return eis
                .Map(ei => ei.Match(Left: l => List(l), Right: r => LanguageExt.List.empty<L>())) // map Left l to [l] and Right _ to []
                .Fold(LanguageExt.List.empty<L>(), (acc, l) => acc.AddRange(l)); // join them
        }

        private static IEnumerable<L> Lefts2<L, R>(this IEnumerable<Either<L, R>> eis)
        {
            return eis
                .Map(ei => ei.Match(Left: l => Enumerable.Repeat(l,1), Right: r => Enumerable.Empty<L>())) // map Left l to [l] and Right _ to []
                .Aggregate((acc, l) => acc.Concat(l)); // join them
        }
    }

[Profpatsch]

You are right, that’s how list expressions work in Haskell. https://www.haskell.org/onlinereport/exps.html#sect3.11

[louthy]

Thanks @fazouane-marouane I'll add that to the project (and rights). It could be more optimal by using imperative constructs internally, so I'll go that route.

I will also add lefts and rights to Prelude so it can be used fluently and functionally.

@Profpatsch - please keep any suggestions coming.

[Profpatsch]

Does it perform, though? It builds a new Lst for each element and then joins them back together. I’m sure ghc can optimize this, but can C#?

Update: Ah, @louthy, didn’t see your answer. Yes, imperatively updating the list is going to perform better.

[louthy]

It wouldn't be great, no. So the implementation I have done is:

    public static IEnumerable<L> Lefts<L, R>(this IEnumerable<Either<L, R>> self)
    {
        foreach (var item in self)
        {
            if (item.IsLeft)
            {
                yield return item.LeftValue;
            }
        }
    }

And similar for Rights. This imperative loop is the quickest way of yielding the results, but also it's lazy (if you don't know C# too well, yield is a coroutines system which works in tandem with foreach via the IEnumerator interface).

I have just done a check-in with updates based on your suggestions:

• Rights and Lefts extension methods for IEnumerable<Either<L,R>> and IEnumerable<EitherUnsafe<L,R>>
• rights and lefts static methods in Prelude
• partition function that returns a tuple of lefts and rights
• More variants of ifLeft and ifRight
• Left variants of iter, forall, fold, exists, map, bind and filter

Note, the LINQ functions Where, Select and SelectMany will continue to be biased toward Right and will early-out when an Either is in a Left or Bottom state.

It's getting a bit late here (2 am), so I will do a nuget release tomorrow with these updates. So if you want them sooner you'll need to build from source.

[Profpatsch]

That’s wonderful, thanks!

If you wanted to take it further you’d introduce Bifunctors as in https://hackage.haskell.org/package/bifunctors-5/docs/Data-Bifunctor.html, that would generalize the mapping over two arguments and reduce redundant functions a bit (if it’s possible with the type system). Of course—as Edward Kmett constantly demonstrates—this game can be played ad infintum.

[louthy]

if it’s possible with the type system

A lot of the reason for language-ext is to 'cheat' the type-system in C#. Unfortunately it's not possible to do higher-kinded polymorphism, so much of this library is doing manually what the GHC does automatically. It means a hell of a lot of typing unfortunately, but I figured if one person does it once for the most commonly used aspects of functional programming then we all win.

If you wanted to take it further you’d introduce Bifunctors

Yep, I was actually considering it last night when going through the changes from your original suggestion. It hadn't quite cleared in my mind the best way to do it, but actually it's relatively simple. So, if you grab the latest source there's now bifunctor, bifoldable, bitraversable, ... support for Either and EitherUnsafe. Again it's been a manual process rather than being able to define a bifunctor typeclass, but that's just the way it is.

So there are now variants of (overloaded functions with the same names):

iter map fold filter bind forall exists

They all now take two functions Right and Left, so you can write them in a similar style to match (using named arguments) for clarity:

    var res = map(either, 
                  Right: r => ..., 
                  Left: l => ... );

Or fluently

    var res = either.Map( Right: r => ..., 
                          Left: l => ... );

You might find you'll have to specify the type-arguments more than you'd like, because C#s type-inference isn't too hot.

Actually, I hope you don't mind me asking: if you've come from a Haskell background why didn't you go straight to F# rather than C#? You still have limitations of the .NET type-system (so no type-classes), but the type-inference system is soooo much better.

[louthy]

As an additional to my comment above, I have added transformer functions for IEnumerable<Either<L,R>> and IEnumerable<EitherUnsafe<L,R>>. They are:

iterT forallT foldT existsT mapT bindT filterT

The transformer functions for all of the other monads are auto-generated by the HKT T4 template. But it's a bit of a ramshackle system that isn't super flexible, and therefore can't handle variants for Left and bifunctors. So for those behaviours I need to add them manually. If you need any other combination of monads let me know.

[Profpatsch]

Haha, that’s super great!

if you've come from a Haskell background why didn't you go straight to F# rather than C#?

I’m fixing bugs and improving a small C# codebase and originally just wanted a Maybe and an Either type because I loathe the null- and exception-passing style. Maybe it escalated a little …

[louthy]

@Profpatsch

Maybe it escalated a little …

Heh, always the way! Please feel free to raise anything else you're missing. Mostly people come to this project as C# guys who have 'seen the light' and want to use functional techniques in a language that fights them; so most requests I get are from that perspective.

Having a Haskell guy coming from the other direction is valuable to me, because although I have used Haskell, I have only used it for a few small projects (F# is my go-to functional language now, because although not as nice as Haskell it hits a number of sweet-spots, especially on the interop front).

The Either requests are a good example of a blind spot that I'd had (I think those blind spots exist in the F# implementations too - although I'd need to check).

[Profpatsch]

Ah, I see. I can only describe myself as “aspiring Haskeller”, since I’m still missing a lot of coding experience.

But understanding the concepts goes a long way, too, as I noticed (currently working in Scala for my bachelor’s, and C# for work and using the stuff everywhere).

[louthy]

Agreed. My other github project: csharp-monad was my first attempt at a general case functional library, but I got a little bit caught in the monad trap and the Haskell laziness idea. Monads are super useful obviously, but there's not really enough grammar in LINQ to make them as nice to use as in Haskell (or indeed F#). So you can only get so far. That's where this project was born from, trying to get a lot of the other fundamentals right.

One valuable part of it though was the time spent porting the Haskell parsec library; that really opened my eyes. I'll bring an improved version of that over to LangExt at some point too.

https://github.com/louthy/csharp-monad/tree/master/CSharpMonad/src/parsec

[Profpatsch]

Oh, I found another guide for Try in Scala: http://danielwestheide.com/blog/2012/12/26/the-neophytes-guide-to-scala-part-6-error-handling-with-try.html

How compatible is that with this Try type?

[louthy]

Very compatible!

From the source in the blog:

    val url = parseURL(Console.readLine("URL: ")) getOrElse new URL("http://duckduckgo.com")

Would be:

    var url = parseURL(Console.ReadLine("URL: ")).IfFail(new URL("http://duckduckgo.com"));

Next example:

    parseURL("http://danielwestheide.com").map(_.getProtocol)
    // results in Success("http")
    parseURL("garbage").map(_.getProtocol)
    // results in Failure(java.net.MalformedURLException: no protocol: garbage)

Would be:

    parseURL("http://danielwestheide.com").Map(GetProtocol);
    parseURL("garbage").Map(GetProtocol);

Or you could use LINQ:

    var result = from x in parseURL("http://danielwestheide.com")
                 select GetProtocol(x);

Next example (flatMap):

    def inputStreamForURL(url: String): Try[InputStream] = parseURL(url).flatMap { u =>
      Try(u.openConnection()).flatMap(conn => Try(conn.getInputStream))
    }

Use LINQ for this:

    Try<InputStream> inputStreamForURL(string url) =>
        from u    in parseURL(url)
        from conn in u.openConnection()
        from str  in conn.getInputString()
        select str;

Next example (filtering):

    def parseHttpURL(url: String) = parseURL(url).filter(_.getProtocol == "http")
    parseHttpURL("http://apache.openmirror.de") // results in a Success[URL]
    parseHttpURL("ftp://mirror.netcologne.de/apache.org") // results in a Failure[URL]

Becomes:

    Try<URL> parseHttpURL(string url) => parseURL(url).Filter(x => GetProtocol(x) == "http");

Or with LINQ:

    Try<URL> parseHttpURL(string url) =>
        from x in parseURL(url)
        where GetProtocol(x) == "http"
        select x;

Next example (iteration):

    parseHttpURL("http://danielwestheide.com").foreach(println)

Becomes:

    // For writing the inner value 'as-is' 
    parseHttpURL("http://danielwestheide.com").Iter(Console.WriteLine);

    // For transforming the inner value (if it's a Try<Lst<T>> for example)
    parseHttpURL("http://danielwestheide.com").IterT(Console.WriteLine);

Next example (comprehensions):

    import scala.io.Source
    def getURLContent(url: String): Try[Iterator[String]] =
      for {
        url <- parseURL(url)
        connection <- Try(url.openConnection())
        is <- Try(connection.getInputStream)
        source = Source.fromInputStream(is)
      } yield source.getLines()

Use LINQ for the most elegant looking code:

    Try<IEnumerable<string>> getURLContent(string url) =>
        from u      in parseURL(url)
        from conn   in u.openConnection()
        from str    in conn.getInputStream()
        from source in str.fromInputStream()
        from lines  in source.getLines()
        from line   in lines
        select line;

Next example (pattern matching):

    getURLContent("http://danielwestheide.com/foobar") match {
      case Success(lines) => lines.foreach(println)
      case Failure(ex) => println(s"Problem rendering URL content: ${ex.getMessage}")
    }

Becomes:

    getURLContent("http://danielwestheide.com/foobar").Match(
        Succ: lines => lines.Iter(Console.WriteLine),
        Fail: ex    => Console.WriteLine(ex.Message)
    );

Or more functionally:

    match( getURLContent("http://danielwestheide.com/foobar",
           Succ: lines => lines.Iter(Console.WriteLine),
           Fail: ex    => Console.WriteLine(ex.Message)
    );

Next example, recovering from failure:

    import java.net.MalformedURLException
    import java.io.FileNotFoundException
    val content = getURLContent("garbage") recover {
      case e: FileNotFoundException => Iterator("Requested page does not exist")
      case e: MalformedURLException => Iterator("Please make sure to enter a valid URL")
      case _ => Iterator("An unexpected error has occurred. We are so sorry!")
    }

Becomes:

    var content = getURLContent("").IfFail()
         .With<FileNotFoundException>(_ => List("Requested page does not exist"))
         .With<MalformedURLException>(_ => List("Please make sure to enter a valid URL"))
         .Otherwise(_ => List("An unexpected error has occurred. We are so sorry!"));

Get the latest source for the last example to work, I streamlined the matching process.

[louthy]

By the way, on the getURLContent example from above there is no clean-up of the system resources that would be acquired by opening connections or streams (which appears to be an issue in the Scala version also):

    Try<IEnumerable<string>> getURLContent(string url) =>
      from u      in parseURL(url)
      from conn   in u.openConnection()
      from str    in conn.getInputStream()
      from source in str.fromInputStream()
      from lines  in source.getLines()
      from line   in lines
      select line;

So, to deal with that, there's a use function for Try<T> and TryOption<T> (I will add the other monads soon) that wraps the monad value in a LinqDisposable object (so Try<Foo> becomes Try<LinqDisposable<Foo>>. Then the Select and SelectMany implemetations (which facilitate LINQ) look for LinqDisposable and deal with the clean-up accordingly. You need to use the Value property to get to the underlying value:

    Try<IEnumerable<string>> getURLContent(string url) =>
        from u      in parseURL(url)
        from conn   in u.openConnection()
        from str    in use(conn.getInputStream())
        from source in use(str.Value.fromInputStream())
        from lines  in source.Value.getLines()
        from line   in lines
        select line;

It's certainly not quite as pretty, but required for safe clean-up.

[Profpatsch]

Use LINQ for this:

There is a monadic notation in Scala, too, something like:

for {
  a <- monadicValue1
  b <- mval2
} yield { a + b }

Then there’s LINQ and do-notation in Haskell. I still like Haskell’s version the most, though.

[Profpatsch]

It's certainly not quite as pretty, but required for safe clean-up.

I know this as with pattern from Python. I use http://jsuereth.com/scala-arm/ for my current Scala project, that does the same. In Haskell normally these things are wrapped in a custom Monad in my experience, but probably a similar pattern exists.

[louthy]

In Haskell normally these things are wrapped in a custom Monad in my experience

I could do that here, but it would involve creating transformer monads for all of the existing monads, which is quite a lot of effort; having to manually unwrap via .Value is the least worst alternative I think.

F#'s computation expressions has the use keyword (and the ability to override its behaviour on a monad by monad basis). Hopefully C# will get some more LINQ grammar in the future (or extensible grammar like in F#)

[Profpatsch]

I think the with pattern is absolutely fine.

[gordonwatts]

I have been watching this conversation for a while now. I agree it would be great to upgrade the way C# handles monads. The C# team seems pretty serious about taking ideas from the community - their GitHub is full of proposals and what looks like serious conversation after they are made. The road into the language, of course, is a bit longer. So I'd encourage us all to propose ideas. In some other work I've been doing I have been stuck in monad hell (as I call it - having to write "var newvalue = from x in monad1 from y in monand2 x + y;" over and over again, obscuring the simple "+" operator which is what is important), and I can't help but wonder if one couldn't write something much simpler that using the pre-existing LINQ infrastructure but hides all the "from x in monad1" code. The issues you've been discussing above would probably require a little more, but I'd urge you not to shy away from putting together a proposal.

[louthy]

@gordonwatts - I agree mostly with what you're saying. I think if C# were to implement computation expressions in pretty much the same way as F# then life would be good. I think I saw some proposal on the Rosyln project for this already actually. However it doesn't seem to be a priority for C#7 (and their current priorities of pattern matching, record types, tuple support, and fixing the null problem would definitely be my preferred items for them to tackle).

Moslty I like the LINQ syntax, from x in y is the same as x <- y in Haskell, or let! x = y in F#. I think combined with let and the additional 'operators' in LangExt (like Map, Fold, etc. and the overridden logical or operator) you can get most of the way to what's needed. The big one I miss is do.

having to write "var newvalue = from x in monad1 from y in monand2 x + y;" over and over again, obscuring the simple "+" operator which is what is important

Perhaps the new applicative work that's currently going on in the Applicative branch will help? i.e.

    var x = Some(10);
    var y = Some(20);

    var z = Some((int a,int b) => a + b).Apply(x,y);

Not sure it's much better than:

    var z = from a in x
            from b in y
            select a + b;

But I guess it depends on the use-case. For a simple addition perhaps not, but for something more complex, maybe. Especially if you already have a function defined, i.e.:

    var z = Some(ComplexFunction).Apply(x,y);

If you're mostly working with numbers, I was considering putting in a load of operator overloads for the standard arithmetic operators. Then you could truly do:

    var x = Some(10);
    var y = Some(20);

    var z = x + y;

Let me know if any of that would be useful to you (or whether you were just using that as an example). It would require some heavy lifting underneath however.

but I'd urge you not to shy away from putting together a proposal.

I'd love to, but it's a heck of a lot of work considering all of the implications of new language features. I'm personally very short of free time at the moment unfortunately, and seeing as it doesn't look like it's on the radar at the moment, could be wasted effort.

[louthy]

@gordonwatts Just to follow up on my last email, if you grab the latest source then you can now do this for numeric values:

    var x = Some(10);
    var y = Some(20);
    var z = x + y;   // Some(30)

And strings:

    var x = Some("Hello");
    var y = Some(" ");
    var z = Some("World");
    var r = x + y + z;   // Some("Hello World")

And lists:

    var x = Some(List(1,2,3));
    var y = Some(List(4,5,6));
    var z = x + y;   // Some(1,2,3,4,5,6)

There's also behaviour for subtract, divide and product:

So for example with lists:

    var x = Some(List(1,2,3));
    var y = Some(List(2,3,4));
    var z = x * y;   // Some(2,4,6,3,6,9,4,8,12)

For your own types you can derive from: IAppendable<T>, ISubtractable<T>, IProductable<T>, and IDivisible<T> (There's a convenient INumeric for bespoke numeric types).

All of the core monads support Append, Subtract, Divide and Product. They will however throw a runtime exception if the underlying type doesn't support the action.

I think combined with apply it should get most of the way down the path of dealing with operations on two monadic types.

I hope that helps :)