Imagine a version of the State
monad where the state is an integer, the state always starts at 0
, and there’s a single operation next
which gets you the next number. Let’s call it the Count
monad. We can write this kind of thing pretty easily by copying from State
.
CountT
looks like StateT
except the state type is specialized to Integer
.
We called CountT
’s function innerRunCountT
because we’ll want to hide it. Instead, we can use this version that always initializes the count to 0:
The Count
monad is just CountT
over Identity
.
type Count = CountT Identity
runCount :: Count a -> (a, Integer)
runCount m = runIdentity $ runCountT m
The Functor, Applicative, and Monad instances for CountT m
look just like the ones for StateT m
, so we can skip over them here.
Consider this definition of a binary tree.
Let’s introduce a version of this type with an “annotation”. In our case, we’ll want to label each node with a unique integer, starting from 0.
We can easily do this (and any other similar labeling task) with the Count
monad.
label :: Tree a -> Count (AnnTree Integer a)
label Empty = pure AnnEmpty
label (Tree val left right) = do
n <- next
labeledLeft <- label left
labeledRight <- label right
pure $ AnnTree n val labeledLeft labeledRight
labeledTree :: AnnTree Integer a
labeledTree = fst . runCount . label $ _your_tree_here
Next, consider this naive function that calculates the nth Fibonacci number.
We want to find out how many times this function runs if we invoke it with fib 20
. Sounds like a job for Count
!
First, we wrap our function in Count
.
countFib :: Integer -> Count Integer
countFib 0 = next >> pure 0
countFib 1 = next >> pure 1
countFib n = do
next
a <- countFib $ n - 1
b <- countFib $ n - 2
pure $ a + b
Then, we runCount $ countFib 20
and get (6765,21891)
. The first number is the 20th Fibonacci number, and the second number is the number of times countFib
was invoked to find it.