The first puzzle was easy, and the second one… was hard. The tokens are iterate ) 5 join !! 1 ( (+) with the goal value of 32. The puzzle also says: “What Monad are we looking for?”. I thought, of course, [] since we have join and !!. I also saw that 5 and 32 were most likely related: 2^5 = 32, but I couldn’t see a way of generating powers of two here.
I spent a few hours on two evenings trying to arrange the tokens into something meaningful, but failed to put anything into iterate. After a pause, I recollected that function arrows are also monads! That’s the clue. It took me a few minutes to solve the puzzle after that. In order not to spoil the solution too much here, it contains join (+). Then I wanted to understand how it works. Starting at the beginning:
1
join::Monadm=>m(mx)->mx
Note: the following code is wrong!
123456789
instanceMonad(->r)(->r)a=a->r-- m ~ (-> r)join::((->r)((->r)a))->((->r)a)join::((->r)a)->r->(a->r)join::a->r->r->a->rjoin::((a->r)->r)->(a->r)
It’s wrong because I missed the parentheses around the arrow, which matters a lot:
12345678910
instanceMonad((->)r)a->b=(->)ab-- m ~ ((->) r)join::(((->)r)(((->)r)a))->((->r)a)((->r)a)=r->a(((->)r)(((->)r)a))=(((->)r)(r->a))=r->(r->a)=r->r->ajoin::(r->r->a)->(r->a)join::(r->r->a)->r->a
(+)::x->x->x-- substituting (r ~ x, a ~ x) in the `join` abovejoin(+)::x->x-- what `iterate` calculates, from the documentationiterate::(a->a)->a->[a]iteratefx=[x,fx,f$fx,f$f$fx,…]iterate(join(+))::x->[x]iterate(join(+))x=[x,join(+)$x,join(+)$join(+)$x,…]
The types work out here, which is great… but what does join (+) actually do?! I can use equational reasoning to figure out the definitions:
1234567891011121314
-- Monad is usually defined via `(>>=)`(>>=)::Monadm=>ma->(a->mb)->mb(>>=)::(r->a)->(a->r->b)->(r->b)ra>>=arb=\r->leta=rarinarbarjoinmma=mma>>=\ma->ma=mma>>=idjoin(+)=(+)>>=id=\r->leta=(+)rinidar=\r->leta=(+r)inidar=\r->id(+r)r=\r->(+r)r=\r->r+r
Turns out, join (+) takes a number and adds it to itself! Therefore: