Further than SAM

NOTE: this is the second part of this article. Please read it if haven’t yet.


The interface

Let’s start from scratch. You know all the things you read in previous article, but you have no code at all.

So we said that SAM interfaces are technically equivalent to functions (to be precise: Func or Action depending on return type). So, let’s see where it can get us.

Knowing the interfaces were declared like this:

1
2
3
4
5
6
7
public interface ILogger {
void Log(Severity severity, Func<string> builder);
}
public interface ILoggerFactory {
ILogger GetLogger(string name);
}

we can redefine them as:

1
2
3
// pseudo-code
type ILogger = Action<Severity, Func<string>>;
type ILoggerFactory = Func<string, ILogger>;

Now, we can substitute ILogger actual type (Action<...>) as ILoggerFactory output type, receiving:

1
2
// Pseudo-code
type ILoggerFactory = Func<string, Action<Severity, Func<string>>>;

So, the interface to logging framework is just Func<string, Action<Severity, Func<string>>>, and next time someone ask you on the tube, “Hey man, what’s your Func<string, Action<Severity, Func<string>>>?” you can just tell him: “I’m using log4net, matey”.

In my opinion, using descriptive names depends on scope. I would actually encourage you to use just Func<T> for locally scoped or internal factory, or i as an index in 3-line for statement but for objects which are known by entire application I would prefer longer, more distinguished names.
In case of “logging framework interface” I would suggest quite descriptive names. Yes, it is just a function, but it would be much more readable if we call it LoggerFactory.

Let’s do it then:

1
2
3
public enum Severity { Trace, Debug, Info, Warn, Error, Fatal }
public delegate Logger LoggerFactory(string name);
public delegate void Logger(Severity severity, Func<string> builder);

That’s our interface.

You can almost go home now

So, the NLog implementation we did in previous article will look now a little bit different:

1
2
3
4
5
6
7
8
9
10
11
public static LoggerFactory NLogLoggerFactory()
{
return name => { // factory
var logger = LogManager.GetLogger(name);
return (severity, builder) => { // logger
var level = ToLogLevel(severity);
if (logger.IsEnabled(level))
logger.Log(level, builder());
};
};
}

You can see that we declared a factory method which can be called LoggerFactory constructor. A LoggerFactory will construct a Logger every time you call it with logger name (name => { ... }). A Logger will log the message when called with severity and (message) builder ((severity, builder) => { ... }).

If you need simplest possible implementations of LoggerFactory I would say it would NullLoggerFactory followed by ConsoleLoggerFactory:

1
2
3
4
5
6
7
8
9
10
public static LoggerFactory NullLoggerFactory()
{
return name => (severity, builder) => { };
}
public static LoggerFactory ConsoleLoggerFactory()
{
return name => (severity, builder) =>
Console.WriteLine($"[{severity}] {name}: {builder()}");
}

Let’s look at specific usage. You have to create a logger factory first (you need one of those):

1
var loggerFactory = NLogLoggerFactory(); // or ConsoleLoggerFactory() ?

Then, you can create loggers when you need them:

1
var logger = loggerFactory("default");

and log messages like you always did:

1
logger(Severity.Warn, () => "Something is rotten in the state of Denmark");

You can also just sprint through all the layers:

1
loggerFactory("root")(Severity.Trace, () => "Adhoc message");

Job’s done. That’s what we wanted.

It is not exactly the same, right?

It is not. There is only one way to use it but wasn’t it a good thing?. Joking aside, we want our extension methods back. Good news is, all you need is to ask:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static class LoggerFactoryExtensions
{
public static Logger Logger(this LoggerFactory factory, string name) =>
factory(name); // the call actually happens here
public static Logger Logger(this LoggerFactory factory, Type type) =>
factory.Logger(type.FullName);
public static Logger Logger<T>(this LoggerFactory factory) =>
factory.Logger(typeof(T));
[MethodImpl(MethodImplOptions.NoInlining)]
public static Logger Logger(this LoggerFactory factory) =>
factory.Logger(new StackTrace().GetFrame(1).GetMethod().DeclaringType);
}

So now you can use extension methods on LoggerFactory or use LoggerFactory as a function (yes, it may look confusing):

1
2
3
4
5
// just call *it*
var logger = loggerFactory("RootLogger");
// or use extension
var logger = loggerFactory.Logger(typeof(GatewayController));
var logger = loggerFactory.Logger();

Normalizing Logger interface

In previous article we’ve introduced message Severity to reduce number of overloads, but when we added convenience methods there was 24 of them again (still better than 24 to be implemented on interface though). Let’s try to apply same tactics and normalize convenience layer as well. We can create new “interface” (it’s not technically an interface but it is still an interface). Let’s call it Channel (like Trace, Debug or Error channel).

1
public delegate void Channel(Func<string> factory);

As you can see, Channel is like a Logger, but without Severity, as Severity has been already applied. We can add some convenience methods as well:

1
2
3
4
5
6
7
8
9
10
11
12
public static partial class LoggerExtensions
{
public static Channel Channel(this Logger logger, Severity severity) =>
builder => logger(severity, builder); // partially apply severity
public static Channel Debug(this Logger logger) => logger.Channel(Severity.Debug);
public static Channel Trace(this Logger logger) => logger.Channel(Severity.Trace);
public static Channel Info(this Logger logger) => logger.Channel(Severity.Info);
public static Channel Warn(this Logger logger) => logger.Channel(Severity.Warn);
public static Channel Error(this Logger logger) => logger.Channel(Severity.Error);
public static Channel Fatal(this Logger logger) => logger.Channel(Severity.Fatal);
}

Now you can use like this:

1
2
var channel = logger.Trace();
channel(() => "This is trace message");

There is still only one way to format a message (using Func<string>). Although, we have a type (Channel) we can add extensions methods to it:

1
2
3
4
5
6
7
8
9
10
11
12
public static class ChannelExtensions
{
public static void Log(this Channel channel, Func<string> builder) =>
channel(builder); // the call actually happens here
public static void Log(this Channel channel, string message) =>
channel.Log(() => message);
public static void Log(this Channel channel, string pattern, params object[] args) =>
channel.Log(() => string.Format(pattern, args));
public static void Log(this Channel channel, Exception error) =>
channel.Log(error.ToString);
}

So, now we have all convenience methods back:

1
2
3
var logger = loggerFactory.Logger(); // for this class
logger.Warn().Log("This is a message with some args, like '{0}' for example", 7);
logger.Error().Log(new Exception("Failed to do something"));

Syntactically, I don’t like the parenthesis after channel (Trace, Debug, etc.). Unfortunately, we don’t have extension properties yet (C# 8, maybe?). As soon as they are available, they could be used to strip parenthesis from channel selection and produce prettier code:

1
2
var logger = loggerFactory.Logger(); // for this class
logger.Warn.Log("This is a message with some args, like '{0}' for example", 7);

Nice, isn’t it?

Full implementation

So, complete implementation of the interface with extension methods is:

While adapter for NLog could be implemented like:

What can be added?

Definitely, message expansion (builder()) should be wrapped in try...catch so badly formatted message cannot blow up the application. It would suggest doing it in Logger.Channel(this Logger logger, Severity severity) as everything ultimately goes through this function (yes, it is by design - there is only one place where it needs to be done).

I would also invest in better error.ToString to log exception. Some Func<Exception, string> (of course) which would explain the exception, processing inner exceptions and stack traces.

Convenience methods can be still added to Logger: like Log(Severity, ...), and all 24 overloads for Trace(...), Debug(...), etc. I didn’t do it here, as they are not really needed anymore, but if you really like them there is no problem to do so (see GitHub project for T4 implementation).

Sources

This project is available on GitHub. Please note, this is just a toy project to present some ideas rather than production ready solution.

You are better off with SAM

NOTE: This is part one of two part article. You can read second part here. To be honest, this is where interesting stuff starts.


This introduction is for hard core OO developers (mostly C# but maybe Java as well) who are trying to add FP to their skillset. If you are FP developer, you most likely know all those things.

SAM is the term introduced in Java 8 and means “Single Abstract Method”. It’s describes an interface with only one method. Of course, we had them before (both in Java and C#):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// C#
public interface IComparer<T>
{
int Compare(T alpha, T bravo);
}
public interface IEnumerable<T>
{
IEnumerator<T> GetEnumerator();
}
// Java
public interface Runnable {
void run();
}

but they became more visible in Java 8, as they were used to implement very important language feature. We will talk about this in few moments.

Design with SAM

Designing your system with SAMs has some quantifiable advantages.

First of all, it helps with Single Responsibility Principle and Interface Segregation Principle. Don’t get me wrong, it is still possible to do it wrong, and create single method with multiple responsibilities. Actually, some of the solutions presented in this article are not the purest, but they are, I hope at least, move in the right direction.

Second, your SAM interfaces are easier to implement. Did you ever try replace a component and found out that interface you need to implement has 50 methods? It just smells like “Oh, we had this God Object with some random methods and doing everything, but someone told us we need interfaces so we extracted every single possible method, job’s done”. They usually never get implemented again.

Third, they are easier to mock. I’m kind of reiterating second point here: they are easier to mock as there is only one method to fake, stub or mock (it’s not the same, I know, but whatever you call it, it’s still easier). You may say, that for bigger interfaces, you still need to mock only one method for a particular test. But which one, I would ask? Oh, the one which given test actually uses. Really? So now, you are making assumptions how exactly tested method works, instead of providing dependencies are checking if it satisfies acceptance criteria? Why testing it at all then? It is also a recipe for brittle tests. Change implementation a bit and your test will start to fail because your function under test calls different overload now (for example, the one with timeout passed as TimeSpan rather than int). Design it with SAM at there will be only one method to mock.

Oh, I forgot to mention, Functional Programmers also have a name for SAM, they call it… a function.

SAM in Java

Java has anonymous classes for injecting behaviour since 1997 (Java 1.1), so in Java world the concept is not new at all. Using them was just very clunky:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
interface Action<T> {
void run(T item);
}
private static <T> void forEach(Iterable<T> collection, Action action) {
for (T item : collection) {
action.run(item);
}
}
private static void printAll(Iterable<String> strings) {
forEach(
strings,
new Action<String>() { // <-- starts here...
@Override
public void run(String item) {
System.out.println(item);
}
} // <-- ...and ends here
);
}

If you look closely, the anonymous class implementing Action interface in printAll is what we would call lambda in C#. It is just completely wrist-unfriendly.

When lambdas were added, they wanted all those functions to support lambda. Who doesn’t like lambdas? Right? But they couldn’t just change them, as Java is all about backwards compatibility. Duplicating every method (to accept anonymous class or lambda) would be a huge task. They decided, and so far it seems like a smart move, that they won’t change the interfaces, they will just modify the compiler to generate those, a little bit inflated, anonymous classes for you (NOTE: this isn’t exactly true, Java 8 implementation of lambdas is actually quite optimized):

1
2
3
4
5
6
7
8
9
10
11
12
13
interface Action<T> {
void run(T item);
}
private static <T> void forEach(Iterable<T> collection, Action action) {
for (T item : collection) {
action.run(item);
}
}
private static void printAll(Iterable<String> strings) {
forEach(strings, item -> System.out.println(item)); // <-- starts and ends here :-)
}

From inside of forEach method nothing has changed, it still “thinks” it works with class implementing Action interface, but this class has been generated on the fly (well, again, not exactly true, but good-enough) from lambda.
This mechanics immediately breaks, of course, when expected interface has more than one (abstract) method, as we can only implement one with lambda function.

Anyway, what’s important to remember is the fact that interface with single abstract method is technically a function, and a function is technically an interface with single abstract method, for example, with IComparer and Comparison defined below:

1
2
3
4
5
6
public interface IComparer<in T>
{
int Compare(T x, T y);
}
public delegate int Comparison<in T>(T x, T y);

we can easily implement conversion function both ways: converting IComparer to Comparison is trivial as IComparer.Compare is-a Comparison while conversion the other way around would require a wrapper:

1
2
3
4
5
6
7
8
9
10
11
12
public class AdhocComparer<T>: IComparer<T>
{
private readonly Comparison<T> _comparison;
public AdhocComparer(Comparison<t> comparison) {
_comparison = comparison;
}
public int Compare(T x, T y) => _comparison(x, y);
}
// for some reason syntax highlight sometimes fails

I will point this fact again later, but please note that this is not a coincidence that converting to FP is usually trivial, while conversion to OO requires a little wrapper. Usually (at least) 4 lines: a class declaration, a field to store the function, a constructor to take function as argument, and single abstract method calling this function. That’s exactly what Java compiler does.

Nevertheless, SAM is function, function is SAM.

Design logging framework with SAM

If you ever used NLog or log4net you can imagine a ILoggerFactory and ILogger interfaces to be declared like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public interface ILoggerFactory
{
ILogger Logger(string name);
ILogger Logger(Type type);
ILogger Logger<T>();
ILogger Logger();
}
public interface ILogger
{
void Trace(string message);
void Trace(string pattern, params object[] args);
void Trace(Func<string> builder);
void Trace(Exception error, string message);
void Trace(Exception error, string pattern, params object[] args);
void Trace(Exception error, Func<string> builder);
void Debug(string message);
void Debug(string pattern, params object[] args);
void Debug(Func<string> builder);
void Debug(Exception error, string message);
void Debug(Exception error, string pattern, params object[] args);
void Debug(Exception error, Func<string> builder);
void Info(string message);
void Info(string pattern, params object[] args);
void Info(Func<string> builder);
void Info(Exception error, string message);
void Info(Exception error, string pattern, params object[] args);
void Info(Exception error, Func<string> builder);
void Warn(string message);
void Warn(string pattern, params object[] args);
void Warn(Func<string> builder);
void Warn(Exception error, string message);
void Warn(Exception error, string pattern, params object[] args);
void Warn(Exception error, Func<string> builder);
void Error(string message);
void Error(string pattern, params object[] args);
void Error(Func<string> builder);
void Error(Exception error, string message);
void Error(Exception error, string pattern, params object[] args);
void Error(Exception error, Func<string> builder);
void Fatal(string message);
void Fatal(string pattern, params object[] args);
void Fatal(Func<string> builder);
void Fatal(Exception error, string message);
void Fatal(Exception error, string pattern, params object[] args);
void Fatal(Exception error, Func<string> builder);
}

Right? With ILoggerFactory we can get logger with given name, logger for given type, or for given type but passed as generic, and maybe a logger for current scope (most likely it will be a class). With ILogger you can log messages of different severity (Trace, Debug, Info, etc.), and provide messages in few different ways: as a string, or maybe as a pattern to be expanded when logging, with or without Exception.

Anyway, great, let’s start implementing it. Method by method… Just joking.

It is one of those interfaces you should really ask: I really like all those methods, and I want them to be available but do I need to implement them all? No, you don’t.

Reduce to SAM

Let’s start with ILoggerFactory as it is much easier. You can notice that somewhere on the end, regardless which method on ILoggerFactory we call, we end up in Logger(string) as this is logger’s primary constructor and all other methods use it in some way:

1
2
3
ILogger Logger(Type type) => Logger(type.FullName);
ILogger Logger<T>() => Logger(typeof(T));
ILogger Logger() => Logger(new StackTrace().GetFrame(1).GetMethod().DeclaringType);

There is nothing in their implementation which would require them to be re-implemented in every possible implementation of ILoggerFactory. So, technically, this interface should be actually reduced to:

1
2
3
4
public interface ILoggerFactory
{
ILogger Logger(string name);
}

Single. Abstract. Method.

Although, you want all the convenience methods to be available. Right? Right.

Extending SAM

I can think of three obvious ways to deliver them to the potential user:

  1. Wrapper class: a new class, let’s say ExtendedLoggerFactory, which takes ILoggerFactory in constructor and delivers additional functionality.
  2. Abstract class: a class with a additional functionality implemented, but with ILogger Logger(string) left as abstract. No interface, just base class, let’s say LoggerFactoryBase (yup, a kitten just died somewhere).
  3. Extension methods: extension methods taking ILoggerFactory as this

For completeness, I have to say, that Scala has traits and implicit wrappers, while Java gives you default methods. It is outside of the scope this article, but worth googling (even if you are C# developer).

There are pros and cons to all of those solutions.

The wrapper class is probably the cleanest from OO perspective, but a little bit confusing and clunky: we implement ILoggerFactory but pass ExtendedLoggerFactory (alternatively, we can also pass ILoggerFactory and rewrap it all the time). Most of the clunkiness of this solution disappears when using IoC container (we always inject ExtendedLoggerFactory leaving ILoggerFactory for library developers).

Abstract class does not have this problem but enforces specific base class, pulling all the dependencies with it. It’s a viable solution, but I tend to stay away from partially implemented abstract classes.

Extension methods are quite controversial, as your extension methods are not polymorphic at all. Once defined, they cannot be overridden. With some functions it is not a problem as there is not “other” implementation of LINQ Where or Select, but it is possible to get it too far. If you think your extension methods may be controversial “hide” them in some namespace with needs to be imported explicitly, for example: LoggingFramework.Extensions. It you think they are just fine, put them into the same namespace as interface, let’s say LoggingFramework.Core. If you think they are so great that everyone should use them day and night, stick them into System.Linq (and add all the warning suppression directives). Definitely, this can make development very easy (because extension are always available thanks to IntelliSense), or it can make you very unpopular (for exactly the same reason). Use them wisely.

In this article I decided to go for extension methods. I think this approach is relatively pragmatic, never had problem with it in a field and even if there is a potential flaw, the net effect is positive. Actually, Reactive Extensions are using the same technique (just check what is available on IObservable<T> interface with and without System.Reactive namespace imported).

So, after this long introduction, the declaration of the interface and implementation of convenience methods:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface ILoggerFactory
{
ILogger Logger(string name);
}
public static class LoggerFactoryExtensions
{
[MethodImpl(MethodImplOptions.NoInlining)]
public static ILogger Logger(this ILoggerFactory factory) =>
factory.Logger(new StackTrace().GetFrame(1).GetMethod().DeclaringType);
public static ILogger Logger(this ILoggerFactory factory, Type type) =>
factory.Logger(type.FullName);
public static ILogger Logger<T>(this ILoggerFactory factory) =>
factory.Logger(typeof(T));
}

Single method on the interface, and some extension methods, which are just redirecting calls to that interface.

Reducing ILogger to SAM

ILogger is quite big. It is also quite repetitive:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public interface ILogger
{
void Trace(string message);
void Trace(string pattern, params object[] args);
void Trace(Func<string> builder);
void Trace(Exception error, string message);
void Trace(Exception error, string pattern, params object[] args);
void Trace(Exception error, Func<string> builder);
void Debug(string message);
void Debug(string pattern, params object[] args);
void Debug(Func<string> builder);
void Debug(Exception error, string message);
void Debug(Exception error, string pattern, params object[] args);
void Debug(Exception error, Func<string> builder);
void Info(string message);
void Info(string pattern, params object[] args);
void Info(Func<string> builder);
void Info(Exception error, string message);
void Info(Exception error, string pattern, params object[] args);
void Info(Exception error, Func<string> builder);
void Warn(string message);
void Warn(string pattern, params object[] args);
void Warn(Func<string> builder);
void Warn(Exception error, string message);
void Warn(Exception error, string pattern, params object[] args);
void Warn(Exception error, Func<string> builder);
void Error(string message);
void Error(string pattern, params object[] args);
void Error(Func<string> builder);
void Error(Exception error, string message);
void Error(Exception error, string pattern, params object[] args);
void Error(Exception error, Func<string> builder);
void Fatal(string message);
void Fatal(string pattern, params object[] args);
void Fatal(Func<string> builder);
void Fatal(Exception error, string message);
void Fatal(Exception error, string pattern, params object[] args);
void Fatal(Exception error, Func<string> builder);
}

Please note, that the methods here are Cartesian product of all choices we can make:

  • 6 severity levels (Debug, Trace, Info, Warn, Error, Fatal)
  • 2 ways to pass exception (with or without exception)
  • 3 ways to format parameters (string, Func<string> and string, params object[])

So we have 6 x 2 x 3 = 36 methods.

Let’s move one of the choices out of the interface, and introduce Severity enum. It will reduce this interface to just 6 methods:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public enum Severity
{
Trace, Debug, Info, Warn, Error, Fatal
}
public interface ILogger
{
void Log(Severity severity, string message);
void Log(Severity severity, string pattern, params object[] args);
void Log(Severity severity, Func<string> builder);
void Log(Severity severity, Exception error, string message);
void Log(Severity severity, Exception error, string pattern, params object[] args);
void Log(Severity severity, Exception error, Func<string> builder);
}

It’s the same technique you might have used for database normalization.

Next, I think that doubling number of overloads, only because we can call it with or without Exception is unnecessary, one dedicated overload for Exception is enough:

1
2
3
4
5
6
7
public interface ILogger
{
void Log(Severity severity, string message);
void Log(Severity severity, string pattern, params object[] args);
void Log(Severity severity, Exception error);
void Log(Severity severity, Func<string> builder);
}

Before we proceed it might be important to explain why these method pair exists (not only in our implementation, but in general, in all logging frameworks):

1
2
void Log(Severity severity, string message);
void Log(Severity severity, string pattern, params object[] args);

Isn’t the second one equivalent to calling first one with string.Format(...) (or with $"...")?

1
2
Log(Severity.Error, pattern, arg1, args2, ...);
Log(Severity.Error, string.Format(pattern, arg1, args2, ...));

Well, effect is the same, but side effects are different. When we leave expansion to the logging framework it won’t be done if logging is disabled (let’s say in production we do not log Severity.Trace). When doing string expansion yourself (string.Format or $"...") you do this before framework has a chance to decide if logging is enabled, so you do this even if expanded string is going to be swallowed, wasting CPU cycles and risking exception being thrown during this operation.

We already have deferral mechanism in this interface, though: Func<string>. Actually, all those four overloads can be implemented using only one method on interface and convenience method on extender:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public interface ILogger
{
void Log(Severity severity, Func<string> builder);
}
public static class LoggerExtensions
{
public static void Log(
this ILogger logger, Severity severity, string message) =>
logger.Log(severity, () => message);
public static void Log(
this ILogger logger, Severity severity, string pattern, params object[] args) =>
logger.Log(severity, () => string.Format(pattern, args));
public static void Log(
this ILogger logger, Severity severity, Exception error) =>
logger.Log(severity, error.ToString);
}

NOTE: Exception.ToString is Func<string>

Of course, we want our convenience methods back. Let’s add them as extension methods, using T4 template engine this time (we could do this by hand, as this is generated only once, but using T4 is useful skill to have):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static class MoreLoggerExtensions
{
<# foreach (var level in new[] { "Trace", "Debug", "Info", "Warn", "Error", "Fatal" }) { #>
#region <#= level #>
public static void <#= level #>(this ILogger logger, string message) =>
logger.Log(Severity.<#= level #>, message);
public static void <#= level #>(this ILogger logger, Func<string> builder) =>
logger.Log(Severity.<#= level #>, builder);
public static void <#= level #>(
this ILogger logger, string pattern, params object[] args) =>
logger.Log(Severity.<#= level #>, pattern, args);
public static void <#= level #>(this ILogger logger, Exception error) =>
logger.Log(Severity.<#= level #>, error);
#endregion
<# LF(level != "Fatal"); } #>
}
<#+ void LF(bool condition = true) { if (condition) WriteLine(""); } #>

Note that these methods are not necessary, they do not add new features. They are just convenient redirects. They do not have to be implemented ever again as long as ILogger has single abstract method void Log(Severity severity, Func<string> builder).

Implementing adapters for NLog

So we need to implement these two interfaces:

1
2
3
4
5
6
7
8
9
public interface ILoggerFactory
{
ILogger Logger(string name);
}
public interface ILogger
{
void Log(Severity severity, Func<string> builder);
}

to make NLog compatible with our logging facade. Let’s do it…

First thing which definitely needs to be addressed is the fact that NLog does not “understand” our Severity. It uses its own enumeration called LogLevel. We need to translate it:

1
2
3
4
5
6
7
8
9
10
11
12
private static LogLevel ToLogLevel(Severity severity)
{
switch (severity) {
case Severity.Trace: return LogLevel.Trace;
case Severity.Debug: return LogLevel.Debug;
case Severity.Info: return LogLevel.Info;
case Severity.Warn: return LogLevel.Warn;
case Severity.Error: return LogLevel.Error;
case Severity.Fatal: return LogLevel.Fatal;
default: return LogLevel.Off;
}
}

Second thing is, NLog does not have an overload taking Func<string>. It has the one taking a string or a string, params object[]. We can settle with the string version and use:

1
2
3
var level = ToLogLevel(severity);
if (logger.IsEnabled(level))
logger.Log(level, builder());

There is another way to do deferred expansion, though. It involves small wrapper class (again!) taking Func<string> and calling it in .ToString():

1
2
3
4
5
6
private class DeferredToString
{
private readonly Func<string> _builder;
public DeferredToString(Func<string> builder) { _builder = builder; }
public override string ToString() { return _builder(); }
}

Now, we could use it like this:

1
logger.Log(ToLogLevel(severity), "{0}", new DeferredToString(builder));

but, even if I actually like it more, it is not necessary and it has some negative performance implications. As I said before, the sole existence of this 4 line class is admission that OO design is not as expressive as FP.

Both ways, it will work just fine, and the implementation is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class NLogLoggerFactory: ILoggerFactory
{
public ILogger Logger(string name) =>
new NLogLogger(LogManager.GetLogger(name));
}
public class NLogLogger: ILogger
{
private readonly Logger _logger;
public NLogLogger(Logger logger) { _logger = logger; }
public void Log(Severity severity, Func<string> builder)
{
var level = ToLogLevel(severity);
if (_logger.IsEnabled(level))
_logger.Log(level, builder());
}
}

Done. Now NLog is compatible with our facade.

Full implementation

So, let me reiterate, as might have disappeared in wall of text:

This is The Interface:

These are The Extensions, a set of functions we extracted from interface, as they don’t really need to be there:

The third part is The Convenience Layer, an even bigger set of functions, which do not added functionality but make typing easier:

Please note, that this is not a .cs file, it is a .tt file, I just used .cs extension on gist to have syntax highlight. The expanded version of this template can be found here

The last part, most likely in different assembly (as it has third party dependency) is The Adapter, adapting actual implementation to our abstract interface:

Summary

We reduced the interface surface from 40 methods (36 + 4), to 2 without affecting functionality, all you need to implement (or fake) logging system is this:

1
2
3
4
5
6
7
8
9
public interface ILoggerFactory
{
ILogger Logger(string name);
}
public interface ILogger
{
void Log(Severity severity, Func<string> builder);
}

All the methods are still available, though:

intellisense

Further with SAM

You can go further with SAM by using just functions. Please read second part here.

Kruskal/DFS hybrid with reduced branching factor

Read original blog-post first

This is just an update to previous blog-post titled Kruskal, Kotlin, and Hex Tiles. I assume you read it, otherwise some things may not make sense.

Problem with “pure” algorithms

We already tried Depth-First Search and Kruskal’s algorithm. They both have some disadvantages. Depth-First Search has low branching factor, meaning that is does not branch unless it gets stuck, so it actually can create one very long path through the whole maze to the point where it is hard to call it “maze” anymore.
On the other side there is Kruskal’s algorithms which is all about branching. The problem with branching is that even if it creates a dead-end the length of dead-end branch is quite often low (let’s say one or two “rooms”) and is very easy to spot.
The “challenge” was to create algorithm which is a hybrid of Depth-First Search and Kruskal’s algorithm.

Original Kruskal's algorithm. Branches, branches everywhere

A Trailblazer algorithm

For this I needed a DFS algorithm using the same domain model as previously implemented Kruskal’s algorithm. It assumed existence of nodes and edges, having no constraint on node (vertex) and expecting edge to be a pair of nodes (vertices):

1
2
3
4
interface Edge<N> {
val A: N
val B: N
}

Algorithm itself had very simple interface, it was taking a sequence of edges (most likely randomized), and provided a method called next() returning next edge forming spanning tree. Please note that in languages with generators (Kotlin is not blessed with them, yet) it could be implemented as function taking a sequence of edges (Sequence<E>) and a returning sequence of edges (Sequence<E>). It had to define method next() instead which just returns next edge (equivalent of yield return) or null (kind-of yield break) if no more edges can be found:

1
2
3
4
5
class Kruskal<N, E : Edge<N>>(edges: Sequence<E>) {
fun next(): E? {
// implementation
}
}

This algorithm will have similar interface (although there is no explicitly defined interface) returning sequence of edges:

1
2
3
4
5
class Trailblazer<N, E : Edge<N>>(...) {
fun next(): E? {
// implementation
}
}

I called it Trailblazer because it is not exactly a Depth-First Search as it does not have backtracking. Backtracking in DFS is used to handle dead-ends (by branching), while in this hybrid algorithm branching is handled by Kruskal’s algorithm, so trailblazer is expected to just push forward.

There is a slight impedance between model used by Kruskal’s algorithm and Trailblazer, so the latter will use some helper methods to adapt:

1
2
3
4
5
6
7
class Trailblazer<N, E : Edge<N>>(edges: (N) -> Sequence<E>) {
private val edges = edges
private val visited = mutableSetOf<N>()
private var head: N? = null
// ...
}

it will need a function (edges) which will provide sequence of edges going out of given node. It will need a set of already visited nodes (visited) and current location (head).

Edges in “Kruskal’s” model are just a pairs of nodes, while for Trailblazer direction is very important. Therefore we will need a method to find “opposite end” of an edge:

1
2
3
4
5
6
private fun opposite(node: N, edge: E): N? =
when (node) {
edge.A -> edge.B
edge.B -> edge.A
else -> null
}

we will also need mark visited nodes and optionally move head to newly visited one. This method will also return true if node has been just added (meaning has not been visited before):

1
2
3
4
5
fun visit(node: N, reset: Boolean = false): Boolean {
val added = visited.add(node)
if (reset && added) head = node
return added
}

This does not look pretty, I have to admit, but it helped keep next method quite short:

1
2
3
4
fun next(): E? {
val current = head ?: return null
return edges(current).firstOrNull { visit(opposite(current, it)!!, true) }
}

I actually like val current = head ?: return null syntax. Kotlin allow you to put control statements like return, break and continue in places where you would expect expressions, when it makes expression value irrelevant. In this case it will extract value from nullable head and put it into current, or it will exit this method returning null immediately. It’s kind-of “something or die()” in PHP.
After that, it takes all edges going out of current node and finds first which opposite end has not been visited yet. So it is exactly like DFS, it just does not have backtracking.

Bind two algorithms together

These two (Kruskal and Trailblazer) algorithms will have to work together, and they need to expose some methods for communication.
First, Kruskal, needs to expose ability to merge node sets (it is the most important concepts in Kruskal’s algorithm, so if you don’t know what I’m talking about please refer to previous blog-post):

1
2
3
4
class Kruskal<N, E : Edge<N>>(...) {
// ...
fun merge(a: N, b: N) = sets.merge(a, b)
}

On the other side of the fence, Trailblazer algorithm will need to be restarted every time Kruskal jumps from one location to another:

1
2
3
4
class Trailblazer<N, E : Edge<N>>(...) {
// ...
fun reset(node: N) { head = node }
}

That’s all we need.

Let’s do the Hybrid algorithm now. It will use the same “interface”, of course:

1
2
3
4
5
6
class Hybrid<N, E : Edge<N>>(edges: Sequence<E>, threshold: Double, rng: () -> Double) {
private val rng = rng
private val threshold = threshold
fun next(): E? = // ...
}

On top of usual stuff (sequence of edges) it will also take random number generator (rng) and a threshold which will control how biased towards Trailblazer (0.0) or Kruskal (1.0) it will be.

It will also need a function returning outgoing edges for Trailblazer. Let’s start with building a dictionary (map) of all edges:

1
2
3
4
5
6
7
8
9
10
11
private val map = mapEdges(edges)
private fun mapEdges(edges: Sequence<E>): Map<N, List<E>> {
val result = mutableMapOf<N, MutableList<E>>()
fun link(node: N, edge: E) = result.getOrPut(node, { mutableListOf() }).add(edge)
for (edge in edges) {
link(edge.A, edge)
link(edge.B, edge)
}
return result
}

It goes through all edges and for both ends (nodes A and B) adds this edge as outgoing (link). So, the result is a dictionary from nodes to list of edges (Map<N, List<E>>). There might be an important question to ask here, if those lists need to be shuffled again, but I assume that input sequence was already shuffled, so shuffling already shuffled sequence does not increase its randomness. Although, in this case, there is a chance I’m completely wrong.

We can use this dictionary to define function needed by Trailblazer algorithm (see Trailblazer’s constructor):

1
2
private fun getEdges(node: N): Sequence<E> =
map[node]?.asSequence() ?: emptySequence<E>()

All those question marks are to handle potential misses (and propagate nulls instead of throwing exceptions). So, what this function does is finds a node in dictionary and returns a sequence of edges incidental to this node or, in case node was not in dictionary, it return empty sequence.

Hybrid algorithm encapsulates both algorithms, original Kruskal and Trailblazer algorithms:

1
2
private val kruskal = Kruskal(edges)
private val trailblazer = Trailblazer({ node: N -> getEdges(node) })

it also combines next functions from both:

1
fun next(): E? = nextTrailblazer() ?: nextKruskal()

which means: try Trailblazer first, and if it fails, try Kruskal’s. If both of them failed then that’s it.
First let’s implement about nextTrailblazer:

1
2
3
4
private fun nextTrailblazer(): E? =
(if (rng() < threshold) null else trailblazer.next())?.apply {
kruskal.merge(A, B)
}

As you can see, it makes a call if it should use Trailblazer algorithm in this step at all. For example, if threshold is set to 0.1 there is a 10% chance on every step that Trailblazer will stop and switch back to Kruskal. Therefore for threshold set to 1.0 it would be working exactly like original Kruskal and Trailblazer’s step would never be executed. For threshold set to 0.0 it would strongly prefer Trailblazer switching to Kruskal only when Trailblazer hit dead-end.
If it decided to use Trailblazer and Trailblazer actually found an edge, both ends of this edge are added to Kruskal’s disjoint-set, making Kruskal’s part of the algorithm aware of this edge being returned.

On the other side, nextKruskal is implemented as follows:

1
2
3
4
5
6
private fun nextKruskal(): E? =
kruskal.next()?.apply {
trailblazer.visit(A)
trailblazer.visit(B)
trailblazer.reset(if (rng() < 0.5) A else B)
}

It takes next edge from Kruskal’s algorithm and if it succeeded, adds marks both ends as visited for Trailblazer algorithm and resets Trailblazer’s starting location.

The presentation layer

There is not really too much to do in presentation layer, there are two lines which have been modified. Actually, it’s still one line too much. If Kruskal and Hybrid implemented same interface from the start it would just one line, but adding interface now is a little bit too late - I just want to make it run. Anyway, it there was an interface it would be interface Sequencer<T> { fun next(): T? }.

So, the lines we need to change:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// here: Kruskal -> Hybrid
fun animate(algorithm: Hybrid<Tile, Door>) {
algorithm.next()?.apply {
paint(context)
handle = window.setTimeout({ animate(algorithm) }, 0)
}
}
val KRUSKAL_BIAS = 0.1 // new constant to control bias
fun launch() {
// ...and here: Kruskal -> Hybrid
animate(Hybrid(
buildWorld(WORLD_WIDTH, WORLD_HEIGHT).shuffled(),
KRUSKAL_BIAS, { Math.random() }))
}

Effect

It seems that it does exactly what I intended. That’s how it looks after few steps:

Hybrid algorithm generates longer isolated paths

Conclusion

I really liked OCP in action. I mean, it did require one line to be added to Kruskal’s algorithm to make it work, but arguably merge method should be exposed from the beginning or disjoint-set (sets) should be injected into it. Anyway, Kruskal class has been completely reused, and new algorithm (Hybrid) composes Kruskal and pseudo-DFS (Trailblazer) quite nicely. I could polish it a little bit, but I think it is good-enough.

Sources

You can find sources here or you can just use online demo

Kruskal, Kotlin, and Hex Tiles

One more time…

So the next approach, after Randomized depth-first search, Randomized depth-first search with stack shaking, Random spanning tree with Prim’s algorithm, to maze generation is Kruskal’s algorithm. Technically, it’s still the same thing: random spanning tree, it’s just different approach. This time the new tech to try was: Kotlin and Jade/Pug. I didn’t do too much Jade, I just wanted to try, but I have to say again: Kotlin… good stuff.

The algorithm

Kruskal algorithm, is quite simple to describe:

  • Take edge with lowest weight
    • if it would form a cycle, ignore it
    • otherwise, add it to solution
  • if there are still edges left, repeat

To apply Kruskal’s algorithm to maze generation we don’t need to do “minimum spanning tree” as “random spanning tree” is enough. So “take edge with lowest weight* should be replaced with “take any edge”. To achieve that we can just shuffle all the edges before feeding them to the algorithm. Let’s write a shuffle method to shuffle array in-place, and shuffled function returning a shuffled version of given sequence:

1
2
3
4
5
6
7
8
9
10
11
12
13
fun <T> MutableList<T>.swap(x: Int, y: Int) {
val t = this[x]
this[x] = this[y]
this[y] = t
}
fun <T> MutableList<T>.shuffle() {
fun random(range: Int) = Math.floor((Math.random() * range) + 1.0)
for (i in size - 1 downTo 0) swap(i, random(i))
}
fun <T> Sequence<T>.shuffled(): Sequence<T> =
this.toMutableList().apply { shuffle() }.asSequence()

NOTE: If you are unfamiliar with Kotlin it might a little bit obscure. All three methods above are extension methods (familiar for C# users), and for all of them this is implicitly pointing to the object they have been executed for. So, this[x] (in swap) is accessing element x in MutableList, size (in shuffle) is the length of MutableList. Extension method apply is a different story.

The only challenge is “cycle detection”. I used disjoint-set data structure, and I strongly recommend reading my other blogpost.

For Kruskal’s algorithm we need to define an Edge:

1
2
3
4
interface Edge<N> {
val A: N
val B: N
}

which is just an entity connecting two nodes, A and B. The algorithm itself is very simple:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Kruskal<N, E : Edge<N>>(edges: Sequence<E>) {
val iterator = edges.iterator()
val sets = DisjointSet<N>()
fun next(): E? {
if (!iterator.hasNext())
return null
val edge = iterator.next()
if (sets.test(edge.A, edge.B))
return next()
sets.merge(edge.A, edge.B)
return edge
}
}

One challenge, as mention before, is “cycle detection” which is handled by DisjointSet. It also, to allow animation, returns only one edge at the time (see next). So what it does?

It takes a sequence of edges as input. They are assumed to be in right order, sorted by weight for minimum spanning tree, and randomized for random spanning tree. It creates empty DisjointSet to track cycles. On each step, it checks if there are still edges to test (iterator.hasNext). If so, it takes next edge and check if it would form a cycle (sets.test). If it would, it tries next edge, if it wouldn’t it adds this edge to solution (sets.merge) and returns it.

That’s kind of it. Rest is just presentation.

Hex tiles

All algorithms I was using so far were in square grid space, but they did not need to be. So for this one I decided to build a maze of hex tiles.

Hex tiles 5x5

It added some complexity to coordinates and drawing. I won’t be getting into details as there is a lot of websites talking about hex tiles as they are foundation of many games. If you are interested just start here.

The domain model is quite trivial:

1
2
data class Tile(val x: Int, val y: Int)
data class Door(override val A: Tile, override val B: Tile) : Edge<Tile>

there are tiles and they are connected with doors. It is worth noting that Door implements Edge<N> interface.

Building the world in rectangular space wasn’t particularly tricky but required some pen and paper experiment to get connection right:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fun buildWorld(width: Int, height: Int): Sequence<Door> {
val result = mutableListOf<Door>()
val map = mutableMapOf<Int, Tile>()
fun encode(x: Int, y: Int) = y * (width + 1) + x
fun tileAt(x: Int, y: Int) = map.getOrPut(encode(x, y)) { Tile(x, y) }
for (y in 0..height) {
for (x in 0..width) {
val tile = tileAt(x, y)
if (x > 0) result.add(Door(tile, tileAt(x - 1, y)))
if (y > 0) result.add(Door(tile, tileAt(x, y - 1)))
if (x < width && y > 0 && x % 2 == 0) result.add(Door(tile, tileAt(x + 1, y - 1)))
if (x > 0 && y > 0 && x % 2 == 0) result.add(Door(tile, tileAt(x - 1, y - 1)))
}
}
return result.asSequence()
}

The method above returns a an ordered sequence of doors (we will need to shuffle them for the algorithm).

Presentation layer is a little bit messy to be honest, but I just wanted to make it work. Using image below and some primary school maths

Geometry

we can calculate positions of tiles in pixels and needed size of canvas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
val TILE_COLOR = "#fff"
val DOOR_COLOR = "#eee"
val TILE_R = 8.0
val TILE_H = TILE_R * Math.sqrt(3.0) / 2
val TILE_MARGIN = (TILE_R - TILE_H) * 2
data class Point(val x: Double, val y: Double)
fun Tile.center(): Point {
val rx = x * TILE_H * 2 + TILE_R
val ry = y * TILE_R * 2 + TILE_H + (x % 2) * TILE_R
return Point(rx + TILE_MARGIN, ry + TILE_MARGIN)
}
fun worldSize(width: Int, height: Int): Point {
val rx = width * TILE_H * 2 + TILE_R * 2
val ry = height * TILE_R * 2 + TILE_H * 2 + TILE_R
return Point(rx + TILE_MARGIN * 2, ry + TILE_MARGIN * 2)
}

On top of that we can draw tiles as well:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
fun Tile.paint(context: CanvasRenderingContext2D) {
val (x, y) = center()
val r = TILE_R
val h = TILE_H
context.fillStyle = TILE_COLOR
context.beginPath()
context.moveTo(x + r, y)
context.lineTo(x + r / 2, y + h)
context.lineTo(x - r / 2, y + h)
context.lineTo(x - r, y)
context.lineTo(x - r / 2, y - h)
context.lineTo(x + r / 2, y - h)
context.closePath()
context.fill()
}
fun Door.paint(context: CanvasRenderingContext2D) {
val (sx, sy) = A.center()
val (ex, ey) = B.center()
context.strokeStyle = DOOR_COLOR
context.lineWidth = TILE_R
context.beginPath()
context.moveTo(sx, sy)
context.lineTo(ex, ey)
context.closePath()
context.stroke()
A.paint(context)
B.paint(context)
}

Just note that these paint functions are extension methods for Tile and Door respectively.

User interface

The only remaining thing is presentation and some user interaction.

We need to get references to some DOM elements:

1
2
3
val canvas = document.getElementById("main") as HTMLCanvasElement
val context = canvas.getContext("2d") as CanvasRenderingContext2D
val button = document.getElementById("restart") as HTMLButtonElement

then configure canvas:

1
2
3
val size = worldSize(WORLD_WIDTH, WORLD_HEIGHT)
canvas.width = size.x.toInt()
canvas.height = size.y.toInt()

and attach event listener to Restart button:

1
2
3
4
5
button.onClick {
cancel()
clear()
launch()
}

which will potentially kill previous animation, clear the canvas and start new animation.
Let’s implement those. Clearing canvas is just about painting it black:

1
2
3
4
fun clear() {
context.fillStyle = "#000"
context.fillRect(0.0, 0.0, size.x, size.y)
}

Starting animation is a little bit more complex:

1
2
3
4
5
6
7
8
9
10
11
12
var handle: Int? = null
fun animate(algorithm: Kruskal<Tile, Door>) {
algorithm.next()?.apply {
paint(context)
handle = window.setTimeout({ animate(algorithm) }, 0)
}
}
fun launch() {
animate(Kruskal(buildWorld(WORLD_WIDTH, WORLD_HEIGHT).shuffled()))
}

It does have a handle (nullable int) to store timeout handler so we can cancel it if needed. We starting animation (launch) it generates all the edges (buildWorld) and shuffles them (shuffled). Then passes this sequence of edges to animate function which is handling one edge at the time using a timer (window.setTimeout). It takes next edge (algorithm.next()), paints it (paint) and schedules next step (handle = window.setTimeout(...)). It worth noting that when first null edge is returned the whole loop stops.

Finally, the cancel method:

1
2
3
4
5
6
fun cancel() {
if (handle != null) {
window.clearTimeout(handle!!)
handle = null
}
}

which just cancels potentially scheduled “next step”, therefore cancelling whole animation.

Conclusion

This is very subjective but Kotlin seems to me to be most polished from all languages I’ve tried. But they are all really good. Fable has a lot of community behind it, Scala.js is backed by… you know… Scala and Kotlin is done by JetBrains. There is elephant in the room as well, and it is called TypeScript. Maybe next time.

Sources

You can find sources here or you can just use online demo

Curious case of disjoint-set

While implementing Kruskal’s algorithm to build mazes (also known as random spanning trees) I encountered interesting problem. Randomized version of Kruskal’s algorithms is quite simple: take any edge, if it would form a cycle reject it (as it will not be a tree anymore) otherwise accept it. That’s it. It’s really simple, there is only one problem: how to detect cycles.

On this picture you can see two separate trees (a forest):

Forest

It is quite clear that connecting 3 and 7 won’t form a cycle as vertex 7 has not been visited yet. The difference between edges 3-1 and 3-6 is not so obvious anymore. All of those vertices (nodes) are visited, but 3-1 will form a cycle, while 3-6 will not.

It would help if we knew which tree given node belongs to, as cycle is formed only when connecting two visited nodes from the same tree (3-1). When connecting visited nodes from different trees, we do not create a cycle, we just connect two trees forming new bigger tree (3-6).

Storing something like TreeId on each node and updating it when trees are merged would theoretically work but would be quite slow. Imagine that we just added single edge connecting two trees, let’s call them A and B. What we would need to do now is to update all nodes from smaller tree (let’s say it is B) and tell them “you are tree A now”. Now let’s assume both trees have 1000000 vertices… oops.

We need a better data structure to store such sets and, fortunately, there is one. It is called disjoint-set (also known as union-find or merge-find set) and it serves exactly that purpose.

How it works?

Disjoint-set organizes items into trees where every item has a parent. Two items belong to the same set when they have same parent.
Let’s start with set of items where no merges has been done so every item is in its own separate set:

Seven distinct sets

Merge

Merging two items into set is about assigning one as a parent of the other one:

One set with 3 items

Now, the root 2 identifies the whole set so the question “Which set item 1 belongs to?” is answered by “It belongs to set 2“. You can also say: 2 is representative items for the whole set.

On the diagram below, we can see two sets: set 2 and set 5. Items 1, 2 and 3 belong to set 2, while items 4, 5, 6, 7 belong to set 5. Which items becomes a root in merging process is irrelevant although we will try to limit the height of the tree to reduce potential number of hops.

Two sets, one with 3 the other with 4 items

Merging sets works exactly as it was shown before but it will be clearer with the picture:

Merging sets

We are trying to merge set containing item 3 with set containing item 7. First we need to find roots of those items (2 and 5 respectively) and then make one the parent of the other one. For algorithm correctness it can be either of those roots, but for performance reasons we choose the root of the higher one as new root. It helps keeping the tree relatively flat, as attaching tree of height 2 to the root of tree of height 3 does not change overall height. If both trees are of equal height we choose one arbitrarily and increase the height of resulting tree. That’s exactly what happened on the picture above, when two trees of height 1 (single item is height 0) formed new tree of height 2 after being merged.

With little though experiment, we can show that minimal tree of height 0 is a single item and minimal tree of height 1 is two items. As height increases only when merging trees of the same height tree of height 2 has to have at least 4 item. Merging two trees of height 2 creates tree of height 3 with at least 8 items. I guess, you can spot the pattern: there is minimum of 2^h items in the tree of height h, therefore finding a root has a pessimistic complexity of O(logn). I emphasized the word pessimistic as usually it does much better.

Find with path compression

Finding a root of element can be used to compress the path at same time. As item’s potentially distant root is found, its parent can be updated to point directly to this root therefore compressing the path.

While merging 3 and 8 on the picture below:

Merging sets with compression

two things can be spotted:

  • root of 3 has been found (5) and parent information has been updates so 3 points to 5 directly from now on
  • 8 is a smaller tree than 5, so 5 becomes a parent of 8

Because of these two techniques union by rank and path compression amortized complexity is lower than O(logn). Wikipedia says:

These two techniques complement each other; applied together, the amortized time per operation is only O(a(n)), where a(n) is the inverse of the function n = f(x) = A(x,x), and A is the extremely fast-growing Ackermann function. Since a(n) is the inverse of this function, a(n) is less than 5 for all remotely practical values of n. Thus, the amortized running time per operation is effectively a small constant.

I actually love the “is less than 5 for all remotely practical values of n” part.

Implementation

All items in set need two properties: parent and rank (or height). There are two possible approaches: objects in set would need to implement some specific interface (T: IDisjointSetExtraInfo) or we could maintain some internal dictionary Dictionary<T, ExtraInfo> and store required extra information this way. As usual there are pros and cons of both approaches.

Trade-offs everywhere

The approach with dictionary is more generic, so I’m going to use it, and allow any T, with no constraints (apart from equality).

I’ve originally needed an implementation in Kotlin but as solution is quite generic I’ve also added an implementation in F# to my ever growing library-of-data-structures-which-I-may-want-to-use-in-F#-on-day (TM).

Tag

Let’s start with encapsulation of, mentioned before, “extra info”:

1
2
3
4
5
// Kotlin
private class Tag() {
var parent = this
var height = 0
}
1
2
3
4
5
// F#
module DisjointSet =
type private Tag() as this =
member val parent = this with get, set
member val height = 0 with get, set

(Completely off-topic: what F# compiler generates here is extremely puzzling, I understand it handles parent = this but it still puzzles me. Check it with ILSpy if you dare)

So, we have extra info class (called Tag), so far.

Find

We can implement find with path compression which is just following parent link on the way up and updating it on the way back:

1
2
3
4
5
6
// Kotlin
private fun find(tag: Tag): Tag {
if (tag.parent != tag)
tag.parent = find(tag.parent)
return tag.parent
}
1
2
3
4
5
// F#
let rec private find (tag: Tag) =
if tag.parent <> tag then
tag.parent <- find(tag.parent)
tag.parent

Merge

Implementing merge (or union) is a little bit complicated, but just a little. We need to find roots of both sets. If they are the same item, it means that objects are already in the same set therefore there is nothing to merge. If roots are different, they are in different sets, so we need to merge them by setting parent property of one root to the other one, potentially updating height (or rank):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Kotlin
private fun merge(x: Tag, y: Tag) {
val xroot = find(x)
val yroot = find(y)
if (xroot == yroot)
return
if (xroot.height < yroot.height) {
xroot.parent = yroot
} else {
yroot.parent = xroot
if (xroot.height == yroot.height)
xroot.height++
}
}
1
2
3
4
5
6
7
8
9
10
// F#
let private merge tagA tagB =
match find(tagA), find(tagB) with
| rootA, rootB when rootA <> rootB ->
match rootA.height - rootB.height with
| balance when balance >= 0 ->
rootB.parent <- rootA
if balance = 0 then rootA.height <- rootA.height + 1
| _ -> rootA.parent <- rootB
| _ -> ()

Map

Now, we can implement the translation layer between Tag and T, most likely a class encapsulating a dictionary:

1
2
3
4
5
// Kotlin
class DisjointSet<T> {
private val map = mutableMapOf<T, Tag>()
//...
}
1
2
3
4
// F#
type DisjointSet<'T when 'T : equality>() =
let map = Dictionary<'T, Tag>()
//...

Test

Find method, implemented before, makes sense only in a domain of tags which are not exposed outside this module/package. The value returned by find is also not really worth keeping as it may change all the time while sets are merged. What we want to expose though is the function which will test if two items are in the same set.

There are two possible optimizations here:

  • We do not need to go though the process if both items (both Ts) are the same item (if (x == y) return true)
  • if one of the items is not in dictionary at all, it means that it was not taking part in any merge operation yet, therefore it cannot be in the same set as the other one
1
2
3
4
5
6
7
// Kotlin
fun test(x: T, y: T): Boolean {
if (x == y) return true
val xtag = map[x]
val ytag = map[y]
return xtag != null && ytag != null && find(xtag) == find(ytag)
}
1
2
3
4
5
6
7
8
9
10
11
// F#
let get key =
let result = ref Unchecked.defaultof<Tag>
match map.TryGetValue(key, result) with | false -> None | _ -> Some result.Value
member x.Test(keyA: 'T, keyB: 'T) =
(keyA = keyB) || (
match get keyA, get keyB with
| Some tagA, Some tagB -> find(tagA) = find(tagB)
| _ -> false
)

The get method in F# is a little wrapper for TryGetValue. It wraps quite ugly Key -> 'Value byref -> bool and converts it into much more functional 'Key -> 'Value option.

Merge

We had merge already implemented, all we need is handling the translation between T and Tag:

1
2
3
4
5
6
// Kotlin
fun merge(x: T, y: T) {
val xtag = map.getOrPut(x) { Tag() }
val ytag = map.getOrPut(y) { Tag() }
merge(xtag, ytag)
}
1
2
3
4
5
6
// F#
let set key tag = map.[key] <- tag; tag
let getOrCreate key = match get key with | Some v -> v | None -> Tag() |> set key
member x.Merge(keyA: 'T, keyB: 'T) =
merge (getOrCreate keyA) (getOrCreate keyB)

And again, we needed a little wrapper functions in F#. Sometimes .NET disappoints me with quite minimalistic API.

Regardless of my complaints, that’s it. Please mention disjoint-set when talking to your friends, maybe when discussing Ackermann function or generating mazes using Kruskal’s algorithm.

Maze generator again this time with Scala.js

Background

So last week I was doing maze generator using randomizes depth first search with Fable. Then, to increase “branching factor” I’ve added stack shaking. Today it’s time for slightly different approach.

As I said before this task was just kind of excuse technologies which I never used before. So far, I managed to scratch the surface of Fable, Webpack and VirtualDOM. For performance reasons VirtualDOM got replaced by jCanvas.

So, today’s new tech is Scala.js! Yay! I’m a big fan of Scala although I did not have a chance to use it for anything bigger than HelloWorld so far. I’m not saying that this task is much bigger, but at least it does something. Anyway, Scala.js, here I come!

Setting environement up

It was not trivial to set up the environment. I actually struggled with the environment for couple of days before I managed to make it run. Making it work with Webpack was painful, especially because I’m not proficient in either of those. Apparently, Scala.js does not produce modular JavaScript and expects everything to be in global, so instead of:

1
2
var jquery = require("jquery");
var scalajs = require("scalajs")(jquery);

we need this:

1
2
3
4
5
// not actual code!
var jquery = require("jquery");
global.jQuery = jquery;
require("scalajs");
var scalajs = global.scalajs;

Quite nasty. Maybe there is easier way, but it wasn’t obvious. If you know how to do it better let me know, but if you have similar problem you can use my generic empty project, but be aware - is highly opinionated.

Let’s do some coding now…

The algorithm

Most of maze generation algorithms on Wikipedia are building spanning trees for graphs where vertices are representing rooms and edges are representing doors.

Last week’s approach was randomized depth first search now it’s time for Prim’s algorithm.

Prim’s algorithm is building minimum spanning tree. We don’t need minimum, we need random spanning tree (that’s what randomized depth first search was doing). To achieve that, we can assign random weights to edges so minimum spanning tree will actually become random spanning tree. I didn’t but it could be actually interesting to play with different random distributions.

Let’s start with modelling the Node (or Vertex) and Edge:

1
2
3
4
5
6
7
8
9
trait Node[E] {
def edges: Seq[E]
}
trait Edge[N] {
def A: N
def B: N
def weight: Double
}

If you don’t know what trait is, you can think about this as interface from Java or C#. It is a little bit more complicated than that, but it is good enough aproximation, at least for this model. So, Node (vertex) has a sequence (list?) of edges going out, and Edge has two nodes, beginning and end, plus weight. That’s what Prim’s algorithm needs to work.

Actually, Edge.weight does not need to be modelled as Double. It could be declared as type parameter, let’s say W:

1
2
3
4
5
trait Edge[N, W] {
def A: N
def B: N
def weight: W
}

In such case implementation of Prim’s algorithm would need a way to compare two Ws (Ordering[W] or IComparator<W>) but, for simplicity, I’ve implemented it as Double so let’s leave it like this.

So, let’s start with Prim’s solver:

1
2
3
class Prim[N <: Node[E], E <: Edge[N]](val node: N) {
// ...
}

So, what we have is a generic class which take two types N and E where N is Node of E and E is Edge of N. We are just making sure types are consistent.

How Prim’s algorithm work? It starts with a single node and marks it as visisted. On every step it choses an edge with minimum weight which connects visited node to not visited node.

That’s kind of it and it can be derived from the name: minimum spanning tree. We know that every node needs to be in solution (the word: spanning), we don’t take edges with both ends already visited as we don’t want cycles (the word: tree), we don’t take edges with both ends not visited as it could create disjoint graph (the word spanning again, and tree but not forest). We also take lightests edge available as we need it to be minimum. Don’t quote this though, it is not formal proof of correctness :)

So this description suggests the solution needs: set of visited nodes and ordered queue of edges.

1
2
3
4
5
6
7
8
9
import scala.collection.{mutable => c}
class Prim[N <: Node[E], E <: Edge[N]](val node: N) {
private val ordering: Ordering[E] = Ordering.by(e => -e.weight)
private val queue = c.PriorityQueue.empty(ordering)
private val visited = c.HashSet.empty[N]
//...
}

Nothing fancy. We have set of visited nodes (visited), we have ordered queue of edges (queue). To make it ordered we use PriorityQueue provide a way to compare edges (ordering) by comparing weights. As PriorityQueue puts heaviest first we need to reverse it. I used -weight but Ordering has actually a method reverse (I just found it out too late).

As I said last week I like one-liners to remove clutter from business code, so let’s define few for this task:

1
2
3
4
5
private def test(node: N) = visited.contains(node)
private def mark(node: N) = visited.add(node)
private def dequeue(): Option[E] = if (queue.isEmpty) None else Some(queue.dequeue())
private def fanout(node: N) = queue.enqueue(node.edges: _*)
private def visit(node: N) = { mark(node); fanout(node) }

We can test the node if it was visited, we can mark the node as such, we dequeue the edge from queue of lightests edges, and we can fanout from given node by adding all outgoing edges to the queue of lightests edges. As last one we have full definition what a visit means, it is marking and then fanning out (I use this word wrongly, don’t I?).

Two non-trivial things. My reimplementation of deqeue returns Option[E]. I actually still don’t belive that there is no dequeue returning option on PriorirtyQueue. I missed it, right? For those who don’t know what I’m whining about let me explain. In functional languages, and Scala claims to be one, exceptions are for trully exceptional situations like, “cosmic ray just hit the CPU”. The expected situations should be handled by type system, and dequeue is perfect example of it: queue can be empty and when you try to get something from it the result should be “nada, come back later”. And that’s exactly what Option type gives us.

The other thing (Am I digressing all the time?) is the splat operator (:_*) in fanout. I actually spent good 15 minutes looking for it as my google-foo failed me. Apparently, enqueue takes multiple arguments (varargs in Java or params in C#) but all I had was a sequence (one argument). C# deals with that implicitly but Scala requires this… thing. I’m actually not sure what it is, maybe something like static cast in F# (:>) with wilcard (_) as a type? Anyway, it works as expected.

So we have mini language for domain of Prim’s algorithm. Let’s do the algorithm then. If it was about solving the problem I would use a for loop (while, foreach whatever). If it was a language with lazy generators or coroutines I would reuse the for loop with yield, but Scala does not have lazy generators. I guess “yet”, as every language is getting them (JavaScript and Kotlin). Anyway, that’s why we need to store the state (visited and queue) as class members and not inside a generator function.

Let’s go:

1
2
3
4
5
6
7
8
9
10
def next(): Option[E] = {
dequeue().flatMap { edge =>
(test(edge.A), test(edge.B)) match {
case (true, true) => next()
case (false, true) => visit(edge.A); Some(edge)
case (true, false) => visit(edge.B); Some(edge)
case _ => throw new IllegalArgumentException("Not a valid graph")
}
}
}

So this method potentially returns next edge. Potentially as we may run out of edges and that’s the stop condition for algorithm. So it takes next edge (dequeue) and if there are no more edges it just returns None and that’s it (flatMap). If there was an edge still available it tests both ends (test(edge.X)). If both are already visited (true, true) this edge is not good let’s take next one. If only one of them is visited (true, false and false, true) mark visit the unvisited one and return this edge (Some(edge)). If both of them seems to be not visited yet something went horribly wrong (cosmic ray?) and it’s time to panic (throw).

Nice.

The domain

We have generic Prim’s algorithm implemented so far but we need to use to solve very specific problem. Building a maze. So let’s deal with the domain.

Let’s start with Point with geometric coordinates:

1
case class Point(x: Int, y: Int)

a Room which is a Node (has trait or implements interface) in a graph:

1
2
3
4
5
6
7
8
9
class Room(val position: Point) extends Node[Door] {
val edges = c.ArrayBuffer.empty[Door]
def add(other: Room, weight: Double) = {
val door = new Door(this, other, weight)
edges += door
other.edges += door
}
}

It additionally, defines add method (I should have named it connect I guess) which creates door connecting two rooms. I’m actually quite impressed how flexible scala is in this respect. Node trait defines edges as def edges: Seq[E] (a method returning sequence) but Room class implements it as val edges: ArrayBuffer[Door] (a field holding mutable collection of Door). No implicit interface implementation or shadowing was needed, it just worked.

The last one is Door (or edge):

1
class Door(val A: Room, val B: Room, val weight: Double) extends Edge[Room]

The last thing we need for domain is the way to create the graph:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Model(size: Point, random: () => Double) {
private val rooms = Array.tabulate(size.x, size.y) { (x, y) => new Room(Point(x, y)) }
private def at(x: Int, y: Int): Room = rooms(x)(y)
private def connect(room: Room, other: Room, weight: Double) = room.add(other, weight)
for (x <- 0 until size.x; y <- 0 until size.y) {
if (x > 0) connect(at(x, y), at(x - 1, y), random())
if (y > 0) connect(at(x, y), at(x, y - 1), random())
}
def room00 = rooms(0)(0)
}

Model object takes a size of the world and random number generator (so we can use any generator we want). It creates two dimensional array of rooms (Array.tabulate) initializes it (new Room(x, y)). If provides a function get room object at given location (at(...): Room) and connect two rooms. Both methods are kind of overkill but make the business logic (the for loop) clutter-free. We also export starting room (room00). If you really wanted to you could implement this Model class as a single function: createModel: (Point, () => Double) => Room, but old habits die hard.

So, once again, the domain is implemented. All what is left is the UI or presentation layer.

The presentation layer

I won’t be describing UI in details, so please refer to Github for actual sources. In general it goes like this…

We have some constants:

1
2
3
4
5
6
7
val WORLD_SIZE = Point(100, 100)
val ROOM_COLOR = "#fff"
val DOOR_COLOR = "#eee"
val ROOM_SIZE = 6
val DOOR_SIZE = 1

defining size of the universe (WORLD_SIZE), some colors, dimensions in pixels (DOOR_SIZE and ROOM_SIZE), and helper functions:

1
2
def toPixel(v: Int): Int = v * ROOM_SIZE + (v + 1) * DOOR_SIZE
def toPixel(p: Point): Point = Point(toPixel(p.x), toPixel(p.y))

to translate between room location to pixel position (toPixel).

We need to intialize canvas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def initialize() = {
val size = toPixel(WORLD_SIZE)
val (width, height) = (size.x, size.y)
val view = s"0 0 $width $height"
jQuery("#canvas")
.attr("width", width).attr("height", height)
.attr("viewbox", view).attr("viewport", view)
val context =
document.getElementById("canvas").asInstanceOf[Canvas]
.getContext("2d").asInstanceOf[CanvasRenderingContext2D]
jQuery("#restart").click((e: Any) => restart(context, width, height))
}

by setting width, height and viewbox, and attach restart method as a handler for click event on Restart button.

Restart shuts down previous animation (shutdown), sets up the drawing context of the canvas (context), initializes the model and algorithm and starts animation on interval (window.setInterval).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var handle: Option[Int] = None
def restart(context: CanvasRenderingContext2D, width: Int, height: Int) = {
shutdown()
context.clearRect(0, 0, width, height)
val model = new Model(WORLD_SIZE, Random.nextDouble)
val algorithm = new Prim[Room, Door](model.room00)
handle = Some(window.setInterval(() => step(algorithm, context), 0))
}
def shutdown() = {
handle.foreach(window.clearInterval)
handle = None
}

We will also need to actually draw rooms and doors:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def drawRoom(context: CanvasRenderingContext2D, room: Room) = {
val p = toPixel(room.position)
context.fillStyle = ROOM_COLOR
context.fillRect(p.x, p.y, ROOM_SIZE, ROOM_SIZE)
}
def drawDoor(context: CanvasRenderingContext2D, door: Door) = {
val a = toPixel(door.A.position)
val b = toPixel(door.B.position)
val o = ROOM_SIZE / 2
context.strokeStyle = DOOR_COLOR
context.lineWidth = ROOM_SIZE
context.beginPath()
context.moveTo(a.x + o, a.y + o)
context.lineTo(b.x + o, b.y + o)
context.closePath()
context.stroke()
}

The last part is the single step of animation, which takes algorithm and drawing context:

1
2
3
4
5
6
7
8
9
def step(algorithm: Prim[Room, Door], context: CanvasRenderingContext2D) = {
algorithm.next() match {
case None => shutdown()
case Some(door) =>
drawDoor(context, door)
drawRoom(context, door.A)
drawRoom(context, door.B)
}
}

If next edge/door (algorithm.next()) cannot be found (case None) then animation is stopped (shutdown()) otherwise it just draws door and two rooms.

And yet again: that’s it.

Online demo

You can get your own copy from Github or you can just watch it working here

Conclusion

I really loved the fact that I had access to Scala collections and they worked as expected. It gives you this warm feeling when you can just use PriorirtyQueue of the shelf. The code Scala.js produces is not nearly as readable as Fable gives us. Is actually pretty awful with horribly mangled names. That’s why I was struggling to understand why it does not see jQuery and how to make it work with Webpack. I do now, but it took me a while.

Shaking maze generator

Note

This blogpost requires familiarity with previous one.

Low branching factor

One of the disadvantages of using DFS to build mazes is “low branching factor”. The problem is that it actually runs for long time before hitting dead-end and having to backtrack, so it creates very long corridors with no room to “make the wrong turn” for potential maze explorer.
Let’s deal with it.

The algorithm

Originally I used recursive version, but to avoid stack overflow, actual demo was done non-recursive version of DFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
let stackless mark test fanout node = seq {
let mutable stack = [[node]]
while stack.Length > 0 do
let head, stack' =
match stack with
| [] -> None, []
| [] :: rest -> None, rest
| (head :: tail) :: rest ->
if test head then None, tail :: rest
else head |> apply mark |> Some, (head |> fanout |> List.ofSeq) :: tail :: rest
match head with | Some n -> yield n | _ -> ()
stack <- stack'
}

This version will be modified to allow “shaking the stack”. I’ll introduce one argument (shake) and use shake stack instead of just stack in match statement.

1
2
3
4
5
6
7
8
9
10
11
12
13
let stackless mark test fanout shake node = seq { // <-- here
let mutable stack = [[node]]
while stack.Length > 0 do
let head, stack' =
match shake stack with // <-- and here
| [] -> None, []
| [] :: rest -> None, rest
| (head :: tail) :: rest ->
if test head then None, tail :: rest
else head |> apply mark |> Some, (head |> fanout |> List.ofSeq) :: tail :: rest
match head with | Some n -> yield n | _ -> ()
stack <- stack'
}

That’s absolutely it in “The algorithm” layer.

The glue

There was a “glue” layer adapting “The algorithm” to “The domain” and it just stopped working as we added new argument to the function. Don’t worry, though, it just a simple fix.

Previously it was calling traverse (or stackless depending which approach you used ‘elegant’ or ‘safe’) now it should call stackless (as traverse does not support shaking) with this extra argument. So the old code:

1
2
InitAt (0, 0)
|> DFS.stackless (targetOf >> mark) (targetOf >> test) (targetOf >> fanout >> Array.shuffle)

should be changed to:

1
2
InitAt (0, 0)
|> DFS.stackless (targetOf >> mark) (targetOf >> test) (targetOf >> fanout >> Array.shuffle) id

and the code will compile again and work exactly as it was working before (you may remember that id function does absolutely nothing). Why we did that then?

Because now, on every single step we have an ability to modify the backtracking stack.

I’ll suggest something like:

1
2
3
let shake stack =
if Random.random () > 0.01 then stack
else stack |> Array.ofList |> apply Array.shuffleInPlace |> Array.toList

Which in 99% of cases returns stack unmodified but from time to time shuffles it completely. Of course, it would be nice to use it now (id gets replaced by shake):

1
2
InitAt (0, 0)
|> DFS.stackless (targetOf >> mark) (targetOf >> test) (targetOf >> fanout >> Array.shuffle) shake

Please note, that from algorithm complexity point of view this is not good approach, as complexity just jumped from O(N) to O(N^2) (it’s a little but more complicated than that), but definitely it gives better results, as it tries to branch earlier.

Pushing forward on the left, branching early on the right

The bottom line is that I did not really modify the algorithm (DFS) I just injected some extra behavior into it, but it is totally externally controlled (kind of definition of “injected”, right?). Functional composition rlz.

Maze generator with Fable

Redgate’s first ever coding challenge

For quite some time I was looking for an excuse to use Fable. Fable is F# to JavaScript compiler. I generally shy away from JavaScript, as I am biased towards backend but as a big fan of F# I wanted to play a little with Fable (and Scala.js actually). On top of that, I wanted to try some other technologies I’ve never used before: VirtualDom (maybe React), Webpack, Pixi.js. All I needed was an excuse…

I’ve found Redgate’s first ever coding challenge on LinkedIn and I decided to do it with Fable in the browser. The challenge is about writing an application to generate mazes (thus the Daedalus reference). I wasn’t going to apply as my solution is probably the most trivial one using “randomized DFS”, so there is nothing to show off, but, I wanted to use those tools.

EDIT: eventually, it did apply

100x100

Initially solution was building SVG with VirtualDOM. It was very neat as Fable/VirtualDOM uses Elm architecture (check Fable samples page). It was fast enough to solve the problem but unfortunatelly, for bigger mazes (>50x50), not fast enough for live animation. Changing multiple <rect> to one long multipart <path> made it a little bit faster (~20%) but it still wasn’t good enough and it was definitely slowing down further it went.

The final version is not as ambitious, uses jQuery and jCanvas. Presentation layer is very old school, but it works and is very fast (relatively speaking, of course). Note, I could deal with the <canvas> without any supporting libraries, but one of my goals was to investigate and evaluate integration with native JavaScript libraries as, in my opinion, integration is one of the most important aspects of any X-to-JavaScript transpiler.

“You’re very clever, young man, very clever,” said the old lady. “But it’s functions all the way down!”

Scott Wlaschin says “No abstraction is too small”. I agree, I’m a big fan of “extracting abstraction” and I’m so glad F# supports and encourages local one-liners. I believe problems should be decomposed into small managable chunks first and then composed back into solution. Things should be named appropriately as well. Let me use example given by Kevlin Henney (it’s actually Dan North’s example but I have no link):

1
2
3
if (portfolioIdsByTraderId.get(trader.getId()).containsKey(portfolio.getId())) {
...
}

Even if we understand every single word in this statement, it is still unclear what purpose it serves. It is not abstract enough, it contains too much of “implementation”. Maybe we should consider this as an alternative:

1
2
3
if (trader.canView(portfolio)) {
...
}

Yup, that’s much better.

For every solution, at some point there will be a need for some “ugly implementation details”. It is just nicer when you can push it far away from business logic so it does not get in a way when you try to reason about what this code “actually does”.

In this article I will use a some one-liners. They might seem like overkill for this task but this is primarily fun project and using them is fun!

The algorithm

There are few algorithms listed on Wikipedia and randomized depth-first search is probably the simplest one.

It has two disadvantages:

  • solution has a low branching factor and contain many long corridors (please note, that this issue was addressed in following blogpost)
  • solution does not contain cycles - This problem applies to most of solutions from Wikipedia. It seems that “maze generation problem” is perceived as “random spanning tree”. Cycles can be seen as shortcuts, therefore making it easier to solve for potential maze explorer, but also they open the door to “be lost forever”, making it infinitely harder. Trade-offs, trade-off, trade-offs.

I’m going to decompose the solution into smaller pieces instead of using single monolithic function.

A physicist and a mathematician setting in a faculty lounge. Suddenly, the coffee machine catches on fire. The physicist grabs a bucket and leaps towards the sink, fills the bucket with water and puts out the fire. The second day, the same two sit in the same lounge. Again, the coffee machine catches on fire. This time, the mathematician stands up, gets a bucket, hands the bucket to the physicist, thus reducing the problem to a previously solved one.

Let’s start with generic depth-first search then:

1
2
3
4
5
6
7
8
9
10
module DFS =
// ('T -> unit) -> ('T -> bool) -> ('T -> 'T seq) -> 'T -> 'T seq
let rec traverse mark test fanout node =
seq {
match node |> test with
| false ->
yield node |> apply mark
yield! node |> fanout |> Seq.collect (traverse mark test fanout)
| _ -> ()
}

where mark: 'T -> unit is the function which will take a node and mark it as visited, test: 'T -> bool will test is node has been visisted already, fanout: 'T -> 'T seq will take a node and return a sequence of connected nodes (neighbours?) and finally node: 'T is just a starting point.

The algorithm goes like this:

  • if node has not been visited yet (node |> test) mark it as visisted (apply mark) and return it (yield).
  • for every connected node (node |> fanout), rinse and repeat (Seq.collect traverse mark test fanout)

If you don’t know what apply does I would recommend my other post.

Done. We can go home… OK, I’m just joking.

NOTE: This solution is vulnerable to stack overflow as it goes deeper and deeper with every visited node. The actual solution uses different implementation of DFS which is using while loop and lists to simulate call stack (I called it stackless which is a little self contradicting, isn’t it?). Idea is absolutely the same though, but code is less elegant.

The domain

So, we have an algorithms. Now we need domain model.

Initially, the domain of this problem consisted of the World, which is a collection of Rooms which in turn have their Location and are connected (or not) through Exits. Not all of those concepts are needed for the algorithm. They may or may not be needed by presentation layer but we probably shouldn’t jump ahead, I guess.

So, let’s start with Location (x and y coordinates) and Direction (north, east, etc…):

1
2
type Location = int * int
type Direction = | North | East | South | West

There is also a relation between directions (opposite) and a function allowing to move from one location in given direction (shift).

1
2
3
4
5
6
7
8
9
let opposite direction = // Direction -> Direction
match direction with
| North -> South | South -> North
| West -> East | East -> West
let shift (x, y) direction = // Location -> Direction -> Location
match direction with
| North -> (x, y - 1) | South -> (x, y + 1)
| East -> (x + 1, y) | West -> (x - 1, y)

Traversing a maze is about actions (or moves). Theoretically, we could model it with single type of action (move south from 5,4 to 5,5), but first move (which is start at 0,0) does not have source nor direction and with language like F# you should not compromise on domain model aka make illegal state unrepresentable.
So, I ended up with two possible actions: teleporting to starting location and moving from one location to another:

1
2
3
type Action =
| InitAt of Location
| MoveTo of Location * Direction * Location

The Action has it’s “property” called target, the Location where it ends:

1
2
3
4
5
// Action -> Location
let targetOf action =
match action with
| InitAt location -> location
| MoveTo (_, _, location) -> location

Bringing “The algorithm” and “The domain” together

It is important to realize, that DFS in this case does not really traverse rooms (graph nodes), it actually traverses actions (graph edges), although it is the room which is visted (not action).

Long story short, there is some glue needed between “The algorithm” and “The domain” presented above.

Let’s start with some one-liners for solution:

1
2
3
4
5
6
7
8
9
10
11
// int -> int -> Action seq
let buildMaze width height =
// Location -> bool
let isValid (x, y) = x >= 0 && y >= 0 && x < width && y < height
let visited = HashSet()
let encode (x, y) = y*width + x // Location -> int
// Location -> unit
let mark location = location |> encode |> visited.Add |> ignore
// Location -> bool
let test location = location |> encode |> visited.Contains
//...

NOTE: HashSet in Fable is modelled using JavaScript Set which does not use structural equality (I learnt it the hard way). Therefore two identical tuples would not be recognised as such. We need to encode tuple value as something which is properly handled by Set. Encoding tuple as single int is one options, encoding it as string would be also valid (but a little but slower, I suppose).

We have function to test is given location is valid for given maze size (isValid), we can test if action points to a room which has been visisted before (test) and mark the location as visisted if needed (mark). That is just a small vocabulary for our problem.

It’s time to define fanout method which will return all valid the neighbours:

1
2
3
4
5
// Location -> Action seq
let fanout source =
[| West; North; East; South |]
|> Array.map (fun direction -> MoveTo (source, direction, shift source direction))
|> Array.filter (targetOf >> isValid)

As you can see, it takes a source location, then generates a sequence of MoveTo actions in every direction and then eliminates the ones with invalid target locations (the ones which would point outside the maze). You may wonder why fanout returns candidates in pretty deterministic order. And that’s fair question. I just don’t think randomization stategy is responsibility of fanout function, I think we can postpone this decision (at least for 5 more seconds).

We have all building blocks ready now and it’s time to call DFS.traverse (or DFS.stackless). As I said before traverse operate on actions (not locations), and functions we defined so far work on locations. We will need some adapters, and some randomization of fanout output.

Functional composition to the rescue:

1
2
InitAt (0, 0)
|> DFS.traverse (targetOf >> mark) (targetOf >> test) (targetOf >> fanout >> Array.shuffle)

It starts with action (InitAt (0, 0)), and uses composition to adapt input argument of mark, test and fanout. It also randomizes the output of fanout with shuffle.

And this sequence of actions it the result of buildMaze.

Done, again. OK, we need presentation.

Presentation

Without getting into much details we need a <button> and a <canvas>:

1
2
<button id="restart" type="button" class="btn">Restart</button>
<canvas id="canvas" class="maze"></canvas>

That’s the UI. Right? Yeah, kind of. Be aware that the code here is for illustration only, please refer to github for actual working sources.

Let’s start with importing native JavaScript libraries:

1
2
let jq = importDefault<obj> "jquery"
(importDefault<obj> "jcanvas") $ (jq, Browser.window) |> ignore

As you can see there a little bit weird syntax when accessing arbitrary JavaScript objects. The good news is you can import TypeScript .d.ts definition files into Fable to have strongly typed interfaces. In this case though, I used so little of it, that I could manage dynamic invocation.

Long story short, importDefault get’s translated into require (for CommonJS). The $ operator is invoke, ? operator is get and <- is set. $ operator in many cases can be ommited.
So, a ? b ? c(77) would be translated to a.b.c(77); while a ? b ? c <- 11 would be translated to a.b.c = 11;.

Please note, that as there is an assumptions that everything returns obj (or obj -> obj which is also an obj). F# does not like dangling result values so you need to ignore results you don’t care about. I definitely recommend referring to Fable website for more details.

Let’s define some constants:

1
2
3
4
5
6
7
let [<Literal>] WORLD_WIDTH = 100
let [<Literal>] WORLD_HEIGHT = 100
let [<Literal>] ROOM_SIZE = 5
let [<Literal>] DOOR_SIZE = 1
let [<Literal>] ROOM_COLOR = "#fff"
let [<Literal>] DOOR_COLOR = "#eee"

and a simple function to convert world location to coordinates in pixels:

1
2
let toPixel (x, y) = // Location -> (int * int) // and yes, I'm cheting with types a little
x*ROOM_SIZE + (x + 1)*DOOR_SIZE, y*ROOM_SIZE + (y + 1)*DOOR_SIZE

Let’s set the <canvas> up, by setting width, height, viewbox and viewport (using jQuery):

1
2
3
4
5
6
7
let w, h = toPixel (WORLD_WIDTH, WORLD_HEIGHT)
let canvas = jq $ ("#canvas")
canvas
? attr("width", w) ? attr("height", h)
? attr("viewbox", sprintf "0 0 %d %d" w h)
? attr("viewport", sprintf "0 0 %d %d" w h)
|> ignore

and wire click event on “Restart” button:

1
2
3
4
5
6
7
let mutable cancel = id
let button = jq $ ("#restart")
button ? click(fun _ ->
cancel ()
canvas ? clearCanvas () |> ignore
cancel <- startAnimation canvas
) |> ignore

The thing with cancel might be a little bit unclear. Function startAnimation will return a function (function returning function, yes) which can be called to cancel animation. So next time Restart button is pressed previous animation will be cancelled before starting new one. To avoid null (or None) checking (on first run) cancel just gets initialized with function which does nothing (yes, id is a function which does nothing).

Back to solution, when button is pressed potential old animation is cancelled (cancel()), canvas is cleared (canvas ? clearCanvas () |> ignore) and new animation is started (cancel <- startAnimation canvas).

There is only one method left, then:

1
let startAnimation canvas = // ...

Please note, the code below in the scope of startAnimation.

We will definitely need to draw rectangles on canvas, and that’s kind of all we are going to do. I will use jCanvas to do this, but it is an overkill, of course, it could (and should?) be done with browser API, but I’m exploring here, right?
As with dynamic invocation eveything is obj we want to add some types when JavaScript and Fable meets. Let’s wrap jCanvas.drawRect first into drawBox function:

1
2
3
4
5
6
7
8
let drawBox (color: string) (x: int) (y: int) (w: int) (h: int) =
let rect =
createObj [
"fillStyle" ==> color
"x" ==> x; "y" ==> y; "width" ==> w; "height" ==> h
"fromCenter" ==> false
]
canvas ? drawRect(rect) |> ignore

Yup. Done. Not pretty but done. We can forget about this traumatic experience now. It actually generates quite readable code:

1
2
3
4
5
6
7
8
9
var rect = {
fillStyle: color,
x: x,
y: y,
width: w,
height: h,
fromCenter: false
};
canvas.drawRect(rect);

From now on, we can forget about JavaScript interop again. We can just use drawBox and implement drawRoom to draw a room, and drawDoor to draw a door:

1
2
3
4
5
6
7
8
9
10
11
12
// Location -> unit
let drawRoom location =
let x, y = toPixel location in drawBox ROOM_COLOR x y ROOM_SIZE ROOM_SIZE
// Location -> Direction -> unit
let drawDoor location direction =
let x, y = toPixel location
match direction with
| North -> drawBox DOOR_COLOR x (y - DOOR_SIZE) ROOM_SIZE DOOR_SIZE
| South -> drawBox DOOR_COLOR x (y + ROOM_SIZE) ROOM_SIZE DOOR_SIZE
| East -> drawBox DOOR_COLOR (x + ROOM_SIZE) y DOOR_SIZE ROOM_SIZE
| West -> drawBox DOOR_COLOR (x - DOOR_SIZE) y DOOR_SIZE ROOM_SIZE

Room is drawn as big square, while Door is just a slim rectangle (depends on relation between DOOR_SIZE and ROOM_SIZE). As you can see doors have different shape depending on direction (for example: North vs East).

5x5

Now, we need to start traversing the maze:

1
let mutable action = buildMaze WORLD_WIDTH WORLD_HEIGHT |> Enumerator.create

You can notice Enumerator here, which might be a little bit cryptic but it just provides slighlty more F#-ish way to use IEnumerable<T> interface.

The last part is the animation loop, we need to draw actions as they come. Let’s schedule a callback every 1/60th of a second (should I use requestAnimationFrame here?) which will take current frame (well… action), draw adequate objects (drawRoom and drawDoor) and then proceed to next action (action <- action |> Option.bind Enumerator.next):

1
2
3
4
5
6
7
8
9
10
11
12
let mutable cancel = id
cancel <- Time.interval (1.0 / 60.0) (fun _ ->
match action |> Option.map Enumerator.value with
| None -> cancel ()
| Some (InitAt location) ->
drawRoom location
| Some (MoveTo (_, direction, location)) ->
drawRoom location
drawDoor location (opposite direction)
action <- action |> Option.bind Enumerator.next
)
cancel

The last line returns cancel (returns a function, but does not call it) from startAnimation so animation can be externally cancelled.
Note: Time.interval is just a wrapper for setInterval and clearInterval to have more F#-ish experience:

1
2
3
4
5
6
module Time =
open Fable.Import.Browser
// float -> (unit -> unit) -> (unit -> unit)
let interval seconds (action: unit -> unit) =
let disposable = window.setInterval (action, seconds * 1000.0)
fun () -> window.clearInterval(disposable)

I guess that’s it.

You can find solution on github. It actually has many branches as I was trying many approaches. I started with “Immutable domain with VirtualDOM to generate SVG”, then I switched to “Mutable domain with VirtualDOM to generate SVG paths”, then I switched to “Mutable domain with jCanvas” and then I realized that half of domain was actually needed by VirtualDOM approach only. So, last incarnation if Daedalus is “Mutable mini domain with jCanvas”.

If you want to just see it work, you can find it here

Dealing with “low branching factor”

As mentioned DFS has a problem with low branching factor. I’ll try to address the problem in next blogpost.

Thanks

Use tee and carry on

Originally, this blogpost was titled “Use apply and carry on”, but I guess naming the function apply after Kotlin (damn you, Kotlin!) wasn’t the most preferred option by the public. I did like apple |> apply eat semantics but if Scott Wlaschin says apply is a different thing then it is a different thing. To be precise Scott’s is apply: (a -> b) -> a -> b and mine was (emphasize on was) apply: (a -> unit) -> a -> a. Apparently, the function which does whatever I wanted apply to do is called tee (after Unix command) or tap (at least in Ruby and Ramda.js).

So I’ve edited it and replaced apply with tee, but essentially it is almost unchanged… Let’s go then.


One of everyone’s favourite features of F# is pipe (|>) operator. It allows to pipe output of one function as input to another function preserving visual honesty. The general idea is that, in English, we read left-to-right and top-down. In C# (C, C++, Java, Pascal, Python) we read in all possible directions, most likely top-down for overall structure but botton-up and right-to-left for single statements.

Visual honesty

For example:

1
var y = Math.Round(Math.Exp(Math.Sin(x*5.2 + 7.1)));

starts at the right end going left-to-right for a moment (x*5.2 + 7.1) but then turns right-to-left with Math.Sin, Math.Exp and finally Math.Round (in this order). In F# the pipe operator (|>) allows to write code exactly in the same order as it is going to be executed:

1
let y = x*5.2 + 7.1 |> Math.Sin |> Math.Exp |> Math.Round

Around the world, many hours have been spent arranging function arguments (guilty!) to allow such seamless experience. But sometimes, the universe is against us. Let’s assume we would like to print out the value after Math.Sin. The conservative approach would be quite intrusive - we would need to break expression in half:

1
2
3
let temp = x*5.2 + 7.1 |> Math.Sin
printf "%g" temp
let y = temp |> Math.Exp |> Math.Round

Whoa! That is intrusive.

But here comes the rescue. The tee function implemented as:

1
let tee func arg = func arg; arg

The function itself is trivial, it takes a function and an argument, executes given function with given argument but then returns it, so the argument goes through the function:

1
let y = x*5.2 + 7.1 |> Math.Sin |> tee (printf "%g") |> Math.Exp |> Math.Round

In the example above, the value passed between Math.Sin and Math.Exp has been redirected “for a moment” to printf "%g" without any temporary variables or breaking the flow.

Recently I needed to shuffle an array. The algorithm I used shuffles array in place:

1
2
3
4
5
6
7
8
let inline swapInPlace i j (array: 'a[]) =
let t = array.[i]
array.[i] <- array.[j]
array.[j] <- t
let shuffleInPlace (array: 'a[]) =
for i = array.Length - 1 downto 1 do
array |> swapInPlace i (Random.randomInt 0 i)

(Random.randomInt is not a standard function, but its implementation is irrelevant for this example)

I needed it as pure function, which will not mutate input array, just return shuffled version of it. Let’s do it:

1
2
3
4
let shuffle array =
let result = Array.copy array
shuffleInPlace result
result

Maybe we can do better with tee? Yes, we can:

1
let shuffle array = array |> Array.copy |> tee shuffleInPlace

Much better.

So, use tee and carry on!

State Machine Construction Kit for F#

NOTE: There is a lot of code in this article, as it is repeated and iteratively added. The final version is just 28 lines near the end, but I think you should read the whole thing anyway.

Once upon the time I needed to implement state machine. To not reinvent the wheel I reviewed what’s available: Windows Workflow Foundation, Appccelerate.StateMachine, bbv.Common.StateMachine, Stateless, SimpleStateMachine, Solid.State, and StateMachineToolkit. Windows Workflow Foundation was just scary, apart from the fact that State Machine is not available in .NET 4.0. It didn’t look lightweight either.

None of the others satisfied my requirements either:

  • Events should be able to carry data - for example, hypothetical event KeyPressed should also carry information which key has been actually pressed;
  • States should be able hold data - for example, state collecting key presses (let’s call it EnteringText) should be able to hold a list of keys pressed so far;
  • Guard statements should have access to both current state and event - for example, KeyPressed event may cause transition to different state depending which key has been pressed;
  • Transition rules should be implemented outside states - states should be more like POCO/DTO object with no logic in them;

I’ve implemented it in C#, and I’m relatively happy with it, and you can find it on GitHub. As an exercise I implemented it for Kotlin as well, also on GitHub. Then I had to implement one for work, in Java this time.

I decided that maybe it’s time to do something for F# community, and implement nice functional State Machine Construction Kit. I dropped the “transition rules should be implemented outside states” requirement as it was adding some messy reflection code.

To make it more F#y and functional I started with fundamental question: what is the state? What is its essence?
It is actually a function which will take an event and produce new state:

1
type State<'Event> = 'Event -> State<'Event>

This would actually not compile, because it would create infinite recursive type alias, but:

1
type State<'Event> = | State of ('Event -> State)

will do just fine.
Actually it would be a little but nicer if it would be possible to return State option to handle termination:

1
type State<'Event> = | State of ('Event -> State option)

…but, I decided to make it rather with explicit state case:

1
2
3
type State<'Event> =
| Next of ('Event -> State)
| Stop

So we have transitive state (Next for State (Some state)) and terminal state (Stop for State None).
Please note, that we could add more cases, for example:

1
2
3
4
type State<'Event, 'Result> =
| Next of ('Event -> State)
| Stop of 'Result
| Fail of Exception

but this would introduce some complexity which I don’t want in this example, but you are more than welcome to introduce yourself.
So, let’s go back to my State Machine Construction Kit. We already have a state but we also need a function to fire events and transition from state to state, let’s call it feed, we feed a state with event. It’s actually almost done as state is a transition function:

1
2
3
4
let feed state event =
match state with
| Stop -> failwith "Terminal state reached"
| Next handler -> event |> handler

For this example I will use some trivial state machine handling opening and closing doors:

simple door state machine

So we have Open and Close events:

1
type Event = | Open | Close

…and have two states: opened and closed. The states themselves are functions which take events and produce new states:

1
2
3
4
5
6
7
8
let rec opened event =
match event with
| Open -> Next opened
| Close -> printfn "closing"; Next closed
and closed event =
match event with
| Open -> printfn "opening"; Next opened
| Close -> Next closed

Let’s define an initial state, a let’s say it is closed:

1
let mutable state = Next closed

Now we can send Open event to it and store new state:

1
state <- Open |> feed state

Ta-dah! Done.

Please note, that to handle sequence of events easily, the only thing you need to is to use fold:

1
events |> Seq.fold feed state

For my personal use I actually created a class to encapsulate mutability. It is, of course, still there but hidden:

1
2
3
4
5
6
type StateMachine<'Event>(initial: State<'Event>) =
let mutable current = initial
member this.Feed event =
current <- feed current event
member this.IsStopped
with get () = match current with | Stop -> true | _ -> false

What about context (data shared by all states) and state’s state (state internal data) you might ask? By the power of closures and currying there is nothing special to implement. For example, let’s imagine a door state machine which makes sounds (with injected sound emitter) and can be locked or unlocked when closed (state’s internal data):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type Event = | Open | Close | Lock | Unlock
let configureDoor sound =
let rec opened event =
match event with
| Close -> sound "bang"; Next (closed false)
| Lock -> sound "clack"; Next opened
| _ -> Next opened
and closed locked event =
match event with
| Open when locked -> sound "dumdum"; Next (closed locked)
| Open -> sound "squeak"; Next opened
| Lock -> sound "click"; Next (closed true)
| Unlock -> sound "clack"; Next (closed false)
| _ -> Next (closed locked)
Next (closed false)

Note, there is a sound function passed and all states have access to it and this is your context. Additionally closed state has a locked ‘property’ and behaves differently depending on the value is this property (cannot be opened when closed, and needs to be unlocked first). You can call it substate if you want.

What if I don’t like mutable variables and I want my state machine to be an actor / agent? Let’s just wrap it:

1
2
3
4
5
6
7
8
9
10
let createAgent initial =
MailboxProcessor.Start (fun inbox ->
let rec loop state = async {
let! event = inbox.Receive ()
match event |> feed state with
| Stop -> ()
| Next _ as next -> return! loop next
}
loop initial
)

So, the full module, already a little bit bloated with helper functions, is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
module StateMachine =
type State<'Event> =
| Next of ('Event -> State<'Event>)
| Stop
let feed state event =
match state with
| Stop -> failwith "Terminal state reached"
| Next handler -> event |> handler
type StateMachine<'event>(initial: State<'event>) =
let mutable current = initial
member this.Fire event = current <- feed current event
member this.IsStopped
with get () = match current with | Stop -> true | _ -> false
let createMachine initial = StateMachine(initial)
let createAgent initial =
MailboxProcessor.Start (fun inbox ->
let rec loop state = async {
let! event = inbox.Receive ()
match event |> feed state with
| Stop -> ()
| Next _ as next -> return! loop next
}
loop initial
)

I can run this now with:

1
2
3
4
5
let agent = printfn "%s" |> configureDoor |> StateMachine.createAgent
agent.Post Lock // click
agent.Post Unlock // clack
agent.Post Open // squeak
agent.Post Close // bang

I have to admit. I failed. There is no such thing as State Machine Construction Kit for F#, at least not the one worth releasing, in short, there is just a function:

1
type StateMachineConstructionKit = 'State -> 'Event -> 'State

but I just can’t put it on GitHub. Maybe gist?