Monads are monoids in the category of Endofunctors, what’s the problem?
Hello there!
Prepare yourself for a journey.
I’m currently buildling a Reversi AI with Ephemeral trees in Scala inspired by the paper “Why Functional Programming Matters” (A post about it will come later),
And I wanted to property test my implementations against each other.
The property is that all implementations: Minimax and Alpha-beta pruning should give the same result, although their runtime behavior may vary.
How would I go about doing it?
I had to generate a board, starting at the initial board, and applying random moves on that board moving forward.
I have a function possibleMoves :: Board => List[Move]
Then I realized we can have a more symmetric looking function possibleMoves :: Board => List[Board]
With which I can get chooseMove :: Board => Gen[Board]
So I figured I wanted to apply bind (>>=/flatMap) n times on the initial board.
Something of the form: Int -> m a -> (a -> m a) -> m a
There’s replicateM :: Int -> m a -> List[m a]
but that isn’t satisfactory.
And I couldn’t find that function built into Scalaz.
What if we juggle that type around?
We get: Int -> (a -> m a) -> (a -> m a)
That looks like Kleisli, and as m is a Monad, those are Kleisli Arrows!
So I could do something like fold(replicate k f) with the kleisli monoid.
Then I thought it looked like a Category, as Kleisli Arrows form a Category.
So it’s just composing an endomorphism n times with itself!
But what’s a category with only one object? A Monoid!
So we want to compose an arrow of the monoid (in the categorical sense) n times with itself.
But what’s an arrow of a monoid?
It is an element of the monoid!
And what is arrow composition?
It is the monoid’s operation!
So we want to compose an arrow n times with itself, which means:
x + x + x + … + x, n times.
Which is: You guessed it!
It is multiplication of an element of a monoid by a natural number!!!!!!!!
We have just reinvented multiplication.
Someone mentioned it’s like church numerals and addition (the successor function as the operation)
Category Theory is everywhere!
The whole code turned out to be:
Category[Kleisli[Gen,?,?]].monoid.multiply(chooseMove,length)(initialBoard)
Hope you enjoyed your daily theoretical beauty dose.
References:
“Why Functional Programming matters” by John Hughes
