I’m going to try and complete the Advent of Code puzzles this year, in Haskell, without bouncing off of those stupid interpreter problems that have always driven me away in the past. Encouraged by a fellow poster on lobste.rs, I’m going to try and blog my attempt here.

I don’t have a lot of extra time, but I would like to be better at blogging, and also at Haskell, so let’s hope that this works out. I’m hoping to build the habits here over the next couple of weeks that will enable me to solve the puzzles in a timely fashion, and write up a description of my solution. I’ve done a bit of Haskell, largely in this Advent of Code context, so I’m not entirely a beginner, but I’m nothing like a “Haskell programmer” yet.

GETTING STARTED

I use a Macintosh, so I’ll install stack via homebrew –

{{< highlight shell >}} % brew install haskell-stack {{< / highlight >}}

… and I’ll create a new project: {{< highlight shell >}} % mkdir -p $HOME/Projects/AOC % cd $HOME/Projects/AOC % stack new AOC2020 % cd AOC2020 % stack build AOC2020 # a lot of stuff happens …. % stack exec AOC2020-exe someFunc {{< / highlight >}}

When the stack new AOC2020 command completed, it created a directory called AOC2020, that has a bunch of directories with stuff in them:

% ls -1 */*
app/Main.hs
src/Lib.hs
test/Spec.hs

It sure looks like the meat is here in app/Main.hs:

module Main where

import Lib

main :: IO ()
main = someFunc

This seems to indicate that there’s a Lib module we can import someFunc from, and in fact, if we look at src/Lib.hs, there we go: {{< highlight haskell >}} module Lib ( someFunc ) where

someFunc :: IO () someFunc = putStrLn “someFunc” {{< /highlight >}}

WHAT’S THE PROBLEM?

In keeping with a fellow lobste.rs poster, I’ll start with last year’s Day 1. The description of the problem is

[fuel] required to launch a given module is based on its mass. Specifically, to find the fuel required for a module, take its mass, divide by three, round down, and subtract 2.

That seems like a pretty clear formula, so let’s write it in Haskell baby-talk, as a function from mass to fuel. Haskell has this equational style where you basically write the equation of the calculation you want in a very straightforward fashion (none of the ceremony of, say, Java’s public static void main () {} foofaraw), so the basic definition is the legal one:

fuel :: Int -> Int
fuel mass = div mass 3 - 2

That looks pretty simple! div is integer division, and operator precedence means there are no brackets needed. The line with the :: in it defines the type of the function – in this case, from Int to Int. Let’s write a quick test function that uses the examples given:

For a mass of 12, divide by 3 and round down to get 4, then subtract 2 to get 2.

For a mass of 14, dividing by 3 and rounding down still yields 4, so the fuel required is also 2.

For a mass of 1969, the fuel required is 654.

For a mass of 100756, the fuel required is 33583.

… to see if we got the logic right:

test :: Bool
test = fuel 12 == 2 && fuel 14 == 2 && fuel 1969 == 654 && fuel 100756 == 33583

OK, but where to put all this code?

A DIGRESSION

I’m going to be writing all my code in Emacs – I use the doom distribution (because life is too short to maintain my own pile of elisp), and to doom’s init.el I added (haskell +dante). Now, I can start an “inferior-mode” interpreter and send my code over to it with C-c C-l.

BACK TO THE HASKELL

I’ve decided to start out with one module per day – obviously, this may not be the ideal way to organize everything, but eh, we’ll burn that bridge when we get there. So, let’s create a lib/Day00.hs module, and put our definitions in there:

-- |

module Day00 where

test :: Bool
test =
  fuel 12 == 2 &&
  fuel 14 == 2 &&
  fuel 1969 == 654 &&
  fuel 100756 == 33583

-- see what we did here? We re-wrote `fuel` in "point-free" style! More on this, later
fuel :: Int -> Int
fuel = max 0 . subtract 2 . flip div 3

Emacs fills out the module Day00 bit, so all I have to do is add the definitions from above. Now, I can load this source into GHCi, with C-c C-l, and run it:

λ> fuel 12
2
λ> test
True

So far, so good! Now, let’s look at the rest of the problem definition.

What is the sum of the fuel requirements for all of the modules on your spacecraft?

Here, we encounter our first real problem: we have a file, with a bunch of numbers, one per line, and we need to sum the result of calling fuel on each of them. We’re going to have to deal with Haskell’s notorious IO system, which could mean learning all about monads and endofunctors and whatnot – or, I could crib like a maniac from Stack Overflow and figure it out later.

I vote we punt. Let’s assume that we have some mechanism of reading a file, and getting the contents of that file into one big String. Let’s solve the problem in a pure fashion with that String as input, and deal with the IO stuff afterwards. Let’s break this problem down: we have a String and we need to turn that into a list of integer values, representing masses; compute the fuel requirement for each mass; and then sum them together. This sounds a lot like three functions:

stringToStrings :: String -> [String]
stringToMass :: String -> Int
finalFuel :: [Int] -> Int

HOOGLE

Surely we cannot be the first people who want to split a String into a [String]! Or convert a String into an Int! But how to find out what functions we have available?

This is where Hoogle comes in. Hoogle is a search engine for Haskell code, and one of the things you can do with it is search by type signature. This is so amazingly cool: you can say, hey, we have a String and we need [String] – and, voila. The very first result is lines :: String -> [String] and the description of the function is:

lines breaks a string up into a list of strings at newline characters. The resulting strings do not contain newlines.

That looks pretty good to me!

How about String -> Int? Hmmm. Nothing here looks reasonable; why is that? Well, it’s because we’re not operating at the right level of generality here. I don’t fully understand how this all is going to work, but I did some Stack Overflowing, and I figured something out. There isn’t a specific String -> Int function; there is instead a function called read that can be used here, with a type coercion/specification (I don’t know the exact lingo here). This has to do with something called “type classes”, which I’m sure I’ll learn more about as we go. The invocation looks like:

stringToMass :: String -> Int
stringToMass s = read s :: Int

We can now start to stitch our functions together:

computeAnswer :: String -> Int
computeAnswer = sum . map (fuel . stringToMass) . lines

Point-free style rears its head again, I see.

REVISITING IO

So we have a function that takes a String representing a list of masses, one per (Unix) line, and computes the total fuel necessary for that mass. But that’s not going to be enough! We also need a way to read this data in from a file, and then apply our computeAnswer to it.

The first thing I’ll do is download the data to use into a location in the AOC2020 project that makes sense: {{< highlight shell >}} % mkdir -p $HOME/Projects/AOC/AOC2020/data # copy the data from the web page … % pbpaste > $HOME/Projects/AOC/AOC2020/data/Day00.txt % head $HOME/Projects/AOC/AOC2020/data/Day00.txt 103450 … {{< / highlight >}}

Let’s try this:

{{< highlight haskell >}} part01 = do raw <- readFile “data/Day00.txt” putStrLn raw {{< /highlight >}}

This now reads the contents of data/Day00.txt and outputs it. Not remotely interesting, but now at least we have read some data from disk and have done something with it.

When I open Day00.hs in my Emacs, it complains about missing top-level type annotations for fuel, test, and part01. You may have seen these type annotations in Haskell source:

isPositive :: Int -> Bool

We read this as “isPositive is a function from an Int to a Bool”. We don’t have the definition, but we already know a lot about isPositive.

What are the type signatures for our functions defined above? Well, I can ask Haskell, by navigating to an expression and using C-c C-t to instruct Emacs to ask Haskell for me, or by using the :t operator in GHCi:

λ> :t part01
part01 :: IO ()

So IO () is apparently the type of the “IO Monad”. I don’t particularly care which metaphor we use to describe it; I think of this as a mechanism for the type system to keep impure code formally distinct from pure code, allowing the compiler to do more work for us; and that’s as much about it as I need right now. If I go deeper, I can see that readFile is of type FilePath -> IO String, meaning that that top-level IO is now also part of the type of the data returned from readFile. But how do we operate on an IO String? This is where the do comes in, I think? We are operating in an sort of “IO context”, so in that context, I can treat an IO String as a String? Is that right? It’s right enough for me, for now.

The basic String type in Haskell apparently is just an alias for a list of Char; in other words, [Char]. So anywhere we see String, we can think [Char], and vice versa. Looking at this again, we can see that readFile returns an IO String, which because of my handwaving above, we can think of as a String in an IO context, or, an IO [Char]. I think?

Let’s see what the compiler tells us!

part01 :: IO ()
part01 = do
   raw <- readFile "data/Day00.txt"
   print (computeAnswer raw)

It runs! It terminates! And it’s the right answer! How about that?

Tomorrow: part 2 of Day 1.