Haskell: Problems implementing a simple Monad case study

Question

I've began studying Monads by implementing a simple example, but my Monad instance does not compile.

I want to do something like:

add5 7 >>= add7

This code must return 19 [ (5 + 7) >>= (12+7) ]

The code i've implemented is:

newtype MyType a = MyType ( a -> a)

instance Monad MyType where
    MyType comm  >>= comm2  = MyType (\inp -> let
                                        value = comm inp 
                                        MyType comm2' = comm2
                                        in  comm2' value)
    return  x       = MyType (\input -> input)


add5 :: MyType Integer
add5 = MyType (\inp -> inp + 5)

add7 :: MyType Integer
add7 = MyType (\inp -> inp + 7)

When i call add5 and add7 without using bind operator (by commenting Monad instance block), it works:

main =  do 
        let MyType x = add5
        let MyType y = add7
        putStrLn $ show $ x $ y 7

The output errors are:

new1.hs:5:94:
    Couldn't match expected type `a' with actual type `b'
      `a' is a rigid type variable bound by
          the type signature for
            >>= :: MyType a -> (a -> MyType b) -> MyType b
          at new1.hs:4:9
      `b' is a rigid type variable bound by
          the type signature for
            >>= :: MyType a -> (a -> MyType b) -> MyType b
          at new1.hs:4:9
    In the first argument of `comm', namely `inp'
    In the expression: comm inp
    In an equation for `value': value = comm inp

new1.hs:6:97:
    Couldn't match expected type `MyType t0'
                with actual type `a -> MyType b'
    In the expression: comm2
    In a pattern binding: MyType comm2' = comm2
    In the expression:
      let
        value = comm inp
        MyType comm2' = comm2
      in comm2' value

I'm not sure you can make a `Monad` instance for that type of endomorphic functions. Removing the `newtype` wrappers, you need to implement a `(>>=)` with the type `(a -> a) -> (a -> (b -> b)) -> (b -> b)`. You can definitely make a `Monad` instance if you allow the argument type to be independent of the result type though (this would be the Reader monad). — David Young, Nov 27 '14 at 04:46

score 4 · Answer 1 · answered Nov 27 '14 at 09:24

4

It cannot be a Monad, because it is not even a Functor, since you have a type variable in the contravariant position.

This means you cannot implement:

fmap :: (a->b)->MyType a->MyType b

You can use f :: a->b to change the type of result in a->a to a->b, but you can't change the type of the argument to that function to get b->b, which is needed to construct MyType b.

answered Nov 27 '14 at 09:24

Sassa NF

5,306
15
22

Yes you can implement `fmap`. My first revision of my answer was almost yours. But `fmap f (MyType g) = MyType id` typechecks. The `id` functor law is violated, though. – Franky Nov 27 '14 at 10:09
@Franky that's a useless implementation. You could have just as well called it `Const`. And you can always plug `undefined`, too. The point is that it must work for any `a->a`. – Sassa NF Nov 27 '14 at 10:17
That `fmap` implementation is just as useless as the OP's `return`. – Franky Nov 27 '14 at 10:30
@Franky I think your suggestion is worse, because it really asserts that any `a` _as a type_ can be mapped into `a->a` _as a type_ - but only one point in `a->a` "behaves well". – Sassa NF Nov 27 '14 at 10:55
@Franky Put in other words, if you have a category with objects `a->a`, there are some arrows between them. What is their composition? Then embed it back into `Hask`. Your `fmap` must "hit" that composition, too, when mapping the composition of functions. You may want to pretend it is a `const`, but I am not convinced; you'd need to show the composition of arrows between `a->a` first. – Sassa NF Nov 27 '14 at 11:05
I don't really understand. Am I right that your `a` is actually the `b` of `fmap :: (a -> b)...`? That `id` in `fmap _ _ = MyType id` is of type `b -> b`, making the result `MyType b`. – Franky Nov 27 '14 at 11:06
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/65752/discussion-between-franky-and-sassa-nf). – Franky Nov 27 '14 at 11:08

score 4 · Accepted Answer · answered Nov 27 '14 at 11:03

I'm not sure what you actually want to do. If you simply want to get the code sample

add5 7 >>= add7

to work and produce a result of 19 by adding the numbers in the "obvious" way, then it is simple, and any monad will do. We can thus pick the simplest possible monad, the "identity" monad:

newtype Id a = Id { runId :: a }

instance Monad Id where
  return x   = Id x
  Id x >>= f = f x

Note that this code will produce warnings in GHC 7.8, because in the future, Applicative will become a superclass of monad and you'll have to define additional instances. For this example, they're irrelevant, so I'll omit them.

Now you can define add5 and add7:

add5 :: Id Int
add5 n = return (n + 5)

add7 :: Id Int
add7 n = return (n + 7)

If you omit the type signatures and ask GHCi, you'll see that both definition actually have the more general type (Num a, Monad m) => a -> m a. That's what I mean by saying that your example works for any monad.

You can try that it all works in GHCi:

GHCi> :t add5 7 >>= add7 
add5 7 >>= add7 :: Id Int
GHCi> runId (add5 7 >>= add7)
19

Franky · Answer 3 · 2014-11-27T07:38:37.560

You are on the wrong track. MyType cannot be a monad. The only monad instance implementation possible for MyType will be fairly trivial, and not able to make add5 7 >>= add7 equal 19.

>>= must have type

MyType a -> (a -> MyType b) -> MyType b -- remove newType
(a -> a) -> (a -> (b -> b)) -> (b -> b)

The only function that typechecks is

(MyType _) >>= _  = MyType (\input -> input)

which looks very similar to your return implemention. We usually write id instead of (\input -> input) in haskell.

Why do I claim this is the only function? Check the simplified type signature (a -> a) -> (a -> (b -> b)) -> (b -> b) again: Without an a as input, the arguments of >>=, a -> a and a -> (b -> b), cannot be evaluated.

This does not satisfy the monad laws: x >>= return = x

MyType (\x -> x + 1) >>= return
 =MyType id
/=MyType (\x -> x + 1)

score 1 · Answer 4 · edited May 23 '17 at 10:26

You don't need monads for what you are trying to do. Instead you can use the Arrows:

Prelude> :m + Control.Arrow
Prelude Control.Arrow> let add5 = (+5)
Prelude Control.Arrow> let add7 = (+7)
Prelude Control.Arrow> let add12 = add5 >>> add7
Prelude Control.Arrow> add12 7
19

The (>>>) function is just the composition operator (i.e. (.)) with its arguments flipped, for function instances. Hence you could just as simply do:

Prelude> let add5 = (+5)
Prelude> let add7 = (+7)
Prelude> let add12 = add7 . add5
Prelude> add12 7
19

There's already a monad instance for functions. It's called the reader monad: What is the purpose of the Reader Monad?.

instance Monad ((->) r) where
    return x = \_ -> x
    f >>= g = \x -> g (f x) x

It allows you to things like:

a2-minus-b2 = \a -> do
    a-minus-b <- (\b -> a - b)
    a-plus-b  <- (\b -> a + b)
    return (a-minus-b * a-plus-b)

Ofcourse it would be better just to write it as:

a2-minus-b2 = \a b -> (a - b) * (a + b)

However, I just wanted to show you what the reader monad can be used to do.

Correct me if I'm wrong, but I think that `Reader` and Monad instance for functions are completely irrelevant. (IOW, this answer is largely nonsense) — Bartek Banachewicz, Nov 27 '14 at 09:27

Haskell: Problems implementing a simple Monad case study

4 Answers4