Tyblog

I recently (finally!) finished the Advent of Code challenges using Haskell. I’m still a Haskell wannabe, but the suite of problems provided an interesting backdrop for a number of Haskell concepts that I wanted to share.

The long-form retrospective is here; if you want to see a condensed collection of a few Haskell toolchain by-products, check out my shorter summary under GitHub pages.

Disclaimer: I am not a Haskell expert (or even what I would label experienced), so the approaches and results here are likely non-optimal and may be flawed. I’m happy to revise and amend my analysis with additional information via comments/email/PRs/etc.

Introduction

Advent of Code is a set of coding challenges that started in December 2015. Although I initially knocked out a couple using Ruby, I found that as the challenges became more difficult they were sufficiently complex enough to provide a good reason to get more familiar with new or foreign concepts.

I haven’t done much heavy lifting with functional, pure, or lazy languages, so this was a good chance to learn more.

Code

There’s lots of examples for general challenges strategies on the Advent of Code subreddit, so here’s the highlights from the Haskell side (I’m sure some of these are shared with $language, but the Haskell take on each concept is still interesting).

Type Safety

If you’ve tinkered with Haskell before, you’ll know that the type system is one of the highlights of the language.

A good example of the helpfulness of the type system is signalling (to a human) when a challenge may not guarantee a solution.

For example, the first day’s challenge is pretty simple: given a string with open and closed parenthesis, pretend each represents moving up and down a floor on an apartment building. It’s easy to find the final floor by just mapping characters to +1 or -1 and summing the result (in Haskell parlance, a map and fold). Part 2, however, asks you to find the string position that moves you below the ground floor (i.e., the first position that moves you to -1 or below).

Clearly, you could sum a sequence of numbers that never goes negative, so the answer to that question could very well be “we never reach the basement”. You could express this limitation for the function different in different languages - maybe raise an UnreachableBasement exception somewhere (with the caveats inherent to exceptions), or return -1 (which, also being an integer, isn’t semantically helpful). The Haskell method of expressing this situation is pretty nice – the type signature is below, and you can also see the implementation on GitHub:

basement :: String -> Maybe Int

The function caller is explicitly informed that given a string of parenthesis like (())(, there’s a possibility the function may return Nothing and thus signal that it couldn’t find an index in the string that meets the requirements. However, unlike, say, an exception in Ruby, the caller must explicitly handle the case in which Nothing is returned.

In other words: Haskell won’t let you compile the solution until there’s some code path that accounts for the Nothing result. A simple example, but this sort of rigor makes complicated logic more resilient down the road.

(Good!) Infinite Loops

An interesting mechanism that you can leverage in Haskell is infinite lists: due to laziness, you can define lists infinitely and the language will only use as much of the list as necessary.

Consider day 11: you’re given a rule for how to rotate a password to a new value, and rules that govern whether a password is acceptable. Given an initial password, you must iterate on the value until it meets all the requirements for a strong password (the challenge comes complete with arbitrary and arcane password strength rules, just like real life!).

One unique approach you can take in Haskell is to write the rule to rotate a password and then repeatedly apply this function to itself to form an infinite list of potential passwords, then just filter that list for password values that meet the formatting requirements, and take the next value in the list. Haskell won’t compute the entire list; just keep generating passwords until you take the last one you need and move on.

In my solution, I’ve got a function to iterate on a password called increment:

increment :: String -> String

There’s a Haskell function called iterate that applies a function to a value an infinite number of times – coupled with some other basic Haskell functions, we can come up with a nice solution:

head . filter meetsReqs . iterate increment

When you hand this a String, it 1) applies the increment function infinitely to the string, filters the resulting list with a predicate that defines the criteria for a valid password, and head just takes the first value.

Modeling a Game (Without Objects)

For day 22’s challenge, you’re given the rules for a game and challenged to find the optimal set of moves to win the game. This is similar to the preceding day’s challenge, but more complicated: it involves spells that have a cost, effect, and potential duration.

The solution for this in Haskell is pretty interesting. Though I model things like game state and players with types, the highlight here are lenses. How lenses work is outside the scope of this blog post, but in short: they let you reach into data types to access or modify them easily.

As an example, take a look at this function – it takes a spell, some game state, and returns an updated game state after the spell is “cast”:

cast :: Spell -> Game -> Game
cast spell = action
           . (player.mana -~ cost)
           . (player.spent +~ cost)
    where
        (action, cost) = case spell of
            MagicMissile -> (boss.hp -~ 4, 53)
            Drain        -> ((boss.hp -~ 2) . (player.life +~ 2), 73)
            Shield       -> (e Shield 6, 113)
            Poison       -> (e Poison 6, 173)
            Recharge     -> (e Recharge 5, 229)
        e s t = effects %~ insert s t

What makes this function so interesting is that nowhere in the body of the function do I ever actually reference the variable that the game is bound to. The juicy part of the function:

action . (player.mana -~ cost) . (player.spent +~ cost)

Is just a series of smaller function compositions. When I hit a Game with player.mana -~ cost, that little function reaches into my Game type, subtracts the spell’s cost from the player’s mana and proceeds to compose with the following function.

This is one of the more complicated examples, but if you worked through this (pretty tricky) challenge, the solution (complete with all sorts of weird recursion) is interesting to compare against typical imperative solutions.

Ecosystem

Aside from interesting core language features, modern Haskell has some really neat components of the toolchain that I also experimented with as a part of the advent. These are repeated in short form on a GitHub pages site, but I’ll go more in depth here.

HPC

Haskell can generate lovely coverage reports, walking your code to help pinpoint places in which code is actually never evaluated and other useful highlights. In my case, you can see several instances in which some typeclasses I’ve derived (like Show) never end up being used within my modules and is thus detected as unnecessary (as far as HPC can tell).

Benchmarking

I found criterion later on in my journey so most of my code isn’t benchmarked, but it has proven to be a really pleasant tool to use.

Using criterion, I was able to compare different implementations for some solutions and found (sometimes unexpected) results regarding efficiency. This is especially relevant in a lazy language like Haskell wherein performance can be tricky to pin down sometimes when some of your code may not necessarily be evaluated.

Docs

This is a fairly standard language feature, but in case you were wondering: my documented code ended up looking like this after passing through haddock.

Special Mention for The Crown Jewel: Stack

Throughout a lot of building, benchmarking, and testing, I became pretty enamored with stack, the (hopefully standard) Haskell build tool. My favorite standard feature of stack is the fact that you define your resolver per project, which encapsulates a given version of GHC (the Haskell compiler) along with a curated set of packages for that point in time. If you’ve done non-trivial work in Ruby or Python, you know that an rvm/virtualenv type of solution is pretty useful, and stack makes that concept a first-class citizen.

Stack is also a very active project, which is refreshing to see. While some languages languish when it comes to taking a critical eye to tools or developer needs, the haskell community has effectively and rapidly fixed a pain point in their toolchain in a great way.

A Final Note

Advent of Code turned out to be a great exercise to learn more about a language and compare notes with the community. If you have the time, I highly recommend trying it out and seeing what you can learn.