MRP Summary & revised MRP 2ed (was: Monad of no `return` Proposal (MRP): Moving `return` out of `Monad`)

Thu Nov 26 08:28:32 UTC 2015

On Wed, Nov 25, 2015 at 7:05 PM, Edward Kmett <ekmett at gmail.com> wrote:
> (>>) becomes slower by default in some cases and drastically faster in
> others, but since the definition is a member in a class it can actually be
> fixed by people.

This is true, but I think it's much better to avoid breaking people's
code in the first place. Also, since the breakage can be silent, one
will not always be able to make a fix promptly.

>
> In situations where (<*>) is asymptotically more efficient than (>>=) then
> the default definition in terms of (<*>) wins.

You are right. I hadn't thought about this.

>
> Right now, if you run through hackage there are lots of places where (>>)
> has been manually improved but the (*>) has not -- or vice versa. We have
> two places where people should apply an optimization and many have only
> realized that they should optimize one or the other.
>
> The key here is to encourage folks to actually define (*>) when it matters.

I understand this, but perhaps there is a way to achieve this without
slowing down existing code. How about introducing a new warning
(enabled with -Wall) that is triggered when a type satisfies the
following 3 conditions?

1. The type has a Monad instance and an Applicative instance declared
in the same module, with the same set of constraints.
2. (*>) is not defined as (*>) = (>>). i.e. either it has a
non-trivial definition or its definition is left out.
3. (>>) is not defined as (>>) = (*>). i.e. either it has a
non-trivial definition or its definition is left out.

This way, people can be warned when (*>) and (>>) can share an
implementation but they don't.

- Akio

>
> -Edward
>
> On Wed, Nov 25, 2015 at 2:37 AM, Akio Takano <tkn.akio at gmail.com> wrote:
>>
>> Hi Herbert,
>>
>> On Thu, Nov 5, 2015 at 10:46 AM, Herbert Valerio Riedel <hvr at gnu.org>
>> wrote:
>> > Hello everybody,
>> >
>> > Based on the feedback gathered from the discussion, the proposal has
>> > been revised to address the raised concerns. The highlights are:
>> >
>> >  - A new stretched out transition scheme complying with the recently
>> >    enacted 3-release policy (and beyond) has been devised.
>> >
>> >  - Unifying `>>`/`*>` has been incorporated into the proposal in the
>> >    interest of bundling changes of obviously related changes.
>> >
>> >  - Moreover, the feasibility of automatic refactoring tooling was
>> >    investigated and resulted in the working `Hs2010To201x`
>> >    proof-of-concept.
>> >
>> > Please re-read the revised proposal at
>> >
>> >   https://ghc.haskell.org/trac/ghc/wiki/Proposal/MonadOfNoReturn
>> >
>> > for more details (or use the Wiki's diffing feature to see what changed
>> > relative to the original revision) if you want to comment, so we can
>> > focus on discussing the actual revised version.
>>
>> I'm sorry to join the discussion so late, but I'd like to mention one
>> thing that doesn't seem to have been brought up. If I understand
>> correctly, this proposal can silently slow down existing programs,
>> sometimes even asymptotically. This applies when a monad is defined
>> with no explicit definition for (>>) nor for (*>).
>>
>> The problem is this: currently, when a Monad instance lacks an
>> explicit definition for (>>), a default implementation based on (>>=)
>> is used. After this proposal, (>>) would be an alias for (*>), for
>> which there is a default implementation based on (<*>). However, at
>> least for some monads, the former is a much better default.
>>
>> [1] is one example where it makes an asymptotic difference in runtime.
>> This type of difference arises when (>>=) has to linearly traverse its
>> LHS, but not its RHS.
>>
>> [1] https://ghc.haskell.org/trac/ghc/ticket/10711#comment:1
>>
>> I also constructed another example [2]. This is a standard
>> implementation of the strict State monad, except that (>>=) is
>> implemented as a NOINLINE function. You can see that using (*>) in
>> place of (>>) changes the memory usage of the program from constant to
>> linear. The difference here arises from the fact that the default
>> implementation for (>>) can "tail-call" its RHS as long as (>>=) also
>> has this tail-call property, but the default implementation of (*>)
>> cannot.
>>
>> [2] https://gist.github.com/takano-akio/7066c511b60d6ab090c5
>>
>> In my opinion introducing this kind of performance regression is quite
>> bad. Although I agree that it's frustrating that we are stuck with
>> mapM, mapM_ etc., I believe this should be fixed in a way that doesn't
>> make (>>) slower by default.
>>
>> Regards,
>> Takano Akio
>>
>> >
>> > Also, as per proposal guidelines, and more importantly, for the benefit
>> > of those that lost track of this rather complex discussion, I've tried
>> > to summarize the core of discussion over at
>> >
>> >   https://ghc.haskell.org/wiki/Proposal/MonadOfNoReturn/Discussion
>> >
>> > More importantly, based on feedback gathered as well as concerns raised
>> > throughout the discussion, I've revised and extended the proposal into a
>> > "2nd edition MRP". I feel confident the new revised proposal addresses
>> > the major concerns as well as adhering to the recently requested 3-yr
>> > compatibility policy.
>> >
>> > PS: One common oversight I noticed when reviewing the discussion is
>> >     that the last-minute proposal addition -- of unifying `>>`/`*>` in
>> >     the same vein as `pure`/`return` -- wasn't noticed by many who
>> >     joined the debate late.
>> >
>> >     However, Unifying `>>`/`*>` and `pure`/`return` are in my opinion
>> >     strongly related concerns as they share the same rationale about
>> >     correctness issues and it doesn't make sense to do one without the
>> >     other. However, the transition time-scales could be set slightly
>> >     different to account for the more breaking nature of effectively
>> >     changing `>>`'s current default method operational semantics.
>> >
>> > Thanks,
>> >   Herbert
>> >
>> > _______________________________________________
>> > Libraries mailing list
>> > Libraries at haskell.org
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> >
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>