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)
= innerRunCountT m 0 runCountT m
```

The `Count`

monad is just `CountT`

over
`Identity`

.

```
type Count = CountT Identity
runCount :: Count a -> (a, Integer)
= runIdentity $ runCountT m runCount 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.

```
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)
Empty = pure AnnEmpty
label Tree val left right) = do
label (<- next
n <- label left
labeledLeft <- label right
labeledRight pure $ AnnTree n val labeledLeft labeledRight
labeledTree :: AnnTree Integer a
= fst . runCount . label $ _your_tree_here labeledTree
```

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

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

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
0 = next >> pure 0
countFib 1 = next >> pure 1
countFib = do
countFib n
next<- countFib $ n - 1
a <- countFib $ n - 2
b 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.