# A Monad is a Monoid in the Category of Endofunctors

I have recently tried to get a better grip on how Monads in Haskell actually work. Mostly I was perplexed by the state monad; so I decided to go ahead and implement some of it in scheme.

Full source code available at my git server

### Bind

I took bind, (`>>=`

) as a base, giving some basic
definitions for it.

```
(define-method (>>= (this <null>) proc) '())
(define-method (>>= (this <pair>)
(proc <procedure>))
(apply append (map proc this)))
```

Binding on a list is simple mapping the function over the list, and concatenating together the results. Which is a way to model calculations with multiple return values. For example:

```
(>>= '(1 2) (lambda (x) (list x (1+ x))))
;; ⇒ '(1 2 2 3)
```

We also give the default binding of the sequence operator
(`>>`

) as

```
(define-method (>> (a <top>) (b <top>))
(>>= a (lambda args b)))
```

Which is a direct match to Haskells default implementation:

`m >> k = m >>= \_ -> k`

### Fmap

I could from there go back to map. Since a Monad is Monoid
in the category of Endofunctors (whatever that means)
everything that is a monad must also be a functor, something
that can be mapped over. Leading to the very simple
implementation of fmap, (`<$>`

):

```
(define (<$> f m_)
(>>= m_ (lambda (m) ((return m_) (f m)))))
```

### Assorted bindings

As a quick side mark, I also implemented the `do`

notation
from Haskell with the simple macro

```
(define-syntax do
(syntax-rules (<- let =)
((_ let ptrn = val rest ...)
(match val
(ptrn (do rest ...))))
((_ ptrn <- val rest ...)
(>>= val (match-lambda (ptrn (do rest ...)))))
((_ a) a) ; Base case
((_ token rest ...)
(>> token (do rest ...)))))
```

allowing forms such as the one used in implementing functor application

```
(define (<*> f_ i_)
(do f <- f_
i <- i_
((return f_) (f i))))
```

## Other Fun Monads

From this I implemented a few different monads. Some trivial, like optional (maybe)

```
(define (div d)
(if (zero? d)
(nothing)
(just (/ d))))
(mapM div '(0 1 2 3))
;; ⇒ [Nothing]
(mapM div '(1 2 3))
;; ⇒ [Just (1 1/2 1/3)]
```

and writer

```
(run-writer
(do "Hello, "
"World"
(return-writer 10))))
;; ⇒ '(10 "Hello, World")
```

The interesting one, which prompted this whole project, is however:

### State

To start of, an example:

```
(run-state
(do let y = 7
(modify (lambda (x) (+ x y)))
(get))
10)
```

The state monad requires at least the get and put procedures which works "inside" it, along with run-state, which runs a composition of "stateful"* procedures and returns a "regular" value.

The interesting parts are however how it is implemented.
State is internally created in two parts. One is the `<state>`

type, which simply is a procedure which maps state pairs to
state pairs. And the other is (thankfully) state pairs.

The implementation both uses the define-stateful macro, which creates functions that creates functions which take state pairs as a secondary argument, and returns state mappers.

```
(define-syntax-rule (define-stateful ((proc args ...) st) body ...)
(define (proc args ...)
(make-state ; creates <state> objects
(lambda (st) body ...))))
```

From there get and put are trivially implementable as

```
(define-stateful ((get) st-list)
"Sets the return value of state to st."
(match st-list
((_ st)
(list st st))))
```

and

```
(define-stateful ((put v) st-list)
"Sets st to v."
(list '() v))
```

From here we can then build up further abstraction without ever caring about how state actually is implemented. for example, a simple (and probably buggy) stack implementation:

```
(define (pop)
(do st <- (get)
let top = (car st)
(put (cdr st))
(return-state top)))
(define (peek)
(do st <- (get)
(return-state (car st))))
(define (push v)
(do st <- (get)
(put (cons v st))))
```

* *The whole point of the state monad is to emulate state,
without actually modyfying anything*

## Everything is a Monad

I also realized that we can give a definition for bind for all types which lack their own.

```
(define-method (>>= (a <top>) (proc <procedure>))
(proc a))
```

This has the fun effect that it allows all values to act as
belonging to the same monad, the monad of the primitive
scheme type. So expressions such as `(>>= 1+ 10) ; ⇒ 11`

,
and `(<$> 1+ 5) ; ⇒ 6`

suddenly work.

## About Monoids

I however still don't understand why a Monad is a Monoid. A Monoid (ℝ, ×) is as known just pair between a group ℝ, and a binary operation ×, which is closed under application of the operator, is associative, and have a "0" element which any applied together with any other object results in the other object.

I do see that monads have many of these characteristics,
with `>>`

sort of acting like ×, but I'm missing at least
one piece for understanding the whole puzzle.

## Refrences

## Further Reading

- http://cswords.com/paper/alamode.pdf

A good article which goes through an almost identical implementation. - https://www.reddit.com/r/scheme/bbo1i1/

Reddit discussion of this page.

RSS-feed to see more like this.