{- |
Description: Collatz conjecture
Copyright: Copyright (C) 2022 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P78" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P78 (collatz) where

import           Control.Monad.Writer
import           Data.Monoid (Sum(..))

{- | Starting from a positive integer \(n\),
we can have a sequence of numbers such that at each step,
the next number is \(3n+1\) if \(n\) is odd,
or \(\frac{n}{2}\) if \(n\) is even.
The Collatz conjecture states that this sequence will always end at 1
after a finite number of steps.

Using the t'Control.Monad.Writer.Lazy.Writer' monad, count the number of these steps
for a given positive integer \(n\).
-}
collatz :: Integral a => a -> a
collatz :: forall a. Integral a => a -> a
collatz a
n = Sum a -> a
forall a. Sum a -> a
getSum (Sum a -> a) -> Sum a -> a
forall a b. (a -> b) -> a -> b
$ Writer (Sum a) a -> Sum a
forall w a. Writer w a -> w
execWriter (Writer (Sum a) a -> Sum a) -> Writer (Sum a) a -> Sum a
forall a b. (a -> b) -> a -> b
$ a -> Writer (Sum a) a
forall a. Integral a => a -> Writer (Sum a) a
collatz' a
n

collatz' :: Integral a => a -> Writer (Sum a) a
collatz' :: forall a. Integral a => a -> Writer (Sum a) a
collatz' a
1 = a -> WriterT (Sum a) Identity a
forall a. a -> WriterT (Sum a) Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return a
1
collatz' a
n = do
  Sum a -> WriterT (Sum a) Identity ()
forall w (m :: * -> *). MonadWriter w m => w -> m ()
tell Sum a
1
  if a -> Bool
forall a. Integral a => a -> Bool
odd a
n
    then a -> WriterT (Sum a) Identity a
forall a. Integral a => a -> Writer (Sum a) a
collatz' (a -> WriterT (Sum a) Identity a)
-> a -> WriterT (Sum a) Identity a
forall a b. (a -> b) -> a -> b
$ a
3a -> a -> a
forall a. Num a => a -> a -> a
*a
na -> a -> a
forall a. Num a => a -> a -> a
+a
1
    else a -> WriterT (Sum a) Identity a
forall a. Integral a => a -> Writer (Sum a) a
collatz' (a -> WriterT (Sum a) Identity a)
-> a -> WriterT (Sum a) Identity a
forall a b. (a -> b) -> a -> b
$ a
n a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2