CODEWITHSUNDEEP
haskelltypesmonads
Mark Karavan
Mark Karavan

Reputation: 2674

Getting a "No instance of Applicative" error when declaring a Monad

I'm trying to implement the example from the first chapter of this paper, which goes like this:

data Tree a = Fork (Tree a) (Tree a) | Leaf a | Nil deriving (Show)

instance Monad Tree where
   return a = Leaf a
   Nil >>= f = Nil
   Leaf a >>= f = f a
   Fork u v >>= f = Fork (u >>= f) (v >>= f)

tree1 = Fork 
         (Fork (Leaf 2) Nil) 
         (Fork (Leaf 2) (Leaf 3))

tree2 = Fork (Leaf 2) (Leaf 3)

f 2 = Fork Nil (Leaf "Two")
f 3 = Fork (Leaf "Three") (Leaf "String")

tree3 = tree2 >>= f

When I run it in GHC, I get this error:

monads.hs:3:10:
    No instance for (Applicative Tree)
      arising from the superclasses of an instance declaration
    In the instance declaration for ‘Monad Tree’
Failed, modules loaded: none.

I've tried adding this to the beginning

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

but I get this error:

monads.hs:7:10:
    Ambiguous occurrence ‘Monad’
    It could refer to either ‘Main.Monad’, defined at monads.hs:1:1
                          or ‘Prelude.Monad’,
                             imported from ‘Prelude’ at monads.hs:1:1
                             (and originally defined in ‘GHC.Base’)

What is the most correct fix?

Upvotes: 3

Views: 2235

Answers (2)

luqui
luqui

Reputation: 60463

To expand on Louis Wasserman's comment, you need to add an Applicative (and therefore Functor) instance now when you are declaring a Monad instance. Once you have written the Monad instance, the other instances are always the same:

import Control.Monad (liftM, ap)

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

This changed because every Monad is an Applicative (using this instance), but not the other way around, so it's morally a superclass. However, Applicative was added to the standard library after Monad so it wasn't made a real superclass for a long time since that would break people's code. Recently, since Applicative has come into very common use, the community decided to make Applicative a real superclass of Monad, breaking everybody's code once but improving it for the future. So that's what you're seeing.

Upvotes: 11

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476719

The problem is that, like the documentation specifies. The Monad class signature is:

class Applicative m => Monad m where
    --...

This means that in order to define the instance of a type to be Monad, you first need to define that type to be Applicative. The problem is even more severe since the signature of Applicative states:

class Functor f => Applicative f where
    --...

So you first need to make Tree an instance of Functor. The reason that in the paper, this wasn't necessary, is because - as far as I know, in the early versions of Prelude these constraints were not necessary.

Now in order to let it work, we first make Tree an instance of Functor. We therefore need to define a function fmap, which - for a given function f :: a -> b, maps a Tree a to a Tree b:

instance Functor Tree where
   fmap f (Leaf a) = Leaf $ f a
   fmap f (Fork u v) = Fork (fmap f u) (fmap f v)
   fmap _ Nil = Nil

Now that we have defined this, we can define Applicative:

instance Applicative Tree where
    pure = Leaf
    (<*>) (Leaf f) = fmap f
    (<*>) Nil = const $ Nil

and finally we can define the Monad instance:

instance Monad Tree where
   return a = Leaf a
   Nil >>= f = Nil
   Leaf a >>= f = f a
   Fork u v >>= f = Fork (u >>= f) (v >>= f)

Upvotes: 5

Related Questions