Using lenses in anger

So after my exploration into immutable lenses (Parts 1, 2 and 3) it is time to put them to use in the engine. To test them I have created two of the level manipulations.

The first, shown below, spawns an actor within a level.

    public static Level SpawnActor(
        this Level level, Actor actor, Point location)
    {
        var actorState = ActorState.Create(actor.Id, location);

        return level
            .Set(ActorLookupAt(location), actor.ToSome())
            .Set(ActorStateLookup(actor.Id), actorState.ToSome());
    }

As you can see the code is very clean.

• Create the new state
• Insert the actor into level.Tiles[location].Actor
• Insert the actor state into level.ActorStates[actorId]

ActorLookupAt() combines a couple of lenses targeted at the specified tile location and ActorStateLookup() is similar.

The situation is similar moving an actor from one location to another, as shown below.

    public static Level MoveActor(
        this Level level, long actorId, Point newLocation)
    {
        var actorLocationLens = ActorLocationByKey(actorId);
        var oldLocation = level.Get(actorLocationLens);

        var actorAtOldLocationLens = ActorLookupAt(oldLocation);
        var actor = level.Get(actorAtOldLocationLens);

        return level
            .Set(actorAtOldLocationLens, Maybe≪Actor>.None)
            .Set(ActorLookupAt(newLocation), actor)
            .Set(actorLocationLens, newLocation);
    }

There are a couple more steps as we need to get some data out of the level first and we also reuse some of the lenses so cache them locally before using them.

To move the actor we:

• Get the old actor location.
• Get the actor from it’s current tile.
• Remove the actor from it’s current tile.
• Place the actor at its new location.
• Update the actors location in the actor states

One downside of this is that level is rebuilt 3 times by the operation. This is not a major impact though as the level object is small but if this does prove an issue later I can tease the code apart some more such that the tiles is pulled out to a builder and then updated and then stuff the updates back into the level as a single operation to minimise churn.

The reality of a roguelike is that the reads vs writes is very asymmetrical with most of the focus on read due to AI path finding and the like. Given the turn based nature this should not be an issue but there is lots of wiggle room to tweak later all located in one area of the code base..

Connecting lenses

This piece on lenses is a follow up to the ImmutableDictionary Lens as the Lookup operation we created there breaks composition through return of IMaybe and this raises an interesting question about the semantics of Lookup.

At the basic level a lens chains are simple, just connect up with Get->Get and Set<-Set as seen below.

The ByKey ImmutableDictionary lens just chains in without issue but throws an exception if the key is not present, this is no different to standard dictionary semantics.

If Lookup is at the end of the chain we have no issues and it gives us handy Add, Update and Delete functionality but if we want to compose a Lookup lens into another lens we need a means to recover from IMaybe.None to get a value, the following shows the dilemma.

We could make use of the monadic Bind (Select, SelectMany) which would then propagate the None down the chain, fine with Get but what does that mean in the context of set? It just falls apart.

The semantics of Lookup composed into lenses on the lookup key value is really saying, get the value and if you can’t use some form of default. Now when we set a property on the default value it will also add it to the dictionary.

This gives us the following overload to Lookup and its associated helper that no longer result in a IMaybe and hence allow composition again.

    public static
        Lens<IImmutableDictionary<TKey, TValue>, TValue>
        Lookup<TKey, TValue>(TKey key, Func<TValue> defaultFactory)
    {
        return
            Lens.Create<IImmutableDictionary<TKey, TValue>, TValue>(
                dictionary => 
                    dictionary.Lookup(key).OrElse(defaultFactory()),
                value => dictionary => dictionary.SetItem(key, value));
    }

    public static Lens<TEntity, TValue>
        Lookup<TEntity, TKey, TValue>(
            this Lens<TEntity, IImmutableDictionary<TKey, TValue>> self,
            TKey key, Func<TValue> defaultFactory)
    {
        return self.With(Lookup(key, defaultFactory));
    }

The interesting part here is that we only need to default on Get because the Set operation performs Get to facilitate the manipulation of the object.

Lens for ImmutableDictionary

Following on from my last piece on Lenses it is time to explore the lenses required for the BCL ImmutableDictionary<TKey, TValue>.

The first is a factory function that when given a key will create a lens for the entry in the dictionary with that key, it is a mapping over this[TKey] on ImmutableDictionary<TKey, TValue>:

	
    public static 
        Lens<IImmutableDictionary<TKey, TValue>, TValue> 
        ByKey<TKey, TValue>(TKey key)
    {
        return 
            Lens.Create<IImmutableDictionary<TKey, TValue>, TValue>(
                dictionary => dictionary[key],
                value => dictionary => dictionary.SetItem(key, value));
    }

The Get action will return the value stored for the key, or throw an exception if not found. While exception throwing is not “pure” functional and we should try and encapsulate that in a Monad we are working in C# so we roll with the punches.

The Set action will either Add or Update the value for the key depending on if there is an existing entry or not.

The second, like the first is a factory that given a key will create a lens but this time makes use of my Maybe monad to allow more subtle manipulation:

    public static 
        Lens<IImmutableDictionary<TKey, TValue>, IMaybe<TValue>> 
        Lookup<TKey, TValue>(TKey key)
    {
        return 
            Lens.Create<IImmutableDictionary<TKey, TValue>, IMaybe<TValue>>(
                dictionary => dictionary.Lookup(key),
                value => dictionary =>
                {
                    return value
                        .Select(x => dictionary.SetItem(key, x))
                        .OrElse(() => dictionary.Remove(key));
                });
    }

The get action will return a IMaybe<TValue> of None if the key is not present and Some when present. Similar to the first apart from you get a None in place of an exception.

The set action though can now be used for Add, Update and Delete. A Some will either Add or Update as before but a None will remove the entry for the key.

There are also two helper helper factories that given a Lens<T, ImmutableDictionary<TKey, TValue>> will return a Lens<T, TValue>. This provides a simple way to add lookup lenses to entities with fields of  ImmutableDictionary<TKey, TValue>.

The helpers are:

    public static Lens<TEntity, TValue> 
        ByKey<TEntity, TKey, TValue>(
            this Lens<TEntity, IImmutableDictionary<TKey, TValue>> self,
            TKey key)
    {
        return self.With(ByKey<TKey, TValue>(key));
    }

    public static Lens<TEntity, IMaybe<TValue>> 
        Lookup<TEntity, TKey, TValue>(
            this Lens<TEntity, IImmutableDictionary<TKey, TValue>> self,
            TKey key)
    {
        return self.With(Lookup<TKey, TValue>(key));
    }

The same concept can be applied to other immutable stores, the factories are simply closing over the supplied key to create the lens.

So used in anger, it looks like this

Lens<Entity, ImmutableDictionary<string, bool> entityFlags = …

entity.Set(entityFlags.ByKey(“someFlag”), newValue);

This will build the updated dictionary with the new flag value and then update the containing entity to use the new flag store in a nice clean easy to read line of code.

The Lookup operation does raise some interesting composition issues which I address in the Next Post.

Immutable update via Lenses

While working on the code to manipulate my immutable level game state I found some interesting Haskell talks around the concept of lenses, these are composable computational blocks for updating immutable object graphs.

A lens holds two basic functions which abstract a property get/set pair:

• A getter that given an object returns a property in the object.
• A setter that given an object and a property value returns an object with the property set.

The basic signature in C# being:

    public class Lens<TType, TValue>
    {
        private readonly Func<TType, TValue> _get;
        private readonly Func<TValue, Func<TType, TType>> _set;

        internal Lens(
            Func<TType, TValue> get, 
            Func<TValue, Func<TType, TType>> set)
        {
            Debug.Assert(get != null);
            Debug.Assert(set != null);

            _get = get;
            _set = set;
        }

        public Func<TType, TValue> Get
        {
            get { return _get; }
        }

        public Func<TValue, Func<TType, TType>> Set
        {
            get { return _set; }
        }
    
        private Func<TType, TType> Modify(Func<TValue, TValue> updater)
        {
            Debug.Assert(updater != null);

            return root => Set(updater(Get(root)))(root);
        }

        public Lens<TType, TChildValue> With<TChildValue>(
            Lens<TValue, TChildValue> childLens)
        {
            Debug.Assert(childLens != null);

            return new Lens<TType, TChildValue>(
                root => childLens.Get(Get(root)),
                childValue => Modify(childLens.Set(childValue)));
        }
    }

I know that is a lot of scary looking generics so I will boil it down.

Get is a function of TType => TValue, so given an object will return you a value from it.

Set is a bit more interesting being a curried function. Uncurried the signature would be (TValue, TType) => TType, so given a value and an object it returns an object. The curried signature being TValue => TType => TType.

With allows composition of lenses so given a lens of A => B and a lens from B => C it will return a lens from A => C. The composed lens, given a A and value C is able to understand how to update A, B and C.

So how can this actually be used?

First you need to create a lens for each property in your object. So here are a couple of immutable objects, the with method giving an F# style “with” operation to ease updating:

    public class Root
    {
        private readonly int _value;
        private readonly Child _child;

        public Root(int value, Child child)
        {
            _value = value;
            _child = child;
        }

        public int Value
        {
            get { return _value; }
        }

        public Child Child
        {
            get { return _child; }
        }

        public Root With(int? value = null, Child child = null)
        {
            return new Root(value ?? _value, child ?? _child);
        }
    }

    public class Child
    {
        private readonly int _value;

        public Child(int value)
        {
            _value = value;
        }

        public int Value
        {
            get { return _value; }
        }

        public Child With(int? value = null)
        {
            return new Child(value ?? _value);
        }
    }

The lens set for these objects are:

    var rootValue = Lens.Create<Root, int>(
        root => root.Value,
        value => root => root.With(value: value));

    var rootChild = Lens.Create<Root, Child>(
        root => root.Child,
        child => root => root.With(child: child));

    var childValue = Lens.Create<Child, int>(
        child => child.Value,
        value => child => child.With(value: value));

    // This is the composition that given a root node allows 
    // manipulation of the child value
    var rootChildValue = rootChild.With(childValue);

As you can see, creating the lenses and plugging them together is very simple and mechanical in nature. It also has codegen written all over it. I already have a codegen in the works using T4 that given a class templates with private fields will generate the scaffolding for an immutable class so this will be extended to create the lenses but that is another subject.

The final part is some syntactical sugar to undo the curry.

    public static TValue Get<TType, TValue>(
        this TType instance,
        Lens<TType, TValue> lens)
    {
        return lens.Get(instance);
    }

    public static TType Set<TType, TValue>(
        this TType instance,
        Lens<TType, TValue> lens,
        TValue value)
    {
        return lens.Set(value)(instance);
    }

So after all this work what has all this actually gained us. The following are some sample manipulations:

    // Given the object structure
    var instance = new Root(0, new Child(0));

    // Both the following perform the same update 
    instance = instance.Set(rootChildValue, 5);
    instance = instance.Set(rootChild.With(childValue), 5);

There are also lens shapes that allow manipulation of dictionaries, sets, arrays that compose in the same manner that I cover in the Next Part.

As you can see, given some simple scaffolding work which screams codegen, you get nice clean manipulation code that is easy to read, reason about and maintain. Above all you remain in a nice pure immutable functional space 🙂