This year I’ve decided to try my hand at the Advent of Code! I’ve decided to use it as an opportunity to learn Haskell and share notes on what I’ve learnt while doing it so it sticks better.

I might not make it through the whole Advent but as long as I’ll learn something new, it will already be a huge success for me! : )

Day 1: The Tyranny of the Rocket Equation

The first puzzle was quite simple to solve, even though not being that familiar with Haskell environment it took me some time to figure out how to set up the most basic working Stack project. From the initial skeleton src/ and test/ directories are not needed (unless you’re planning to write unit tests which will be useful for more tricky puzzles). All comments and most properties can be removed from both package.yaml and stack.yaml files for clarity.

When it comes to Haskell itself, I’ve already learnt a lot:

  • the difference between float ((/)) and integer (div, quot) division
  • how to read command line arguments in program (System.Environment.getArgs FTW)
  • reduce and fold mean exactly the same
  • the difference between:
    • foldr: combine the first element of the list with the result of applying the function to the rest of the list, so in some funky hybrid of C/Haskell notation: f a[0] (f a[1] (f a[2] (f a[3] k)))
    • foldl: combine the result of applying the function to the whole list except from the last element with that last element, so using the same notation: f (f (f (f k a[0]) a[1]) a[2]) a[3]

    where f is the function to be “folded” and k is an initial value. The order of foldl and foldr arguments is different!

My code solving day 1 puzzle is available here.

Day 2: 1202 Program Alarm

Even though my understanding of functional programming is still quite shallow, because of pattern matching this day’s puzzle sounded like a problem that Haskell shines in solving. I got a much better grasp of the concept. Yes, there’s a difference between a tuple of elements and a list of elements!

I’m still struggling with the application of ($) function, but hopefully when I try applying it more and more it will finally click. For example I had problems understanding the difference between (notice no ($) in f'):

f :: [Int] -> Int -> [Int]
f xs i = drop i . take (i + 4) $ xs -- sublist of elements from i to i + 4

AND

f' :: [Int] -> Int -> [Int]
f' xs i = drop i . take (i + 4) xs -- sublist of elements from i to i + 4

f' will not even compile because of a type mismatch.

Finally, I had a first encounter with the most basic Haskell debugging tool: Debug.Trace.trace!

It always reminds me of this graphic (for non-Polish speakers, DUPA stands for Data User Password Authentication):

printf DUPA driven development

I’ve also run into the monomorphism restriction, which turns out to be a counter-intuitive rule in Haskell type inference. I encountered it while debugging - it dissappeared as quickly as it showed up. I’ll have to bump into it at least a few more times to understand it better.

For the second part I’ve mainly struggled with changing my way of thinking about the program - I wanted to refrain from using the equivalent of for loop. I’ve used recursion instead, which feels like a more Haskellish way to do things.

My code solving day 2 puzzle is available here.

Day 3: Crossed Wires

Even though I cracked the problem on a piece of paper quite quickly, expressing my thoughts in Haskell was way much more problematic. This one was quite tricky, mainly because of nested lists that I was trying to map functions to. Turns out:

  • map doesn’t solve all problems! If you end up trying to map a map to a nested list it’s better to use recursion and pattern matching instead
  • the order of statements in where clause doesn’t matter (knowing that now, I prefer ordering the logic from top to bottom)
  • type synonym is incredibly useful when it comes to readability of code (but nothing more)
  • once again, the trace tool helped me to find the obvious bug in my code (absolute value in Manhattan distance)
  • I’ve used Set typeclass (from containers package) for the first time
  • Data.List.findIndex returned Maybe type, which really baffled me in the beginning! Fortunately Data.Maybe.fromJust came to the rescue

Additionally (even though I didn’t use it in the end) I’ve learnt quite a nice trick - applying a list of functions to a list of elements. Say you wanted to take first i elements from the ith list. zipWith with ($) that we apply to to pairs is very clean and quite easy to comprehend (see also here):

Prelude> let lists = [[1, 2, 3, 4, 5], [11, 22, 33, 44, 55], [12, 34, 56, 78, 90]]
Prelude> let getters = map take [1..3]
Prelude> zipWith ($) getters lists
-- produces:
-- [[1],[11,22],[12,34,56]]

My code solving day 3 puzzle is available here.

Day 4: Secure Container

This is the puzzle after which I’ve had the least number of tabs left open so far. It was mainly about using the filter function properly. I was trying to use a list of predicate functions to filter with but struggled with using sequence function so decided to just spend my time reading up about monads instead. I’ll get my head around it soon!

My code solving day 4 puzzle is available here.

Day 5: Sunny with a Chance of Asteroids

Oh boy, this one took me a while! Since the task involves interacting with the outer world, (as it turned out) the whole program had to be written around IO actions for this purpose. I’ve struggled to get my head around it for a few days as I was initially trying to mix IO action with a function returning regular values depending on the pattern matched (which, as now I think about it, doesn’t make sense). So after having the whole logic written without IO actions, I started getting errors similar to:

Couldn't match expected type ‘[Char]’
                  with actual type ‘IO String’

or

Couldn't match type ‘IO String’ with ‘[Char]’
      Expected type: [String]
        Actual type: [IO String]

all over the place.

The solution was to make functions return IO action and rewrite them using do notation, which is easier if you’re using let construct (I preferred where so far). This website reminds us that do notation should be used wisely and is not always the best fit.

Additionally, that was the first time I’ve defined my own algebraic data types. Record syntax is very useful in scenarios in which there’s more than 2-3 parameters or they’re nested.

My code solving day 5 puzzle is available here.

Day 6: Universal Orbit Map

That’s the most that I’ve dealt with Maybe and Data.Map types so far. The task first sounded like a classic tree-like data structure, but I wanted to benefit from a fast lookup time. In C-like language I’d implement it as a regular tree with a dictionary where keys would be planet identifiers and values would be pointers to tree nodes. I don’t think this way of thinking about data is Haskell-native, so I didn’t implement it this way, but “faked” that kind of structure with a Map holding node’s:

  • list of children
  • parent (as a planet might not be orbiting around anything)
  • depth

Hence, used algebraic data type was defined as follows:

type PlanetOrbitNumbers = Map.Map Planet  -- key (planet identifier)
    (
      [Planet]      -- planets orbiting the key (children)
    , Maybe Planet  -- planet that the key is orbiting (parent)
    , Int           -- level of the orbit
    )

The abuse of Map matched the title of this day’s puzzle, it should have been obvious! : P

My code solving day 6 puzzle is available here.