Woz.Functional

With the two easy class libraries extracted and published to Nuget (Woz.SimpleIOC and Woz.Linq) it is time to move on to Woz.Functional. This will be a more iterative piece of work as I would like this library to have no dependencies and optional sub libraries/packages that carry the code with dependencies such as Woz.Functional.Immutable which will pull in the MS immutable collections and integrate them with Woz.Functional code.

My though here was go back to Haskell and CategoryTheory first principles and see if I could implement Functors, Monoids, Aplicative and the like for C# in a generic way. This would allow me to build every thing on top of these building blocks.

The sad truth is that C# is not capable of re-creating a Haskell like type system. Searching the web you will find many different attempts but in all cases they break down as the .NET/C# generic system is not capable of the Haskell type system subtlety. All the examples you will find are a compromised approximation that look fine in the various contrived examples but then all fall apart when pushed in the real world. For example, the simple definition of:

fmap :: (a -> b) -> Ma -> Mb

C# is just not capable of this definition in a generic means, you have no way to ensure the M in Ma is the same M in Mb, the generic type system treats each one as a separate type. This really forces you to declare a separate fmap declarations for each M to ensure the output boxing type us the same as the input one, such as:

IEnumerable FMap<T, TResult>(IEnumerable source, Func<T, TResult> selector);
IMaybe FMap<T, TResult>(IMaybe source, Func<T, TResult> selector);

This makes trying to build from first principles a bit pointless. I knew this was coming as the Monad library I built in BadlyDrawRogue went through this same fight. In that code I accepted the limitations in C# and instead decided that Linq integration was the better path. In C# Linq is really a monad and computational engine with IEnumerable being the only supplied monad. This means instead of the more normal naming of bind, return, map, fmap etc you instead use Linq naming such as Select, SelectMany etc.

Game engine commands

In the context of BadlyDrawnRogue commands are requests from the player or NPC AI to make the associated actor perform an operation in the game world. Previous topics have covered the validation and execution of operations so now it is time to stitch them together.

The command record is very simple, just two fields:.

    public sealed class Command
    {
        public readonly Func<Level, IValidation<Level>> Validator;
        public readonly Func<Level, IValidation<Level>> Operation;

        private Command(
            Func<Level, IValidation<Level>> validator,
            Func<Level, IValidation<Level>> operation)
        {
            Validator = validator;
            Operation = operation;
        }

        public static Command Create(
            Func<Level, IValidation<Level>> validator,
            Func<Level, Level> operation)
        {
            return new Command(
                validator, x => validator(x).Select(operation));
        }
    }

Validator() is a function that given a level will validate the command operation. Operation() is a function that given a level will validate and then executes the command operation returning the resulting level. Create() being a factory where we compose compose the operation and validator together.

Closures feature heavily in the command so we really need to look at the command factory to see how the commands are put together but first a quick look at the functions that are the building blocks for SpawnActor

    public static IValidation<Level> CanSpawnActor(
        this Level level, long actorId, Point location) {...}

    public static Level SpawnActor(
        this Level level, Actor actor, Point location) {...}

As you can see, these are no the correct shape for the command structure. This is where the command factory for SpawnActor comes to the rescue:

    public static class CommandFactory
    {
        public static Command 
            CreateSpawnActorCommand(Actor actor, Point location)
        {
            return Command.Create(
                level => level.CanSpawnActor(actor.Id, location),
                level => level.SpawnActor(actor, location));
        }
    }

Simple, all it does is close over CanSpawnActor() and SpawnActor() with the supplied parameters to partially apply via lambdas. They are now in the required level => IValidation<Level> and level => level shapes for the command record.

Commands for the game engine done! Function composition is a beautiful thing 🙂

In a Bind over C# Monads

Over the past couple of years I have explored Monads in C#, their implementation and usage, while trying to bring my code further into the functional world.

Many of the implementations I have encountered have been variations on the theme of, including my own implementations.

M<A>
Func<M<A>, A> Return()
M<B> Bind(Func<A, M<B>> mapper)

Bind is the most common name you will encounter as your explore monads yet this does not come from the category theory that underpins the whole concept but instead from Haskell operator >>=, also known as bind. Haskell being the poster child for monadic operation and hence has influenced naming conventions.

Bind is all well and good in the Haskell domain but the Linq operations for this operation is SelectMany along with its counterpoint Select. To solve this name mismatch the common approach is to implement Bind in the monad and then layer Linq operations as a set of extension methods, the extensions normally nothing more than pass through to bind and hence a pointless level of abstraction.

C# is not Haskell so why stick to these names. Linq is the .NET world generic monad engine, it is not just about IEnumerable<‘a>, so it makes sense to use the Linq naming conventions for monadic operation. Those being:

Select = map = M<A> -> Func<A, B> -> M<B>
SelectMany = flatmap = bind = M<A> -> Func<A, M<B>> -> M<B>

Given that Linq does not care if the functions are implemented as member methods or extension methods it is time the hangup over bind was lost..

So I have refactored my Monads and Bind is gone, the code is now far far cleaner, faster and more succinct.

Rolling my own Maybe

Since finding the interfaced struct based solution to monadic computation the Maybe library I had been using, nuget Functional.Maybe, was starting to jar somewhat. While a fantastic library functionality wise the fact that each maybe instance carried the value and an associated flag for HasValue meant that each Maybe passed around consumed more on the stack that was really required. The only solution was to create my own implementation.

The basic interface is below

        
    public interface IMaybe<T> : IEquatable<IMaybe<T>>
    {
        bool HasValue { get; }

        T Value { get; }

        IMaybe<TResult> Bind<TResult>(Func<T, IMaybe<TResult>> operation);

        T OrElseDefault();
        T OrElse(T defaultValue);
        T OrElse(Func<Exception> builder);
        
        bool Equals(object obj);
        int GetHashCode();
    }

The old library also has the issue that Bind and OrElse were implemented via extensions, which meant extra code to test for value to switch paths. Pushing these down into the implementation means these paths now have direct flow without the need to test the state of the value.

I have a number of extensions layered on top for basic Linq functionality and express these via Bind when possible to limit the need to test HasValue. The implementation is far from complete in the area of Linq and IEnumerable<T> but I will grow on a need to basis. I might even spin it out to a separate nuget at a later date for other to use.

It is a shame to have to go back to do this sort of refactor but I am quickly learning that it is best to get the core structure correct early on when working with large scale Immutability to stop far more work later down the line.

Monad implementation the correct way

Most implementations of Monadic type code in C# have always concerned me, there appears to be two common techniques, I will outline these in terms of Maybe

• Class hierarchy – An abstract class for Maybe and a Some and None inheritance off the base.
• Struct – A struct that has storage for the Value and the HasValue properties because structs are sealed.

The class based solution has issues with Object churn on which effects GC due to the fleeting nature of the Maybe and the struct means you are passing more data about than is really required.

While looking around github I finally hit on a great solution that has not really crossed my mind before, use interfaces with structs. This means you have a IMaybe interface which acts as the abstract from the class solution and you back it with a Some and None implemented by structs.

Now you are not passing around more data than required and you avoid the object churn as the data is passed around on the heap.

🙂