Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Sat Nov 8 21:04:33 UTC 2014

for is in rather broad use; I know you have a pet alternative definition. ;)

sequenceA is unlikely to be reclaimed any time soon -- it is in the
Traversable class.

There are is also a couple of annoying side-cases where mapM/sequence can
be implemented with better stack behavior than traverse/sequenceA.
Basically if you have a very _large_ but not infinite list like container
you can find a way to fold it that abuses your heap more when using the
Monad to dump into an accumulator and reverse, rather than the stack which
you wind up on in the Applicative case.

When you add the fact that many folks have manual mapM implementations
already, we can't remove mapM/sequence from the class or even generalize
their signatures *at this time*.

We can and have at least simplified their default definitions so they take
advantage of the Applicative superclass rather than go through the
WrappedMonad overhead. This means that most consumers of mapM will just get
automatically upgraded behavior even if the types don't change.

We can decide over the next year if in 7.12 we want to deprecate manual
definitions of mapM, if we can figure out a workaround for the the
aforementioned counter-example, or find that it isn't an issue in practice,
but it isn't something that can reasonably happen now.

The AMP and Foldable/Traversable work are starting to let a lot of things
work together, but while reclaiming some names some day might be nice, it
is something that is pretty much off the table in the short term.

Longer term we can talk about deprecation/consolidation of more
combinators, but I'd really like to push such discussions out past 7.12 to
a time when folks have had time to adapt to the status quo and start to
find the redundancy more annoying than useful, and when you are more likely
to get something like what you'd want without incurring undue pain.

That'd need to be a much broader discussion though.

*tl;dr* It's complicated.

-Edward

On Sat, Nov 8, 2014 at 3:39 PM, Andreas Abel <abela at chalmers.se> wrote:

> Thanks for your replies.
>
> My hope for AMP was to get generalization of effectful combinators without
> requiring more identifiers (and actually freeing some, like making
> `sequenceA` and `for` obsolete).  I see that it is not so easy if GHC's
> reduction behavior has to be taken into account.
>
> So +1 from me if you deem liftA4 and liftA5 necessary.
>
> On 08.11.2014 21:21, David Feuer wrote:
>
>> On Sat, Nov 8, 2014 at 2:39 PM, Edward Kmett <ekmett at gmail.com
>> <mailto:ekmett at gmail.com>> wrote:
>>
>>     We have two competing tensions that have been guiding the work so
>>     far, which is scattered across a few dozen different proposals and
>>     patches in Phab and is alarmingly intricate to detail.
>>
>>     We've generally been guided by the notion you suggest here. In the
>>     wake of the AMP, the 'M' suffix really comes to mean the minimal set
>>     of effects needed to get the effect. This lets us generalize large
>>     numbers of combinators in Control.Monad (e.g. when/unless/guard) to
>>     'just work' in more contexts.
>>
>>     However, we also have to balance this carefully against two other
>>     concerns:
>>
>>     1.) Not breaking user code silently in undetectable ways.
>>
>>     This is of course the utmost priority. It guides much of the AMP,
>>     including the 'backwards' direction of most of the dependencies.
>>     e.g. The reality is a large number of folks wrote (*>) = (>>) in
>>     their code, so e.g. if we defined (>>) = (*>), we'd get a large
>>     chunk of existing production code that just turns into infinite
>>     loops. We can always do more later as we find it is safe, but "first
>>     do no harm."
>>
>>
>> Indeed. I've looked at quite a few Applicative and Monad instances
>> lately, and one conclusion I've come to is that it often makes *more*
>> sense to define (*>) = (>>) than the other way around. In particular,
>> monads like IO and ST have a (>>=) that's about as simple as anything
>> remotely interesting you can do with them. In particular,
>>
>>    fs <*> xs = fs >>= \f -> xs >>= \x -> return (f x)
>>
>> is about as simple as it gets. The default definition of (*>) looks like
>> this:
>>
>>    m *> n = (id <$ m) <*> n
>>
>> But these don't have particularly special Functor instances either. So
>> this expands out to
>>
>>    m *> n = fmap (const id) m <*> n
>>
>> which becomes
>>
>>    m *> n = (m >>= (return . const id)) >>= \f -> n >>= \x -> return (f x)
>>
>> Can we say "ouch"? We now have to hope that GHC inlines enough to do
>> anything more. If it does, it will take a few extra steps along the way.
>>
>> Compare this mess to (>>):
>>
>> m >> n = m >>= \_ -> n
>>
>> So I think there's a pretty clear case for (*>) = (>>) actually being
>> the right thing in a lot of cases.
>>
>>     2.) Not introducing rampant performance regressions.
>>
>>     David Feuer has been spending untold hours on this, and his work
>>     there is a large part of the source of endless waves of proposals
>>     he's been putting forth.
>>
>>     Considering `liftM2` as 'redundant' from `liftA2` can be dangerous
>>     on this front.
>>
>>
>> That's definitely a valid concern, for the reasons described above.
>> Everything works out nicely because of monad laws, but GHC doesn't know
>> that.
>>
>>     The decision of if we can alias liftM3 to liftA3 needs to be at
>>     least /partially/ guided by the question of whether the latter is a
>>     viable replacement in practice. I'm not prepared to come down on one
>>     side of that debate without more profiling data.
>>
>>
>> Yes, that makes sense. I think the problem fundamentally remains the
>> same--the monadic operations ultimately need to be inlined and
>> completely twisted around in order to be fast.
>>
>>
>>     Adding liftA4, liftA5 runs afoul of neither of these caveats.
>>     Aliasing liftMn to liftAn is something that /potentially/ runs afoul
>>     of the latter, and is something that we don't have to do in a
>>     frantic rush. The world won't end if we play it safe and don't get
>>     to it in time for 7.10.
>>
>>
>> The more I think about it, the more right I think you are.
>>
>> David
>>
>
> --
> Andreas Abel  <><      Du bist der geliebte Mensch.
>
> Department of Computer Science and Engineering
> Chalmers and Gothenburg University, Sweden
>
> andreas.abel at gu.se
> http://www2.tcs.ifi.lmu.de/~abel/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141108/1ff8705e/attachment.html>