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
> 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.
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.
> 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
> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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".)
On 5/4/07, Derek Elkins <derek.a.elk...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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 :)
>> 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.Zigans...@gmail.com
