[Haskell-cafe] The Trivial Monad

134 views
Skip to first unread message

Adrian Neumann

unread,
May 4, 2007, 3:40:47 AM5/4/07
to haskel...@haskell.org
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

I've read this blogpost about the "trivial monad"
http://sigfpe.blogspot.com/2007/04/trivial-monad.html, because I still
don't understand what this monad thingy is all about.

The author defines three functions:

data W a = W a deriving Show

return :: a -> W a
return x = W x

fmap :: (a -> b) -> (W a -> W b)
fmap f (W x) = W (f x)

bind :: (a -> W b) -> (W a -> W b)
bind f (W x) = f x

and asks the reader to prove the tree monad laws for them. However I
don't understand the type signatures for bind and fmap. I'd say (and
ghci's type inference agrees) that bind and fmap have the type

bind:: (a->W b) -> W a -> W b
fmap:: (a->b) -> W a -> W b

They take a function f and something and return what f does to that. I
don't see why they should return a function.

This of course makes it hard for me to prove the monad laws. The first
however works nonetheless:

1) bind f (return a)= f a

=> bind f (return a)= bind f (W a) = f a

Can someone explain bind and fmap (and possible law 2 and 3)?

Thanks,

Adrian
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGOuQS11V8mqIQMRsRCmngAJ9NwQMwXeS/PSM1NUsVA8gxPuA0KACfSLiA
ItqRZW5a4XyQ099bhMtSWmU=
=/8i/
-----END PGP SIGNATURE-----
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Thomas Davie

unread,
May 4, 2007, 3:52:54 AM5/4/07
to Adrian Neumann

On 4 May 2007, at 08:43, Adrian Neumann wrote:

> However I
> don't understand the type signatures for bind and fmap. I'd say (and
> ghci's type inference agrees) that bind and fmap have the type
>
> bind:: (a->W b) -> W a -> W b
> fmap:: (a->b) -> W a -> W b
>
> They take a function f and something and return what f does to that. I
> don't see why they should return a function.

I suggest you look up currying. In the mean time, I shall attempt an
explanation.

In Haskell (as in many other functional languages), function types
appear as if the function were curried. This means that a function
accepts one single argument, and returns one single result. The
important thing to realise though is that the result (or less
importantly the argument) may be a function.

Let's study a (slightly over constrained) variant on the (+)
function, with type (+) :: Int -> Int -> Int. This type signature
should be read to mean:

(+) takes an Int, and returns a new function of type (Int -> Int).
We can see an example of this (+ 5) -- (+) is given an argument (5),
and returns a function (that adds 5 to integers).

Another way to think about it is that the (->) type constructor is
right associative, so any type written as a -> b -> c -> d -> e, can
also be written as a -> (b -> (c -> (d -> e))).

I hope that helped a bit, and if it didn't I suggest going and
looking up currying in as many places as you can.

Bob

Michael Vanier

unread,
May 4, 2007, 3:55:56 AM5/4/07
to Adrian Neumann
The -> in type signatures associates to the right, so the type signatures

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

> bind :: (a -> W b) -> (W a -> W b)

are the same as:

> fmap :: (a -> b) -> W a -> W b
> bind :: (a -> W b) -> W a -> W b

Sometimes people put in the extra parentheses because they want to
emphasize a particular way to use the function.

I'm assuming you understand that a function that takes two arguments and
returns a (possibly non-function) value is equivalent to a function that
takes one argument that returns a function that takes the other argument
and returns a value.

HTH,

Mike

Dan Piponi

unread,
May 4, 2007, 12:48:05 PM5/4/07
to Adrian Neumann, haskell-cafe
Hi Adrian,

> They take a function f and something and return what f does to that. I
> don't see why they should return a function.

Consider a function, f, that takes two arguments, one of type A, and
one of type B, and returns something of type C. In conventional
mathematical notation this would be written as f : A x B -> C.

Think about what this function does from a practical point of view. It
waits to be handed an object of type A. It then waits for an object of
type B. And now it can return an object of type C.

But suppose we hand f an object of type A, but not another of type B.
What do we get? Well we basically have something that's still waiting
for an object of type B, and when it gets that it'll return an object
of type C. Something that's waiting for a B in order to give you a C
is of type B->C. So after you've given f an A, you get back a B->C. So
f can be thought of as being of type A->(B->C).

So there are two ways of thinking of f. (1) A function that takes an A
and a B and gives you a C. Or (2) a function that takes an A and gives
you back a function mapping a B to a C. Haskell blurs the distinction
between these things and the transition from view (1) to view (2) is
called 'currying'.

Internally, the Haskell parser automatically converts A->B->C to
A->(B->C) so you can view the former as simply being shorthand for the
latter. (In CS-speak '->' is considered to be right associative but
that's just another way of saying the same thing.)
--
Dan

Bulat Ziganshin

unread,
May 4, 2007, 1:02:02 PM5/4/07
to Adrian Neumann
Hello Adrian,

Friday, May 4, 2007, 11:43:35 AM, you wrote:

> don't understand what this monad thingy is all about.

the whole monadic business was introduced with the sole goal to let
haskellers believe that they are smarter than other programmers :)


--
Best regards,
Bulat mailto:Bulat.Z...@gmail.com

Derek Elkins

unread,
May 4, 2007, 1:05:04 PM5/4/07
to Bulat Ziganshin, Adrian Neumann, haskel...@haskell.org
Bulat Ziganshin wrote:
> Hello Adrian,
>
> Friday, May 4, 2007, 11:43:35 AM, you wrote:
>
>> don't understand what this monad thingy is all about.
>
> the whole monadic business was introduced with the sole goal to let
> haskellers believe that they are smarter than other programmers :)

Indeed. Continuation-based IO would have been so much clearer.

Dan Piponi

unread,
May 4, 2007, 7:58:26 PM5/4/07
to Derek Elkins
I don't know anything about Continuation-based IO. Is there a
reference online I could read about it?
--
Dan

Derek Elkins

unread,
May 4, 2007, 9:00:49 PM5/4/07
to Dan Piponi, haskel...@haskell.org
Dan Piponi wrote:
> I don't know anything about Continuation-based IO. Is there a
> reference online I could read about it?

Many of the hits you get from putting 'Haskell "continuation-based IO" into
Google give some information. But here is one reasonable paper on it
http://citeseer.ist.psu.edu/hudak89expressiveness.html
"On the Expressiveness of Purely-Functional I/O Systems" Hudak 1989. (Also, one
may want to look at "The Essence of Functional Programming".)

Note, however, that I was being sardonic in my previous email.

Dan Piponi

unread,
May 4, 2007, 9:39:14 PM5/4/07
to Derek Elkins
On 5/4/07, Derek Elkins <derek.a...@gmail.com> wrote:
> Dan Piponi wrote:
> > I don't know anything about Continuation-based IO. Is there a
> > reference online I could read about it?

> Note, however, that I was being sardonic in my previous email.

Nonetheless, I'd never heard of it, it sounds intriguing, and I
couldn't find anything with google that succinctly explained what it
was. So thanks for the link.
--
Dan

Ketil Malde

unread,
May 7, 2007, 5:48:08 AM5/7/07
to Bulat Ziganshin
On Fri, 2007-05-04 at 20:02 +0400, Bulat Ziganshin wrote:

>> don't understand what this monad thingy is all about.

> the whole monadic business was introduced with the sole goal to let
> haskellers believe that they are smarter than other programmers :)

Or perhaps to ensure that they are?

-k

Bulat Ziganshin

unread,
May 8, 2007, 5:00:18 AM5/8/07
to Ketil Malde
Hello Ketil,

>> the whole monadic business was introduced with the sole goal to let
>> haskellers believe that they are smarter than other programmers :)

> Or perhaps to ensure that they are?

you mean Darwin's idea of natural selection? :)

--
Best regards,
Bulat mailto:Bulat.Z...@gmail.com

_______________________________________________

Reply all
Reply to author
Forward
0 new messages