Monday, December 07, 2015

A whirlwind tour of Haskell, via Advent of code solutions

Advent of Code is a website listing 50 small programming challenges, revealing two per day from December 1st to December 25th. I'm currently going through the puzzles which have been revealed so far using my favorite programming language, Haskell. As the puzzles become slightly harder, I'm reaching for more and more sophisticated Haskell libraries, and this made me realize that the solutions to those puzzles would be a great way to showcase those libraries, and also to introduce a few basic Haskell idioms and workflows.

The intended audience is Haskell beginners, who might enjoy such a whirlwind tour of many different Haskell libraries. There is too much code for me to explain every single line, but that's fine: the idea is not to teach how to use all of those libraries, but to give a taste of the way in which we do things in Haskell.

Day 0: doctest and ghcid

Each puzzle comes with a few example inputs and outputs, as well as one larger input file for which we need to find the output. So after I write an algorithm, I'd like to run it on each of the example inputs in order to make sure that my algorithm's output matches the example outputs. If so, I then run my algorithm on the input file, and I submit the result. I automate most of those steps using the following setup.

import Test.DocTest

-- |
-- >>> day0 "advent"
-- 6
-- >>> day0 "of"
-- 2
-- >>> day0 "code"
-- 4
day0 :: String -> Int
day0 = length

main :: IO ()
main = do
    doctest ["src/Main.hs"]
    [input] <- lines <$> readFile "input.txt"
    print $ day0 input

This is not a puzzle from the Advent of Code website, instead it's a dummy example in which the algorithm simply computes the length of the input string. I write the example inputs and outputs in doctest format, and I run those tests on every execution. If the tests pass (doctest exits with an error message if one of the tests fails), I then run my algorithm on the input file and print the result. In this example and most of the Advent of Code puzzles I've seen so far, the test file consists of a single line of input, which is why I'm pattern-matching on a list of length one.

To further automate the process, I use ghcid to automatically run the above each time I save. Using ghcid requires a bit of setup, but no more than what you would need to compile a program normally using cabal. You need to create a .cabal file using cabal init, then modify the build-depends section of the generated file to include the comma-separated names of the libraries required by your program (so far, only the standard base library and doctest), and then run cabal install in order to install those dependencies (preferably inside a sandbox, by running cabal sandbox init first). In the sections below, I'll introduce new libraries, and you'll have to add each of them to build-depends, to run cabal install again, and to restart ghcid.

Once this setup is taken care of, I simply run ghcid --test=main, in a separate window which will be updated with compilation errors or with my program's output each time I save. Convenient!

Days 1 onwards

This post originally contained implementations for days 1 through 3, and was very long. I have now moved each day's implementation to its own post, which also makes it easier to share links to a particular day.

Here are all the posts in the series so far.

  • Day 1: monads, monad transformers, pattern-matching,
    composition, laziness, and higher-order functions
  • Day 2: type inference and type classes
  • Day 3: 2D vectors, sets, infinite lists, lenses, and constraints
  • Day 4: external programs and streaming
  • Day 5: list comprehensions and non-determinism
  • Day 6: precise types, arrays, and in-place updates
  • Day 7: laziness-based caching and meta-programming
  • Day 8: invertible parsers
  • Day 9: skipped
  • Day 10: skipped
  • Day 11: skipped
  • Day 12: skipped
  • Day 13: skipped
  • Day 14: skipped

I plan to continue this series as I go through the puzzles. I might skip a few if they don't involve interesting Haskell features or libraries I haven't covered yet, but otherwise, stay tuned for more!


Andrew Condon said...

This is a super article, i really like the contrasting X vs X.5 solutions, i can totally use those in explaining Haskell's advantages to people coming from an imperative programming background.

One comment - i think your 3.5 solution is missing a "Set.toList" before you take the length? or else use Set.size?

gelisam said...


In ghc 7.10, length has been generalized to work on any Foldable, so I don't need to convert to a list before calling it. It was a big change called "FTP" or "Burning Bridges" proposal, and it caused a lot of fuss when it got in because not everybody agreed it was a good idea. I think it is!

Andrew Condon said...

oh, of course, i just banged it into Haskell for Mac to play with and forgot that it's still on GHC 7.8 (i'm a big fan of the FTP change too). cheers, A