Details about a Haskell puzzle

I’ve seen this “Haskell Puzzles” https://jaspervdj.be/posts/2023-06-19-haskell-puzzles.html page on Haskell Weekly and decided to see what it was about. It has puzzles where you need to rearrange the given tokens so that the final expression produces the needed value.

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:

join :: Monad m => m (m x) -> m x

Note: the following code is wrong!

instance Monad (-> r)

(-> r) a = a -> r

-- m ~ (-> r)
join :: ((-> r) ((-> r) a)) -> ((-> r) a)
join :: ((-> r) a) -> r -> (a -> r)
join :: a -> r -> r -> a -> r
join :: ((a -> r) -> r) -> (a -> r)

It’s wrong because I missed the parentheses around the arrow, which matters a lot:

instance Monad ((->) r)

a -> b = (->) a b

-- m ~ ((->) r)
join :: ( ((->) r) ( ((->) r) a ) ) -> ( (-> r) a )
( (-> r) a ) = r -> a
( ((->) r) ( ((->) r) a ) ) = ( ((->) r) (r -> a) ) = r -> (r -> a) = r -> r -> a
join :: (r -> r -> a) -> (r -> a)
join :: (r -> r -> a) -> r -> a

This is confirmed by ghci:

λ> :t join @((->) _)
join @((->) _) :: Monad ((->) w) => (w -> (w -> a)) -> w -> a

And here is how the function arrow behaves just like any other operator:

λ> :t (!!) :: ([a] -> (Int -> a))
(!!) :: ([a] -> (Int -> a)) :: [a] -> Int -> a
λ> :t (!!) :: ((->) [a] (Int -> a))
(!!) :: ((->) [a] (Int -> a)) :: [a] -> (Int -> a)
λ> :t (!!) :: (((->) [a]) (Int -> a))
(!!) :: (((->) [a]) (Int -> a)) :: [a] -> (Int -> a)

Applying join (+) to iterate:

(+) :: x -> x -> x

-- substituting (r ~ x, a ~ x) in the `join` above
join (+) :: x -> x

-- what `iterate` calculates, from the documentation
iterate :: (a -> a) -> a -> [a]
iterate f x = [x, f x, f $ f x, f $ f $ f x, …]

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:

-- Monad is usually defined via `(>>=)`
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(>>=) :: (r -> a) -> (a -> r -> b) -> (r -> b)
ra >>= arb = \r -> let a = ra r in arb a r

join mma = mma >>= \ma -> ma = mma >>= id

join (+)
  = (+) >>= id
  = \r -> let a = (+) r in id a r
  = \r -> let a = (+ r) in id a r
  = \r -> id (+ r) r
  = \r -> (+ r) r
  = \r -> r + r

Turns out, join (+) takes a number and adds it to itself! Therefore:

iterate (join (+)) 1 :: [Int]
iterate (join (+)) 1 =
  [ 1
  , 1+1 = 2
  , (1+1) + (1+1) = 4
  , ((1+1) + (1+1)) + ((1+1) + (1+1)) = 8
  , (((1+1) + (1+1)) + ((1+1) + (1+1))) + (((1+1) + (1+1)) + ((1+1) + (1+1))) = 16
  , 32
  , …
  ]

iterate (join (+)) 1 !! 5 = 32