Functional Thread 7 : Lazy Transformations

[[)roi(]]

Previous Thread
In the last Functional thread I explored how FP uses the 1st class function abilities in C# and ended introducing some higher order functions:

• Exception handling in Functional Programming (FP) vs. the OOP approach.
• Loose versus Tight coupling of input validations or any procedural data verification

For reference, you can find that thread here:
https://mybroadband.co.za/forum/threads/functional-thread-6-part-2-exceptions.1000254/

Lazy Transformations
The purpose of this thread will be to focus on laziness and in particular two FP Algebras related to this:

• Yoneda
• Coyoneda (the dual of Yoneda)

Yoneda is named after the Japanese mathematician and computer scientist (Nobuo Yoneda) who discovered the:

• Yoneda product in homological algebra, and it's dual the Coyoneda
• Yoneda lemma in category theory

Target Audience
This thread is targeted at intermediate developers; hence we'll be using a few of the extension methods created in the last FP thread, for example:

• Map
• Fold
• etc.

Note:

• This is going to be a fairly short thread, but it will include a bit of code.
• There is no need to understand the mathematics behind this to use it and the implementations in C# will be quite easy to understand without a maths background.
• At the end of this I'll update the previous FP project incorporating the Coyoneda type and some enhancements to our exceptional handling types: Maybe, Either, Validation.

 

[[)roi(]]

Yoneda and Coyoneda (Lazy Transformations)
At this point, assuming of course that you have followed along with a few of the functional threads, you should be somewhat familiar with higher order abstractions like Functors, Applicatives and Monads, namely:

• Map (Select in Linq)
• Apply (No equivalent in Linq)
• FlatMap (SelectMany in Linq)

Which means that introducing you to some new higher order abstractions like Yoneda and Coyoneda should not be not be an impossible ask.

It is however just an inkling into the world Free Objects with abstractions like:

• Free Monoids
• Free Functors
• Free Applicative Functors
• Free Monads

Framing the problem
To understand the need for something like a Yoneda or Coyoneda it would be best to first frame a standard computational problem when using Higher Order Functiions like Linq, for example:

var input = Enumerable.Range(0, 1000000);
var result = input.map(f).map(g).map(h);

Here we are mapping over (I.e. transforming) the 1 million elements contained in the input list, 3 times, once for each function f, then g, and finally h.

It really doesn't matter what these transformations represent, but if it helps with the understanding think of them as follows:

Func<int, int> f = x => x + 1; // Increment
Func<int, int> g = x => x * 2; // Double the value
Func<int, int> h = x => x - 1; // Decrement

The mapping over input first by f, then by g, and finally h results in the computation looping over each of elements in input 3 times, which isn't a very efficient way to compute the result.

It would be far more efficient to perform these 3 transformations in 1 step, for example:

var result = input.map(x => h(g(f(x))));

I.e. the single composition of functions f, g, and h, which effectively loops only once over the elements in the input list.

Whilst this may appear to be an easy enough solution, in practice things rarely are this easy when it comes to more complex computation scenarios. Plus if we syntactically compare the 2 variations of the same result:

var result = input.map(f).map(g).map(h);
var result = input.map(x => h(g(f(x))));

Which one is is syntactically less complex. Considering more complex transformations scenarios than just f, g, and h, I would say the 1st one, because it is syntactically quite obvious that we are applying 3 transformation, 1 after the other to the elements of input, whereas with the 2nd example it's not quite so clear, we need to think in reverse, or inside out.

Naturally you may agree or disagree here, and that's fine.

However let's frame what could be happening in the 2nd scenario. Effectively we are applying transformations to the elements but delaying their computation until we have composed together all the computations that we require for the result.

Now imagine if we could use this syntax:

var result = input.map(f).map(g).map(h);

...and still delay the final computation in the same way as the compositional variant did. Would that be something interesting or useful?

That essentially describes what the Yoneda Product in homological algebra achieves. It allows us to lazily, defer the computation of transformations of elements until we are ready to compute the result, and it reduces the overall complexity of a computation by ensuring that we loop only once over the elements as opposed to once per transformation.

This is also the essence of what constitutes a Free Object in the mathematical sense, and should help to give you an inkling into why more complex abstractions like Free Monads might exist; ...because they are in part based on an abstractions like the Yoneda Lemma, which has been described as the hardest trivial abstraction in mathematics. Whilst the proof of the lemma is not too difficult to understand, it has significance in a wide variety of areas, and corresponds with group theory's Cayley’s theorem.

Additional References:

• https://bartoszmilewski.com/2013/05/15/understanding-yoneda/
• http://blog.higher-order.com/blog/2013/11/01/free-and-yoneda/

The goal of this thread will be to make this syntactical variant:

var result = input.map(f).map(g).map(h);

..have the same compute cost as this compositional variant:

var result = input.map(x => h(g(f(x))));


Note:
Next post should be up in a day or two.

 

[[)roi(]]

Lazy versus Eager Evaluation
C# like many mainstream languages is an eager evaluated language, where, an expression is evaluated as soon as it is bound to a variable. An opposite alternative to eager evaluation is lazy evaluation, where expressions are evaluated only when a dependent expression is evaluated depending upon a defined evaluation strategy.


A simple example of C#'s eager evaluation

namespace EagerExample {
  class MainClass {
    public static bool WriteLn(string s, bool b) {
      Console.WriteLine(s);
      return b;
    }

    public static void Main(string[] args) {
      int q_age = 17;
      var answer = q_age <= 18 ? WriteLn("Teenager", true) : WriteLn("Adult", false)
    }
  }
}

Console Output

Teenager

Even though we never use the variable answer; the above output is nevertheless written to the console. The reason this happened is because of eager evaluation.


So how do we make the above code Lazy?
In C# closures are lazily evaluated, so if we rewrite the above example as below; the text Teenager won't be written to console until we execute answer.

Func<bool> answer = () => q_age <= 18 ? WriteLn("Teenager", true) : WriteLn("Adult", false);

With that in mind we have the basics of what is required to construct our Yoneda.



Building the Yoneda Functor
A yoneda is built around a functor; a container type that has the Map or Select method like Maybe, Either, ...


Let's first build a Yoneda for the Maybe functor

using System;

namespace FPIntro {
  public static partial class ƒ {

    #region Syntactic Sugar
    public static MaybeYoneda<A, A> ToMaybeYoneda<A>(this Maybe<A> functor) => new MaybeYoneda<A, A>( functor, Id);
    #endregion

    #region Functor
    public static MaybeYoneda<A, C> Map<A, B, C>(this MaybeYoneda<A, B> @this, Func<B, C> g) => new MaybeYoneda<A, C>(@this. functor, a => g(@this.f(a)));
    #endregion

    #region Linq Conformance
    public static MaybeYoneda<A, C> Select<A, B, C>(this MaybeYoneda<A, B> @this, Func<B, C> f) => @this.Map(f);
    #endregion

    #region MaybeYoneda Run Conformance
    public static Maybe<R> Run<V, R>(this MaybeYoneda<V, R> @this) => @this. functor.Map(@this.f);
    #endregion

  }

  public struct MaybeYoneda<A, B> {
    internal readonly Maybe<A> functor;
    internal readonly Func<A, B> f;

    public MaybeYoneda(Maybe<A> value, Func<A, B> f) {
      this.functor = functor;
      this.f = f;
    }
  }
}

It's a simple design that encapsulates a functor, in this case a Maybe functor and a function f from generic type A to generic type B.


Extension Methods for MaybeYoneda Functor
The extensions methods for the MaybeYoneda add some syntactic sugar to aid in lifting an existing Maybe functor instance into a Yoneda; and uses the Id as the starting point for the internal function f i.e. Id is a function that returns it's input unchanged.

Id function code

public static T Id<T>(T t) => t;

Map method
We have also added a Map method specific to our MaybeYoneda type, and as you should see, it's a simpl composition of functions; function g with the current function in the property f, initialising a new instance of MaybeYoneda with our input Maybe functor instance. This is the essential part of the lazy evaluation process within the Yoneda.

Run method
The Run method quite simply applies our composited Map transforms stored in property f to the our Maybe functor's Map method to finally perform the computation.


Here's a usage example of our MaybeYoneda Functor

Func<int, int> f = x => x + 1; // increment
Func<int, int> g = x => x * 2; // double
Func<int, int> h = x => x - 1; // decrement
Func<int, string> i = x => x.ToString();

Some(23).ToMaybeYoneda() // Lift a Maybe into a MaybeYoneda
  .Map(f)
  .Map(g)
  .Map(h)
  .Map(i)
  .Run() // cumulative Map transform only executes at this point
  .Print("MaybeYoneda"); // Output: MaybeYoneda ---> Maybe[Some: 47]

Naturally it would be quite tedious if we had to create a new Yoneda type for every functor; it would be much better if we could create a Yoneda that was generic over both the element types stored in our functors and also be generic over the functors as well.

Sadly this is an area that hits the limits of the C# static typing generics. We simply cannot describe a type that is both generic over the element type and functor type at the same time; however if we forgo the safety net of static typing we can redefine our Yoneda using the object type.



Generic Yoneda Functor (forgoing a bit of type safety)

using System;
using System.Collections.Generic;

namespace FPIntro {

  public static partial class ƒ {

    #region Syntactic Sugar
    public static Yoneda<A, A> ToYoneda<A>(this object functor) => new Yoneda<A, A>(functor, Id);
    #endregion

    #region Functor
    public static Yoneda<A, C> Map<A, B, C>(this Yoneda<A, B> @this, Func<B, C> g) => new Yoneda<A, C>(@this.functor, a => g(@this.f(a)));
    #endregion

    #region Linq Conformance
    public static Yoneda<A, C> Select<A, B, C>(this Yoneda<A, B> @this, Func<B, C> f) => @this.Map(f);
    #endregion

    #region Yoneda Run Conformance
    public static Identity<R> RunIdentity<V, R>(this Yoneda<V, R> @this) => ((Identity<V>)@this.functor).Map(@this.f);
    public static Maybe<R> RunMaybe<V, R>(this Yoneda<V, R> @this) => ((Maybe<V>)@this.functor).Map(@this.f);
    public static IEnumerable<R> RunIEnumerable<V, R>(this Yoneda<V, R> @this) => ((IEnumerable<V>)@this.functor).Map((V v) => @this.f(v));
    public static Either<string, R> RunEither<V, R>(this Yoneda<V, R> @this) => ((Either<string, V>)@this.functor).Map(@this.f);
    public static Validation<string, R> RunValidation<V, R>(this Yoneda<V, R> @this) => ((Validation<string, V>)@this.functor).Map(@this.f);
    #endregion

  }

  public struct Yoneda<A, B> {
    internal readonly object functor;
    internal readonly Func<A, B> f;

    public Yoneda(object functor, Func<A, B> f) {
      this.functor = functor;
      this.f = f;
    }
  }
}

Everything is almost the same except of course for the functor's property type i.e. object, and then a named Run method for each of the functor's we cater for. Naturally this code can cause runtime errors because we have to cast our object to a functor type in order to call the Map method; there's just no easy way to elegantly solve a lack of higher-kinded polymorphism.

Usage Example

new List<int> { 1, 2, 3, 4, 5 }
  .ToYoneda<int>()
  .Map(f)
  .Map(g)
  .Map(h)
  .Map(i)
  .RunIEnumerable()
  .Print(); // Output: Generic Yoneda ---> List {3, 5, 7, 9, 11}

Next Post

• What about types that are not functors; is there a way to apply lazy evaluation to any type, by lifting a type in a functor.
• Also is there another solution to the lack of type safety with the generic version of the Yoneda type?

In short, the answer is yes; we can make use of the algebraic dual of the Yoneda Functor, a contravariant functor; the Coyoneda.

 

[[)roi(]]

Coyoneda
Is it possible to achieve the same versatility as Yoneda but without the restriction that our input value is a functor or write code that requires the use of the object type and explicit type casting?

Well, sort of — we can compose all our given functions A => B but we still need to know how to apply all those functions over the functor of A.

We could defer these restrictions on input value to the end; by essentially pretending that out input value is a functor; that way we can Map over our input value as per normal and only defer any of these restrictions to point of executing the composition of our transforms. i.e. in the Run method.

Building the Yoneda Functor

using System;
using System.Collections.Generic;

namespace FPIntro {

  public static partial class ƒ {

    #region  Syntactic Sugar
    public static Coyoneda<V, B, B> ToCoyo<V, B>(this V value) => new Coyoneda<V, B, B>(value, Id);
    #endregion

    #region Functor
    public static Coyoneda<V, A, C> Map<V, A, B, C>(this Coyoneda<V, A, B> @this, Func<B, C> g) => new Coyoneda<V, A, C>(@this.value, a => g(@this.f(a)));
    #endregion

    #region Linq Conformance
    public static Coyoneda<V, A, C> Select<V, A, B, C>(this Coyoneda<V, A, B> @this, Func<B, C> f) => @this.Map(f);
    #endregion

    #region Coyoneda Run Conformance per Functor Data Type
    public static R Run<V, R>(this Coyoneda<V, V, R> @this) => @this.f(@this.value);
    public static Maybe<R> Run<V, R>(this Coyoneda<Maybe<V>, V, R> @this) => @this.value.Map((V v) => @this.f(v));
    public static IEnumerable<R> Run<V, R>(this Coyoneda<IEnumerable<V>, V, R> @this) => @this.value.Map((V v) => @this.f(v));
    public static Either<string, R> Run<V, R>(this Coyoneda<Either<string, V>, V, R> @this) => @this.value.Map((V v) => @this.f(v));
    public static Validation<string, R> Run<V, R>(this Coyoneda<Validation<string, V>, V, R> @this) => @this.value.MapR((V v) => @this.f(v));
    #endregion

  }

  public struct Coyoneda<V, A, B> {
    public readonly V value;
    public readonly Func<A, B> f;

    public Coyoneda(V value, Func<A, B> f) {
      this.value = value;
      this.f = f;
    }
  }
}

Usage Examples:

Some(23)
  .ToCoyo<Maybe<int>, int>()
  .Map(f)
  .Map(g)
  .Map(h)
  .Map(i)
  .Run()
  .Print("Generic Coyoneda with Maybe");

// Output: Generic Coyoneda with Maybe ---> Maybe[Some: 47]

new List<int> { 1, 2, 3, 4, 5 }
  .ToCoyo<IEnumerable<int>, int>()
  .Map(f)
  .Map(g)
  .Map(h)
  .Map(i)
  .Run()
  .Print("Generic Coyoneda with IEnumerable");

// Output: Generic Coyoneda with IEnumerable ---> List {3, 5, 7, 9, 11}

...and we can even lift input values that are not functors, for example:

var nonfunctor = 23
  .ToCoyo<int, int>()
  .Map(f)
  .Map(g)
  .Map(h)
  .Map(i)
  .Run();
Console.WriteLine(nonfunctor);

// Output : 47

So what about these Free types like Free Functor ...
If we were to expand our Coyoneda a bit more we'd end up with what is essentially considered a Free Functor. For a more complete example, I suggest you look at the Scala Cats implementation of the Coyoneda (aka Free Functor):

• https://github.com/typelevel/cats/blob/master/free/src/main/scala/cats/free/Coyoneda.scala

 

[[)roi(]]

So what's this Yoneda Lemma thing?
Basically if we have a function defined like this:

F<B> Map<A, B>(Func<A, B) f)

Note:

• This is not valid C# code as we are unable to express a generic placeholder variable for both the container type F and the elements A and B.
• C# as mentioned before only supports generic elements, and doesn't have support for Higher-Kinded Polymorphism that would enable this.
• In the above code example the variable F refers to any type that conforms to the functor algebra, for example: Maybe, Either, IEnumerable, ...

The above code snippet also implies we most certainly have a value of type F<A>. i.e. To obtain our F<A> we need simply pass our Map the identity Id function.

In fact, a function like this is in practice is most likely defined as an extension method or struct / class method on a value of type F<A> anyway, for example:

F<B> Map<A, B>(this F<A> @this, Func<A, B) f)

Yoneda Lemma Synopsis
The Yoneda Lemma says that this also goes the other way around. If you have a value of type F<A> for any functor F and any type A, then you certainly have a Map function with this signature:

F<B> Map<A, B>(this F<A> @this, Func<A, B) f)

..and more so the Yoneda lemma says that there is an isomorphism between Yoneda<F, A> and F<A>, for any functor F and any type A.

Note:
Isomorphism refers to a function for which an inverse function exists.

• isos meaning "equal"
• morphemeaning "form" or "shape"

Uses of the Yoneda Lemma
The high level of abstraction in the statement of the Yoneda lemma like the Functor and Monad means that it can be applied in many contexts, some of which are actually quite familiar.

For example:

• It explains Cayley’s Theorem for monoids, which is the trick that enables the use of an accumulating parameter, which can often turn a quadratic-time program into a linear-time one.
• Its employed in Profunctor Optics.

Note:
Profunctor Optics including the Yoneda Lemma is not easy to express in C#.

 

[[)roi(]]

What does C# offer in terms of Laziness
Microsoft provides for general type laziness with it's Lazy container type:

• https://docs.microsoft.com/en-us/dotnet/api/system.lazy-1?view=netframework-4.7.2

... but this sadly does not conform to any of base FP algebras like Linq's IEnumerable type does; however this does not mean its impossible.

Mark Seeman has done a series of blog posts on functors in C#, and also covers the Lazy type with both functors and applicative functors:

• http://blog.ploeh.dk/2018/03/19/functors-applicatives-and-friends/

 

[CT_Biker]

Am I correct in saying that under the right circumstances, Variables which are lazily evaluated, and also be lazily iterated...even though that may mean you have forgo a fair amount of type safety?

 

[[)roi(]]

Am I correct in saying that under the right circumstances, Variables which are lazily evaluated, and also be lazily iterated...even though that may mean you have forgo a fair amount of type safety?

The only example that I provide which skirts around type safety is the code of the generic form of the Yoneda i.e. a lazy iteration of the Map method (or Select as Linq refers to it) -- and it's not type safe because of the limitations inherent in C# type generics. Another alternative solution around this would have been type erasure, but C# doesn't support that.

Lazy evaluation: Pros / Cons
The benefit behind lazy computation over eager computation is curbing wasted processing cycles; with a language like Haskell where the entire language is lazy by default; a majority of code branches will never be executed depending on the computational branching. Even simple binary operations like addition are lazily computed in Haskell.

Whereas in an eager language like C#, a lot of code is computed even if that particular branch is never taken, including binary operations. Hence there should be quite a few situations where code can be better optimised by simply adding on lazy evaluation like that offered by Microsoft's Lazy type, or the lambda closure syntax or the Yoneda / Coyoneda algebras I shared.

FYI the entire Linq API is typically lazily computed; but that's only for IEnumerable, for any other container types you have to add this on yourself; the Coyoneda (and by extension the Free Functor) is a simple solution around that.

Naturally lazy evaluation is not a perfect fit for everything; for example:

• In a UI environment it might make sense to trickle compute changes over time, as opposed to compositing everything and running it all at once; i.e. to avoid a perception of lag.
• A good example of this is the compositing style of work that is performed with garbage collection on Android i.e. the perceivable stutter and/or UI lag when resources are low.
• However for asynchronous / parallel computes, lazy computation is very beneficial.

In short if done correctly, you should never have to sacrifice type safety at all, and I certainly would never advice you to do that.

Btw With the type unsafe Yoneda code example, one would naturally need to add a lot more code to make it more robust; but I'd argue why even bother when the Coyoneda approach is far more flexible and inherently type safe.

 

[CT_Biker]

Thank you for the excellent explanation of the above concept.

I really appreciate the wealth of knowledge you share freely.