DEV Community: Jan van Brügge

My Open Source Journey

Jan van Brügge — Fri, 06 Nov 2020 14:08:29 +0000

This post was first published on the Futurice Blog

It's October again, Hacktoberfest time. Also time for me to reminisce about my personal learning journey that was so heavily influenced by open source.

The Beginning

My interest in computers and coding started rather early, so when I was 14 years old, I went to the local library, got myself a book about programming ("From Zero to Hero: Java") and started on this wonderful path that is now not only my job, but also my passion.

I first came in contact with open source - well other than using excellent software like VLC - was when I encountered a problem with my music library. My dad and I had built a NAS server that I put Linux on to serve our media with a Plex Media server. We also used iTunes to sync parts of the library to mine and my sister's iPod touch. But many of the songs and especially the audiobooks had the wrong metadata, so iTunes and thus the iPod did not sort them correctly! Plex however used the filenames and based on those downloaded the correct metadata from the internet. So the question was: Is it possible to have Plex write the correct metadata for the files so iTunes would also have them?

After a bit of searching the internet I found Plex Media Tagger which did exactly the thing I wanted! Sadly however it used "subler" for writing the metadata, a software that only works on MacOS and not on our Linux NAS. With the loads of time on my hands that comes with being a high school student, I wanted to try and make it work also on Linux. The tagger is written in Python, but at that point I had already tried my hand in several other languages like C++ and JavaScript, so I was confident that I just needed to take a look at the syntax - programming languages are all the same, right? (A misconception I would realise much later).

With this new goal in mind, I again searched around and found a pure python library that could write the metadata, so I could replace subler and have a pure python plugin that could run on any operating system! I forked and cloned the repository (I already used git for my personal code) and got the changes done rather quickly. It worked well enough on the Linux NAS, so I shared my work in order for others to benefit from it. Knowing not much about programming and good code style, I basically just copy pasted the python library into the project and commited that. You can see the horror that is the PR here. Apparently I missed some stuff or there are differences in the metadata for different operating systems, so it never got merged (I also did not really care about it as it was working well enough for myself).

Getting Involved More Consistently

I however would mark the start of my journey a bit later. It was near the end of high school and I had started freelancing on a project for a client of my dad. This was the first big web project I had. Before, I only played around with a bit of PHP and jQuery, but that had more of a duct tape feel than a properly organized application that I would be able to maintain for more than a month. So I started looking around what the status quo was for frontend development. At that time Angular 2 was in alpha and I was amazed. Two way data binding! A proper way to structure your app into components and more. It also introduced me to RxJS which I found intriguing. But it had a lot of issues. My two main gripes were debuggability - you would get a stack trace that mostly consisted of Angular code and was not really helpful - and I did not understand RxJS correctly, so I was burned by some hot/cold stream issues. To fix those I found "The introduction to Reactive Programming you've been missing", which cleared a lot of the misconceptions I had. Sadly in the end, the debugging experience ate my productivity so I searched for something to replace Angular.

The two pieces I wanted to keep from Angular were RxJS and Typescript. I had always coded in typed languages (Java and C++ mainly), and I really hated that JavaScript did nothing to prevent stupid errors on my side. I've seen "undefined is not a function" too many times even in those short tries with jQuery. Again searching around for frontend frameworks, I came across React, and saw a conference talk on YouTube about the virtual DOM that React uses. I liked the idea, but found the execution lacking.

In the end I stumbled across Cycle.js that was created by André Staltz, the same person who wrote the reactive programming introduction that basically went all in on RxJS by centering the whole framework around it. It was also recently converted into TypeScript at that time, so that was another plus.

The Normal Open Source Trajectory

From now on I was on what I would call a typical open source trajectory. I used the Cycle.js framework to rewrite my frontend and in that process I hit some walls. I eventually figured that the error was on my side and that I was just missing some information to avoid the error. To spare others the hours of debugging I started to contribute small patches to the documentation. At the same time I also found some missing features that I voiced in GitHub issues.

All in all I got more involved in the community and soon I also started fixing bugs myself that I found, instead of just opening issues. I got more known by the core team. This was then the reason I was asked if I want to speak at CycleConf 2017 in Stockholm. This being my first conference I was quite excited and in the end it was a fantastic experience that I still remember fondly. Shortly after, I was invited to become part of the core team myself, getting access to the OpenCollective Funds and helping steer the framework together with André and Nick.

Continuing My Learning

During that time I also wanted to dive deeper into functional programming. When I first came in contact with RxJS, it was the first time I learned about higher order functions like map and reduce and I really liked the concept. It allowed me to express what I wanted to do, not really caring about how exactly it was done. So after hearing the fantastic talk about Ramda, I was addicted. So I again searched around for functional languages because I thought that this way I could really learn the concepts in their purest form and it would prevent me from falling back to my old patterns - mainly OOP. This turned out to be one of the better decisions I made in my life. I started to learn Haskell, at the beginning with Learn you a Haskell for Great Good and later with Real world Haskell which is sadly a bit outdated (so do not expect to follow the code 100%), but the general ideas still hold true today.

This was the first time since starting to program that a new way of thinking about code and algorithms was opened to me. Through me learning Java and C++ as my first languages, I used to solely think in for-loops and if-conditions. But being forced to write purely functional code makes you think differently about problems. At least for me, it pushed me to think more about the data structures and not only about the algorithms. It showed me that there are more ways to do concurrency than slapping a synchronized keyword everywhere. That mutable state is the root of all evil and just so much more.

My Academic Path

Learning Haskell also set me on a more research-focused path. I had already started my computer science studies, but after learning Haskell I became more interested in the theoretical science. I wanted to see why languages are like they are. What are the similarities? What are the pros and cons of e.g. garbage collection. And especially type systems became really intriguing to me. Haskell is just so much more expressive than for example Java where the type system can be a burden at times. While not perfect, in Haskell the type system is much more helpful, preventing you from making dumb mistakes, and with some more work on your side, even not so dumb mistakes.

I got more into theorem proving, i.e. using a programming language to write mathematical proofs and have them checked by a compiler. Step by step I am working on a machine checked proof of type safety of System Fc, the intermediate language of the Haskell compiler.

In Retrospect

Looking back at my journey, there were a few key events that brought me to where I am now. The first one was getting this freelance project that made me look more into modern frontend frameworks. Then, through Angular, getting to know RxJS and thus getting in contact with functional programming. Going deeper into Cycle.js and being invited to speak at my first conference. And lastly starting to learn Haskell which set me on a more research oriented path.

I am also super grateful that the Open Source work I do is sustainable for me. This is in part thanks to our generous backers on OpenCollective, but also through Futurice, the company I work for. Futurice has the Spice Program that pays a flat hourly rate for any Open Source work any employee does in their free time. Those two sources of income would not be enough to work full time, but they allow me to have dedicated days that I can focus on Cycle.js.

All in all, I can say that every time I learned something fundamentally different and new, even if I would not use it in my day to day job, I've really benefited from the experience. So in case you want advice from a 23 year old, keep learning! Try out completely new stuff even if it is not immediately useful for you! My style of writing code even in imperative languages has evolved a lot over the years.

Redesigning a framework

Jan van Brügge — Tue, 11 Aug 2020 13:31:20 +0000

For the last few years, the core team of Cycle.js (André and me) has been redesigning the architecture and the developer experience of the framework. This February we finally found a solution to our problems that still stays true to the core ideas of the framework.

This blog post marks the first in a series that will cover the new design and its development. In this installment, I want to bring everyone onto the same page. What where the problems I described earlier and how does the new design solve them. In the later articles I will cover the new run function (the core of the framework) and the new HTTP driver and especially the issues I encountered while implementing those. *cough* race conditions *cough*.

The status quo

Everyone that is familiar with Cycle.js may skip this part, for the rest here is how the framework work in the current version: Everything in your application is based around the notion of streams. The kinds of streams that RxJS made popular. All you application code is doing is reading streams of events from the outside (ie click events on the DOM or responses of HTTP requests), transform and combine them and finally giving streams of commands back to the outside (ie a new virtual DOM to render on the DOM or a HTTP request to execute).

Let's take a concrete example, a simple counter:

function main(sources) {
    const incrementStream = sources.DOM.select(".increment")
        .events("click")
        .mapTo(1);

    const decrementStream = sources.DOM.select(".decrement")
        .events("click")
        .mapTo(-1);

    const valueStream = xs
        .merge(incrementStream, decrementStream)
        .fold((sum, current) => sum + current, 0);

    const domStream = valueStream.map(x =>
        div([
            h2(`The current value is ${x}`),
            button(".increment", "Increment"),
            button(".decrement", "Decrement")
        ])
    );

    return {
        DOM: domStream
    };
}

As you can see we are listing to the click events of the two buttons and convert those events into +1 and -1. We then merge those two streams and use fold to sum up all numbers (fold is similar to array.fold, but instead of calculating the value once, fold will send out the current value after every number that comes in). We then take the stream of all the sums and transform it into a virtual dom tree that is then given to the outside for rendering.

This stream-centric design has some nice benefits. First, all of the application logic is a pure function. It does not directly access the DOM API, it does not do HTTP requests to 3rd parties or do any other interaction with the outside world. Everything happens through the sources and the sinks (ie input and output of the main function). This means that we do not need to mock the actual APIs with something like JsDOM, we can just provide some inputs to the application and assert on the outputs. Second, adding async behavior does not add any complexity, synchronous code looks exactly like asynchronous code. Third, on the top level, we can intercept and modify/filter/log any command that any component in the hierarchy sent. One nice use case for this intercepting every HTTP request the components do and add some API token to the headers for example. We could also add some rate limiting here in case we are fetching from a third party API. We could also put this functionality in a library that provides a function that wraps you application and returns a new application with logging. This pattern has evolved out of the community and there are several libraries that provide such "main wrappers". Last, there is only unidirectional data flow. All the data comes in from the sources, gets transformed and leaves through the sinks. It is really easy to trace commands back to the data or events that caused them.

The problem

The streaming idea works really well if the outside is interactive, for example it is a really good approach for the DOM where the user may interact at any time. However there is also another kind of outside: question and answer style effects. The most simple example for this is doing HTTP requests. Usually when you send a request, you want to wait for the result and then work with the data. But at the moment doing a request looks like this:

function main(sources) {
    const responseStream = sources.HTTP.select("myRequest");

    const domStream = responseStream.startWith(initialData).map(view);

    const requestStream = sources.DOM.select(".requestButton")
        .events("click")
        .mapTo({
            url: myUrl,
            method: "GET",
            category: "myRequest"
        });

    return {
        DOM: domStream,
        HTTP: requestStream
    };
}

As you can see, while the flow of the data is still strictly from the sources to the sinks, the code is awkward to read for the HTTP portion. First, we listen to a response with some tag (myRequest in this case) and then only later we see the code that actually sent it. And they are not directly connected, they are completely independent, so you have to use the tag to find which request belongs to which response. What we really wanted, was an API similar to this:

function main(sources) {
    const domStream = sources.DOM.select(".requestButton")
        .events("click")
        .map(() => sources.HTTP.get(myUrl))
        .flatten()
        .startWith(initialData)
        .map(view);

    return {
        DOM: domStream
    };
}

This code does exactly the same as the one before, but it is a lot easier to read because you can just start at the top and work your way down. It clearly says: "Listen to all 'click' events on the request button and for each of the clicks make a get request to myUrl. Starting with some initial data, render every response with the view function onto the DOM".

But if we would implement this like that, we would loose one of the benefits of using stream: The ability to inspect and modify every command that happens. As you can see there is nothing returned through the sinks for HTTP, so we can not intercept this request anywhere, not even at the top.

The solution

The solution we have settled on now is to split the drivers that interpret the commands and provide the events. At the moment a driver take a stream of commands as input and returns either a stream of events or, for more complex drivers like HTTP and DOM, an object that provides methods that return streams. For example the DOM driver returns the DOMSource object that provides the methods select() and events() where the latter one returns a stream of events.

A very simplified example of this would look like this:

class DOMSource {
    events(type) {
        return fromEvent(type);
    }
}

function domDriver(commands) {
    commands.subscribe({
        next: renderDOM
    });

    return new DOMSource();
}

In this example fromEvent would attach an event listener and emit a new event every time the event listener gets activated.

The new solution changes this to require drivers to take a stream as input and return a stream as output. If a more complex driver wants to offer a nicer API it can provide it separately. The job of such an API is to convert the calls from the user into commands that will be sent to the driver and to take the events from the driver and filter them for the user. For our DOM example this might look like this:

class DomApi {
    constructor(subject, driverEvents, idGenerator) {
        this.subject = subject;
        this.driverEvents = driverEvents;
        this.idGenerator = idGenerator;
    }

    events(type) {
        const id = this.idGenerator();
        this.subject.send({
            commandType: "attachEventListener",
            type,
            id
        });

        return this.driverEvents.filter(event => event.id === id);
    }
}

function domDriver(commands) {
    const subject = makeSubject();

    commands.subscribe({
        next: command => {
            if (command.commandType === "attachEventListener") {
                document.addEventListener(command.type, event => {
                    subject.send({ ...event, id: command.id });
                });
            } else {
                renderDOM();
            }
        }
    });

    return subject;
}

As you can see, the driver is completely independent from the API, you could also not use the API and send the commands to the driver directly. The API on the other hand does not interact with the outside world at all, it only sends a command to the driver and filters the events for the ones the user is actually interested in. In case you are wondering, a subject is like the beginning of a stream where you can manually put events into the stream via send().

The whole picture

With the new design, Cycle.js exports a function makeMasterMain() that takes your application and the APIs of the drivers and returns a new main function that just expects streams of events as inputs and returns streams of commands. The APIs of the drivers take care of sending out the right commands and reading the right events. You can now wrap that new main function with code that inspects for example the HTTP requests. But now such code could also intercept and log the addition of event listeners to the DOM! This was not possible before. After adding as many layers of wrapping code to the master main as you like, you can give it to run() that takes the main function and the drivers and connects the two. Remember that the main function now only works with plain streams, no APIs any more.

So, coming back to the code from earlier:

function main(sources) {
    const domStream = sources.DOM.select(".requestButton")
        .events("click")
        .map(() => sourcs.HTTP.get(myUrl))
        .flatten()
        .startWith(initialData)
        .map(view);

    return {
        DOM: domStream
    };
}

This is how the code will actually look like in the next major version of Cycle.js! All while you will still be able to intercept/modify/log all requests that leave your application even though they are not explicitly returned from your application code (ie no HTTP: requestStream). Getting to this point took some time, but I am very happy with the final architecture. The user code is easier to read and the framework code also got quite a bit simpler.

In the next part I will talk about the run() and the makeMasterMain() functions and how to prevent race conditions with synchronous stream code. Thanks for reading, feel free to voice any questions you might have.

Why vim macros are awesome

Jan van Brügge — Sat, 25 Jan 2020 13:26:36 +0000

Today I had to write some TypeScript code again, in particular the pipe function. It takes any amount of functions and composes them left to right. In JavaScript this function is fairly easy to implement:

function pipe(...fns) {
  return argument => {
    let result = argument;

    for (let i = 0; i < fns.length; i++) {
      result = fns[i](result);
    }

    return result;
  };
}

As you can see, we just repeatedly apply the argument to the functions one by one and return the final result. The problem is, we can't really provide a good type for this in TypeScript:

function pipe(...fns: [(arg: any) => any]): (arg: any) => any {
  return (argument: any) => {
    let result: any = argument;

    for (let i = 0; i < fns.length; i++) {
      result = fns[i](result);
    }

    return result;
  };
}

For me, the types in the function itself are fine. The function is pretty simple, so I don't care if result has type any or not. But the types the function exposes for others are not acceptable. It just tells us that the function expects many single argument functions and returns one single argument function. I want to use TypeScript to ensure that all the functions I pass in are compatible and fit together. I also want that the returned function has the input type of the first function and the return type of the last.

Sadly the type system of TypeScript is not strong enough to express this function, this would need some sort of type level fold operation while TypeScript only has mapped types.

Function overloading

Since the beginning of TypeScript, the answer to such problems has been function overloading. As long as the function type is more general, you can add any amount of additional, more concrete type signatures to provide better types. For example, if you have a function that can work with string and number:

// These are the overloads
function doSomething(input: string): string;
function doSomething(input: number): number;

function doSomething(input: string | number): string | number {
  return input;
}

As you can see, the base type is pretty general, because even if you pass in a string, the type would still allow to return a number. But this is not what the implementation does! It always returns the same type as the input. So we can add two overloads to fully cover all the possible input types and specify their return types. Note how the types in the overload are still possible in the actual, general type. This is needed in TypeScript, because it can't to type directed overloading like Java or C++, so you can just constrain the general type with overloads. This for example, would be a type error because the general type does not allow objects.

// These are the overloads
function doSomething(input: string): string;
function doSomething(input: number): number;
function doSomething(input: {}): {}; // Error

function doSomething(input: string | number): string | number {
  return input;
}

Back to pipe

So we can fix our bad pipe type with overloads. We can not provide all possible overloads because pipe can take any amount of arguments and we can only provide a finite amount of overloads. But in reality you would not expect people to use more than let's say 20 arguments at once. And even if they do, the function will still work, because TypeScript will fall back to the general type.

So let's start with the simplest overload: For just one function.

function pipe<A, B>(fn1: (arg: A) => B): (arg: A) => B;

function pipe(...fns: [(arg: any) => any]): (arg: any) => any {
  /* body omitted */
}

With only one function, pipe is the identity, it behaves like the function passed in. Now we extend the overload to two functions:

function pipe<A, B>(fn1: (arg: A) => B): (arg: A) => B;
function pipe<A, B, C>(fn1: (arg: A) => B, fn2: (arg: B) => C): (arg: A) => C;

function pipe(...fns: [(arg: any) => any]): (arg: any) => any {
  /* body omitted */
}

I think the pattern should be pretty obvious. We just add another parameter that fits to the one before and change the overall return type. Sadly, this is really tedious to do by hand, especially if we want to have overloads for up to 20 arguments!

Vim macros to the rescue

The pattern to create new overloads is pretty regular, we should somehow be able to automate this. Luckily my favorite text editor comes with the tools needed for this: vim macros.

A vim macro is just the editor recording every keystroke that you make. This includes any vim commands in normal mode and anything you write in insert mode. To record a macro you have to press q followed by one other letter. This letter will be the name of the macro, so you can have multiple macros in parallel. As we want to do overloading, let's use o. Once you now have pressed qo, you should see recording @o in the bar at the bottom. This means that vim is now listening to your keystrokes.

Now press i to go into insert mode, write some short text and finished with a press on escape to leave insert mode again. Press q to stop recording. To play back a macro you can hit @o (where o is of course the letter you used while recording) and you will see the same text you have just written appear again.

The last bit of preparation that is needed is changing one setting about auto-increment (we will use this later). When in normal mode (just hit escape to be sure), type :set nrformats=alpha and hit enter. This will allow us to not only increment numbers, but also letters.

Recording our macro

We start again with the function and those two overloads.

function pipe<A, B>(fn1: (arg: A) => B): (arg: A) => B;
function pipe<A, B, C>(fn1: (arg: A) => B, fn2: (arg: B) => C): (arg: A) => C;

function pipe(...fns: [(arg: any) => any]): (arg: any) => any {
  /* body omitted */
}

Now, put the cursor on the line with the second overload and hit qo to start recording. Follow with a press on 0 to jump to the start of the line. Then we want to create a new overload, so we copy and paste the current line. We can do this with yy (yank) and p (paste).

So what is our goal now with our fresh overload? First, we want to add a new generics name at the end of all the other ones. For this, we jump to the > with f>. After that, we need to copy the last generic name (C in our case). Use yh to copy the character on the left. Now we need to add the comma and the space. For this we can simply go into insert mode with a and type out ,. Leave insert mode again with escape. Paste the character with p. You should have this now:

function pipe<A, B>(fn1: (arg: A) => B): (arg: A) => B;
function pipe<A, B, C>(fn1: (arg: A) => B, fn2: (arg: B) => C): (arg: A) => C;
function pipe<A, B, C, C>(fn3: (arg: A) => B, fn2: (arg: B) => C): (arg: A) => C;
                    // ^ Cursor should be here

function pipe(...fns: [(arg: any) => any]): (arg: any) => any {
  /* body omitted */
}

Now comes the magic trick: Press Ctrl+A to increment the letter. This is why we needed to change that setting earlier. This will turn the C into a D, but it will also do that for any other letter. This is important because we want to reuse our macro to create many lines automatically where the letter would be different each time.

The next step is adding a new argument. For this, we first jump to the end of the line with $. Then we jump to the comma in front of the last argument with F,. To copy the last argument, we need to press y2t) which means "yank to second )" aka copy everything until the second closing parenthesis (the first one is part of the type). Now we jump forward to the end of the arguments with 2f) (skipping the one parenthesis of the type). Pasting requires now a capital P because we want to paste before our cursor. The result should look like this:

function pipe<A, B>(fn1: (arg: A) => B): (arg: A) => B;
function pipe<A, B, C>(fn1: (arg: A) => B, fn2: (arg: B) => C): (arg: A) => C;
function pipe<A, B, C, D>(fn3: (arg: A) => B, fn2: (arg: B) => C, fn2: (arg: B) => C): (arg: A) => C;
                                                                                // ^ Cursor should be here

function pipe(...fns: [(arg: any) => any]): (arg: any) => any {
  /* body omitted */
}

To finish the work on that argument, we need to change its name and adjust the types. To change the name we jump back two colons with 2F: and go one further by hitting h. The cursor is now over the 2. With Ctrl+A we can again increment that number to 3. To adjust the types we first go to the closing parenthesis with f) and one character back with h. Increment it with Ctrl+A. Now we jump to the second closing parenthesis with 2f) and again go one back with h and increment it with Ctrl+A. The final result looks like this:

function pipe<A, B>(fn1: (arg: A) => B): (arg: A) => B;
function pipe<A, B, C>(fn1: (arg: A) => B, fn2: (arg: B) => C): (arg: A) => C;
function pipe<A, B, C, D>(fn3: (arg: A) => B, fn2: (arg: B) => C, fn3: (arg: C) => D): (arg: A) => C;
                                                                                // ^ Cursor should be here

function pipe(...fns: [(arg: any) => any]): (arg: any) => any {
  /* body omitted */
}

The last thing that is still missing is the return type of the function, but this is now rather easy. Jump to the end of the line with $, go one back with h and increment it with Ctrl+A. And we are done recording! Hit q to stop it.

Reaping the benefits

That was quite a lot of work for just one single line, but when recording the macro, we never used any absolute positioning, we always jumped to landmarks like a parenthesis, a comma or the start and end of the line. This makes the command work even if there are more than just two arguments already defined. With the cursor still on the new overload press @o and you will see a new overload appears right below the one that took us so much time.

function pipe<A, B>(fn1: (arg: A) => B): (arg: A) => B;
function pipe<A, B, C>(fn1: (arg: A) => B, fn2: (arg: B) => C): (arg: A) => C;
function pipe<A, B, C, D>(fn1: (arg: A) => B, fn2: (arg: B) => C, fn3: (arg: C) => D): (arg: A) => D;
function pipe<A, B, C, D, E>(fn1: (arg: A) => B, fn2: (arg: B) => C, fn3: (arg: C) => D, fn4: (arg: D) => E): (arg: A) => E;

function pipe(...fns: [(arg: any) => any]): (arg: any) => any {
  /* body omitted */
}

Now to finish our 20 overloads we could manually do @o a bunch of times, but you can also just put the cursor on the last overload and hit 16@o. I chose 16 because we said 20 overloads were enough.

The full macro

Before recording the macro you need to type :set nrformats=alpha<enter> in normal mode and the cursor needs be on the second overload.

qo       // Start recording to register o
0        // Jump to the beginning of the line
f>       // Jump to >
yh       // Copy character to the left
a        // Go into insert mode after the cursor
,<space> // Normal typing
<escape> // leave insert mode
p        // Paste
<ctrl>a  // Increment character
$        // Jump to the end of the line
F,       // Jump back to the last comma
y2t)     // Copy everything until the second closing parenthesis
2f)      // Jump two closing parenthesis further
P        // Paste before cursor
2F:      // Jump back two colons
h        // Go one character left
<ctrl>a  // Increment number
f)       // Jump to next closing parenthesis
h        // Go one character left
<ctrl>a  // Increment character
2f)      // Jump two closing parenthesis further
h        // Go one character left
<ctrl>a  // Increment character
$        // Jump to the end of the line
h        // Go one character left
<ctrl>a  // Increment character
q        // Stop recording

After recording press 17@o to run the macro 17 times.

Conclusion

Vim commands and movements are very powerful. Even if you don't use them that often in your daily work or when you have just started using vim, after some time they will be a powerful ally to help automate repetitive tasks. Macros are one of the reasons why vim is my favorite editor and I think this example shows that while you (or at least I) don't need them on a daily basis, in some situations they are live savers.

Let the compiler do the work for you!

Jan van Brügge — Thu, 01 Aug 2019 18:05:26 +0000

Recently I came across a little programming puzzle, the task was to take a binary search tree and return a new tree, where every node is replaced by the sum of the nodes to the right. So given this tree:

We start on the rightmost number and set it to zero (because the sum of nothing is still nothing). The seven above it comes next and the current sum is 8 because there is only one node to the right. After this comes the "second" 6, so the child of the other 6, again, because it is further to the right. In general, the order is always right subtree, self, left subtree. In the end we end up with this tree, check if you understand where every number comes from:

Implementing this algorithm in Java

For the following implementations, we will only use stuff from the standard library.

First, we define ourselves a tree:

public class Node {
    Node left;
    int value
    Node right;

    public Node(Node l, int v, Node r) {
        this.left = l;
        this.value = v;
        this.right = r;
    }
}

Now, as always with recursive data structures like lists and trees, we will define the algorithm as a recursive function. We will need to keep track of the current sum and just build up a new tree with the new data.

public class Pair {
    Node n;
    int v;

    public Pair(Node n, int v) {
        this.n = n;
        this.v = v;
    }
}

public class Node {
    Node left;
    int value;
    Node right;

    public Node(Node l, int v, Node r) { /* ... */ }

    public Pair solve(int currentSum) {
        // Store the current sum in here, as fallback if right is null
        Pair rightResult = new Pair(null, currentSum);
        // First, go to the right subtree, if it exists
        if(this.right != null) {
            rightResult = this.right.solve(currentSum);
        }
        int sum = rightResult.v + this.value;

        // Again, save the sum as fallback
        Pair leftResult = new Pair(null, sum);
        if(this.left != null) {
            leftResult = this.left.solve(sum);
        }

        // Finally create a new node (to replace self)
        Node newSelf = new Node(leftResult.n, rightResult.v, rightResult.n);
       // And return it together with the sum
       return new Pair(newSelf, leftResult.v);
    }
}

Now, we just need a main function to run this:

public class Main {
    static Node testTree = new Node(
        new Node(
            new Node(null, 1, null),
            2,
            null
        ),
        5,
        new Node(
            new Node(
                null,
                6,
                new Node(null, 6, null)
            ),
            7,
            new Node(null, 8, null)
        )
    );

    public static void main(String[] args) {
        Pair result = testTree.solve(0);
        System.out.println(result.n);
    }
}

To see our result, we also need a toString method on the Node:

public class Node {
    Node left;
    int value;
    Node right;

    public Node(Node l, int v, Node r) { /* ... */ }

    public Pair solve(int currentSum) { /* ... */ }

    public String toString() {
        String leftTree = left == null ? " " : left.toString();
        String rightTree = right == null ? " " : right.toString();
        return "Node(" + leftTree + ", " + value + ", " + rightTree + ")";
    }
}

If you run the code now, you will see

Node(Node(Node( , 34,  ), 32,  ), 27, Node(Node( , 21, Node( , 15,  )), 8, Node( , 0,  )))

which is exactly the tree we are looking for!

Implementing this in Haskell

Now you may ask, what does this have to do with the title? The compiler does not write the code for us here. This is because the Java compiler is merely a "checking" compiler (as I call it). It complains if you mismatch types or make syntax errors, but it does not do work for you, it is basically like the teacher that checks your answer afterwards.

The Haskell compiler is different. And is so for several reasons. First, Haskell infer types, so you do not have to annotate them everywhere and errors also say which type is expected where. The other reason is that Haskell focuses a lot more on fundamental abstractions than other commonly used languages.

One of this fundamental abstractions is a Functor. If your datatype is a functor, you can map a function over it. Nothing more, nothing less. For example, an array or list is a Functor where you apply a function for each element (you may know this from Java streams or JavaScript Array.map). In Haskell, this works over any datatype that "contains" other data. So let's define such a datatype - note that we leave the type of data in the tree abstract, in the Java example it was int:

module Main where

data Tree a = Leaf | Node (Tree a) a (Tree a)

This declaration is fundamentally the same as the Node class in the Java example. Just instead of null we use Leaf to signal empty children and we did not name the data left, value, right, but just put them in that order.

So, now back to functor: The compiler is able to automatically generate the code you would need to implement this mapping. All you need to do is to enable that feature and use the deriving clause.

{-# LANGUAGE DeriveFunctor #-}
module Main where

data Tree a = Leaf | Node (Tree a) a (Tree a)
            deriving Functor

This would already allow us to increment all nodes in the tree by one for example:

incrementNodes :: Tree Int -> Tree Int
incrementNodes tree = fmap (+1) tree

But now we would like to map and collect at the same time. We solved the first half, let's do the second half. For collapsing a structure down to a singular value, there is the type class Foldable that requires your data to be a Functor already. Again, array and lists are foldable, and it works just like collect in Java 8 and Array.reduce in JavaScript. And again, this can be automatically generated by the compiler for you:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
module Main where

data Tree a = Leaf | Node (Tree a) a (Tree a)
            deriving (Functor, Foldable)

Now we could calculate the sum of all nodes for example:

sumNodes :: Tree Int -> Int
sumNodes tree = foldr (+) 0 tree

Now to the last step: mapping and folding in one. For this we need another abstraction - Traversable. This class allows to map and also simultaneously keep track of some "side effects", but needs your data to be Foldable already. For example we can keep track of some local state - the current sum. And like the classes before, the compiler can generate it automatically for us:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
module Main where

data Tree a = Leaf | Node (Tree a) a (Tree a)
            deriving (Functor, Foldable, Traversable)

With all this in place, our final solution is pretty simple:

solve :: Tree Int -> (Int, Tree Int)
solve tree = mapAccumR (\a b -> (a + b, a)) 0 tree

mapAccumR is a function from the Haskell standard library that is defined like this:

mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumR fun init x = runStateR (traverse (StateR . flip fun) x) init

This exact definition is not that important, just see that in the inner parenthesis it uses StateR to make your function behave like a side effect. Then it uses traverse to combine the stateful effects in the right order and runStateR then executes them one by one.

Java required us to write a toString method by hand. In Haskell we can again use the compiler for this by deriving Show. So with a main method to make everything runnable, our complete code for the puzzle is just:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
module Main where

data Tree a = Leaf | Node (Tree a) a (Tree a)
            deriving (Show, Functor, Foldable, Traversable)

solve :: Tree Int -> (Int, Tree Int)
solve tree = mapAccumR (\a b -> (a + b, a)) 0 tree

testTree :: Tree Int
testTree =
    Node
        (Node
            (Node Leaf 1 Leaf)
            2
            Leaf
        )
        5
        (Node
            (Node
                Leaf
                6
                (Node Leaf 6 Leaf)
            )
            7
            (Node Leaf 8 Leaf)
        )

main :: IO ()
main = do
    let (sum, tree) = solve testTree
    print tree

Conclusion

As you can see if the compiler has your back, you can severely cut down the number of lines of code. More code always means more bugs, so everything we do not have to write ourselves is good.

What the heck is polymorphism?

Jan van Brügge — Sat, 23 Feb 2019 00:24:37 +0000

Polymorphism is the idea of defining data structures or algorithms in general, so you can use them for more than one data type. The complete answer is a bit more nuanced though. Here I have collected the various forms of polymorphism from the common types that you most likely already used, to the less common ones, and compare how they look in object-oriented or functional languages.

Parametric polymorphism

This is a pretty common technique in many languages, albeit better known as "Generics". The core idea is to allow programmers to use a wildcard type when defining data structures that can later be filled with any type. Here is how this looks in Java for example:

class List<T> {
    class Node<T> {
        T data;
        Node<T> next;
    }

    public Node<T> head;

    public void pushFront(T data) { /* ... */ }
}

The T is the type variable because you can later "assign" any type you want:

List<String> myNumberList = new List<String>();
myNumberList.pushFront("foo");
myNumberList.pushFront(8) // Error: 8 is not a string

Here the list can only contain elements of type string and nothing else. We get helpful compiler errors if we try to violate this. Also, we did not have to define the list for every possible data type again, because we can just define it for all possible types.

But not only imperative or object oriented languages have parametric polymorphism, it is also very common in functional programming. For example in Haskell, a list is defined like this:

data List a = Nil | Cons a (List a)

This definition means: A list takes a type parameter a (everything left of the equals sign defines the type) and is either an empty list (Nil) or an element of type a and a list of type List a. We don't need any external pushFront method, because the second constructor already does this:

let emptyList = Nil
    oneElementList = Cons "foo" emptyList
    twoElementList = Cons 8 oneElementList -- Error: 8 is not a string

Ad-hoc polymorphism

This is more commonly known as function or operator overloading. In languages that allow this, you can define a function multiple times to deal with different input types. For example in Java:

class Printer {
    public String prettyPrint(int x) { /* ... */ }
    public String prettyPrint(char c) { /* ... */ }
}

The compiler will automatically choose the right method depending on the type of data you pass to it. This can make APIs easier to use as you can just call the same function with any type and you do not have to remember a bunch of variants for different types (à la print_string, print_int, etc).

In Haskell, Ad-hoc polymorphism works via type classes. Type classes are a bit like interfaces in object oriented languages. See here for example the same pretty printer:

class Printer p where
    prettyPrint :: p -> String

instance Printer Int where
    prettyPrint x = -- ...

instance Printer Char where
    prettyPrint c = -- ...

Subtype polymorphism

Subtyping is better known as object oriented inheritance. The classic example is a vehicle type, here in Java:

abstract class Vehicle {
    abstract double getWeight();
}

class Car extends Vehicle {
    double getWeight() { return 10.0; }
}

class Truck extends Vehicle {
    double getWeight() { return 100.0; }
}

class Toyota extends Car { /* ... */ }

static void printWeight(Vehicle v) {
    // Allowed because all vehicles have to have this method
    System.out.println(v.getWeight()); 
}

Here we can use any child class of the vehicle class as if it was a vehicle class directly. Note that we cannot go the other way, because not every vehicle is guaranteed to be a car for example.

This relation gets a bit hairy when you are allowed to pass functions around, here for example in Typescript:

const driveToyota = (c: Toyota) => { /* ... */ };
const driveVehicle = (c: Vehicle) => { /* ... */ };

function driveThis(f: (c: Car) => void): void { /* ... */ }

Which of the two functions are you allowed to pass to driveThis? You might think the first one, after all as we have seen above a function that expects an object can also be passed its subclasses (see the printWeight method). But this is wrong if you pass a function. You can think of it like this: driveThis wants something that can accept any car. But if you pass in driveToyota, the function can only deal with Toyotas which is not enough. On the other hand if you pass in a function that can drive any vehicle (driveVehicle), this also includes cars, so driveThis would accept it.

As Haskell is not object oriented, subtyping would not make much sense.

Row polymorphism

Now we come to the less commonly used types of polymorphism that are only implemented in very few languages.

Row polymorphism is like the little brother of subtyping. Instead of saying every object in the form { a :: A, b :: B } is also a { a :: A }, we allow to specify a row extension: { a :: A | r }. This makes it easier to use in functions, as you do not have to think if you are allowed to pass the more specific or the more general type, but instead you just check if you type matches the pattern. So { a :: A, b :: B } matches { a :: A | r } but { b :: B, c :: C} does not. This also has the advantage that you do not lose information. If you cast a Car to a Vehicle you have lost the information which specific vehicle the object was. With the row extension, you keep all the information.

printX :: { x :: Int | r } -> String
printX rec = show rec.x

printY :: { y :: Int | r } -> String
printY rec = show rec.y

-- type is inferred as `{x :: Int, y :: Int | r } -> String`
printBoth rec = printX rec ++ printY rec

One of the most popular languages implementing row polymorphism is PureScript and I am also currently working on bringing it to Haskell.

Kind polymorphism

Kinds are sort of the types of types. We all know values, it's the data that every function deals with. 5, "foo", false are all examples of values. Then there is the type level, describing values. This should also be very known to programmers. The types of the three values before are Int, String and Bool. But there is even a level above that: Kinds. The kind of all types is Type also written as *. So this means 5 :: Int :: Type (:: means "has type"). There are also other kinds. For example while our list type earlier is a type (List a), what is List (without the a)? It still needs another type as argument to form a normal type. Therefore its kind is List :: Type -> Type. If you give List another type (for example Int) you get a new type (List Int).

Kind polymorphism is when you can define a type only once but still use it with multiple kinds. The best example is the Proxy data type in Haskell. It is used to "tag" a value with a type:

data Proxy a = ProxyValue

let proxy1 = (ProxyValue :: Proxy Int) -- a has kind `Type`
let proxy2 = (ProxyValue :: Proxy List) -- a has kind `Type -> Type`

Higher-rank polymorphism

Sometimes, normal ad-hoc polymorphism is not enough. With ad-hoc polymorphism you provide many implementations for different types and the consumer of your API chooses which type he wants to use. But sometimes you as producer of an API wants to choose which implementation you want to use. This is where you need higher-rank polymorphism. In Haskell this looks like this:

-- ad-hoc polymorphism
f1 :: forall a. MyTypeClass a => a -> String
f1 = -- ...

-- higher-rank polymorphism
f2 :: Int -> (forall a. MyTypeClass a => a -> String) -> Int
f2 = -- ...

Instead of having the forall on the outer most place, we push it inwards and therefore declare: Pass me a function that can deal with any type a that implements MyTypeClass. You can probably see that f1 is such a function, so you are allowed to pass it to f2.

The standard example why this is useful is the so called "ST-Trick". It is what allows Haskell to have mutable state that cannot escape the scope:

doSomething :: ST s Int
doSomething = do
    ref <- newSTRef 10
    x <- readSTRef ref
    writeSTRef (x + 7)
    readSTRef ref

The s parameter here is important, every stateful operation requires the same s in the signature. The magic is now the function that converts a stateful computation to a pure one, runST:

runST :: forall a. (forall s. ST s a) -> a

You can see that s is created using higher-rank polymorphism. As we do not specify any constraints on what the s is, the stateful computation cannot do anything with it except passing it around in the type signatures. It behaves just like the "tag" of Proxy. And because it only defined in the scope of the stateful action (by the inner forall), every attempt at leaking anything from the computation is an error in the compiler.

Linearity polymorphism

Linearity polymorphism is connected to linear types, aka types that track "usage" of data. A linear type tracks the so called multiplicity of some data. In general you distinguish 3 different multiplicities: "zero", for stuff that exists only at type level and is not allowed to be used at value level; "one", for data that is not allowed to be duplicated (file descriptors would be an example for this) and "many" which is for all other data.

Linear types are useful to guarantee resource usage. For example if you fold over a mutable array in a functional language. Normally you would have to copy the array at every step or you have to use low-level unsafe functions. But with linear types you can guarantee that this array can only be used at one place at a time, so no data races can happen.

The polymorphism aspect comes into play with functions like the mentioned fold. If you give fold a function that uses its argument only once, the whole fold will use the initial value only once. If you pass a function that uses the argument multiple times, the initial value will also be used multiple times. Linarity polymorphism allows you to define the function only once and still offer this guarantee.

Linear types are similar to Rust's borrow checker, but Rust does not really have linearity polymorphism. Haskell is getting linear types and polymorphism soon.

Levity polymorphism

In Haskell all normal data types are just references to the heap, just like in Python or Java, too. But Haskell allows also to use so called "unlifted" types, meaning machine integers directly for example. This means that Haskell actually encodes memory layout and location (stack or heap) of data types on the type level! These can be used to further optimize code, so the CPU does not have to first load the reference and then request the data from the (slow) RAM.

Levity polymorphism is when you define functions that work on lifted as well as unlifted types.

Haskell by example - Utopian Tree

Jan van Brügge — Tue, 06 Nov 2018 12:01:46 +0000

In this series we solve coding challenges from Hackerrank in Haskell in a proper, functional way. In the last part I did not mention which how to get up and running with Haskell on your own PC, so I want to fix that. The easiest way is to download Stack. Then create a file with the ending .hs somewhere and open a terminal in the same directory. Type stack ghci to open an interactive Haskell REPL, this will take some time the first time as stack has to download the haskell compiler first. Once that is done, you can type :load <filename>.hs to compile and type check your code. You can also get the type of an expression with :type <expr>.

The problem

A Utopian Tree has two growth spurts every year, one in spring and one in summer. In spring the tree doubles its size, in summer it grows by one meter. You plant a tree that is initially one meter tall. How big is the tree after n growth spurts?

To recap what is going on, for n == 5:

Period  Height
  0       1      We start with a 1 meter tree
  1       2      Double the size
  2       3      Increase by one meter
  3       6      Double again
  4       7      Plus one meter
  5       14     And a final double

Input format

We will receive multiple lines with one number each. The first line is the number of lines that follow. The other numbers are the amount of growth spurts. The goal is to answer for each number how big the tree is afterwards.

So for example (refering to the table from earlier) when we get

We have to return (remember the first line is just the length)

7
3
1

If you don't want to get the solution spoiled, head now to Hackerrank and solve the problem yourself first.

Just a note, the Haskell template of Hackerrank is horrible, do not use it. You will see later the complete solution is much shorter than the template alone.

The solution

If we think a bit about the problem, it boils down to doing one thing: Doubling or incrementing the current height n times (where n is the number given to us). In imperative programming languages you would use a for loop to do this, but in Haskell there is no for loop. The reason is simple, you are not allowed to change variables, so you cannot change the i variable in the loop. But this is not limiting at all, rather it has some interesting consequences: In Haskell, lists double as control structures. What does that mean? You saw it a bit in the last part of this series:

Now for each line (aka element in the list), we want to first split the string into words and then for each word we want to convert the string to an integer.

In other languages "for each x" would be a clear signal to use a for loop, but here we used map and lists.

For our new problem map is not enough as we have to remember the last height of the tree. But luckily there is also a function for that, foldl (for those who know JavaScript, array.reduce is basically the same function).

foldl :: (b -> a -> b) -> b -> [a] -> b

foldl takes a function from the remembered value and the current value to a new remembered value as first argument, the initial value as second argument and a list of values as third one. It returns the remembered value at the end.

So, let's start with our solve function, note that this function will only calculate the height of one tree, not all of trees.

solve :: Int -> Int
solve n = foldl fn init list

Ok, now we have to find the values of fn, init and list. The initial value should be clear, the problem already states that we start with a tree of height 1.

solve :: Int -> Int
solve n = foldl fn 1 list

The list is a bit more complicated. Remember how I said that lists double as control structures (ie a for loop). We want to double and increment the height alternatingly. We can define a list that expresses exactly this behavior:

solve :: Int -> Int
solve n = foldl fn 1 {- stuff missing -} [(*2), (+1)]

Now we have a list of two functions, both from Int to Int. But we don't want to do this twice, but more often! Here comes another strength of Haskell into play: Laziness. Laziness means that values are only computed when they are needed. For example:

first :: [Int] -> Int
first [a, b] = a

x = first [1, error "this will crash"]

This snippet will work just fine, even though we have an run-time error in there. The reason for this is that we never try to use the value of the error, so it never gets evaluated. But again, this has a nice side effect too: Haskell can deal with infinite lists! Of course an infinite list would never fit in memory, but as Haskell only evaluates the stuff it needs, the list never get allocated completely.

allEvenNumbers = filter even [1 ..]
x = take 6 allEvenNumbers

Here we filter a list of all positive numbers to return only even ones. In other programming languages, this snippet would cause either a stack overflow error or an infinite loop.

Going back to our solve function, we can use cycle to create an infinite list by repeating the given list forever.

solve :: Int -> Int
solve n = foldl fn 1 {- stuff missing -} cycle [(*2), (+1)]

But we don't want the result after infinite growth spurts, but after n! We already know how to do this from the last part:

solve :: Int -> Int
solve n = foldl fn 1 . take n . cycle $ [(*2), (+1)]

We simply take n values from our infinite list. Now the last question is, what should fn do? Here we can use the REPL to help us. If we type in our current solution with a placeholder instead of fn, Haskell will tell us what it expects:

Prelude> foldl _ 1 $ cycle [(*2), (+1)]

<interactive>:7:7: error:
    • Found hole: _ :: b -> (Integer -> Integer) -> b
      Where: ‘b’ is a rigid type variable bound by
               the inferred type of it :: Num b => b at <interactive>:7:1-30
    • In the first argument of ‘foldl’, namely ‘_’
      In the expression: foldl _ 1
      In the expression: foldl _ 1 $ cycle [(* 2), (+ 1)]
    • Relevant bindings include it :: b (bound at <interactive>:7:1)

The message might look scary, but let's digest it step by step. The first line tells us already most of what we want to know: The placeholder has type b -> (Integer -> Integer) -> b. The third line tells us that b has to be a number type (this is what Num b => b means). The reason for this is that the 1 in our code could still be any number type. We could add a type signature to force it to be an integer:

Prelude> foldl _ (1 :: Integer) $ cycle [(*2), (+1)]

<interactive>:10:7: error:
    • Found hole: _ :: Integer -> (Integer -> Integer) -> Integer
    • In the first argument of ‘foldl’, namely ‘_’
      In the expression: foldl _ (1 :: Integer)
      In the expression: foldl _ (1 :: Integer) $ cycle [(* 2), (+ 1)]
    • Relevant bindings include
        it :: Integer (bound at <interactive>:10:1)

As you can see now, we need a function that takes a value and a function and returns the result of the function applied to the value. Here we can make use of another great tool: Hoogle. If we head to haskell.org/hoogle and enter the type signature we received from the REPL, we get a bunch of results. If we ignore the first few that are more complicated, we quickly see one entry in the list that we know already:

The $ operator. The only problem is that the arguments are in the wrong order. But this is not an issue as there is a flip function that swaps the arguments. So now we can finish our solve function:

solve :: Int -> Int
solve n = foldl (flip ($)) 1 . take n . cycle $ [(*2), (+1)]

We have two wrap the operator in parenthesis to use it as a normal function and not as an operator.

Making it executable

Again, the solve function is not enough, we need to read from standard input and write to standard output. We will use the interact function for this again.

solve :: Int -> Int
solve n = foldl (flip ($)) 1 . take n . cycle $ [(*2), (+1)]

main :: IO ()
main = interact $ -- stuff missing

Ok, we need all the lines except the first. We already did this last time:

solve :: Int -> Int
solve n = foldl (flip ($)) 1 . take n . cycle $ [(*2), (+1)]

main :: IO ()
main = interact $ tail . lines

Now, for each line we want to convert the string to a number, run the solve function and convert the number back into a string

solve :: Int -> Int
solve n = foldl (flip ($)) 1 . take n . cycle $ [(*2), (+1)]

main :: IO ()
main = interact $ map (show . solve . read) . tail . lines

Finally, we want to put a newline between all strings in the list. There is already a function for that called unlines - because it is the inverse of lines.

solve :: Int -> Int
solve n = foldl (flip ($)) 1 . take n . cycle $ [(*2), (+1)]

main :: IO ()
main = interact $ unlines . map (show . solve . read) . tail . lines

And that's it! Two lines of code to have a complete solution without going into stuff like code golf. Even more than last time, we did not write a whole lot ourselves, we just composed functions from the standard library to form bigger functions. This is the core of functional programming!

Performance PSA

While our current solution works and will pass the tests of Hackerrank, it is not suitable for production. The reason is (unwanted) laziness. The definition of foldl looks like this:

foldl _ x [] = x
foldl f x (y:xs) = foldl f (f x y) xs

The problem is that Haskell does not evaluate (f x y) at this point, but only allocates a so called "thunk" that tells how to calculate it. When we run through the list we can see the problem:

x = foldl (+) 0 [1,2,3,4]
x = foldl (+) (0 + 1) [2,3,4]
x = foldl (+) ((0 + 1) + 2) [3, 4]
x = foldl (+) (((0 + 1) + 2) + 3) [4]
x = foldl (+) ((((0 + 1) + 2) + 3) + 4) []
x = ((((0 + 1) + 2) + 3) + 4)

At that point in time, none of the expressions in the parenthesis are evaluated, but for each + a thunk has to be allocated. This is a huge waste of space and a severe drop in performance. Luckily there is a strict (as in "not lazy") version of foldl in the standard library: foldl'. We can also implement it ourselves with the BangPatterns extension (I will go deeper into language extensions in a later post).

foldl' _ !x [] = x
foldl' f !x (y:xs) = foldl f (f x y) xs

This exclamation mark causes the argument to be strict, ie it will be evaluated before the rest of the function. With it, our evaluation looks like this:

x = foldl (+) 0 [1,2,3,4]
x = foldl (+) (0 + 1) [2,3,4]
x = foldl (+) (1 + 2) [3, 4]
x = foldl (+) (3 + 3) [4]
x = foldl (+) (6 + 4) []
x = 10

This time, we did not allocate a bunch of thunks, and our function runs fast. We do not have to define this function ourselves though, we can simply import it from the standard library:

module Main where

import Data.Foldable (foldl')

solve :: Int -> Int
solve n = foldl' (flip ($)) 1 . take n . cycle $ [(*2), (+1)]

main :: IO ()
main = interact $ unlines . map (show . solve . read) . tail . lines

In general, never use foldl always use foldl'.

Closing thoughts

I hope this example is easy enough to get more familiar with the language. If you have any question, be it about my code or Haskell in general, feel free to ask them.

Haskell by example - The birthday bar

Jan van Brügge — Fri, 02 Nov 2018 21:35:52 +0000

This is the beginning of a series where I show you how to solve coding challenges in Haskell in a proper, functional way. If you do not know Haskell, that is fine, I will explain everything in detail. The problems are from Hackerrank, so you can try them out yourself and play with the implementation.

The problem

You have a chocolate bar where each of the squares has a number on it. You want to share the bar with your friend, so that the length of the slice is equal to his birth month and the sum of the numbers in those squares is the birth day. You have to print how many of such slices you can make with a given chocolate bar.

As example, you have the chocolate bar [2, 2, 1, 3, 2]. Your friend's birthday is at the 4. of February. In this case there are two possible slices: [2, 2] and [1, 3], because they have length two (month) and sum 4 (day).

Input format

We will receive the details via standard input where the first like contains just the length of the chocolate bar, the second like contains the bar - separated by spaces - and the last line is first the birthday and then the birth month, also separated by a space. Our example from earlier would look like this:

5
2 2 1 3 2
4 2

We know that all values we receive will be greater than zero.

If you don't want to get the solution spoiled, head now to Hackerrank and solve the problem yourself first.

Just a note, the Haskell template of Hackerrank is horrible, do not use it. You will see later the complete solution is much shorter than the template alone.

The solution

We will start with the actual solve function that takes the chocolate bar as a list of integers, the birth day and month. We start by writing the type signature.

solve :: [Int] -> Int -> Int -> Int

Here solve is the name of our function, after the double colon is the type of the function. Every arrow represents a function, everything right of the arrow is what the function returns. So this function takes a list of integers and returns a function that takes an integer and so forth until it just returns an integer. This is because every function in Haskell has only one argument (this is called currying). In practice this does not matter, because the syntax is very convenient. We continue to write the beginning of the implementation, starting with naming our function arguments.

solve :: [Int] -> Int -> Int -> Int
solve bar m d =

See? You do not even notice that solve returns a function! But it does, if we would want to call the function, we could do any of this:

fn1 = solve [1,2,3,4] -- fn1 takes an integer and returns a function that takes an integer
fn2 = solve [1,3] 4 -- fn2 takes an integer and returns an integer
x = solve [1,3] 3 4
x' = fn1 2 4 -- I can give the rest of the arguments later

Now, back to the problem. We want to cut the bar in slices whose length is equal to the month of your friend's birth. For this we write ourselves a little helper function that checks if the bar is long enough to make a new slice and if so recursively calls itself again. Else it just returns an empty list. In Haskell we can add helper functions to the function definition with the where keyword.

solve :: [Int] -> Int -> Int -> Int
solve bar m d = {- stuff missing here -} slice bar
    where slice b
            | length b >= m = take m b : slice (tail b)
            | otherwise     = []

Here, we use a so called "guard". We split the definition in two and only if the condition before the equals sign is met, we evaluate the right side. As said, first we check if we can make another slice and if so, we take m elements from b. As you already guessed, take returns a list of the first m elements in the list b. We then use : to prepend the new list to the list returned by slice. The argument to slice is using tail on the input, which returns the list without the first element.

Let's play through this function by hand. The nice thing about functional programming is that you can just replace definitions with their implementations to see what is evaluated.

m = 2
b = [2,2,1]
x = slice b -- length b is greater than 2, so we use the first definition
x = take 2 b : slice (tail b) -- replace tail and take with their results
x = [2,2] : slice [2,1] -- replace slice with definition, still the first one
x = [2,2] : (take 2 [2,1] : slice (tail [2,1])) -- replace tail and take again
x = [2,2] : ([2,1] : slice [1]) -- replace slice again, this time the second definition
x = [2,2] : ([2,1] : []) -- prepend list to empty list
x = [2,2] : [[2,1]] -- do again
x = [[2,2], [2,1]] -- now we got a list of list, with the possible slices

Now we are only interested in those slices which sum is equal to the date of birth. For this we can filter the list.

solve :: [Int] -> Int -> Int -> Int
solve bar m d = filter fn $ slice bar
    where slice b
            | length b >= m = take m b : slice (tail b)
            | otherwise     = []

The $ operator in Haskell is to avoid parenthesis. It evaluates the thing on the right first, before using it as argument to the left. foo $ bar x is the same as foo (bar x).

Currently there is still this fn in there that we have not defined yet. We could write another helper function, but we don't have to. We can compose existing functions to form the function we need. Let's recap what the function should do: Filter will iterate through all lists in the list of slices, so our function will receive a single slice. First we have to take the sum of that list and then we have to check if that value is equal to the day of birth.

solve :: [Int] -> Int -> Int -> Int
solve bar m d = filter ((== d) . sum) $ slice bar
    where slice b
            | length b >= m = take m b : slice (tail b)
            | otherwise     = []

That's it! In Haskell, operators are also just functions, so we can also only provide a part of their arguments. This is what we do here: (== d) returns a function that checks if the input is equal to d. This input comes from the sum function that takes a list of numbers and adds them up.

The last thing missing is to count how many such slices there are. For we just need the length of our filtered list.

solve :: [Int] -> Int -> Int -> Int
solve bar m d = length $ filter ((== d) . sum) $ slice bar
    where slice b
            | length b >= m = take m b : slice (tail b)
            | otherwise     = []

Here you can also see: Composition (the .) and application (the $) are directly related. It depends on the point of view. At the moment our point of view is: "Evaluate the slices of bar, then apply the result to the filter function and then apply that result to the length function". But we can change our point of view very easily:

solve :: [Int] -> Int -> Int -> Int
solve bar m d = length . filter ((== d) . sum) . slice $ bar
    where slice b
            | length b >= m = take m b : slice (tail b)
            | otherwise     = []

Now our view is: "apply bar to the function that is the result of composing length with filter and slice". The code still does the same, but (at least in my opinion) the meaning changed a bit.

Making it executable

The core of our solution is done, but now we need to process the data from standard input and print the result to standard output. In Haskell the entry point of every program is main. It is not a function, but a value in fact. Because in Haskell IO is also a value that you can pass around!

solve :: [Int] -> Int -> Int -> Int
solve bar m d = -- omitted

main :: IO ()
main = putStrLn "Hello"

Here, putStrLn is function that takes a string and returns such an IO value. Note that in the type signature, the parenthesis does not stand for function, but for the empty tuple, also called unit. It is just there because IO needs to "contain" a value, so we give it unit.

But we don't want a function that takes a string and does IO, we would like a function that reads and writes from stdin/stdout lets us handle just the strings. There is also a function for this: interact. It takes a function from string to string and returns IO.

interact :: (String -> String) -> IO ()

So now we have to create a function that takes a string in the input format from above and returns a string with the result, calling our solve function somewhere in between. We will use function composition for this again, step by step. First, we want to split the input into the individual lines. We can use the lines function for that, it takes a string and returns a list of strings. Then we are not interested in the first line, so we can use tail from earlier to get rid of the first element in that list of lines:

solve :: [Int] -> Int -> Int -> Int
solve bar m d = -- omitted

main :: IO ()
main = interact $ tail . lines

Now for each line (aka element in the list), we want to first split the string into words and then for each word we want to convert the string to an integer. Every time we want to convert every element in a list in Haskell we use the map function. It takes a function and a list of values and returns a list with the function applied to every element in the list.

map :: (a -> b) -> [a] -> [b]
------
x = map (+1) [1,2,3] -- x is [2,3,4]

You see that the type signature uses lower case letters and not capitalized words like earlier. This means that this is a type variable, so you can put any type you want in there. Now let's convert the sentence above into a function:

solve :: [Int] -> Int -> Int -> Int
solve bar m d = -- omitted

main :: IO ()
main = interact $ map (map read . words) . tail . lines

The outer map will apply the inner function for each line it receives. The inner function first splits the line into words and then applies read to every element in the list of words.

At the moment our function takes a string and returns a list of list of integers, where the first element in the list is the bar (or the list representing the bar) and the second element is the list consisting of the day and the month of your friend's birth. Now we could call solve, but the arguments do not match, solve does not want a list of lists, but three arguments instead. Because we always know how the list of lists will look, we can use pattern matching to extract the arguments from the list.

solve :: [[Int]] -> Int
solve [bar, [m, d]] = -- omitted, did not change

main :: IO ()
main = interact $ solve . map (map read . words) . tail . lines

You can see we first match on the outer list, naming the first element bar. Then we further match on the second element and name its elements m and d. We also have to adjust our type signature accordingly. In a production environment, you would factor the pattern matching out in a different function, as the original type signature of solve was a lot more meaningful than the new one. But as this is only a coding challenge we will not bother to do that.

The last step needed is to convert the integer returned from solve back to a string (remember interact takes a function from string to string). For this there is the function show in haskell.

solve :: [[Int]] -> Int
solve [bar, [m, d]] = length . filter ((== d) . sum) . slice $ bar
    where slice b
            | length b >= m = take m b : slice (tail b)
            | otherwise     = []


main :: IO ()
main = interact $ show . solve . map (map read . words) . tail . lines

And with that, our solution is complete!

Closing thoughts

As you could see, when using a functional language, you do not try to tell the computer how to do something, but more what you want to do. This is one of the reasons why function composition is preferred over function application (within reason of course).

I really enjoy writing Haskell daily, but I know it's a daunting language. I hope this series will make it a bit easier to "grasp" the language. Thank you for reading.

Inside a framework - How the Cycle.js DOM driver works

Jan van Brügge — Mon, 20 Aug 2018 20:44:59 +0000

Often, we use a framework without really knowing how it works internally. Sometimes we contribute to that framework without having any clue about the inner workings.

For me, this was the case with Cycle.js. I was even invited to be a Core Team Member without having any clue how the DOM part of it worked besides "it uses virtual DOM under the hood".

Lately I stumbled across severe issues in the DOM driver that (together with older issues) convinced me to deep dive into it and rewrite it basicly from scratch.

In this article I want to show you the main algorithm and the data structures that make the DOM driver efficient, but still easy to use.

The main problem - isolation

A Cycle.js component is just a pure function from some inputs (the sources) to some outputs (the sinks). This looks like this:

function Counter(sources) {
    const increment$ = sources.DOM.select('.increment')
        .events('click').mapTo(+1); // On every click on the .increment
                                    // button emit a 1

    const decrement$ = sources.DOM.select('.decrement')
        .events('click').mapTo(-1); // Same but with -1

    const state$ = xs.merge(increment$, decrement$)
        .fold((last, curr) => last + curr, 0) // Starting with 0, add up all
                                            // numbers on the stream

    const view$ = state$.map(count => div([
        span(['Count: ' + count]),
        button('.increment'),
        button('.decrement')
    ]));

    return {
        DOM: view$
    };
}

But if you call that function twice:

function main(sources) {
    const sink1 = Counter(sources);
    const sink2 = Counter(sources);

    const view$ = xs.combine(sink1.DOM, sink2.DOM)
        .map(children => div(children));

    return {
        DOM: view$
    };
}

You get this:

Why? Because if you take a look at the DOM, you see that there are two elements with the .increment class, so either one triggers the emission of events:

You can solve this issue by using isolate() which scopes the events to their components:

function main(sources) {
-    const sink1 = Counter(sources);
-    const sink2 = Counter(sources);
+    const sink1 = isolate(Counter, 'counter1')(sources);
+    const sink2 = isolate(Counter, 'counter2')(sources);

    const view$ = xs.combine(sink1.DOM, sink2.DOM)
        .map(children => div(children));

    return {
        DOM: view$
    };
}

Building the bridge between APIs

The goal of us is to build the bridge between the declarative API of the DOM driver including isolation and the native DOM API of the browser.

For this we need to know how the browser processes events. When an event is emitted on an element it first runs through the capture phase. This means the event runs top down from the <html> to the <button> in our case, triggering the event listeners that specified useCapture: true.

Then, the more well known bubbling phase. Now the event runs bottom up through the DOM tree, triggering all event listeners that were not triggered in the capture phase.

So for our isolation we want to stop the events from propagating outside of the current scope. Sadly we can't use stopPropagation, because the capture phase always starts at the root of the DOM tree, not the root of our isolation scope.

We want the bubbling phase to look like this:

Implementing a custom event propagation algorithm

As we already said, we can't use the native event bubbling of the DOM. To make our live a bit easier, we will just attach an native event listener at the root of our cycle app, and use the bubbling to catch all events that happen in the DOM with just one listener (yes, there are events that do not bubble, but I will exclude them for sake of simplicity here).

This root event listener looks like this:

root.addEventListener('click', function(event) {
    const element = event.target;
    // do something
});

We know the element where the event happened, but not in which isolation scope this element is, as the DOM does not know anything about isolation. This means we need a mapping from element to isolation scope.

But remember how I said before, the only thing I know about the DOM driver is, that it uses virtual DOM under the hood? How do we get the actual DOM nodes, and not the vnodes?

Hooking into the VDOM

Snabbdom, the virtual DOM implementation that Cycle.js uses, allows to create modules that can hook into the DOM node create/update/delete live cycle. A basic module looks like this:

const myModule = {
  create: function(emptyVnode, vnode) {
    // invoked whenever a new virtual node is created
    // the actual DOM element is under vnode.elm
  },
  update: function(oldVnode, vnode) {
    // invoked whenever a virtual node is updated
  },
  delete: function(vnode) {
    // invoken whenever a DOM node is removed
  }
};

So if we attach the isolation scope information to the vnode, we can use the create hook to save the scope together with a reference to the DOM node.

Attaching the scope information

If we take a look at the isolate() API again, we can see that it is a higher order function, so a function that takes a function as input and (in our case) returns a new function:

const isolatedComponentFunction = isolate(Component, scope);

If we imagine the inner workings of isolate and ignore all other drivers except DOM, it would look a bit like this:

function isolate(Component, scope) {
    return function IsolatedComponent(sources) { // Return isolated component
        const isolatedSource = sources.DOM.isolateSource(sources.DOM, scope);
        const sinks = Component({ ...sources, DOM: isolatedSource });

        return {
            ...sinks,
            DOM: sources.DOM.isolateSink(sink.DOM, scope)
        };
    }
}

So we have two points of attack, isolateSource and isolateSink. Also, as you can see, sources.DOM is an object, not a plain stream, so we can use it store information. We can use isolateSink to add this stored information to the virtual dom nodes created by the user. This could look like this:

class DOMSource {
    constructor(namespace) {
        this.namespace = namespace;
    }

    isolateSource(source, scope) {
        return new DOMSource(this.namespace.concat({ type: 'total', scope }));
    }

    isolateSink(vnode$, scope) {
        return vnode$
            .map(node => ({
                ...node,
                data: {
                    ...node.data,
                    isolate: this.namespace.concat(scope)
                }
            }));
    }
}

Now we can use a Snabbdom module to hook into the DOM creation and keep track of namespaces and elements:

class IsolateModule {
    constructor() {
        this.namespaceMap = new Map();
    }

    createModule() {
        const self = this;
        return {
            create(empty, vnode) {
                if(vnode.data && vnode.data.isolate) {
                    self.namespaceMap.set(vnode.elm, vnode.data.isolate);
                }
            },
            delete(vnode) {
                self.namespaceMap.delete(vnode.elm);
            }
        };
    }
}

Using the information to distribute events

To get our desired API of sources.DOM.events(eventType), we have to implement a function called events on our DOM source. This function has to register its event type in a central place that we will call the event delegator. Why? Because that is where we will implement the custom event bubbling functionality. This register function has to return a stream of future events that the function can return to the user. We will also add a select function that just adds a css selector to the namespace so element can be filtered for those later.

class DOMSource {
    constructor(eventDelegator, namespace) {
        this.namespace = namespace;
        this.eventDelegator = eventDelegator;
    }

    events(eventType) {
        return this.eventDelegator.registerListener(this.namespace, eventType);
    }

    select(selector) {
        return new DOMSource(
            this.eventDelegator, this.namespace.concat({
                type: 'selector', scope: selector
            })
        );
    }

    isolateSource(source, scope) { /* ... */ }
    isolateSink(vnode$, scope) { /* ... */ }
}

How can we implement registerListener? How can we return a stream of events even if they have not happened yet? The answer to this question is a subject. A subject is like beginning of a conveyor belt. Its output is a stream of events, but you can put events onto the stream via function calls.

class EventDelegator {
    constructor(isolateModule) {
        this.isolateModule = isolateModule;
    }

    registerListener(namespace, eventType) {
        const subject = xs.create(); // our subject
        // TODO: save subject with namespace in some data structure
        return subject;
    }
}

We want to save all listener subjects in a central data structure. This data structure should be able to give me a subject when I give it the namespace. Our first impulse would be to use a Map again, but this is not possible due to the namespace being an array:

let test = new Map();
test.set([1,2,3], "test");
test.get([1,2,3]); // undefined

The problem is, that Javascript does not check if the arrays are equal but identical. This means, that this would work:

let test = new Map();
const arr = [1,2,3];
test.set(arr, "test");
test.get(arr); // "test"

So, we need a different data structure here.

Trees to the rescue

As our application is a tree of components, just as the DOM is a tree of nodes, our isolation scopes will also be like a tree, where each subtree shares the parent's namespace plus additionally has scopes of its own. So we can implement a tree that can carry an element at every node, plus has children that refer to scopes. See the type signatures for such a tree:

type Node = [Element | undefined, InternalTree];
interface InternalTree {
    [scope: string]: Node;
}

As you can see, a Node is an Element (or undefined) and an object containing the scopes as keys and again Nodes as Values. As you can see, this is a recursive definition. To make it easier to grasp, here is an example drawing of one such tree:

The implementation details of this tree is not that important, but if you are interested you can see it on GitHub.

Finishing our listener registration

With this tree we can finally implement registerListener.

class EventDelegator {
    constructor(isolateModule) {
        this.isolateModule = isolateModule;
        this.listenerTree = new SymbolTree();
    }

    registerListener(_namespace, eventType) {
        let namespace = _namespace.filter(scope => scope.type !== 'selector');
        let map = this.listenerTree.get(namespace);
        if(map && map.get(eventType)) {
            return map.get(eventType);
        }

        if(!map) {
            map = new Map();
            this.listenerTree.insert(namespace, map);
        }

        const subject = xs.create(); // our subject
        const arr = map.get(eventType) || [];

        map.set(eventType, arr.concat({
            namespace: _namespace,
            selector: _namespace.filter(scope => scope.type === 'selector').join(' '),
            subject
        });

        return subject;
    }

    getListeners(namespace, eventType) {
        const map = this.listenerTree.get(
            namespace.filter(scope => scope.type !== 'selector'),
        );
        return map ? map.get(eventType) : [];
    }
}

Writing our own event bubbling

Now we have registered our listeners, but they are still not receiving any events. Time for us to write our own event bubbling implementation.

For this, let's recap where we start at the beginning of each event.

root.addEventListener('click', function(event) {
    const element = event.target;
    // do something
});

With our current data structures we can expand this pice of code a bit:

root.addEventListener('click', function(event) {
    const element = event.target;
    const namespace = isolateModule.getNamespace(element);
    const namespaceRoot = isolateModule.getRootElement(namespace);
    const listeners = eventDelegator.listenerTree.get(namespace);

    //TODO: Capture phase, starting at root element, ending at element

    //TODO: Bubbling phase, starting at element, ending at root
});

Ideally we would be able to get the bubbling path from the event, and in fact this might be the case in the future with the event.path property, but at the moment we have to contruct the bubbling path ourselfs. Each element has a property parentNode, so we can just start at the element and work upwards to the namespaceRoot.

let arr = [];
let curr = element;
while(curr && curr !== namespaceRoot) {
    arr.push(curr);
    curr = curr.parentNode;
}
arr.push(namespaceRoot);

for(let i = arr.length - 1; i >= 0; i--) {
    // do bubble step
}

Now we can walk through the array to simulate our bubbling. But this implementation has a big flaw: It allocates an array on every run. This array is not needed afterwards so it will be discarded and eventually garbage collected. If we use an event that happens frequently, like mousemove, this could be a real performance bottleneck.

Recursion to the rescue

Instead of first remembering all elements and then iteration over them, we can also use recursion to walk up the DOM tree, but without allocating an array! For the capture phase, we want to first walk to the topmost element, and then on our way back down we want to execute our bubble logic. The trick is, to go into the recursive call first and then do the logic.

function bubble(elm, event)
    if(elm && elm !== namespaceRoot) {
        bubble(elm.parentNode, event);
    }

    // do bubble step
}

As you can see, the recursive implementation is not only more performant, but also a lot easier to read. Implementing each bubble step is now fairly easy, we take the css selectors from the listener and check if the element matches this selector.

function doBubbleStep(elm, event) {
    for(let i = 0; i < listeners.length; i++) {
        if(elm.matches(listeners[i].selector)) {
            listeners[i].subject.shamefullySendNext(event);
        }
    }
}

Conclusion

Implementing the DOM driver was a fun challenge. As part of a framework, you expect it to be performant but also easy to use. The implementation should not leak to the user and we have to work in the confines of the APIs we are given.

You can find the whole code of the new DOM driver on the GitHub PR.

If you have questions about the article or the implementation on GitHub, feel free to ask them!

How does a Map work?

Jan van Brügge — Wed, 04 Apr 2018 22:31:26 +0000

Sometimes, as a developer, you want to store key-value pairs. For example you may want to access a user object by its username. The best suited data structure for this is a map. It allows us to get a value by its unique key in O(1). If you are not familiar with Big-O notation, check out my article about it.

Let's take the simplest map you can think of: an array! It stores key-value-pairs, but the keys are limited to natural integers only. Random access in an array is O(1). But why?

In memory an array is one continuous block of memory. You additionally have to know where the array starts in memory and how big the individual elements are. To access a random element, you simply take the index, multiply it with the element size (assuming a uniform element size) and add the start address of the array:

memory_location_to_fetch = index * size_of_single_element + start_of_array

Hashing

Ok, but what if we want to use strings to index our elements? Here we will use a technique called hashing. A hashing function takes an input of arbitrary length and produces a deterministic output of fixed length. This is normally accomplished by the modulo operator.

hash(x) = f(x) ℅ size_of_map

f(x) is some arbitrary function that is dependent on the implementation. The easiest function would be the identity: f(x) = x.

And what about strings as keys? Or objects?

Everything is an integer

If we go back to the computer memory, everything is stored in binary. But nothing prevents you from interpreting that binary as a normal integer. Let's use a simple string as example. C-strings are just the ASCII characters in one continuous chunk of memory suffixed with a zero byte. To convert from (binary-)number to ASCII, the ASCII table is used. As example we will translate the string Hello into its number representation (in hex here, because it's easier to translate to binary than decimal):

 H     e     l     l     o     \0
0x48  0x65  0x6C  0x6C  0x6F  0x00

We can now simply interpret these 6 bytes as a number, and we can use this number as input for our hash function.

Hash collisions

As you might have already asked yourself, what happens if two different values get hashed to the same result? For example , we have a map of size 10 and put in 0, 10, 20, and so on?

For this we can implement an avoidance strategy:

Linear hashing: If spot is already occupied, move new value by fixed amount (often 1)
Double Hashing: If sport is accupied, simply hash the hash again and put our element there
Using a linked list as array elements and appending collision. This effectively gives us "buckets" filled with objects that have the same hash value.

Bringing it all together

We will now implement a map that first will only work for integers. I will be using Typescript for the examples here.

As we have already seen we can represent every type as integer, so we only care about integers for now.

First what we actually store inside our map:

class OurMap<Value> {
    private array: [number, Value][];

    constructor(size: number) {
        this.array = new Array(size);
    }
}

We just define an array of a fixed length that stores our key-value pairs.

Now we add an insert method:

class OurMap<Value> {
    private array: [number, Value][];

    constructor(size: number) {
        this.array = new Array(size);
    }

    public insert(key: number, value: Value) {
        const origIndex = this.hash(key);
        let index = origIndex;
        while(this.array[index] !== undefined
          && this.array[index][0] !== key) {
            index = (index + 1) % this.array.length;
            if(index === origIndex) {
                throw new Error('Map is already full');
            }
        }
        this.array[index] = [key, value];
    }
}

Can you see what collision avoidance strategy we have used? If you said linear hashing, you are right! If our spot is already occupied, we go one to the right.

The get method works exactly the same as the insert method, it just doesn't check for undefined but for the key you passed in.

Deletion is also similar, but we additionally have to check for elements on the right. If there is an element it might have got there by our linear hashing so if the original element is missing the get will not try to look at the right. We have to shift those elements back to the left. This, of course, could lead to further corrections.

Bonus round: Sets

You might have also stumbled across sets. As it turns out, you can implement a set with a map. In older versions of Google Chrome, you were able to see this in the DevTools. There a Set had the same properties as a Map (both keys and values instead of just values).

Let's copy that approach by simply using our keys as values.

class OurSet {
    private map: OurMap<number>;

    constructor(size: number) {
        this.map = new OurMap<number>(size);
    }

    public insert(value: number) {
        this.map.insert(value, value);
    }
}

This works because using the same key will always lead to the same memory location. So if there is already the key you overwrite it which doesn't change anything. If there is no entry you can know that this key does not yet exists in the Set.

Putting it into perspective

Data structures are all about tradeoffs and use cases. So where does our map fit in?

Maps, just like arrays, have O(1) insertion, random access and deletion. This depends on the implementation of the map though. Both have to be allocated with a fixed size upfront. If you need a dynamicly growing data structure, you should use a linked list. It is also O(1) for insertion and sequencial access, but is O(n) for deletion and random access.

You would use an array if you just want to store multiple elements for easy iteration. Use a map if you need a key-value lookup. You could use an array, but maps deal with hash collisions while an array will just overwrite the old value.

Conclusion

I hope you have learned something new in this article. This is part two of my series on data structures, you can find part one (about Big-O Notation) here. Feel free to share any feedback.

What does "Big-O notation" mean anyway?

Jan van Brügge — Wed, 07 Mar 2018 23:59:38 +0000

If you are a programmer, chances are that you have stumbled over the term "Big-O notation". But what does this actually mean?

Big-O notation is used to specify the computational complexity of your program or data structure. This basicly means: How many steps do I need to perform a certain action. "Step" in this context does not mean CPU cycles or lines in a program, but arbitrary steps with a fixed length, no matter how big they are.

Let's start with an example: Check if an element is in an array. In JavaScript you would implement this like so:

function findInArray(array, element) {
    for(let i = 0; i < array.length; i++) {
        if(array[i] === element) {
            return true;
        }
    }
    return false;
}

You can see it quite easily: Everything inside of the loop takes a constant time: Accessing an element in an array with the index and a comparison. Let's define this as 1 "step". But because of the for loop, we do this n times. In Big-O: O(n).

Other standard examples that are described in Big-O notation are sorting algorithms. Take the most simple sorting algorithm as example, bubble sort. Its implementation could be this:

function bubblesort(array) {
    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length - 1; j++) {
            if(array[j] > array[j + 1]) {
                let tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}

For every element in the array it runs through the whole array and swaps if needed. As before, everything in the loop is constant. Then we have a loop doing this n times. But we additionally have a second loop that executes the first loop n times. So we execute n steps n times. In Big-O notation: O(n*n) = O(n²)

But there are also other cases where the answer is not so straight forward. Take this code snippet for example:

function mapAndFilter(x) {
    return x
        .map(n => n * 2)
        .filter(n => n > 0);
}

What is the complexity of this function? Is it

O(1)?
O(n)?
O(n²)?
Something different?

The correct answer is O(n). Why? While our code in itself is constant (no direct loops), executing other functions will also take some time. In the map case, the browser will run trough all elements and call the function on them (so this would be O(n)), filter is basicly the same as our findInArray, so also O(n). Together our function would have O(n+n) = O(2n), but Big-O notation does not care about constant factors, so the 2 gets erased resulting in O(n).

I think this is a good example that you always have to check not only your own code, but also code you import through a library or through the browser. Every algorithm that operates on a datastructure has a computational complexity. If you know it, you can write your code to have the smallest complexity possible. You can also ask yourself: "What operations do I need to do on my data structure and is there another data structure that has less complexity for those?".

This is the first article in a series about common data structures and how they work internally. Follow me if you are interested in those kinds of articles and also write which data structures you are interested in.

Why I always recommend Arch Linux

Jan van Brügge — Mon, 18 Sep 2017 13:22:10 +0000

Normally, the go to distro for newcomers is Ubuntu. It comes with a nice installer and an interface of brand "good enough". But I always recommend Antergos Linux for newcomers, because it is an Arch Linux based distro. Why?

Software

In Ubuntu the software is usually around one whole year behind the current version. Because the maintainers want the software to be tested and not buggy as new versions are often. In my experience however, the exact opposite is the case: I just had another "incident". Currently I have to use ubuntu, because it is not my PC. I was using Keepass and tried to synchronize the password database via my WebDAV server.

It was not working. Why? Because the version of Mono that was installed by Ubuntu (the "newest" version) was one complete major version behind the current stable version and this old version was not able to handle letsencrypt certificates. The solution after 1 day of searching: Adding the official mono ppa as repository and use the version from there.

With Arch (and Arch based distros) you always get the newest version in the main software repositories. I never encountered this issue on my Arch machine, simply because installing keepass also pulled the newest version of mono.

Software not in the official repositories

On Ubuntu, if your software is not in the official repositories, you are out of luck most of the time. If you are lucky, the software maintainer is hosting a ppa from where you can install it. If not, you have to download a .deb and update it manually.

Arch Linux on the other hand has the AUR - the Arch User Repository. Every user can upload a package build script to package any software available. This has the consequence, that if a software is available for linux, you can find it in the AUR. This also means you get normal package updates for those user packages.

Package manager

Ubuntu's package manager is very verbose, so you have to type a lot in order to do common tasks. To update all installed packages:

sudo apt update && sudo apt upgrade

compare that to pacman, the Arch Linux package manager:

sudo pacman -Syu

If you want access to the AUR through the package manager, the most common way is to install yaourt a wrapper around pacman. With this you can search easily the database of packages:

yaourt vlc

TL;DR

If you are a Linux beginner, install Antergos Linux. Once you are comfortable with the command line, switch to bare Arch Linux.

Understanding Observables

Jan van Brügge — Fri, 01 Sep 2017 10:45:49 +0000

Reactive programming has gained a lot of traction lately. Libraries like RxJS and Most.js and frameworks like Cycle.js make it easy to compose complex async behavior. But understanding how those observables or streams (I will use both terms interchangeable from now on) work is often difficult to explain. In my experience, if you can build something yourself, you understood it. That's why we will build a toy RxJS in this article!

What are we trying to achieve

As many people are not familar with streams, here is short summary: Streams are arrays over time. What I mean by this:

const myArray = [1, 2, 3, 4];

const myValue = myArray
    .map(i => i * 2)
    .reduce((acc, curr) => acc + curr, 0);
console.log(myValue);

In this code snippet we are taking an array and sum up all the elements in there. But what if we get the values from an external source, like from an API? Then we could use promises:

const myValuePromise = getData() //uses a promise based API
    .then(data => data
        .map(i => i*2)
        .reduce((acc, curr) => acc + curr, 0)
    )
    .then(console.log);

This also works very well. But what if we get the data from a websocket? A websocket is not a single value in the future like a Promise, but many values! This is where streams become helpful:

let websocket = new Websocket(/* ... */);
const websocketStream = Observable.create(observer => {
    websocket.onMessage = (msg) => observer.onNext(msg);
    websocket.onClose = () => observer.complete();

    return () => websocket.close();
});

const myValueStream = websocketStream
    .map(i => i * 2)
    .scan((acc, curr) => acc + curr, 0)
    .subscribe(console.log);

Now, every time a new value arrives via the websocket, scan will emit the new sum. If you want to wait until the websocket closes and then just print the final sum, you can use reduce.

Building a toy RxJS

Now that we know how to use streams, it's time to start building a stream library. Let's first ask us, what whe want when to happen. We want to have some observer that can subscribe to an observable. The observer will then receive the values from upstream. So, to start simple we will first define our observable. I will use typescript here, as it helps to understand what's going on.

interface Observer<T> {
    next(t: T): void;
    complete(): void;
}

As you can see, an observer is an object with a next and a complete function. Now we need the observable. For this we will start bottom up, this means for now, our observable just needs a subscribe method.

interface Observable<T> {
    subscribe(observer: Observer<T>): void;
}

So to use that naively, we would just create an object with a single method. Let's replicate our websocket example:

let websocket = new Websocket(/* ... */);
const websocketStream = {
    subscribe(observer) {
        websocket.onMessage = msg => observer.next(msg);
        websocket.onClose = () => observer.complete();
    }
}

Okay, that looks almost as the real RxJS example. The only difference is the missing cleanup, but for simplicity sake, I won't cover that. Next, we have to define a map function that takes a function and an observable and returns a new one:

function map<T, U>(fn: (t: T) => U): (s: Observable<T>) => Observable<U> {
    return stream => ({
        subscribe(observer: Observer<U>) {
            stream.subscribe({
                next: (value: T) => observer.next(fn(value)),
                complete: observer.complete
            });
        }
    });
}

We are basicly just creating a factory function that subscribes to the previous observable with an internal observer that applies the function and returns the values to the next observer. Again Typescript helps for understanding what's going on.

Now we can do this (extending the previous example):

const myValueStream = map(i => i * 2)(websocketStream);

While this works, it's not the most beautiful API. We are used to calling functions on the observable. Luckily, this can be fixed quite easily:

class Stream<T> implements Observable<T> {
    constructor(public subscribe: (o: Observer<T>) => void) {}

    public compose<U>(operator: (s: Stream<T>) => Stream<U>): Stream<U> {
        return operator(this);
    }

    public map<U>(fn: (t: T) => U): Stream<U> {
        return this.compose(map(fn));
    }
}

Now we have an ES6 class that gets a subscribe method as constructor argument and has map on it's prototype. This means our example looks like this:

let websocket = new Websocket(/* ... */);
-const websocketStream = {
-    subscribe(observer) {
+const websocketStream = new Stream(observer => {
        websocket.onMessage = msg => observer.next(msg);
        websocket.onClose = () => observer.complete();
    }
}

const myValueStream = websocketStream
    .map(i => i * 2);

Now to implement scan is rather easy, so we will instead implement reduce which waits until the last value has arrived an then emits the result once:

function fold<T, U>(fn: (acc: U, curr: T) => U, seed: U): (s: Stream<T>) => Stream<U> {
    return stream => new Stream(observer => {
        let accumulator = seed;
        stream.subscribe({
            next: value => {
                accumulator = fn(accumulator, value);
            },
            complete: () => {
                observer.next(accumulator);
                observer.complete();
            }
        });
    });
}

It can be seen that we have an internal state that gets updated on every event from the previous stream. Once the previous stream completes, we emit the value and complete too. We could implement scan the same way except that we would emit every time there is a new value and not on completion.

With that we can now replicate our websocket example (assume we have added scan to the Stream class just like map):

let websocket = new Websocket(/* ... */);
const websocketStream = new Stream(observer => {
    websocket.onMessage = (msg) => observer.onNext(msg);
    websocket.onClose = () => observer.complete();
});

const myValueStream = websocketStream
    .map(i => i * 2)
    .scan((acc, curr) => acc + curr, 0)
    .subscribe({
        next: console.log,
        complete: () => {}
    });

Let's take it even a step further. We want an initial HTTP request and future updates via websocket. Without streams this is difficult to do. For this we first need something to convert a Promise into a stream:

function fromPromise<T>(p: Promise<T>): Stream<T> {
    return new Stream<T>(observer => {
        p.then(data => observer.next(data));
    });
}

Then, we need a way to convert an stream of arrays to a stream of individual items (assuming our API returns an array of data and the websocket just singular items). We can split this into one function that converts an array into a stream and a second function that "flattens" a stream:

function fromArray<T>(array: T[]): Stream<T> {
    return new Stream(observer => {
        array.forEach(e => {
            observer.next(e);
        });
        observer.complete();
    });
}

function flatMap<T, U>(fn: (t: T) => Stream<U>): (s: Stream<T>) => Stream<U> {
    return stream => new Stream<U>(observer => {
        stream.subscribe({
            next(s: Stream<U>) {
                s.subscribe({
                    next: observer.next,
                    complete: () => {}
                });
            },
            complete: () => observer.complete()
        });
    });
}

As you can see in fromArray we just take every element and push it into the stream. flatMap is a lot more interesting here. We first subscribe to the outer stream and on every new inner stream that we receive, we subscribe to that too and output all values to the next observer.

Let's use our new methods (assume we have added flatMap to the Stream class):

let websocket = new Websocket(/* ... */);
const websocketStream = new Stream(observer => {
    websocket.onMessage = (msg) => observer.onNext(msg);
    websocket.onClose = () => observer.complete();
});

let httpStream = fromPromise(getData())
    .flatMap(data => fromArray(data));

const myValueStream = websocketStream
    .map(i => i * 2)
    .scan((acc, curr) => acc + curr, 0)
    .subscribe({
        next: console.log,
        complete: () => {}
    });

The last bit missing is something to merge those two streams:

function merge<T>(...streams: Stream<T>[]): Stream<T> {
    return new Stream(observer => {
        let numCompleted = 0;
        streams.forEach(s => {
            s.subscribe({
                next: value => observer.next(value),
                complete: () => {
                    numCompleted++;
                    if(numCompleted === streams.length) {
                        observer.complete();
                    }
                }
            });
        });
    });
}

As you can see, we are simply subscribing to all streams and emit a value when any one of them emits. We complete the stream if all streams complete. With this we can finally finish our example:

let websocket = new Websocket(/* ... */);
const websocketStream = new Stream(observer => {
    websocket.onMessage = (msg) => observer.onNext(msg);
    websocket.onClose = () => observer.complete();
});

let httpStream = fromPromise(getData())
    .flatMap(data => fromArray(data));

const myValueStream = merge(httpStream, websocketStream)
    .map(i => i * 2)
    .scan((acc, curr) => acc + curr, 0)
    .subscribe({
        next: console.log,
        complete: () => {}
    });

Wrapping it up

Observables can be extremely useful if you have complex async behavior. They are not that hard to write yourself too! The toy RxJS I showed here is not how the mayor stream libraries are implemented because the closures are expensive in performance in Javascript. But the core ideas stay the same.

I hope you liked the article and learned something new. If you are interested in reactive programming, take a look at Cycle.js, a fully reactive framework where I am part of the core team.