# A Counting Monad

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`

.

```
newtype CountT m a =
CountT { innerRunCountT :: Integer -> m (a, 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:

```
runCountT :: CountT m a -> m (a, Integer)
runCountT m = innerRunCountT m 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.

## Example: Annotated Trees

Consider this definition of a binary tree.

```
data Tree a
= Empty
| Tree a (Tree a) (Tree a)
```

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.

```
data AnnTree ann val
= AnnEmpty
| AnnTree ann val (AnnTree ann val) (AnnTree ann val)
```

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
```

## Example: Function Call Counting

Next, consider this naive function that calculates the nth Fibonacci number.

```
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
```

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.