Okay, I still can't read. Now I was confusing this with the GHC only patch. I'll back away slowly, now. On Sun, Jan 2, 2011 at 9:49 AM, Antoine Latter wrote:

Ah! Yup, I just noticed.

I can't read, apparently :-)

Yeah, I get irritated whenever I come across a Monad instance and I cannot use the Applicative combinators. So I guess I'm in favor.

Is there a reason this is appropriate for the libraries process? Do any of these changes spill out into the public interface of base or GHC.Ext?

Sorry for the confusion, Antoine

On Sun, Jan 2, 2011 at 9:46 AM, John Smith wrote:

...

On 02/01/2011 14:04, John Smith wrote:

...

Please note that although the ticket references the wiki page at http://haskell.org/haskellwiki/Functor-Applicative-Monad_Proposal, the patches attached to the ticket are much more conservative than the more ambitious reforms on the wiki. (I would like to change the ticket description to make this clearer, but I can't edit it.)

To clarify - this proposal is to implement just the patches attached to the ticket, /not/ everything in the related wiki page.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

On 2 January 2011 17:50, John Smith wrote:

The Haskell' process expects proposals to have already been implemented, so I'll propose it there after acceptance by GHC. If the patches are accepted for HEAD, this may be adequate for proposing towards the next Haskell report, so GHC and the report will only be out of sync for a minimal time.

Someone in the previous discussion (might have been me...) suggested that the Haskell Prime committee might want a different criteria for library changes than the one it has language extensions. A change like this one would be particularly disruptive outside a language revision, but a lot more tolerable as part of one.

On Sun, Jan 2, 2011 at 9:04 PM, Isaac Dupree wrote:

On 01/02/11 12:50, John Smith wrote:

...

On 02/01/2011 19:14, David Menendez wrote:

...

On Sun, Jan 2, 2011 at 7:04 AM, John Smith wrote:

...

The patches attached to http://hackage.haskell.org/trac/ghc/ticket/4834 make Applicative a superclass of Monad. Default definitions are provided for backwards compatibility.

Monad is defined in the Haskell 98 and Haskell 2010 reports. How are you planning to maintain compatibility with them?

The Haskell' process expects proposals to have already been implemented, so I'll propose it there after acceptance by GHC. If the patches are accepted for HEAD, this may be adequate for proposing towards the next Haskell report, so GHC and the report will only be out of sync for a minimal time.

Even GHC 7.100 is intended to maintain compatibility with Haskell 98. We desire a way to implement the change that allows Haskell 98 and Haskell 2010 programs to compile unchanged, *even if* Haskell 2011 Report includes libraries with a Monad hierarchy change.

The naive way to do this is to make a different Monad class, without any superclasses, and put it in the haskell98 package.  This has the general issue that instances of the two "class Monad"s aren't compatible.  I think it also has a particular difficulty related to "do"-notation.

GHC supports the notion of a 'language' command line switch. I don't know how hard it would be to co-opt it to control 'do' desugaring. Also, there would need to be a value for language other than 'haskell98' and 'haskell2010' to turn on the new behavior. This is all brainstorming, and may not be appropriate for a consensus discussion, and may not be feasible for other reasons. I also don't know if other implementations (or even GHC) would be willing to take on this sort of complexity burden. Antoine

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

On Mon, Jan 3, 2011 at 12:43 PM, Ian Lynagh wrote:

On Sun, Jan 02, 2011 at 06:27:04PM -0800, Iavor Diatchki wrote:

...

I think that it would be useful if there was a wiki page which describes the proposal exactly, so that we can discuss the details

I agree. I'm confused as to what is part of the proposal, what are other changes necessary due to the classes changing, what are orthogonal cleanups, and what is not being proposed.

The patch for base makes a few changes: 1) Make Applicative a superclass of Monad. So the new hierarchy becomes: class Functor f where fmap :: (a -> b) -> f a -> f b (<$) :: a -> f b -> f a (<$) = fmap . const class Functor f => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b (*>) :: f a -> f b -> f b a *> b = fmap (const id) a <*> b (<*) :: f a -> f b -> f a a <* b = fmap const a <*> b class Applicative m => Monad m where (>>=) :: forall a b. m a -> (a -> m b) -> m b m >>= f = join $ fmap f m join :: m (m a) -> m a join m = m >>= id (>>) :: forall a b. m a -> m b -> m b (>>) = (*>) return :: a -> m a return = pure fail :: String -> m a fail s = error s 2) Make 'join' a method of Monad. 3) Export Applicative(pure, (<*>), (*>), (<*)) from the Prelude. (Maybe we shouldn't export the (*>) and (<*) methods.) 4) Also export the join method from the Prelude. 5) Add Applicative instances for all monads in base. 6) Add a Monad instance for ((,) a): (There are already Functor and Applicative instances for it.) instance Monoid a => Monad ((,) a) where (u, x) >>= f = let (v, y) = f x in (u `mappend` v, y) (Maybe this one should be left out of the patch) The patch for ghc simply adds Applicative instances for all monads in ghc. Also included in the ghc patch bundle are some refactoring patches that will make the transition easier: * Added (<>) = mappend to compiler/utils/Util.hs. * Add a Monoid instance for AGraph and remove the <*> splice operator. Instead of <*>, the (<>) = mappend operator is now used to splice AGraphs. This change is needed because <*> clashes with the Applicative apply operator <*>, which is probably going to be exported from the Prelude when the new Monad hierarchy is going through. (Simply hiding <*> from the Prelude is also possible of course. However, I think this makes things easier to understand) * Make SDoc an abstract newtype and add a Monoid instance for it. The (<>) combinator of SDocs is removed and replaced by the more general (<>) = mappend combinator from Util. Note that all the ghc patches can be applied independently of the base patch. Now which notable things are not included in the patch for base: * fmap is not renamed to map. * return and (>>) are not removed as a method. * fail is not removed as a method. * All the liftM functions are not removed in favour of fmap and liftAs. I think these are better left as separate proposals. Regards, Bas

On 1/3/11 7:22 PM, Isaac Dupree wrote:

On 01/03/11 17:30, Bas van Dijk wrote:

...

... The patch for base makes a few changes:

1) Make Applicative a superclass of Monad. So the new hierarchy becomes:

2) Make 'join' a method of Monad. ... class Applicative m => Monad m where ... (>>) :: forall a b. m a -> m b -> m b (>>) = (*>)

The former/current default definition of (>>) was based on (>>=), not (*>) (which if itself is undefined, itself defaults to (fmap (const id) a <*> b). That's a change.

Yes, that is a change.

You also added defaults for most of the Monad methods, though they're obvious and I approve. The (>>) default might have worse performance than the previous default though?

Nope. Since (*>) is a class method it can be given the most efficient implementation possible for the given type. Since (>>) is logically the same function, then it should default to (*>) so that the efficient implementation doesn't need to be duplicated. In the event that neither is defined explicitly, then they will both default to the same definition as pre-patch. -- Live well, ~wren

Thanks for the detailed clarification, I've copied this message to the wiki page On 04/01/2011 00:30, Bas van Dijk wrote:

The patch for base makes a few changes:

1) Make Applicative a superclass of Monad. So the new hierarchy becomes:

class Functor f where fmap :: (a -> b) -> f a -> f b

(<$) :: a -> f b -> f a (<$) = fmap . const

class Functor f => Applicative f where pure :: a -> f a

(<*>) :: f (a -> b) -> f a -> f b

(*>) :: f a -> f b -> f b a *> b = fmap (const id) a<*> b

(<*) :: f a -> f b -> f a a<* b = fmap const a<*> b

class Applicative m => Monad m where (>>=) :: forall a b. m a -> (a -> m b) -> m b m>>= f = join $ fmap f m

join :: m (m a) -> m a join m = m>>= id

(>>) :: forall a b. m a -> m b -> m b (>>) = (*>)

return :: a -> m a return = pure

fail :: String -> m a fail s = error s

2) Make 'join' a method of Monad.

3) Export Applicative(pure, (<*>), (*>), (<*)) from the Prelude. (Maybe we shouldn't export the (*>) and (<*) methods.)

4) Also export the join method from the Prelude.

5) Add Applicative instances for all monads in base.

6) Add a Monad instance for ((,) a): (There are already Functor and Applicative instances for it.)

instance Monoid a => Monad ((,) a) where (u, x)>>= f = let (v, y) = f x in (u `mappend` v, y)

(Maybe this one should be left out of the patch)

The patch for ghc simply adds Applicative instances for all monads in ghc. Also included in the ghc patch bundle are some refactoring patches that will make the transition easier:

* Added (<>) = mappend to compiler/utils/Util.hs. * Add a Monoid instance for AGraph and remove the<*> splice operator. Instead of<*>, the (<>) = mappend operator is now used to splice AGraphs. This change is needed because<*> clashes with the Applicative apply operator<*>, which is probably going to be exported from the Prelude when the new Monad hierarchy is going through. (Simply hiding<*> from the Prelude is also possible of course. However, I think this makes things easier to understand) * Make SDoc an abstract newtype and add a Monoid instance for it. The (<>) combinator of SDocs is removed and replaced by the more general (<>) = mappend combinator from Util.

Note that all the ghc patches can be applied independently of the base patch.

Now which notable things are not included in the patch for base:

* fmap is not renamed to map. * return and (>>) are not removed as a method. * fail is not removed as a method. * All the liftM functions are not removed in favour of fmap and liftAs.

I think these are better left as separate proposals.

Regards,

Bas

On Tue, Jan 4, 2011 at 1:25 PM, Ian Lynagh wrote:

On Mon, Jan 03, 2011 at 11:30:44PM +0100, Bas van Dijk wrote:

...

1) Make Applicative a superclass of Monad. So the new hierarchy becomes:

class Applicative m => Monad m  where

...

Now which notable things are not included in the patch for base:

* fmap is not renamed to map. * return and (>>) are not removed as a method. * fail is not removed as a method. * All the liftM functions are not removed in favour of fmap and liftAs.

I think these are better left as separate proposals.

OK, but I think it would be good to get any changes into a single release, so people only need to fix their instances once.

...

    (>>=) :: forall a b. m a -> (a -> m b) -> m b     m >>= f = join $ fmap f m

    join :: m (m a) -> m a     join m = m >>= id

Have you got an example of a Monad for which you'd want to define join but not (>>=)?

...

    (>>) :: forall a b. m a -> m b -> m b     (>>) = (*>)

    return :: a -> m a     return = pure

    fail :: String -> m a     fail s = error s

2) Make 'join' a method of Monad.

Why?

Of course I'm only a sample size of one, but I find join a lot easier to think about and implement than (>>=). Even trying to look at it objectively and factor out my own potential idiosyncracies, it's obvious that it only has one argument to (>>=)'s two, and the type signature looks a lot more straightforward any way I slice it. I was very glad to see this proposal to make it possible to define a Monad using return (pure), fmap, and join, rather than return and (>>=). I also recall reading somewhere that mathematically speaking join is the more significant operation but I'll leave that to the experts.

...

6) Add a Monad instance for ((,) a): (There are already Functor and Applicative instances for it.)

(Maybe this one should be left out of the patch)

It does sound like a separate issue.

Thanks Ian

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Work is punishment for failing to procrastinate effectively.

Gábor Lehel schrieb:

On Tue, Jan 4, 2011 at 1:25 PM, Ian Lynagh wrote:

...

On Mon, Jan 03, 2011 at 11:30:44PM +0100, Bas van Dijk wrote:

...

2) Make 'join' a method of Monad.

Why?

Of course I'm only a sample size of one, but I find join a lot easier to think about and implement than (>>=). Even trying to look at it objectively and factor out my own potential idiosyncracies, it's obvious that it only has one argument to (>>=)'s two, and the type signature looks a lot more straightforward any way I slice it. I was very glad to see this proposal to make it possible to define a Monad using return (pure), fmap, and join, rather than return and (>>=).

Mathematically I like 'join' more than '>>=', but for RMonads like StorableVector you will in general be able to define a '>>=' but not 'join'. Of course, you can ignore this reason, because Monad is not RMonad, but for reasons of consistency it might count.

Hello, I am also skeptical about the need to add "join" to the monad class. My reasoning is that I doubt that one can define an instance where "join" and "bind" perform differently, so we are just adding overhead, both cognitive (because the Monad class get more complex) and resource-wise (because dictionaries need to carry an additional method). Note that if you find "join" easier to define then "bind" (which I'd be surprised for any monad other then lists), you can still do just that: define "join", and then define "bind" in the usual way. In terms of the "symmetry" that Tyson mention, this is how I like to think about the three applications: fmap :: (a -> b) -> f a -> f b (<*>) :: f (a -> b) -> f a -> f b (=<<) :: (a -> f b) -> f a -> f b So really, (=<<) seems the most symmetric to me, but I don't think that the pain of changing the class to use (=<<) would really be justified. I completely agree with Ian that it'd be better to get all changes in a single proposal, so that we only need to fix things once, so let's at least drop the duplicated methods. -Iavor On Tue, Jan 4, 2011 at 7:51 AM, Tyson Whitehead wrote:

On January 4, 2011 07:25:36 Ian Lynagh wrote:

...

Have you got an example of a Monad for which you'd want to define join but not (>>=)?

...

(>>) :: forall a b. m a -> m b -> m b (>>) = (*>)

return :: a -> m a return = pure

fail :: String -> m a fail s = error s

2) Make 'join' a method of Monad.

Why?

It seems to me that while join is more of a value transformer as apposed to a flow combining operator, which makes it fit in better with the rest applicative.

That is,

(<*>) :: f (a -> b) -> f a -> f b -- (<*>) f -- transforms f join :: f (f a) -> f a -- join y -- transforms y return :: a -> f a -- return x -- transforms x

Cheers! -Tyson

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

On January 4, 2011 13:53:22 Maciej Piechotka wrote:

The bind is always harder as join x == x >>= id so join have 1 parameter known. In some cases it is large simplification (see Writer).

That's a very nice explanation. I also find join is quite a bit clearer for me to think about in terms of exactly what additional power monad gives you over applicative. In applicative the outer computations can not access the results of inner computations to react to them (values can only be injected inwards). Thus the sequence/structure of the outer computation is independent of the inner one. (presumably this strong guarantee makes various optimizations possible -- making it a shame to use a full blown monad when only applicative is needed) Join makes makes the results of inner computations available to outer ones. This allows the outer computation to react to the specifics of the inner one, which is the additional power/complexity of a monad (e.g., my next IO action can depend on the actual content of the file read in my previous IO action). Cheers! -Tyson

Hi, On Wed, Jan 5, 2011 at 8:04 AM, wrote:

On Tue, 4 Jan 2011, Iavor Diatchki wrote: In my completion monad, "join" is more efficent than "bind id"

This suggests that your monad will work less efficiently if you use it with the do-notation. Join and bind are very similar and, at least in standard Haskell code, I think that "bind" has proven to be a lot more useful then "join". Also, as I mentioned before, if people find "join" easier to define then "bind", then they can define "join", and then define "bind" in terms of that---I am still not convinced that we need a new method added to the Monad class. -Iavor

On Wed, 2011-01-05 at 10:03 -0800, Iavor Diatchki wrote:

Hi,

On Wed, Jan 5, 2011 at 8:04 AM, wrote: On Tue, 4 Jan 2011, Iavor Diatchki wrote: In my completion monad, "join" is more efficent than "bind id"

This suggests that your monad will work less efficiently if you use it with the do-notation.

Join and bind are very similar and, at least in standard Haskell code, I think that "bind" has proven to be a lot more useful then "join".

Also, as I mentioned before, if people find "join" easier to define then "bind", then they can define "join", and then define "bind" in terms of that---I am still not convinced that we need a new method added to the Monad class.

-Iavor

I think that's the least of the problems. The method may not even be exported by Prelude just like (<$), which can be defined in terms of fmap. Regards

Hi, On Wed, Jan 5, 2011 at 3:29 PM, wrote:

On Wed, 5 Jan 2011, Iavor Diatchki wrote:

Hi,

...

On Wed, Jan 5, 2011 at 8:04 AM, wrote: On Tue, 4 Jan 2011, Iavor Diatchki wrote: In my completion monad, "join" is more efficent than "bind id"

This suggests that your monad will work less efficiently if you use it with the do-notation.

No. If I need to use fmap, there is no getting around it. Only if I use "bind id" is it faster to use "join".

I am not familiar with your monad but if you are not making essential use of "bind" (or join and fmap together), then perhaps the monadic structure is not particularly important?

Join and bind are very similar and, at least in standard Haskell code, I

...

think that "bind" has proven to be a lot more useful then "join".

AFAIU, In applicative style programming "join" has proven to be a lot more useful than "bind".

I am not sure what you mean here, I find the "do" notation quite useful.

Also, as I mentioned before, if people find "join" easier to define then

...

"bind", then they can define "join", and then define "bind" in terms of that---I am still not convinced that we need a new method added to the Monad class.

If people find "bind" easier to define "join", then they can define "bind", and then define "join" in terms of that---Your argument is totally symetric in the terms "bind" and "join".

The situation is not symmetric because we already have a class with ">>=" and lots of code which depends on it---so I don't think that replacing ">>=" with "join" is really plausible (I would certainly not support such a change). I am not convinced that adding "join" to the class, in addition to ">>=", buys us anything but complexity. -Iavor

On Thu, 6 Jan 2011, Tyson Whitehead wrote:

On January 6, 2011 11:42:09 Iavor Diatchki wrote:

...

...

AFAIU, In applicative style programming "join" has proven to be a lot more useful than "bind".

I am not sure what you mean here, I find the "do" notation quite useful.

I think he was meaning when you are using monads in a more "function style" (applicative) than "imperative style" (do notation).

As an example, consider the definition of ">>=" using join and the "$" and "<$>" application operators

x >>= f = join $ f <$> x

versus that using "do" notation

x >>= f = do x' <- x f x'

Notice that in the applicative style we didn't need to name the "x'" value. To add to this excellet comment, the idea of applicative style is to use a long string of functions and parameters with various <$> and <*> in between them with the occassional peppering of join and other combinators. I understand this is becomming quite popular with parser combinators. e.g. (this example is from mm_freak): char '(' *> skipSpace *> someToken <* skipSpace <* char ')' Haskell is famous for allowing users the choice of multiple programming styles: * matching on the LHS vs case statements on the RHS * where clauses vs let statements * 2-D layout vs braces and semi-colons Given this, it seems only appropriate to support both applicative style and do notation programming. -- Russell O'Connor http://r6.ca/ ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''

On Thu, 6 Jan 2011, Maciej Piechotka wrote:

Maybe better example:

doA :: String -> String -> String -> IO String doB :: IO String

doC = join $ doA <$> doB <*> doB <*> doB

vs.

doC = do x <- doB y <- doB z <- doB doA x y z

This is a good illustration. Notice how the intermediate variables don't have to be named. -- Russell O'Connor http://r6.ca/ ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''

Since this seems to be a contentious part of this proposal, can we table it and have it in its own proposal? I think having it on its own would make a lot of since, as this is the sort of change that can happen with almost no concern for backwards compatibility - we don't need to tie it to the rest of the compatibility breaking changes. Antoine 2011/1/6 Gábor Lehel :

On Thu, Jan 6, 2011 at 5:42 PM, Iavor Diatchki wrote:

...

Hi,

On Wed, Jan 5, 2011 at 3:29 PM, wrote:

...

On Wed, 5 Jan 2011, Iavor Diatchki wrote:

...

Hi,

On Wed, Jan 5, 2011 at 8:04 AM, wrote:      On Tue, 4 Jan 2011, Iavor Diatchki wrote:      In my completion monad, "join" is more efficent than "bind id"

This suggests that your monad will work less efficiently if you use it with the do-notation.

No.  If I need to use fmap, there is no getting around it.  Only if I use "bind id" is it faster to use "join".

I am not familiar with your monad but if you are not making essential use of "bind" (or join and fmap together), then perhaps the monadic structure is not particularly important?

...

...

Join and bind are very similar and, at least in standard Haskell code, I think that "bind" has proven to be a lot more useful then "join".

AFAIU, In applicative style programming "join" has proven to be a lot more useful than "bind".

I am not sure what you mean here, I find the "do" notation quite useful.

...

...

Also, as I mentioned before, if people find "join" easier to define then "bind", then they can define "join", and then define "bind" in terms of that---I am still not convinced that we need a new method added to the Monad class.

If people find "bind" easier to define "join", then they can define "bind", and then define "join" in terms of that---Your argument is totally symetric in the terms "bind" and "join".

The situation is not symmetric because we already have a class with ">>=" and lots of code which depends on it---so I don't think that replacing ">>=" with "join" is really plausible (I would certainly not support such a change).  I am not convinced that adding "join" to the class, in addition to ">>=", buys us anything but complexity. -Iavor

I'm not sure what you mean here by "replace" -- to _remove_ bind from Monad, and add join instead? I don't know of anyone proposing this.

You're perfectly correct that it's possible to define a standalone join function yourself, and then write in what would be the proposed default definition for bind manually -- but roconnor is also perfectly correct that if the situation were the other way around, the same thing would be true in reverse. In other words, the argument is that the situation with bind being a method of Monad and join not being such is a historical accident, and not one supported by the merits.

The fact that you can still write the function outside the class and define the class method in terms of it manually is true of approximately every class method and standalone function ever written. We could write all of our classes so that the most complicated and impressive functions are the methods, while defining the simple ones standalone in terms of those, with perhaps only a small amount of annoyance overhead resulting for our users -- but we don't. We tend to seek the ability to write minimal class definitions using the simplest and most straightforward methods we can find. It sends a message: this is the easiest/best way to write an instance. If you resort to writing what should've been a method as a standalone function instead and defining the method in terms of it, the message it sends is "the definition of this class is flawed and I'm working around it". But most people probably don't think of doing this, and just define the simplest out of whatever methods they are given. After all, writing simple functions and then defining the more complex ones as combinations of those is what Haskell is all about, isn't it? So we should strive to support that, even if it can be done in our spite when we don't.

And as has been argued at length in this thread, for a great many types it is easier, cognitively if not physically, to define fmap and join than to define bind. (And for the others, like Oleg's example, they can just say fmap = liftM and keep merrily on.) It was actually thinking about the type signature of join which made the whole Monad thing finally 'click' for me, which isn't bad considering that Applicative has only about halfway clicked so far. It absolutely feels more fundamental as an operation than bind does, even if bind might be the more useful combinator.

There's also the consideration that when defining instances for a new type, many (most?) people tend to write an instance for the superest class in a hierarchy first, and then to work their way down. (Even without the hierarchy being explicit a lot of people, myself included, already do this for Functor/Applicative/Monad). So by the time they get to Monad they have an fmap already written, and they're like -- "why do I have to reimplement essentially the same functionality again as part of (>>=)? Oh wait, here's join instead, that'll be easier."

...

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Work is punishment for failing to procrastinate effectively.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

2011/1/6 Gábor Lehel :

On Thu, Jan 6, 2011 at 5:42 PM, Iavor Diatchki wrote:

...

Hi,

On Wed, Jan 5, 2011 at 3:29 PM, wrote:

...

On Wed, 5 Jan 2011, Iavor Diatchki wrote:

...

Hi,

On Wed, Jan 5, 2011 at 8:04 AM, wrote:      On Tue, 4 Jan 2011, Iavor Diatchki wrote:      In my completion monad, "join" is more efficent than "bind id"

This suggests that your monad will work less efficiently if you use it with the do-notation.

No.  If I need to use fmap, there is no getting around it.  Only if I use "bind id" is it faster to use "join".

I am not familiar with your monad but if you are not making essential use of "bind" (or join and fmap together), then perhaps the monadic structure is not particularly important?

...

...

Join and bind are very similar and, at least in standard Haskell code, I think that "bind" has proven to be a lot more useful then "join".

AFAIU, In applicative style programming "join" has proven to be a lot more useful than "bind".

I am not sure what you mean here, I find the "do" notation quite useful.

...

...

Also, as I mentioned before, if people find "join" easier to define then "bind", then they can define "join", and then define "bind" in terms of that---I am still not convinced that we need a new method added to the Monad class.

If people find "bind" easier to define "join", then they can define "bind", and then define "join" in terms of that---Your argument is totally symetric in the terms "bind" and "join".

The situation is not symmetric because we already have a class with ">>=" and lots of code which depends on it---so I don't think that replacing ">>=" with "join" is really plausible (I would certainly not support such a change).  I am not convinced that adding "join" to the class, in addition to ">>=", buys us anything but complexity. -Iavor

I'm not sure what you mean here by "replace" -- to _remove_ bind from Monad, and add join instead? I don't know of anyone proposing this.

You're perfectly correct that it's possible to define a standalone join function yourself, and then write in what would be the proposed default definition for bind manually -- but roconnor is also perfectly correct that if the situation were the other way around, the same thing would be true in reverse. In other words, the argument is that the situation with bind being a method of Monad and join not being such is a historical accident, and not one supported by the merits.

The fact that you can still write the function outside the class and define the class method in terms of it manually is true of approximately every class method and standalone function ever written. We could write all of our classes so that the most complicated and impressive functions are the methods, while defining the simple ones standalone in terms of those, with perhaps only a small amount of annoyance overhead resulting for our users -- but we don't. We tend to seek the ability to write minimal class definitions using the simplest and most straightforward methods we can find. It sends a message: this is the easiest/best way to write an instance. If you resort to writing what should've been a method as a standalone function instead and defining the method in terms of it, the message it sends is "the definition of this class is flawed and I'm working around it". But most people probably don't think of doing this, and just define the simplest out of whatever methods they are given. After all, writing simple functions and then defining the more complex ones as combinations of those is what Haskell is all about, isn't it? So we should strive to support that, even if it can be done in our spite when we don't.

And as has been argued at length in this thread, for a great many types it is easier, cognitively if not physically, to define fmap and join than to define bind. (And for the others, like Oleg's example, they can just say fmap = liftM and keep merrily on.) It was actually thinking about the type signature of join which made the whole Monad thing finally 'click' for me, which isn't bad considering that Applicative has only about halfway clicked so far. It absolutely feels more fundamental as an operation than bind does, even if bind might be the more useful combinator.

There's also the consideration that when defining instances for a new type, many (most?) people tend to write an instance for the superest class in a hierarchy first, and then to work their way down. (Even without the hierarchy being explicit a lot of people, myself included, already do this for Functor/Applicative/Monad). So by the time they get to Monad they have an fmap already written, and they're like -- "why do I have to reimplement essentially the same functionality again as part of (>>=)? Oh wait, here's join instead, that'll be easier."

As a yet further note, it seems that the comonads package[1] defines the Comonad class in an analogous way, with the analogues for return, join, and bind (extract, duplicate, and extend) being the methods, default definitions given in terms of each other, and also an external liftW function defined in terms of extend (~bind) which is recommended as a simple definition for fmap for when extend has already been defined. So I'm not the only one who feels this structure is logical. [1] http://hackage.haskell.org/packages/archive/comonad/0.1.1/doc/html/Control-C...

...

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- Work is punishment for failing to procrastinate effectively.

-- Work is punishment for failing to procrastinate effectively.

Hello, In my experience, defining monads in terms of "fmap" and "join" leads to code duplication. The examples we have seen in this thread---so far---are a bit misleading because they compare a partial implementation of a monad (join without fmap) with a complete implementation (bind). Here is an example of what I mean: data SP a = PutChar Char (SP a) | GetChar (Char -> SP a) | Return a fmapSP :: (a -> b) -> (SP a -> SP b) fmapSP f (PutChar c sp) = PutChar c (fmapSP f sp) fmapSP f (GetChar k) = GetChar (\c -> fmapSP f (k c)) fmapSP f (Return a) = Return (f a) joinSP :: SP (SP a) -> SP a joinSP (PutChar c sp) = PutChar c (joinSP sp) joinSP (GetChar k) = GetChar (\c -> joinSP (k c)) joinSP (Return sp) = sp bindSP :: (a -> SP b) -> (SP a -> SP b) bindSP f (PutChar c sp) = PutChar c (bindSP f sp) bindSP f (GetChar k) = GetChar (\c -> bindSP f (k c)) bindSP f (Return a) = f a I chose this example because I think that it illustrates nicely how the three operators work, I hope that other readers find it useful. 2011/1/9 Conal Elliott

* The familiarity advantage of (>>=) is a historical accident. I like to see the language improve over time, rather than accumulate accidents.

I would be surprised if choosing ">>=" was an accident: it seems more likely that it was chosen because it matches a commonly occurring pattern in functional programs, and abstraction is all about giving names to common patterns. I completely agree with the sentiment of your second sentence but I think that adding "join" to the Monad class would be an example of "accumulating an accident" rather then simplifying things. -Iavor

On Sun, 2011-01-09 at 18:16 -0800, Iavor Diatchki wrote:

Hello, In my experience, defining monads in terms of "fmap" and "join" leads to code duplication. The examples we have seen in this thread---so far---are a bit misleading because they compare a partial implementation of a monad (join without fmap) with a complete implementation (bind). Here is an example of what I mean:

data SP a = PutChar Char (SP a) | GetChar (Char -> SP a) | Return a

fmapSP :: (a -> b) -> (SP a -> SP b) fmapSP f (PutChar c sp) = PutChar c (fmapSP f sp) fmapSP f (GetChar k) = GetChar (\c -> fmapSP f (k c)) fmapSP f (Return a) = Return (f a)

joinSP :: SP (SP a) -> SP a joinSP (PutChar c sp) = PutChar c (joinSP sp) joinSP (GetChar k) = GetChar (\c -> joinSP (k c)) joinSP (Return sp) = sp

bindSP :: (a -> SP b) -> (SP a -> SP b) bindSP f (PutChar c sp) = PutChar c (bindSP f sp) bindSP f (GetChar k) = GetChar (\c -> bindSP f (k c)) bindSP f (Return a) = f a

I chose this example because I think that it illustrates nicely how the three operators work, I hope that other readers find it useful.

Yes and no: 1. In monad transformers & co. you want weakened conditions on Functor and Applicative so you cannot reuse (>>=) in them - you end up with a function anyway. 2. I don't recall anyone claiming it is shorter - the only claim was that it was simpler to think of (for some people) and 'nicer' from mathematical standpoint. Simplifying problem is common technique so I guess that defence of join is unharmed. Say - you want to prove linearity of function φ - you can either: 1. Prove aφ(x) = φ(ax) and φ(x) ⊕ φ(y) = φ(x + y) 2. Prove aφ(x) ⊕ bφ(y) = φ(ax + by) Which one do you choose? well it depends on φ and your skills. If φ is simple you and you have done it before you may prefer the 2. Otherwise you may prefer 1 even if it longer.

2011/1/9 Conal Elliott * The familiarity advantage of (>>=) is a historical accident. I like to see the language improve over time, rather than accumulate accidents.

I would be surprised if choosing ">>=" was an accident: it seems more likely that it was chosen because it matches a commonly occurring pattern in functional programs, and abstraction is all about giving names to common patterns.

Yes and no. Common pattern is function of form (read :: Read a => String -> a) - surprisingly it is not the one you define as it is too limited. (>>=) is probably better described as 'what happens' and functional programming is not about what happens but what people want to achieve (usually (>>=) but not always) or what people find easier to think about (quick survey of this thread point into direction of join). PS. As of simplifying. I have a feeling that the thread is: around 6 people with opinion (sorry if I've counted incorrectly): - Ok - sometimes (>>=) is simpler for implementation sometimes join so adding join would allow to choose simpler one or favourite 1 person with opinion - But (>>=) is great and noone is using join so why bother with join PPS. As of tutorials - somehow I don't recall anyone bothering with getting in deep of Read class on my Haskell course. Tutorial may not even mentioning it as class method and novice will not notice that the method existed

On Mon, 2011-01-10 at 19:01 -0500, David Menendez wrote:

On Sun, Jan 9, 2011 at 10:41 PM, Maciej Piechotka wrote:

...

On Sun, 2011-01-09 at 18:16 -0800, Iavor Diatchki wrote:

...

Hello, In my experience, defining monads in terms of "fmap" and "join" leads to code duplication. The examples we have seen in this thread---so far---are a bit misleading because they compare a partial implementation of a monad (join without fmap) with a complete implementation (bind). Here is an example of what I mean:

data SP a = PutChar Char (SP a) | GetChar (Char -> SP a) | Return a

fmapSP :: (a -> b) -> (SP a -> SP b) fmapSP f (PutChar c sp) = PutChar c (fmapSP f sp) fmapSP f (GetChar k) = GetChar (\c -> fmapSP f (k c)) fmapSP f (Return a) = Return (f a)

joinSP :: SP (SP a) -> SP a joinSP (PutChar c sp) = PutChar c (joinSP sp) joinSP (GetChar k) = GetChar (\c -> joinSP (k c)) joinSP (Return sp) = sp

bindSP :: (a -> SP b) -> (SP a -> SP b) bindSP f (PutChar c sp) = PutChar c (bindSP f sp) bindSP f (GetChar k) = GetChar (\c -> bindSP f (k c)) bindSP f (Return a) = f a

I chose this example because I think that it illustrates nicely how the three operators work, I hope that other readers find it useful.

Yes and no:

1. In monad transformers & co. you want weakened conditions on Functor and Applicative so you cannot reuse (>>=) in them - you end up with a function anyway.

Is this true? Applicative functors compose, so you shouldn't need to use monad transformers. Of the common monad transformers, the only ones where the Applicative instance can be defined in terms of the underlying Applicative instance are Identity, Reader, and Writer, all of which are equivalent to composition (that is, you don't gain anything by using the transformer instead of composition).

1. Add MaybeT and ListT to 'the only ones'. 2. As of non-trivial Applicative see InterleaveT from last MonadReader (issue 17). Regards

2011/1/9 Conal Elliott :

... [fair points deleted.] I relate to Gábor's points that

* The familiarity advantage of (>>=) is a historical accident. I like to see the language improve over time, rather than accumulate accidents. * I prefer functions & methods with simpler interfaces over more complex interfaces. I'm happy to compose these simpler operations to get more complex operations, e.g. join+fmap vs (>>=).

I find this pretty funny, actually, because the early papers on monads in a programming context still used the categorical formulation in terms of join, and were pretty opaque reading as a consequence! When things are re-stated in terms of >>=, the parallels with interchange of let-bindings suddenly becomes obvious and it becomes possible to start to explain this stuff to programmers or computer architects (rather than mathematicians). This is a bias I developed from actually trying to teach this stuff in 1-2 lectures to advanced undergrads and grad students. Which of course says nothing about which form is easier to *write*, but I'm inclined to believe that it's easiest to read and write the form whose use you understand best (ie brevity is not the sole criterion here by any means; understandability has to be paramount). My bias is to assume my reader is, like me, a programmer first and a mathematician second. For example, I find it relatively easy to understand >>= in the continuation monad, but have to spend a long time puzzling my way through join. For simple stuff like [] and Maybe, of course, the code complexity argument is moot, and join is pretty natural unless you spend your time re-formulating list comprehensions for fun. -Jan-Willem Maessen

Maciej Piechotka schrieb:

I agree that there are advantages of both ways and they are perfectly compatible with each other. While I don't know about GHC internals I'd assume that class v-tables (term borrowed from C++ I'm not sure about Haskell terminology) is per-class and not copied for each function invocation.

"Method dictionary" http://www.haskell.org/haskellwiki/OOP_vs_type_classes

On Sun, 16 Jan 2011, wren ng thornton wrote:

On 1/16/11 12:43 PM, Henning Thielemann wrote:

...

Maciej Piechotka schrieb:

...

I agree that there are advantages of both ways and they are perfectly compatible with each other. While I don't know about GHC internals I'd assume that class v-tables (term borrowed from C++ I'm not sure about Haskell terminology) is per-class and not copied for each function invocation.

"Method dictionary"

http://www.haskell.org/haskellwiki/OOP_vs_type_classes

Perhaps I missed it, but I don't see anything in that page clarifying whether the actual underlying table is shared (i.e., the dictionary is just a pointer to a global table) or not (i.e., the dictionary is a constructed copy of the table). As far as the surface language is concerned the distinction doesn't matter, but as far as people worrying about performance considerations due to the size of dictionaries it does.

Sorry, I just wanted to answer the question how these class v-tables are called in Haskell.

Am Sonntag, den 16.01.2011, 10:44 +0100 schrieb Maciej Piechotka:

class v-tables (term borrowed from C++ I'm not sure about Haskell terminology)

Dictionaries. Best wishes, Wolfgang

Ahem On 17 Jan 2011, at 17:22, Tyson Whitehead wrote:

On January 15, 2011 22:43:32 Jan-Willem Maessen wrote:

...

For example, I find it relatively easy to understand >>= in the continuation monad, but have to spend a long time puzzling my way through join.

It's not that bad once you get used to thinking of it. Join simply merges an inner computation into an outer one.

[..]

Something a lot more friendly to the notation would be if A, B, and C were independent computations whose combined results were to determine another computation via a function g. This result, along with D and E, where then to be fed into yet another function f. This is simply expressed as

f <$> join (g <$> A <*> B <*> C) <*> D <*> E

Funnily enough, SHE lets you write (| f (| g A B C @ |) D E |) where the postfixed @ denotes a join: g's effects happen "after" those of A, B and C, but "before" those of D and E. [..] I'm tempted to support if <- b then t else f for (b >>= \ z -> if z then t else f) and case <- s of {p1 -> e1; ..} similarly.

The unfortunate pain you pay for this additional power is manually having to specify the application (<$> and <*>) and merging (join). If the compiler could figure this all out for you based on the underlying types, wow!

To achieve such a thing, one would need to ensure a slightly more deliberate separation of "value" and "computation" in the presentation of types. In Haskell, we use, e.g., [Int], for * pure computations of lists of integers * nondeterministic computations of integers and we spend syntax (do-notation, lifting operators) to distinguish the two modes of usage. If every type was clearly decomposable into its computation and value components, the above possibilities would be distinct (but isomorphic) and we could spend less syntax on plumbing in programs. I fear it's too late to reorganize Haskell along these lines, but it's bound to happen in some language (Disciple? Eff?) sometime. As any ML programmer will tell you, functional programming is really cool, even when it isn't purely functional programming. All the best Conor

Hi, On Mon, Jan 17, 2011 at 1:20 PM, Conor McBride wrote:

I'm tempted to support

if <- b then t else f

for

(b >>= \ z -> if z then t else f)

and

case <- s of {p1 -> e1; ..}

similarly.

Habit (from PSU) uses this syntax. (ref. p. 22 http://hasp.cs.pdx.edu/habit-report-Aug2009.pdf) They also allow one-armed monadic if-then-else, like in C, where the omitted "else" branch is filled in with "return ()". -Iavor PS: sorry that this is not at all on topic but I thought it might of interest to folks.

On January 17, 2011 16:20:22 Conor McBride wrote:

Ahem

: )

...

The unfortunate pain you pay for this additional power is manually having to specify the application (<$> and <*>) and merging (join). If the compiler could figure this all out for you based on the underlying types, wow!

To achieve such a thing, one would need to ensure a slightly more deliberate separation of "value" and "computation" in the presentation of types. In Haskell, we use, e.g., [Int], for

* pure computations of lists of integers * nondeterministic computations of integers

and we spend syntax (do-notation, lifting operators) to distinguish the two modes of usage. If every type was clearly decomposable into its computation and value components, the above possibilities would be distinct (but isomorphic) and we could spend less syntax on plumbing in programs.

I'm pretty sure I know what "pure computations of lists of integers" is, but I'm not so sure about "nondeterministic computations of integers". If it is not too much of an effort, could you clarify with a quick example? Thanks! -Tyson

On 1/17/11 12:22 PM, Tyson Whitehead wrote:

On January 15, 2011 22:43:32 Jan-Willem Maessen wrote:

...

For example, I find it relatively easy to understand>>= in the continuation monad, but have to spend a long time puzzling my way through join.

It's not that bad once you get used to thinking of it. Join simply merges an inner computation into an outer one.

I've been doing a lot more of that lately, or rather _not_ doing it. In particular, there's often a desire when working in monads like IO to do some computation now (and share it) and then do some computation later (possibly many times). The natural way of doing this is to have your function return IO(IO X) where the outer IO is run now and the inner IO is run later. If you want to do both of them now you just call join. One example where this is especially helpful is when dealing with file handling based on commandline flags. In most programs we'd like to run the commandline sanity checks as early as possible so that we can fail fast, but the actual file manipulation can happen much later and far away from main. In the conventional (>>=) style of thinking ---often seen in imperative languages--- we'd have to do something like open the files early and then pass filehandles throughout the program (or worse, pass the file names throughout the program and open/close the files repeatedly). This is not only against what we'd like to do, it's also unsightly, error prone, and a maintenence nightmare. But once we switch over to a join style of thinking, the IO(IO X) approach becomes obvious. We simply check the flags now and return a thunk that will manipulate the file later. We have to pass the thunk around, but the action encapsulates whatever we want to do with the file rather than being the file itself. An added benefit of this style is that it allows us to keep the code that verifies commandline flags close by the code that makes use of that information, instead of smearing it across the whole program and loosing track of the interrelatedness. -- Live well, ~wren

On Mon, Jan 17, 2011 at 7:24 PM, Jan-Willem Maessen wrote:

Using these definitions, and join = (>>= id), we obtain:

join (CPS cca) = CPS (\k -> cca (\ca -> unCPS ca k))

That is, we construct a fresh continuation that we pass to cca, that receives the computation ca returning an a, and invokes ca with continuation k.  I believe this is rather different from your definition, as the type of the continuation that we pass to cca is (say)  a -> r  in the above definition, but is a -> a in yours.

Argh, I meant ca -> r and ca -> ca in the types above. Which just goes to show, I suppose. -Jan

On Mon, Jan 17, 2011 at 10:36 PM, Tyson Whitehead wrote:

On January 17, 2011 19:24:12 Jan-Willem Maessen wrote:

...

...

join (CPS f) = CPS $ \k -> unCPS (f id) k

<snip>

...

Using these definitions, and join = (>>= id), we obtain:

join (CPS cca) = CPS (\k -> cca (\ca -> unCPS ca k))

That is the same.  The key is that the final computation here is unCPS ca k. Delaying the application of k (returning unCPS ca and then applying k gives the same result as directly applying unCPS ca k and returning it) we get

join (CPS cca) = CPS (\k -> cca (\ca -> unCPS ca k)) join (CPS cca) = CPS (\k -> cca (\ca -> unCPS ca) k)

Now, delaying the transformation by unCPS (returning ca and then forming unCPS ca gives the same result as directly forming unCPS ca and returning it) we get

join (CPS cca) = CPS (\k -> unCPS (cca (\ca -> ca)) k) join (CPS cca) = CPS (\k -> unCPS (cca id) k)

which brings us back to the above.

How are you defining CPS? In order to use id as a continuation in these circumstances, you pretty much need newtype CPS a = CPS { unCPS :: forall w. (a -> w) -> w } But that's (mostly) isomorphic to the Identity monad (i.e., you can't define callCC). The advantage of Jan-Willem's definition is that you can use it with the more-familiar Cont monad. I'd argue that it's truer to the sense of continuation passing as well. -- Dave Menendez http://www.eyrie.org/~zednenem/

Am Montag, den 17.01.2011, 19:24 -0500 schrieb Jan-Willem Maessen:

I think Tyson Whitehead unwittingly made my point rather well using the example of the CPS monad. I believe his simple explanation of join in CPS actually leads to an incorrect definition, whereas explaining >>= in CPS is about as straightforward as anything involving CPS can be (which is to say, more than a little convoluted).

If both (>>=) and join are class methods with default implementations that use the respective other method, you can still define the Cont monad instance in terms of (>>=), while you can use join where it is easier (e.g. in the [] instance). So instead of arguing whether join or (>>=) is easier, more natural or whatever, just let us make both a method of Monad. Best wishes, Wolfgang

Wolfgang Jeltsch wrote:

If both (>>=) and join are class methods with default implementations that use the respective other method, you can still define the Cont monad instance in terms of (>>=), while you can use join where it is easier (e.g. in the [] instance). So instead of arguing whether join or (>>=) is easier, more natural or whatever, just let us make both a method of Monad.

Does anyone want to comment on my comparison with restricted monads, where '>>=' can be defined, but 'join' cannot?

On 20 January 2011 10:58, Henning Thielemann wrote:

Wolfgang Jeltsch wrote:

...

If both (>>=) and join are class methods with default implementations that use the respective other method, you can still define the Cont monad instance in terms of (>>=), while you can use join where it is easier (e.g. in the [] instance). So instead of arguing whether join or (>>=) is easier, more natural or whatever, just let us make both a method of Monad.

Does anyone want to comment on my comparison with restricted monads, where '>>=' can be defined, but 'join' cannot?

Just for clarity, are you referring to the restricted monads from the rmonad package[1]? If so, I see no reason (yet) why the RMonad type class can't be defined as: class RMonad m where join :: Suitable m a => m (m a) -> m a Where the Set instance becomes: instance RMonad Set where join ss = withResConstraints $ \SetConstraints -> fold union empty ss Regards, Bas [1] http://hackage.haskell.org/package/rmonad

Sittampalam, Ganesh schrieb:

Bas van Dijk wrote:

...

Just for clarity, are you referring to the restricted monads from the rmonad package[1]?

yes

...

If so, I see no reason (yet) why the RMonad type class can't be defined as:

class RMonad m where join :: Suitable m a => m (m a) -> m a

Where the Set instance becomes:

instance RMonad Set where join ss = withResConstraints $ \SetConstraints -> fold union empty ss

I haven't tried it, but I think you'd need Suitable m (m a) in the constraints, either of join itself, or of (>>=) to make the default definition typecheck.

I ran into similar problems with trying to make RApplicative. Many of the Applicative combinators use intermediate functions heavily, leading to a need for Suitable m (a -> b) for various a and b, and there are often multiple different possible definitions of the combinators that lead to different constraints being needed.

I tried the same and got the same problems. My favorite example is a list like monad on StorableVector. Suitable StorableVector a means Storable a and there is no Storable (a -> b) I could define an RApplicative class only if I introduced an auxiliary type, in the example a stream-fusion:Stream. Then I could define a ZipList instance for StorableVector by converting each StorableVector to Stream and the zipped resulting Stream back to StorableVector.

Dan Doel schrieb:

On Thursday 20 January 2011 3:26:53 pm Henning Thielemann wrote:

...

I could define an RApplicative class only if I introduced an auxiliary type, in the example a stream-fusion:Stream. Then I could define a ZipList instance for StorableVector by converting each StorableVector to Stream and the zipped resulting Stream back to StorableVector.

Relating to my other mail, applicatives are already sort of equipped to be restricted, because their category theoretic analogues are lax monoidal functors. However, you need to look at their first-order interface:

unit :: f () pair :: (f a, f b) -> f (a, b)

The Applicative class takes advantage of the existence of exponential objects to provide a nicer interface to program with, but the above is the closer to the category theory. So, we can probably define a restricted applicative like so:

let Suitable identify a monoidal subcategory of Hask, with Suitable () and (Suitable a, Suitable b) => Suitable (a, b) A restricted applicative is a lax monoidal functor from the subcategory to Hask, so:

unit :: f () pair :: (Suitable a, Suitable b) => (f a, f b) -> f (a, b)

Satisfying some coherence conditions. In general, the subcategory needn't have (all) exponential objects, so we cannot provide the Applicative interface. The only problem with this in Haskell might be enforcing the conditions on Suitable.

Translating for me: liftA2 is essentially pair with subsequent fmap. I already though about this and came to the conclusion, that this does not help in my case. A zipWith3 written as pure f <*> storableVectorA <*> storableVectorB <*> storableVectorC would require a Storable instance for pairs. I provided that in storable-tuple, but then it is not efficient to store intermediate pairs in StorableVector. That's why I think that an optimal solution would neither require (Suitable a, Suitable b) => Suitable (a -> b) nor (Suitable a, Suitable b) => Suitable (a, b) but would best have no such constraint at all. Using an intermediate type does not have such an constraint, but unfortunately does not look nice. Maybe I should switch thread topic now ...

On Thu, 20 Jan 2011, Dan Doel wrote:

I can believe it isn't efficient. But it's possible. An implementation more like vector (for instance) would obviously work out better, because:

unit = UnitVector pair (l, r) = PairVector l r

Yes, this one is much easier. It means that actual zipping is defered to the final fmap. This gives me the idea to use such pairs of vectors as temporary types, and not stream-fusion:Stream.

instead of building a new vector and copying all the elements. Anyhow, my mails were more concerned with whether or not these things are 'unprincipled hacks,' not whether they're practically useful.

I wonder whether practically useful definitions would require unprincipled hacks. :-)

Dan Doel wrote:

However, you can also count me as another person who doesn't care what difficulties exist for RMonad with regard to deciding what functions should go in the Monad class.

I agree, this small and unimportant tail certainly shouldn't wag the dog. Ganesh =============================================================================== Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html ===============================================================================

On January 17, 2011 19:24:12 Jan-Willem Maessen wrote:

...

Join allows you to merge the C1--C2--C3 dynamically determined from A--B--C into the continuation passing string to get

A--B--C--C1--C2--C3--D--E ... (C1--C2--C3 is determined by A--B--C)

This is actually relatively clear from join's type

join :: Monad m => m (m a) -> m a

It takes a string of computations (as indicated by the outer m) that generates a string of computations generating an a (as indicated by the inner m a). It changes this into just a string of computations generating an a.

How can it do this? It must set things up to first run the given string of computations in order to determine the string of computations that give a. Once it gets this, it must then run it in order to get a.

join (CPS f) = CPS $ \k -> unCPS (f id) k

That is, when invoked (i.e., when given a continuation k), invoke f with the continuation id. This will cause f to return the inner computation it computes. Then invoke this returned computation by passing it k.

You guys are both right. It shouldn't be any reflection on join or the description I gave for it though. I simply screwed up by lifting operations out of the continuation without thinking about preserving callCC. Let me restate the last little bit of the above. --- join (CPS f) = CPS $ \k -> f (g -> unCPS g k) That is, when invoked (i.e., when given a continuation k), invoke f with a continuation that takes the computation g generated by f and invokes it next by passing it k. --- My mistake in simplifying this expression was assuming f ends with returning unCPS k0 k1 (letting me lift the unCPS transformation and application of k1 out of the lambda giving id). callCC allows f to not end with unCPS k0 k1. The net effect of lifting these operations out was that it stops f from being able to discard them (i.e., escape past the join). Well subtle, I'm not sure it was too subtle. It is pretty clearly reflected in the types newtype Cont r a = CPS { unCPS :: (a -> r) -> r } join :: Cont (Cont r a) (Cont r a) -> Cont r a join (CPS f) = CPS $ \k -> unCPS (f id) k vs join :: Cont r (Cont r a) -> Cont r a join (CPS f) = CPS $ \k -> f (g -> unCPS g k) Cheers! -Tyson PS: I don't have anything against bind. I just find join is also nice to have for more functional/applicative style programming. It is also conceptually nice as it is quite clear about what additional complexity a monad gives you.

On 04/01/2011 14:25, Ian Lynagh wrote:

...

Now which notable things are not included in the patch for base:

* fmap is not renamed to map. * return and (>>) are not removed as a method. * fail is not removed as a method. * All the liftM functions are not removed in favour of fmap and liftAs.

I think these are better left as separate proposals.

OK, but I think it would be good to get any changes into a single release, so people only need to fix their instances once.

Further patches can be proposed for the next release of GHC after this change is accepted.

On 03/01/2011 22:30, Bas van Dijk wrote:

On Mon, Jan 3, 2011 at 12:43 PM, Ian Lynagh wrote:

...

On Sun, Jan 02, 2011 at 06:27:04PM -0800, Iavor Diatchki wrote:

...

I think that it would be useful if there was a wiki page which describes the proposal exactly, so that we can discuss the details

I agree. I'm confused as to what is part of the proposal, what are other changes necessary due to the classes changing, what are orthogonal cleanups, and what is not being proposed.

The patch for base makes a few changes:

1) Make Applicative a superclass of Monad. So the new hierarchy becomes:

class Functor f where fmap :: (a -> b) -> f a -> f b

(<$) :: a -> f b -> f a (<$) = fmap . const

class Functor f => Applicative f where pure :: a -> f a

(<*>) :: f (a -> b) -> f a -> f b

(*>) :: f a -> f b -> f b a *> b = fmap (const id) a<*> b

(<*) :: f a -> f b -> f a a<* b = fmap const a<*> b

class Applicative m => Monad m where (>>=) :: forall a b. m a -> (a -> m b) -> m b m>>= f = join $ fmap f m

join :: m (m a) -> m a join m = m>>= id

(>>) :: forall a b. m a -> m b -> m b (>>) = (*>)

return :: a -> m a return = pure

fail :: String -> m a fail s = error s

We have a hard time explaining Monads to people already. But now the entire API goes from being one class with 3 methods (only 2 of which you need to care about) to being 3 classes with a total of 11 methods, with a lot of complex interactions. That's a significant increase in cognitive overhead. It might well be the "right" thing in some sense, but is it really worth the pain? What about all those monad tutorials? They now have to include some Functor/Applicative boilerplate, and hope it doesn't put the reader off too much. I like Applicative, I really do, but I want it to be something you only have to buy into if you want to. Someone knocking up a monad for a simple job now has to define 3 instances, not one. So it affects not just people learning the language, but also those already familiar with it and trying to get the job done. Furthermore, we have some significant compatibility issues with Haskell 98/2010 code. I wouldn't be in favour of doing this unless we can retain Haskell 98/2010 compatibility somehow (e.g. with superclass defaults or class aliases). Cheers, Simon

Er, hi... On 5 Jan 2011, at 11:24, Bas van Dijk wrote:

On Wed, Jan 5, 2011 at 11:33 AM, Simon Marlow wrote:

...

Furthermore, we have some significant compatibility issues with Haskell 98/2010 code. I wouldn't be in favour of doing this unless we can retain Haskell 98/2010 compatibility somehow (e.g. with superclass defaults or class aliases).

It would indeed be really nice to have something like this:

{-# LANGUAGE DefaultInstances #-}

class Functor f where fmap :: (a → b) → f a → f b

class Functor f ⇒ Applicative f where pure :: a → f a (<*>) :: f (a → b) → f a → f b

instance Functor f where fmap f m = pure f <*> m

[..]

Now only someone has to implement it :-)

(ahem) cabal install she http://personal.cis.strath.ac.uk/~conor/pub/she/superclass.html [ducks and runs] Conor

On 5 Jan 2011, at 12:31, Bas van Dijk wrote:

On Wed, Jan 5, 2011 at 1:14 PM, Conor McBride wrote:

...

cabal install she

I knew about her but not that she supported default superclass instances. Nice!

She didn't. But she does now. Cheers Conor

Hi Dave On 5 Jan 2011, at 17:25, David Menendez wrote:

On Wed, Jan 5, 2011 at 8:05 AM, Conor McBride wrote:

...

On 5 Jan 2011, at 12:31, Bas van Dijk wrote:

...

On Wed, Jan 5, 2011 at 1:14 PM, Conor McBride wrote:

...

cabal install she

I knew about her but not that she supported default superclass instances. Nice!

She didn't. But she does now.

How does she handle multiple subclasses?

E.g., Functor can be defined in terms of Applicative (fmap = liftA) and in terms of Traversable (fmap = liftT). There are plenty of types which are both.

She lets you opt out. This is vital to any such default subclass scheme. I can write instance Monad Maybe where return = Just Nothing >>= _ = Nothing Just x >>= f = f x hiding instance Functor Maybe -- notation renegotiable and I'll get the Monad and Applicative instances, but not the Functor. Of course, if I don't otherwise provide a Functor instance, GHC will complain that it's missing. Crucially, however, I'm not forced to take the default. The ability to opt out of the default is crucial for several reasons: (1) You might have a choice of defaults, e.g. indeed, Functor from Applicative or Traversable, and you must choose at most one, even if they are extensionally equal. (2) You might have inherited a Functor from a library whose author did not know or care that it was Applicative (because it was obviously not a Monad, of course). You should not be prevented from declaring an Applicative instance by the prior Functor instance. (3) In the case of monad transformers, I might not want an instance Monad m => Functor (T m), especially if it prevents me from defining an instance Functor f => Functor (T f). (cf Oleg's example.) Please note that it's the cheapness of opting in, not requiring the user to assign the methods to their superclasses which assists with backward compatibility. It's been pointed out to me that one might consider class (A x, A y) => B x y where bthingy = .. instance A x where aring = .. ading = .. instance A y where aring = .. ading = .. with *two* default A instances. If we were to allow this, we should need to be able to switch at least one off in some instance B x x and, otherwise, to write stuff like instance B Int Bool where bthingy = .. instance A Int where aring = .. to be clear which A instance gets the overridden aring. At the moment, she doesn't handle this terribly well: you can have both defaults (unmodified) or neither. It's been helpful thinking about the problem in preprocessor terms, because it helps to figure out where the controls need to be. I hope this is progress, anyway. Cheers Conor

Hi On 5 Jan 2011, at 15:22, John Smith wrote:

On 05/01/2011 12:33, Simon Marlow wrote:

...

We have a hard time explaining Monads to people already. But now the entire API goes from being one class with 3 methods (only 2 of which you need to care about) to being 3 classes with a total of 11 methods, with a lot of complex interactions. That's a significant increase in cognitive overhead. It might well be the "right" thing in some sense, but is it really worth the pain? What about all those monad tutorials? They now have to include some Functor/Applicative boilerplate, and hope it doesn't put the reader off too much. I like Applicative, I really do, but I want it to be something you only have to buy into if you want to.

I think a lot of people take that entirely reasonable position, and it's worth thinking about how to choreograph a good compromise if possible. I believe it is.

The original Arrow was one class with a few simple methods, and extremely easy to explain. There are now several classes in the Arrow module, and Arrow itself is a subclass of Category. Tutorials simply use the original Arrow definition, which gets the concept across fine. The learner can then proceed to understand the richer, and better factored, current implementation.

Arrows (rightly or wrongly) tend to be a pedagogical step beyond Monad, anyway, so one can expect more of Arrow-learners. It's better to avoid unlearning experiences, so it's worth thinking about how to ensure that people can engage with the Monad concept, as available when they fire up ghci, without needing to see its further refinements.

...

Someone knocking up a monad for a simple job now has to define 3 instances, not one.

It's one interesting instance, plus a copy-paste mantra, but it's still annoying, even if you actually want to use those extra instances.

...

So it affects not just people learning the language, but also those already familiar with it and trying to get the job done.

This creates a little extra work for those who don't want Functor or Applicative (the methods have to be defined anyway, it's just split across the new class hierarchy). Those who do want Functor or Applicative now have them where they belong, without writing boilerplate definitions.

They must still write boilerplate instances, but not those awful (Functor m, Monad m) contexts.

Much like anyone declaring an instance of Ord also needs an instance of Eq, even if they're not going to use it.

...

Furthermore, we have some significant compatibility issues with Haskell 98/2010 code. I wouldn't be in favour of doing this unless we can retain Haskell 98/2010 compatibility somehow (e.g. with superclass defaults or class aliases).

This is part of a larger problem. Is Haskell to be forever frozen as something which can be easily made compatible with Haskell 98? Haskell 98 an earlier made many non-backwards compatible changes, including changes to the Monad class.

Change that breaks stuff gets more expensive as uptake grows, so the H98 comparison needs refinement: the cost-benefit analysis is different. I'm in favour of Applicative => Monad in principle, and as soon as is practicable. I just think that if there are helpful measures we can take first to reduce the cost of that change, then we should try to do it the easier way around. The choreography matters. To that end, a little joyride...

{-# OPTIONS_GHC -F -pgmF she #-} {-# LANGUAGE NoImplicitPrelude #-}

module NewMonad where

import Prelude hiding (Functor, Monad, return, (>>=), fmap)

class Functor f where fmap :: (s -> t) -> f s -> f t

class Functor f => Applicative f where return :: x -> f x (<*>) :: f (s -> t) -> f s -> f t instance Functor f where fmap = (<*>) . return

pure :: Applicative f => x -> f x pure = return -- for backward compatibility

class Applicative f => Monad f where (>>=) :: f s -> (s -> f t) -> f t instance Applicative f where ff <*> fs = ff >>= \f -> fs >>= \s -> return (f s)

Now, hark at the dog not barking in the nighttime.

instance Monad [] where return x = [x] [] >>= f = [] (x : xs) >>= f = f x ++ xs >>= f

And away we go!

ex1 :: [Bool] ex1 = fmap (>2) [0..9]

ex2 :: [Int] ex2 = (| [1..6] + [1..6] |) -- she has idiom brackets

ex3 :: [Int] ex3 = do n <- [0..5] [0..n]

Let's go for win-win, or as close as we can get. All the best Conor

On January 5, 2011 11:06:52 Stephen Tetley wrote:

Now that someone has brought Arrows up...

Personally I find the current arrows situation unpleasant and frustrating. I only use arrows infrequently so I haven't built up an intuition about them the way I have with monads. The current code is unlike the best tutorial (John Hughes's AFP lecture notes), and last night when I was looking for tutorial material covering the new classes I couldn't find any, all I had to work with was the code in Base and Ross Paterson's arrow transformer package. There isn't even an explanation in the Control.Arrow Haddock docs elucidating the changes.

The arrow stuff seems a bit unpleasant/squishy to me as well. I wonder if Patai hit upon the root of the issue when in his blog (which includes a nice hierarchy diagram) he suggested/proposed that "Arrow is strictly the intersection of Applicative and Category". http://just-bottom.blogspot.com/2010/04/programming-with-effects-story-so- far.html I haven't really seen any reason to believe otherwise myself. If true, it greatly clarifies my understanding of exactly what additional power you get (and possibly suggests that hierarchy needs some care too). Cheers! -Tyson

Bas van Dijk schrieb:

The patch for base makes a few changes:

1) Make Applicative a superclass of Monad. So the new hierarchy becomes:

class Functor f where fmap :: (a -> b) -> f a -> f b

(<$) :: a -> f b -> f a (<$) = fmap . const

class Functor f => Applicative f where pure :: a -> f a

(<*>) :: f (a -> b) -> f a -> f b

(*>) :: f a -> f b -> f b a *> b = fmap (const id) a <*> b

(<*) :: f a -> f b -> f a a <* b = fmap const a <*> b

class Applicative m => Monad m where (>>=) :: forall a b. m a -> (a -> m b) -> m b

Is the explicit 'forall' intended?

m >>= f = join $ fmap f m

join :: m (m a) -> m a join m = m >>= id

(>>) :: forall a b. m a -> m b -> m b (>>) = (*>)

return :: a -> m a return = pure

fail :: String -> m a fail s = error s

2) Make 'join' a method of Monad.

Is there a need for it?

3) Export Applicative(pure, (<*>), (*>), (<*)) from the Prelude. (Maybe we shouldn't export the (*>) and (<*) methods.)

No, please avoid that. Importing Applicative explicitly is completely ok for me. I use (<*>) already for scalar product in NumericPrelude. For me it looks like a commutative operator, which Applicative.<*> is not. The existence of (<*>) in Applicative module is ok for me, but I do not want name clashes with it when automatically imported by Prelude. If at all, Functor stuff should be moved from Control.Applicative and Control.Monad to a new module Control.Functor (and could be re-exported by Control.Applicative and Control.Monad for compatibility reasons). Then fmap could be renamed to 'map' and used as F.map (using "import qualified Control.Functor as F"). All those infix operators for Monad and Functor are not so important for me to be imported automatically from Prelude. Thus I would not like to move Applicative in this direction.

4) Also export the join method from the Prelude.

no please, as above

5) Add Applicative instances for all monads in base.

+1

6) Add a Monad instance for ((,) a): (There are already Functor and Applicative instances for it.)

That is, a Writer instance? I am uncertain about it, because using it may hide a bug. So far I am happy with Writer from transformers package. Using Writer explicitly shows everybody, what I am doing and that I do it intentionally.

The patch for ghc simply adds Applicative instances for all monads in ghc. Also included in the ghc patch bundle are some refactoring patches that will make the transition easier:

* Added (<>) = mappend to compiler/utils/Util.hs. * Add a Monoid instance for AGraph and remove the <*> splice operator. Instead of <*>, the (<>) = mappend operator is now used to splice AGraphs. This change is needed because <*> clashes with the Applicative apply operator <*>, which is probably going to be exported from the Prelude when the new Monad hierarchy is going through. (Simply hiding <*> from the Prelude is also possible of course. However, I think this makes things easier to understand)

For me this is another argument against automatic import of (<*>).

* Make SDoc an abstract newtype and add a Monoid instance for it. The (<>) combinator of SDocs is removed and replaced by the more general (<>) = mappend combinator from Util.

An infix operator for monoids would be nice, indeed. Why not use something that resembles (++), which is the "mappend" for lists? I am uncertain. Maybe something containing '+' looks too commutative. :-) But '<>' looks too much like 'not equal' in other languages.

On Fri, Jan 7, 2011 at 11:59 AM, Henning Thielemann wrote:

Bas van Dijk schrieb:

...

class Applicative m => Monad m  where     (>>=) :: forall a b. m a -> (a -> m b) -> m b

Is the explicit 'forall' intended?

The explicit 'forall' was already there with the following comment: -- Explicit for-alls so that we know what order to -- give type arguments when desugaring

...

2) Make 'join' a method of Monad.

Is there a need for it?

Like others in this thread have shown, I believe it allows you to write shorter/simpler/elegant Monad instances. However, maybe it's better to move this to its own proposal so we can focus our attention to the proposed hierarchy.

...

3) Export Applicative(pure, (<*>), (*>), (<*)) from the Prelude. (Maybe we shouldn't export the (*>) and (<*) methods.)

No, please avoid that. Importing Applicative explicitly is completely ok for me.

Currently you can define a Functor and Monad instance without importing anything (because they are both exported by the Prelude). When Applicative becomes a superclass of Monad users _have_ to write an instance for it. I think it would be weird and irritating that you can define the Functor and Monad instances without importing anything but you do have to import Applicative. I would rather either export all the three classes from the Prelude or export none of them.

I use (<*>) already for scalar product in NumericPrelude. For me it looks like a commutative operator, which Applicative.<*> is not. The existence of (<*>) in Applicative module is ok for me, but I do not want name clashes with it when automatically imported by Prelude.

Personally, I'm not the biggest fan of the '<*>' symbol either. I would rather like something which doesn't look commutative and features a '$' somewhere to indicate its "applicative" nature. However, I don't think we should be proposing name changes in this proposal. Is there a possibility you can rename your scalar product combinator to something else? '.*.' maybe?

If at all, Functor stuff should be moved from Control.Applicative and Control.Monad to a new module Control.Functor (and could be re-exported by Control.Applicative and Control.Monad for compatibility reasons). Then fmap could be renamed to 'map' and used as F.map (using "import qualified Control.Functor as F"). All those infix operators for Monad and Functor are not so important for me to be imported automatically from Prelude. Thus I would not like to move Applicative in this direction.

...

4) Also export the join method from the Prelude.

no please, as above

Fair enough.

...

5) Add Applicative instances for all monads in base.

+1

...

6) Add a Monad instance for ((,) a): (There are already Functor and Applicative instances for it.)

That is, a Writer instance?

I am uncertain about it, because using it may hide a bug. So far I am happy with Writer from transformers package. Using Writer explicitly shows everybody, what I am doing and that I do it intentionally.

Yes, I think I need to remove this from the patch. However, I do believe we either need to have both Functor, Applicative and Monad instances or none of them. It feels weird to only have Functor and Applicative instances.

...

The patch for ghc simply adds Applicative instances for all monads in ghc. Also included in the ghc patch bundle are some refactoring patches that will make the transition easier:

* Added (<>) = mappend to compiler/utils/Util.hs. * Add a Monoid instance for AGraph and remove the <*> splice operator. Instead of <*>, the (<>) = mappend operator is now used to splice AGraphs. This change is needed because <*> clashes with the Applicative apply operator <*>, which is probably going to be exported from the Prelude when the new Monad hierarchy is going through. (Simply hiding <*> from the Prelude is also possible of course. However, I think this makes things easier to understand)

For me this is another argument against automatic import of (<*>).

...

* Make SDoc an abstract newtype and add a Monoid instance for it. The (<>) combinator of SDocs is removed and replaced by the more general (<>) = mappend combinator from Util.

An infix operator for monoids would be nice, indeed. Why not use something that resembles (++), which is the "mappend" for lists? I am uncertain. Maybe something containing '+' looks too commutative. :-) But '<>' looks too much like 'not equal' in other languages.

I choose '<>' because it was already the append for SDocs. I too like something featuring '++'. Or maybe '++' itself. Regards, Bas