Define a new monad in Haskell?

Question

I would like to create my own monad in Haskell, and have Haskell treat it just like any other built in monad. For instance, here is code for creating a monad that updates some global state variable each time it is called, along with an evaluator that uses it to compute the number of times the quot function is called:

-- define the monad type
type M a = State -> (a, State)
type State = Int

-- define the return and bind operators for this monad
return a x = (a, x)
(>>=) :: M a -> (a -> M b) -> M b
m >>= k = \x -> let (a,y) = m x in
                let (b,z) = k a y in
                (b,z)

-- define the tick monad, which increments the state by one
tick :: M ()
tick x = ((), x+1)

data Term = Con Int | Div Term Term
-- define the evaluator that computes the number of times 'quot' is called as a side effect
eval :: Term -> M Int
eval (Con a)   = Main.return a
eval (Div t u) = eval t Main.>>= \a -> eval u Main.>>= \b -> (tick Main.>>= \()->Main.return(quot a b))

answer :: Term
answer = (Div (Div (Con 1972)(Con 2))(Con 23))

(result, state) = eval answer 0

main = putStrLn ((show result) ++ ", " ++ (show state))

As implemented now, return and >>= belong in the namespace Main, and I have to distinguish them from Prelude.return and Prelude.>>=. If I wanted Haskell to treat M like any other type of monad, and properly overload the monad operators in Prelude, how would I go about that?

Answer 1

Here is an implementation:

    -- Otherwise you can't do the Applicative instance.
    import Control.Applicative


    -- Simple function
    foo :: String -> String
    foo x = do
        x ++ "!!!"

    -- Helper for printing Monads
    print2 :: (Show a) => MyBox a -> IO()
    print2 (MyBox x) = print x


    -- Custom type declaration
    data MyBox a = MyBox a


    -- MyBox functor
    instance Functor MyBox where  
        fmap f (MyBox x) = MyBox (f x)


    -- MyBox Applicative 
    instance Applicative MyBox where  
        pure = MyBox 
        (MyBox f) <*> x = f <$> x


    -- MyBox Monad
    instance Monad MyBox where  
        return x = MyBox x
        MyBox x >>= f  = f x 

    -- (MyBox as a functor) Use a function with a wrapped value
    result1 = foo <$> (MyBox "Brian")

    -- (MyBox as an Applicative) Use a wrapped function with a wrapped value
    result2 = (MyBox foo) <*> (MyBox "Erich")

    -- (MyBox as a Monad)  Use a wrapped value with a lambda (it can be chainable)
    myLambda1 = (\ x -> MyBox (x ++  " aaa"))
    myLambda2 = (\ x -> MyBox (x ++  " bbb"))
    myLambda3 = (\ x -> MyBox (x ++  " ccc"))
    result3 = (MyBox "Rick") 
        >>= myLambda1
        >>= myLambda2
        >>= myLambda3


    -- Another Monad syntax
    result4 = do
        x <- MyBox "A" 
        y <- MyBox "B"  
        z <- MyBox "C"  
        MyBox (x ++ y ++ z)


    main = do
        print2(result1) -- "Brian!!!"
        print2(result2) -- "Erich!!!"
        print2(result3) -- "Rick aaa bbb ccc"
        print2(result4) -- "ABC"

Answer 2

To make your new monad work with all the existing Haskell machinery--do notation, for instance--all you need to do is declare your type an instance of the Monad typeclass. Then the Prelude functions >>=, return, etc. will work with your new type just as they do with all other Monad types.

There's a limitation, though, that will require some changes in your examples. Type synonyms (declared with type) cannot be made class instances. (Your M a is exactly the same as Int -> (a, Int).) You'll need to use data or newtype instead. (The distinction between those two is not relevant here.)

Both of those keywords create a genuinely new type; in particular, they create a new data constructor. You should read up on this in any fundamental Haskell text. Briefly, newtype X a = Y (...) creates a new type X a; you can create values of that type using the constructor Y (which can, and often does, have the same name as the type constructor X); and you can consume values by pattern matching on Y. If you choose not to export the data constructor Y, only functions in your module will be able to manipulate the values directly.

(There's a GHC extension TypeSynonymInstances but it won't help you here, because of a separate issue: type synonyms cannot be partially applied; for any type X a = {- ... -} you can only write X a or X Int or whatnot, never just X. You can't write instance Monad M because M is partially applied.)

After that, all you need to do is move your definitions of return and >>= into an instance Monad declaration:

newtype M a = M (State -> (a, State))

instance Monad M where
  return a = M $ \x -> (a, x)
  m >>= k = {- ... -}

Note that the implementation of (>>=) is slightly verbose because you need to unwrap and rewrap the newtype using its data constructor M. Look at the implementation of StateT in transformers, which uses a record accessor to make it easier. (You can manually write a function runM :: M -> State -> (a, State) equivalent to the record syntax that transformers and many other packages use.)