Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive liftIO

I've looked at the some instances of MonadTrans, for MaybeT the implementation looks like this:

instance MonadTrans MaybeT where
    lift = MaybeT . liftM Just

As I understand the instance for MonadIO is used to do a variable number of lifts from the inner most, a IO monad, directly to the outermost. For the MaybeT case it looks like this:

instance (MonadIO m) => MonadIO (MaybeT m) where
    liftIO = lift . liftIO

What I don't understand is how this recursive function escapes the infinite loop. What is the base case?

like image 540
Marius Catalin Avatar asked Mar 21 '17 11:03

Marius Catalin


2 Answers

Perhaps surprisingly, the definition below is not recursive, even if it looks such.

instance (MonadIO m) => MonadIO (MaybeT m) where
    liftIO = lift . liftIO

This is because the liftIO on the left hand side is the liftIO for the MaybeT m monad, while the liftIO on the right hand side is the liftIO for the m monad.

Hence, this simply defines liftIO in one monad in terms of the liftIO for another monad. No recursion here.

This is similar to e.g.

instance (Show a, Show b) => Show (a,b) where
   show (x,y) = "(" ++ show x ++ ", " ++ show y ++ ")"

Above, we define how to print a pair depending on how to print their components. It looks recursive, but it is not really such.

It could help visualizing this by inserting explicit type arguments, at least mentally:

-- pseudo-code
instance (Show a, Show b) => Show (a,b) where
   show @(a,b) (x,y) = 
      "(" ++ show @a x ++ ", " ++ show @b y ++ ")"

Now show @(a,b), show @a, and show @b are distinct functions.

like image 121
chi Avatar answered Oct 11 '22 18:10

chi


Simple equational reasoning and rewriting definitions for some specialization can help you. Base case for MonadIO is IO. MaybeT is monad transformer, so lets combine MaybeT and IO in some simple example.

foo :: MaybeT IO String
foo = liftIO getLine

Now let's rewrite this function definition applying instance implementations from your question step by step.

foo
= liftIO {- for MaybeT -} getLine
= lift (liftIO {- for IO here -} getLine)  -- step 2
= lift (id getLine)
= lift getLine
= MaybeT (liftM Just getLine)
  1. getLine has type IO String
  2. liftM Just getLine has type IO (Maybe String)
  3. MaybeT m a constructor needs value of type m (Maybe a) where m = IO and a = String in our case.

Probably hardest step to analyze is step 2. But in reality it's very easy if you remind yourself types of liftIO :: IO a -> m a and lift :: Monad m => m a -> t m a. So all work is done by type inference.

like image 21
Shersh Avatar answered Oct 11 '22 16:10

Shersh