Fintan Halpenny
2 Jan 2019
•
11 min read
If you hang around fellow Haskeller/Scala head, Greg Pfeil (a.k.a sellout), enough you will hear about recursion schemes, as well as some other abstract concepts but those are not the topic of the day. No, today we will join the conversation and talk about recursion schemes as well.
I have dabbled with the concept for a long time. Due to being a colleague of Greg's at Formation I had to familiarise myself somewhat with the concepts. But what annoyed me was that I didn't always get a full understanding of it. I could be given a jumping off point to work with, but could never arrive at the initial ideas myself.
On the lookout for the perfect opportunity to add some skill points to my recursion shcemes knowledge I decided to tackle the Advent of Code challenges but force myself to use recursion schemes. Granted I am very slow at solving these problems, and even slower at writing and publishing them. I hope everyone enjoyed the holidays!
So I started Day 1, armed with the yaya library, my point of contact, @sellout, some tunes on Spotify (listen to some Jacques Greene and The Blaze), and the thirst for knowledge.
Before I discuss Day 1 though, I would like to explore my thoughts on recursion schemes that fell out from this attempt and speaking with Greg. Recursion schemes seem to fall into the space of algorithm implementation or business logic. So when we look to use them we have some problem we are trying to solve. I think this is why I found previously read literature on the topic frustrating. One would usually find how to recover natural numbers or lists from pattern functors. While these are useful concepts, I saw a massive valley between these ideas and actually moving towards using recursion schemes. This is why I felt the advent of code was the perfect medium to marry exploring recursion schemes and trying to solve problems.
So as I've said, recursion schemes tackle problem solving. They are an abstraction of recursion
in data structures and computations. With data structures they factor out the recursion we would
tend to reach for and we gain pattern functors. For example we will heavily use the List
pattern
functor XNor
. For computations we abstract folding and unfolding by utilising the fact that these
computations can be done for any Functor
.
Already we are off to a good start because we have gained two concepts for free. Many pattern functors already exist and it easy to define one for your domain, and this in turn gives us a cornucopia of folds and unfolds for free. What does that leave us? The stuff we care about, our business logic or algorithm implementation.
We take our pattern functor we believe matches the structure we would want to work with, and attempt to write the function definition as simple as possible. I have personally found myself starting with the smallest assumption I can make about what I need and adding new power or functionality as I see fit. We then massage these implementations into algebras or coalgebras that can used in our folds/unfolds. As I explore recursion schemes further I hope to keep these ideas in mind and refine them to gain a full understanding of the concepts.
Without further ado, lets see how we can solve Day 1 of AOC with recursion schemes!
To understand what we need to do, let's discuss the problem first. We are given some input that
consists of a series of numbers separated by newline characters. Each number is prefixed by a +
or -
to show whether is positive or negative.
For example:
+1
-2
+3
The first part of Day 1 is to write a function that can read this input and sum them. Thus
the answer to the above example would be 2
.
The second part of Day 1 is to write a function that while summing the input can detect if
the current sum has been detected before. If the end of the series of numbers has been reached
we should loop back over them until we reach a repeated frequency. In the example input our answer
would be 1
. To demonstrate:
0 + 1 = 1
1 - 2 = -1
-1 + 3 = 2
2 + 1 = 3
3 - 2 = 1 -- we saw 1 when we did 0 + 1
So our stream of numbers was: 1, -2, 3, 1, -2
.
Not much to see here other than some general set up.
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE TypeApplications #-}
module Frequencies where
import Control.Applicative ((<|>))
import Control.Monad.Except
import Control.Monad.State
import Data.Attoparsec.ByteString
import Data.ByteString (ByteString)
import Data.Set (Set)
import qualified Data.Set as Set
import Text.Parser.Char (char, digit, newline)
import Yaya
import Yaya.Control
import Yaya.Data
import Yaya.Either
import Yaya.Unsafe.Data () -- imported for orphan instances
import Yaya.Zoo
I've left the parsing of the input upto attoparsec
since it's lightweight. This does the heavy lifting of grabbing our numbers
and turning them into positive or negative numbers.
-- | Parse a `+` token.
plus :: Parser Char
plus = char '+'
-- | Parse a `-` token.
minus :: Parser Char
minus = char '-'
-- | Parse a sign (+/-) followed by its digits.
number :: Parser Int
number = do
sign <- try (minus >> pure negate) <|> (plus >> pure id)
sign . read <$> many1 digit
-- | Parse a newline separated string of 'number'.
numbers :: Parser [Int]
numbers = number `sepBy` newline
Here is our first function that defines an algebra for summing numbers.
sum' :: Algebra (XNor Int) Int
sum' = \case
Both x y -> x + y
Neither -> 0
This Algebra
serves as the summing of our incoming frequencies.
XNor acts as our "pattern functor" which is the pattern functor
for lists, i.e. [a]
. We can see this by looking at the definition
of XNor
from yaya
.
data XNor a b
= Neither
| Both a b
The case of Neither
acts as the base case []
(or Nil
).
While Both
acts as a : [a]
(or Cons
). It contains
the head of the list and the tail of the list.
Algebra f a
is an alias for f a -> a
, so we can
translate the original type signature to XNor Int Int -> Int
.
The x
can be seen as the head of the list, our current element,
and the y
being the accumulated sum, from the tail upwards.
Neither
then acts as the base case of our recrsion
and thus we can return 0.
This Algebra
can then be passed to cata
which will
process things from the back of the list, read leaf of computation,
up to towards the head.
We can already see the usefulness of expressing our functions via
pattern functors and simple functions. We are simply expressing the
semantics of summation when we write x + y
, and 0
acting as our
base element. We did not have to talk about recursion and conflate our
logic.
This captures everything we need for part 1, but we will demonstrate the computation later. Before that we will discuss our other functions for solving part 2.
To build up our solution for part 2 we need to solve the issue of repeating elements.
When we consider repeating elements we must think about how we need at least one
element to repeat. That means we will be dealing with a NonEmptyList
.
repeatConcat :: Coalgebra ((,) a) (NonEmptyList a, NonEmptyList a)
repeatConcat (orig, current) =
case project current of
Only a -> (a, (orig, orig))
Indeed a t -> (a, (orig, t))
This Coalgebra
serves as taking the NonEmptyList
and repeating it, followed
by concatenating them together.
This can be visualised as:
NonEmptyList a
is a type alias for Mu (AndMaybe a)
. There are two things
we need to address here, so let's talk about AndMaybe
first.
AndMaybe
is our pattern functor and acts as, you guessed it, the pattern functor
for non-empty lists. We can understand this by looking at its definition:
data AndMaybe a b
= Only a
| Indeed a b
We can read this as:
a `AndMaybe` b
We are always guaranteed an a
and possibly a b
. There is a guaranteed item in Only
,
and then Indeed
looks similar to Both
from XNor
, so the head, and the rest of the list.
A usual construction of NonEmpty is that we have a guaranteed head
of the
list and the rest of the list. In this case Only
actually acts as the guaranteed last
of the list, and Indeed
as the front (init
) of the list.
We also introduced Mu
when inspecting NonEmptyList
. Let's gain some intuition for what it is
by saying that the type alias List a
can be defined as Mu (XNor a)
.
Mu
is the fixed-point operator for finite/inductive data structures. This means
we can build up a List
, embedding our pattern functor, XNor
in Mu
and this
expresses that we have a finite computation. We can do the same for NonEmptyList
by
embedding AndMaybe a
into Mu
.
At this point we can unpack what our type signature means:
Coalgebra ((,) a) (NonEmptyList a, NonEmptyList a)
=== (NonEmptyList a, NonEmptyList a) -> (a, (NonEmptyList a, NonEmptyList a))
We keep the original list as our first element in the (,)
, and the
current NonEmptyList
that we are inspecting. Calling project
lets
us unwrap one layer of Mu
and this gives us back an AndMaybe
value that we case on.
If we have Only
one item we return the last item of the list and the original
list again, i.e. we've reached the end so now we repeat.
In the case where we have Indeed
we unpack the head and pass on our tail.
We always keep the original to refer to it once we get to the end of the list.
Since our input will be a list of numbers we want to write a function that
will give us a NonEmptyList
from a List
.
nonEmpty :: Algebra (XNor a) (a -> NonEmptyList a)
nonEmpty = \case
Neither -> embed . Only
Both a f -> embed . flip Indeed (f a)
As we saw in sum'
we were representing a list through its pattern functor
XNor
, which we also use here.
And in repeatConcat
we looked through NonEmptyList
and how it was an
alias for Mu (AndMaybe a)
our pattern functor for non-empty lists and
the fixed-point operator for finite data structures.
So lets look at what this Algebra
breaks out into:
Algebra (XNor a) (a -> NonEmptyList a)
=== XNor a (a -> NonEmptyList a) -> (a -> NonEmptyList a)
So, given an XNor
of a
s as the items, and a -> NonEmptyList a
as the tail or continuation of the list, we get back a function from
a -> NonEmptyList a
.
This comes across as intuitive, since we can turn any list into a
non-empty list as long as provide at lease one item. Our initial a
from the function!
In the case of Neither
, our function will be Only
. So we take that
a
passed in and return the singleton, non-empty list.
In the case of Both
, we have the head of our list, and the NonEmptyList
being built up from our Only
element. So, we apply the continuation and
it now acts as the head of our Indeed
non-empty list. Again, waiting
for the next continuation, when we finally call this function.
We are starting to move out of the territory of writing basic functions
and into the territory of using these functions in folds and unfolds.
The task at hand being able to create a Stream
of Int
s from a List
of Int
s.
makeStream :: List Int -> Stream Int
makeStream l = case project l of
Neither -> ana duplicate 0
Both h t -> ana repeatConcat (duplicate $ (cata nonEmpty t h))
where
duplicate :: Coalgebra ((,) a) a
duplicate i = (i, i)
Our input is a List Int
which is a type alias for Mu (XNor a)
.
At this point we know by now that combining the pattern functor for
lists, XNor
and Mu
we are saying we have a finite list structure.
Our output is Stream Int
, which is a type alias for Nu ((,) a)
.
This particular pattern we have not come across yet. So lets see what
these two things in tandem entail.
Nu
is the dual fixed-point operator to Mu
. As its dual it means
that it describes infinite/co-inductive data structures. So when we
combine Nu
with pattern functors, we are saying that we have potentially
infinite data. This is very true for our case of repeating a list.
(,) a
is chosen as the pattern functor because it naturally represents
an infinite stream of data. We have the head of the stream, the first element
of the tuple, and the rest of the stream, the second element of the tuple.
We could anaolgise this to a manual recursive definition of a stream:
data Stream = { element :: a, more :: Stream a }
Another way of looking at it is that streams are lists without a Nil case.
With this explanation out of the way we can break down how to implementation works.
We first project
our list l
to unwrap one layer of our List
.
In the case of Neither
we make a "safe" move of producing a stream of 0s.
We cannot do much with an empty list, since it is undefined for Stream
data,
but it works in our larger problem because adding 0 is no-op.
In the case of Both
we utilise our nonEmpty
algebra to convert our List
into a NonEmptyList
. We duplicate this result and infinitely generate, via ana
,
a Stream
of NonEmptyList
s using repeatConcat
.
This our final coalgebra that implements finding the repeating frequency in a stream of input.
We can break up the problem into its constituent parts:
Stream Int
.Set Int
.The output is the first repeated element we find. But the thing is, we might
actually never find a repeating element. Consider the input of a single +1
.
We will forever compute the natural numbers until we overflow, since we are using
Int
.
Thus, we split our computation into two. We either return a repeated frequency, or
we continue our computation.
Either Int (Int, Set Int, Stream Int)
where
our Left
case short-circuits the computation and returns our result, while
the Right
case continues our computation.repeatCoalgebra :: Coalgebra (Either Int) (Int, Set Int, Stream Int)
repeatCoalgebra (tally, env, stream) =
let (currentElem, restOfStream) = project stream
result = tally + currentElem
in if result `Set.member` env
then Left result
else Right $ (result, Set.insert result env, restOfStream)
As we mentioned above, we don't necessarily know how long this algorithm can go on
for so we describe it as a Coalgebra
and provide it a seed. The seed if made up
of our constituent parts of: a tally, the previously seen frequencies, and the stream
of numbers.
The first thing we want to do is inspect the head of the stream, this
can be done by using project
to split the stream into its head and its
tail.
We can then get our latest tally by summing our current element, the head of the stream, with our aggregated tally, the seed.
We then check that our result
is a member of the Set
of previously seen tallies.
If it is, then great! We found our result and short-circuit with Left
.
If not, we continue the computation updating our seed values, and returning
with Right
.
Lets take a moment to consider the semantics of Either
in this case, because
it's important to note how its acting and its general use in recursion schemes.
When we think about Either
we generally think about short-circuiting behaviour.
This is drilled into us when we write the Functor
, Applicative
, and Monad
instances.
When we see the Left
case we propagate this result.
In our case it's the natural pattern functor for partial functions. This can be seen in the
newtype defined in yaya
, Partial
. It is defined as Partial a = Nu (Either a)
.
The Partial
relates to the short-circuiting. We may get a result and this will be
passed back as a Left
value. Or we may just keep computing forever with a Right
value.
In our case this is very true given our previous problem case of having a single input of +1
.
While trying to figure out how to solve part 2 I wrote the following function. It has a couple of problems and it's left as an exercise to the reader to see what they are.
repeatAlgebra :: XNor Int Int -> State (Set Int) (Either Int Int)
repeatAlgebra = \case
Both currentElement tally -> do
let result = currentElement + tally
env <- get
if result `Set.member` env
then pure $ Left result
else put (Set.insert result env) >> pure (Right result)
Neither -> pure (Right 0)
Our answer to part 1 is implemented in frequency
. We parse our list of numbers and
use the combination of cata
and our sum'
algebra to find the answer. We simply
explode if our parsing fails.
frequency :: ByteString -> Int
frequency = either (error . show) id . fmap (cata sum') . parseOnly numbers
Our answer to part 2 is implemented in findRepeat
. This is the helper to run our repeatCoalgebra
.
It uses ana
to unfold our seed values (0, {0}, makeStream numbers)
and uses the runToEnd
fold to
evaluate our result to get our final result.
findRepeat :: ByteString -> Int
findRepeat = either (error . show) id
. fmap (runToEnd . runner)
. parseOnly numbers
where
runner :: [Int] -> Nu (Either Int)
runner ns = ana repeatCoalgebra (0, Set.singleton 0, makeStream $ cata embed ns)
So there we have it. Our first day of Advent of Code implemented using recursion schemes and some quick parser functions. I hope this helps bridge the gap between defining natural numbers using recursion schemes and actually solving problems.
You can follow the rest of my Advent of Code antics on my github. They'll be coming through slow and steady! You can feel free to contact with me with any feedback or questions :)
Fintan Halpenny
Passionate about Haskell as it is the perfect language to help me be productive but also constantly drives me to learn new things. The day I stop learning is the day I'm no longer on this Earth. I also have an interest in Dhall and helped start a functional library for the language (despite Dhall's original intention of being a config language) https://github.com/FormationAI/dhall-bhat
See other articles by Fintan
Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ
108 E 16th Street, New York, NY 10003
Join over 111,000 others and get access to exclusive content, job opportunities and more!