The weirdest Monad

I was going through base's haddock, when I saw that a functions has a Monad instance.

If we define have a look at Collatz conjecture, given a number n, then next number is:

• 3 * n + 1 if n is odd
• n/2 if n is even

We can define each branch as the following functions:

onEven :: Int -> Int
onEven x = x `div` 2

onOdd :: Int -> Int
onOdd x = 3 * x + 1

If we want to pipe them, the following two functions are equivalent:

startOdd0 :: Int -> Int
startOdd0 = onEven . onOdd

startOdd1 :: Int -> Int
startOdd1 = onEven <$> onOdd

The first one uses regular Haskell composition, the second one relies Functor.

We can also try the following implementations based on Applicative and Monad:

startOdd2 :: Int -> Int
startOdd2 = const onEven <*> onOdd

startOdd3 :: Int -> Int
startOdd3 = const . onEven =<< onOdd

I have used const, but regarding function, I could have used pure.

This is why Reader is often defined as newtype Reader r a = Reader { runReader :: r -> a }.

As such, we can use the do-notation as follows:

startOdd4 :: Int -> Int
startOdd4 = do
  newEven <- onOdd
  const $ onEven newEven

Alternatively, MOnad.Monoid is providing Endo, which defines the Monoid instance, and allows the composition as follows:

startOdd5 :: Int -> Int
startOdd5 = appEndo $ Endo onEven <> Endo onOdd

Lastly, Control.Arrow provides ArrowChoice, which helps to combine functions, conditionally calling one or the other, which helps to build a branchless version of the Collatz as follows:

collatz :: Int -> Int
collatz x = transform $ maybeToRight x $ mfilter even $ Just x
  where
    transform :: Either Int Int -> Int
    transform = onOdd ||| onEven