import Control.Monad       (liftM, ap)

-- When Resource is Integer, it can keep track of computation steps.

type Resource = Integer

data R a = R (Resource -> (a, Resource))  -- the monadic type

instance Monad R where
   -- (>>=) :: R a -> (a -> R b) -> R b
   R c1 >>= fc2  = R (\r -> let (s,r') = c1 r
                                R c2 = fc2 s in
                              c2 r')
   -- return :: a -> R a
   return v      = R (\r -> (v,r))

instance Functor R where
    fmap = liftM
 
instance Applicative R where
    pure  = return
    (<*>) = ap

-- step adds one more to the step count
step   :: a -> R a
step v =  R (\r -> (v,r+1))

-- count (fib 10) => (fib 10, ~2^10)
count        :: R Integer -> (Integer, Resource)
count (R c)  = c 0

-- sample function:
inc :: Integer -> Integer
inc n = n + 1

-- lifted inc function to R monad:

incR :: R Integer -> R Integer
incR n = do nValue <- n
            step (nValue+1)

{-- Test it with:

count (incR (return 5))  -- displays (6,1)

--}

-- Lifting +,-,fib

lift1 :: (a->b) -> R a -> R b
lift1 f n = do nValue <- n
               step (f nValue)

incR' :: R Integer -> R Integer
incR' = lift1 (+1)

{-- Test it with:

count (incR' (return 5))  -- displays (6,1)

--}

lift2 :: (a->b->c) -> R a -> R b -> R c
lift2 f n1 n2 = do n1Value <- n1
                   n2Value <- n2
                   step (f n1Value n2Value)

instance Num a => Num (R a) where
   (+)         =  lift2 (+)
   (-)         =  lift2 (-)
   fromInteger =  return . fromInteger

ifR :: R Bool -> R a -> R a -> R a
ifR b t e = do bVal <- b
               if bVal then t
                       else e

(<=*) :: (Ord a) => R a -> R a -> R Bool
(<=*) = lift2 (<=)

fib :: R Integer -> R Integer
fib n = ifR (n <=* 1) n (fib (n-1) + fib (n-2))


{-- Test it with:

count (fib 0)
count (fib 1)
count (fib 2)
count (fib 3)
count (fib 4)
count (fib 5)

count (fib 10)

--}