2021-12-01 22:10:27

Advent of Code 2021: Day 1

Hi all! I'm participating in Advent of Code this year, and I'll be using Haskell to solve the problems. I thought it could be fun to write a little blog post about each of the entries, or at least the ones I have time for. I don't think I'll get day 25, since the problems get very complicated towards the end, but it should be a fun experience anyways.

I think it could also be fun if I could use each of the days to talk about some of the reasons I love Haskell so much. I'll try to make it as understandable as possible for people who haven't used Haskell before!

You can see the code for day 1 here. I will only be posting the relevant snippets.

Part 1

So, as usual, the problem in day 1 is very simple: reading a list of numbers, and comparing each element with the previous one. Already here, though, there are a few places where Haskell shines! I wanna highlight the main function that does the work, which only takes up one line:

process :: [Int] -> Int
process xs = count $ zipWith (>) (tail xs) xs

I think this looks pretty elegant. That's one of the advantages of Haskell: it lets you express a lot with very few words. One of the ways it does this is with "higher order functions", that is, functions that take other functions as arguments.

zipWith is a good example of that. What we're doing is taking our original list and its "tail" (that is, all elements except for the first, also called the "head") and zipping them with the function (>), that is, the comparison operator. What zipping does is apply the given function to each pair of elements, taking one from each list. So, first we apply the (>) function to the first two elements, then the second two, then the third two, and so on. Since the two lists are the same but offset by one, this will give us a list of booleans representing whether each element is greater than the last. Then we simply pass that list to count, which will tell us how many of those booleans are true, and that's our result.

All of that is expressed very clearly in a single line. I usually don't like code one-liners because they tend to be very obscure and esoteric, but in Haskell you can see what we're doing very plainly!

Part 2

The code for the second part is similar, but instead of comparing the numbers on each list, we need to compare the sums of each window of three elements. For this, we simply add another function:

process :: [Int] -> Int
process xs = count $ zipWith (>) (windows $ tail xs) (windows xs)

We need to define a windows function, and we do it like this:

windows :: [Int] -> [Int]
windows xs = zipWith3 add xs (tail xs) (tail $ tail xs)
    add x1 x2 x3 = x1 + x2 + x3

This time, we use the zipWith3 function, which acts on three lists element-wise with a ternary function, instead of two with a binary function. We pass it the add function, which we declare below, and three copies of the list with their offsets. It's as simple as that.

In summary, I think higher order functions are a very natural way of thinking about code without having to use loops, which are very finnicky and easy to get wrong. Most functional languages will give you a few basic higher order functions like map and filter, but Haskell's standard library is full of very useful tools for any need you might have.

Posted by Emi Socks | Permanent link