Learning Haskell via AoC 2021

This page contains remarks on Haskell that I encountered when working with source files that span multiple AoC 2021 problems.

and have Haskell solutions. It’ll be nice to compare how they solved the problems. I don’t want to end up perfecting the wrong approach!

Setting Up Haskell Env for AoC

To manage dependencies, Cabal and Stack are pretty popular. Stack incorporates the Cabal build system.

The package structure is of the form:

2021
├── advent-of-code-y2021.cabal
├── app
│   └── Main.hs
├── src
│   ├── AoC2021.hs
│   ├── SonarSweep.hs
│   └── SonarSweep.md
└── test
    └──  AoC2021Test.hs

I ended up using Cabal only as I thought it wouldn’t have too many bells and whistles. cabal init --interactive got most of my .cabal file set up.

cabal run advent-of-code-y2021 runs my solutions to the AoC problems . cabal run advent-of-code-y2021-test runs some checks based on the sample inputs on AoC problem description .

has a more comprehensive setup, e.g. specifying which problem to run, running tests, and running benchmarks. They even published an advent-of-code-api package that abstracts away the network calls!

VS Code Setup

Haskell , Haskell Syntax Highlighting , and haskell-linter (which is a wrapper for ndmitchell/hlint ) are pretty useful.

hlint is especially useful as some of the resources linked in https://www.haskell.org/documentation/ use idioms that have since been improved.

VS Code’s Haskell Language Server is currently a bit buggy in that the symbols may not update leading to erroneous flagging of code that compiles fine. Restarting the language server every once in a while is a tad inconvenient.

Sometimes VS Code reports that it can’t find both GHC and HLint. ’s suggestion of launching VS Code via code . works.

Debugging Haskell

A lot of the errors are caught by the compiler given the strong typing.

One option is to load the .hs file into GHCi and experiment in there.

$ ghci
GHCi, version 8.10.7: https://www.haskell.org/ghc/  :? for help
Loaded package environment from /Users/dchege711/.ghc/x86_64-darwin-8.10.7/environments/default
Prelude> :load src/Dive/Dive.hs
[1 of 1] Compiling Dive.Dive        ( src/Dive/Dive.hs, interpreted )
Ok, one module loaded.
*Dive.Dive>

Haskell GHCi Debug Adapter Phoityne seems like the de-factor debugger for VS Code. I’m having issues of the form:

test/AoC2021Test.hs:5:1: error:
    Could not load module ‘Paths_advent_of_code_y2021’
    it is a hidden module in the package ‘advent-of-code-y2021-0.1.0.0’
    Use -v (or `:set -v` in ghci) to see a list of the files searched for.
  |
5 | import Paths_advent_of_code_y2021 (getDataFileName)
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

… so I need to figure out how to send arguments from the extension to GHCi. That said, GHCi comes with a debugger included so that’s promising!

Literate Programming

Literate Haskell intrigued me , but I don’t use it much because it’s not well-integrated into VS Code’s intellisense and linting extensions.

uses , which allows one to put code inside markdown code blocks. Entangled then extracts code and writes it to traditional source files, and syncs changes made in either the markdown or the source file.

uses to generate markup from source code. Haddock reminds me of Python’s Sphinx , Java’s Javadoc and JavaScript’s JSDoc .

Cabal has integrations with Haddock, and that’s useful for generating docs for the package. For some reason, cabal init doesn’t generate a Setup.hs that is needed in runhaskell Setup.hs haddock --internal. Update: cabal haddock and cabal v2-haddock are alternative ways of using haddock on a package.

However, I’d like the code inlined, and the non-code portions of the .lhs files rendered as normal text instead of being included inside a code block, like how is structured. Maybe the lhs2TeX package can get me there?

Aha, lhs2tex --markdown -o Foo.md Foo.lhs gets me a nice .md file that could use some additional processing, e.g. removing the two leading lines that only have %s, adding YAML, changing the opening back-ticks to have hs (HighlightJS guesses the language correctly though). Maybe lhs2TeX has some customization options that won’t require me to whip up a Python script? Didn’t find anything promising. This script suffices:

#!/bin/zsh

if [[ $1 == "--all" ]]
then
working_dir="$(dirname $0)"
lhs_files=($working_dir/**/*.lhs)
elif [[ $1 ]]
then
lhs_files=($1)
else
printf "Either supply a filepath to an .lhs file, or use '--all'\n"
exit 1
fi

for lhs_file in $lhs_files ; do
    output_file=${lhs_file/.lhs/.md} # Replace .lhs with .md
    # Delete the first 2 lines which only have a `%` character.
    # The 2nd expression replaces `\#` with `#`. The former is needed for .lhs
    # to compile. As an SO user said, when in doubt, add another backslash.
    lhs2tex --markdown $lhs_file | sed -e '1,2d' -e s.^\\\\\#.\#. > $output_file
    printf "Published $output_file\n"
done

VS Code lacks multi-mode, which is helpful when editing .lhs files. Emacs it is! The editor shows highlights the non-code portions as Haskell, but the language server doesn’t trip up. I’ll keep using VS Code for now, especially with the Run On Save extension for regenerating the markdown as I save.

The Standard Library

uses the RIO library to replace the standard Prelude. aims to be the de-facto standard library for Haskell development, as the base package is quite minimal, has some contentious APIs, and avoid re-inventing the wheel in the name of fewer dependencies.

Partial functions (e.g. head, tail, init, last, and (!!)) in the Prelude (the module with a bunch of standard definitions that get implicitly imported into every Haskell program) are an example of a contentious standard library API. A partial function is one that could crash for some inputs (e.g. head [] crashes because an empty list doesn’t have a first item). A total function is one that is well-defined on all possible inputs.

Lazy Evaluation

Pattern matching drives evaluation. Expressions are only evaluated when pattern-matched, and only as far as necessary for the match to proceed, and no farther. For example, given these definitions:

repeat :: a -> [a]
repeat x = x : repeat x

take :: Int -> [a] -> [a]
take n _ | n <= 0   = []
take _ []           = []
take n (x:xs)       = x : take (n-1) xs

… we expect take 3 (repeat 7) to evaluate to [7, 7, 7]. A step-by-step evaluation looks like:

  take 3 (repeat 7)
    -- Matches clause 2, which needs the 2nd arg. Expand `repeat 7` one
    -- step.
= take 3 (7 : repeat 7)
    -- Matches clause 3. (3-1) not yet evaluated as not needed for
    -- pattern-matching.
= 7 : take (3-1) (repeat 7)
    -- (3-1) <= 0 forces evaluation of (3-1).
= 7 : take 2 (repeat 7)
    -- Matches clause 2; expand 2nd arg one step.
= 7 : take 2 (7 : repeat 7)
= 7 : 7 : take (2-1) (repeat 7)
= 7 : 7 : take 1 (repeat 7)
= 7 : 7 : take 1 (7 : repeat 7)
= 7 : 7 : 7 : take (1-1) (repeat 7)
= 7 : 7 : 7 : take 0 (repeat 7)
= 7 : 7 : 7 : []

The GHC compiler uses graph reduction, where the expression being evaluated is represented as a graph, so that different parts of the expression can share pointers to the same subexpression. Haskell’s runtime works out the memoization aspect of dynamic programming on our behalf!

Parsing Input

For the first two AoC problems, my parsing technique has basically been:

solutionX :: IO ()
solutionX = do
  fileName <- getDataFileName "dayX/input.txt"
  withFile
    fileName
    ReadMone
    ( \h -> do s <- hGetContents h
               print (solveX lines (fromString s))
    )

Granted, IO is lazy, but there are improvements to the above sort of parsing.

For example, Day 1 has input of the form:

199
200

parsed it as follows:

import RIO
import qualified RIO.Text as Text

readInput :: MonadIO m => m [Int]
readInput = do
  text <- Text.lines <$> readFileUtf8 "data/day01.txt"
  return $ mapMaybe (readMaybe . Text.unpack) text

Notice how readInput parses the input and takes care of converting into expected data types [Int] and takes care of parsing uncertainty with *Maybe. In comparison, my SonarSweep.num*Increases and Dive.productOfFinalPosition* functions receive a [String] which they then parse into intended types.

Day 2 had input of the form:

forward 5
down 5
forward 8

… and I parsed it using regular expressions. used the Parsing module, which results in pretty concise code:

data Instruction = GoForward Int | GoUp Int | GoDown Int deriving (Show)

instructions :: Parser [Instruction]
instructions = sepEndBy1 (lexeme direction <*> integer) eol
  where direction = (string "forward" $> GoForward)
                <|> (string "up" $> GoUp)
                <|> (string "down" $> GoDown)

readInput :: (Monad IO m, MonadReader env m, HasLogFunc env) => m [Instruction]
readInput = readInputParsing "data/day02.txt" instructions

These parsing utilities are not in the packages on Stackage. Turns out has a custom app/Parsing.hs , that extends functionality from , which is an advanced fork of Text.Parsec , the “default” parsing library for Haskell.

My takeaway is to first get the hang of Text.Parsec, as it probably has more “official” resources, e.g. Real World Haskell > 16. Using Parsec .

Monad

Values of type IO a are descriptions of effectful computations, which, if executed would (possibly) perform some effectful I/O operations and (eventually) produce a value of type a. Values of type IO a are only ever executed by the Haskell runtime system, and they’re are passed to the runtime system via the special function main :: IO (). Given the special main function, there exists a need for ways to combine smaller IO computations, and pass them off to main. The (>>=) and (>>) operators (described below) come in handy for this.

Instances of Monad (e.g. IO monad) satisfy left identity, right identity, and associativity. The minimal complete definition is the (>>=) (bind) operator. From a Haskell programmer’s perspective, a monad is an abstract datatype of actions. Haskell’s do expressions are syntactic sugar for writing monadic expressions.

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool

The (>>=) (bind) operator sequentially composes two actions, passing any value produced by the first as an argument to the second. as >>= bs can be understood as:

do a <- as
   bs a

dissects (>>=) :: m a -> (a -> m b) -> m b in an enlightening way. (>>=) takes two arguments. The first one is a monadic value (or computation or mobit) that represents a computation which results in a value (or several values, or no values) of type a, and may have some sort of “effect”. The second argument is a function of type a -> m b, i.e. it will choose the next computation to run based on the result(s) of the first computation. Therein lies the promised power of Monad to encapsulate computations which can choose what to do next based on the results of previous computations.

The (>>) (“and then”) operator sequentially composes two actions, discarding any value produced by the first. as >> bs can be understood as:

do as
   bs

Each statement in a do block is one of these:

• A single expression e, which is then prepended to the rest with e >> ...
• A monadic bind p <- e, which is replaced by e >>= (\p -> ...)
• A let binding let p = e, which is translated to let p = e in ...

… so main and main' are equivalent:

-- Side note: `readLn` throws an exception if the input is not a number.
-- Actual code should use `getLine`, `readMaybe`, and handle input that
-- is not a number. However, we're currently concerned with monads.

main :: IO ()
main = putStrLn "Please enter a number: " >>
       readLn >> \n ->
       let m = n + 1 in
       putStrLn (show m)

main' :: IO ()
main' = do putStrLn "Please enter a number: "
           n <- readLn
           let m = n + 1
           putStrLn (show m)

A Monad m also offers a return function of type a -> m a, which injects a value into the monadic type.

There are still holes in my understanding of Monads. They relate to Functors and Applicatives, and I don’t want to go into that rabbit hole (yet). promises to help me develop an intuition for this [scary] diagram.

For now, my takeaway is: Monads encapsulate computations which can choose what to do next based on the results of previous computations.

Functor

does:

text <- Text.lines <$> readFileUtf8 "data/day01.txt"

A simple intuition is that a Functor represents a “container” of some sort, along with the ability to apply a function uniformly to every element in the container. A more useful but more difficult to explain intuition is that a Functor represents some sort of “computational context”.

A Functor instance needs to implement fmap, whose type is fmap :: (a -> b) -> f a -> f b.. <$> is an infix synonym for fmap, which allows for more readable code. Functor instances include [], Maybe, Either, and IO.

The signature f a tells us that f is a sort of type function that takes another type as a parameter, e.g. there are no values of type Maybe, but we can have Maybe Integer. More precisely, the kind of f must be * -> *. From the container PoV, fmap applies a function to each element of a container, producing a new container of the same structure. From the context PoV, fmap applies a function to a value in a context, without altering its context.

fmap’s type with extra parentheses illustrates the concept of lifting. fmap :: (a -> b) -> (f a -> f b) is more apparent that it transforms a “normal” function (g :: a -> b) into one which operates over containers/contexts fmap g :: f a -> f b.

References

1. Advent of Code 2021. Johan Hidding. jhidding.github.io . Accessed Feb 20, 2022.
2. Entangled: literate programming for the new millennium. Johan Hidding. entangled.github.io . github.com . Accessed Feb 20, 2022.
3. rio: A standard library for Haskell. hackage.haskell.org . www.fpcomplete.com . github.com . Accessed Feb 20, 2022.
4. mstksg/advent-of-code-2021: 🎅🌟❄️☃️🎄🎁. Justin Le. github.com . Accessed Feb 20, 2022.
5. Welcome to Haddock’s documentation! — Haddock 1.0 documentation. haskell-haddock.readthedocs.io . Accessed Feb 20, 2022.
6. Advent of Code 2021. Johan Hidding. jhidding.github.io . Accessed Feb 20, 2022.
7. Control.Monad.IO.Class. hackage.haskell.org . Accessed Feb 21, 2022.
8. 3: Recursion Patterns, Polymorphism, and the Prelude - School of Haskell. Brent Yorgey. www.schoolofhaskell.com . Jul 14, 2014. Accessed Feb 21, 2022.
9. 6: Laziness - School of Haskell. Brent Yorgey. www.schoolofhaskell.com . Accessed Feb 21, 2022.
10. CIS194 Fall 2016: IO and Monads. Joachim Breitner. www.cis.upenn.edu . Accessed Feb 21, 2022.
11. Control.Monad. hackage.haskell.org . Accessed Feb 21, 2022.
12. 5: Type Classes - School of Haskell. Brent Yorgey. www.schoolofhaskell.com . Accessed Feb 21, 2022.
13. Associative property - Wikipedia. en.wikipedia.org . Accessed Feb 22, 2022.
14. Identity element - Wikipedia. en.wikipedia.org . Accessed Feb 22, 2022.
15. CIS194 Spring 2013: Monads. Brent Yorgey. www.cis.upenn.edu . Apr 8, 2013. Accessed Feb 22, 2022.
16. Data.Functor. hackage.haskell.org . Accessed Feb 22, 2022.
17. Typeclassopedia - HaskellWiki. Brent Yorgey. wiki.haskell.org . Accessed Feb 22, 2022.
18. Advent of Code 2021: Day 2: Dive! jhidding.github.io . Accessed Feb 22, 2022.
19. Text.Megaparsec. Mark Karpov. hackage.haskell.org . markkarpov.com . Accessed Feb 23, 2022.
20. Haskell Extension for VS Code can't find GHC installed with nix-shell. Help! : haskell. www.reddit.com . Accessed Feb 25, 2022.