Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
34 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

David Feuer
Another point: using `liftA` or `liftM`, specialized to the relevant type, may reduce code size in some cases. With f <$> a <*> b <*> c and such, you have to hope that you either get some benefit from the inlining or that CSE is able to save you from the duplication.

On Fri, Nov 7, 2014 at 7:47 AM, Jacques Carette <[hidden email]> wrote:
On 2014-11-07 5:30 AM, Henning Thielemann wrote:

On Fri, 7 Nov 2014, Andreas Abel wrote:

I hope the same happens for sequence, mapM and the like!

 sequence :: (Applicative m) => [m a] -> m [a]
 sequence = foldr (\ x xs -> (:) <$> x <*> xs) (pure [])

Actually, this is an example, where liftA2 shows its advantage:

  sequence = foldr (liftA2 (:)) (pure [])

This looks much clearer to me than decoding the mixture of infix and uninfixed infix operators. It simply says, that 'sequence' is like 'id = foldr (:) []' but with everything lifted to an applicative functor.

I agree.  I have lots of code which looks really clean because I can use liftA2 (and even liftA3) in exactly the way above.  Having to eta expand everything obscures the real meat of what is going on.

Jacques

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

John Lato-2
I still don't think it's worth adding liftA4 and liftA5 just so that liftM4+ can be rewritten.

Very weakly -0.1

On Fri Nov 07 2014 at 10:24:27 AM David Feuer <[hidden email]> wrote:
Another point: using `liftA` or `liftM`, specialized to the relevant type, may reduce code size in some cases. With f <$> a <*> b <*> c and such, you have to hope that you either get some benefit from the inlining or that CSE is able to save you from the duplication.

On Fri, Nov 7, 2014 at 7:47 AM, Jacques Carette <[hidden email]> wrote:
On 2014-11-07 5:30 AM, Henning Thielemann wrote:

On Fri, 7 Nov 2014, Andreas Abel wrote:

I hope the same happens for sequence, mapM and the like!

 sequence :: (Applicative m) => [m a] -> m [a]
 sequence = foldr (\ x xs -> (:) <$> x <*> xs) (pure [])

Actually, this is an example, where liftA2 shows its advantage:

  sequence = foldr (liftA2 (:)) (pure [])

This looks much clearer to me than decoding the mixture of infix and uninfixed infix operators. It simply says, that 'sequence' is like 'id = foldr (:) []' but with everything lifted to an applicative functor.

I agree.  I have lots of code which looks really clean because I can use liftA2 (and even liftA3) in exactly the way above.  Having to eta expand everything obscures the real meat of what is going on.

Jacques

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Edward Kmett-2
I don't want them for rewriting liftM4 and liftM5, I want them in their own right.

It doesn't do anyone any good to just have random asymmetries in the API like that.

It just means a user goes to reach for a tool, doesn't find it and flails around.

-Edward

On Fri, Nov 7, 2014 at 1:37 PM, John Lato <[hidden email]> wrote:
I still don't think it's worth adding liftA4 and liftA5 just so that liftM4+ can be rewritten.

Very weakly -0.1

On Fri Nov 07 2014 at 10:24:27 AM David Feuer <[hidden email]> wrote:
Another point: using `liftA` or `liftM`, specialized to the relevant type, may reduce code size in some cases. With f <$> a <*> b <*> c and such, you have to hope that you either get some benefit from the inlining or that CSE is able to save you from the duplication.

On Fri, Nov 7, 2014 at 7:47 AM, Jacques Carette <[hidden email]> wrote:
On 2014-11-07 5:30 AM, Henning Thielemann wrote:

On Fri, 7 Nov 2014, Andreas Abel wrote:

I hope the same happens for sequence, mapM and the like!

 sequence :: (Applicative m) => [m a] -> m [a]
 sequence = foldr (\ x xs -> (:) <$> x <*> xs) (pure [])

Actually, this is an example, where liftA2 shows its advantage:

  sequence = foldr (liftA2 (:)) (pure [])

This looks much clearer to me than decoding the mixture of infix and uninfixed infix operators. It simply says, that 'sequence' is like 'id = foldr (:) []' but with everything lifted to an applicative functor.

I agree.  I have lots of code which looks really clean because I can use liftA2 (and even liftA3) in exactly the way above.  Having to eta expand everything obscures the real meat of what is going on.

Jacques

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Andreas Abel-2
I am a bit alert about this discussion because it seems that we have
quite different ideas about how the AMP implementation should affect the
base libraries.

1. Where can we see and discuss the proposed changes?

Not on
https://www.haskell.org/haskellwiki/Functor-Applicative-Monad_Proposal

Not on https://ghc.haskell.org/trac/ghc/ticket/9586

2. Imho, the reasonable thing is to

   rewrite all of F/A/M base functions such that they use the minimal
F/A/M constraints.

This of course includes

   liftM  :: (Functor m) => (a -> b) -> m a -> m b
   liftM2 :: (Applicative m) => (a -> b -> c) -> m a -> m b -> m c

and sequence and friends even if the M postfix can then "only explained
historically" (HT).

One can say "M" stands for "effectful", but the minimal type class to
realize the effect is chosen from F/A/M.

If we burn bridges, we should do it properly.

Cheers,
Andreas


On 07.11.2014 20:35, Edward Kmett wrote:

> I don't want them for rewriting liftM4 and liftM5, I want them in their
> own right.
>
> It doesn't do anyone any good to just have random asymmetries in the API
> like that.
>
> It just means a user goes to reach for a tool, doesn't find it and
> flails around.
>
> -Edward
>
> On Fri, Nov 7, 2014 at 1:37 PM, John Lato <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     I still don't think it's worth adding liftA4 and liftA5 just so that
>     liftM4+ can be rewritten.
>
>     Very weakly -0.1
>
>     On Fri Nov 07 2014 at 10:24:27 AM David Feuer <[hidden email]
>     <mailto:[hidden email]>> wrote:
>
>         Another point: using `liftA` or `liftM`, specialized to the
>         relevant type, may reduce code size in some cases. With f <$> a
>         <*> b <*> c and such, you have to hope that you either get some
>         benefit from the inlining or that CSE is able to save you from
>         the duplication.
>
>         On Fri, Nov 7, 2014 at 7:47 AM, Jacques Carette
>         <[hidden email] <mailto:[hidden email]>> wrote:
>
>             On 2014-11-07 5:30 AM, Henning Thielemann wrote:
>
>
>                 On Fri, 7 Nov 2014, Andreas Abel wrote:
>
>                     I hope the same happens for sequence, mapM and the like!
>
>                       sequence :: (Applicative m) => [m a] -> m [a]
>                       sequence = foldr (\ x xs -> (:) <$> x <*> xs)
>                     (pure [])
>
>
>                 Actually, this is an example, where liftA2 shows its
>                 advantage:
>
>                    sequence = foldr (liftA2 (:)) (pure [])
>
>                 This looks much clearer to me than decoding the mixture
>                 of infix and uninfixed infix operators. It simply says,
>                 that 'sequence' is like 'id = foldr (:) []' but with
>                 everything lifted to an applicative functor.
>
>
>             I agree.  I have lots of code which looks really clean
>             because I can use liftA2 (and even liftA3) in exactly the
>             way above.  Having to eta expand everything obscures the
>             real meat of what is going on.
>
>             Jacques
>
>             _________________________________________________
>             Libraries mailing list
>             [hidden email] <mailto:[hidden email]>
>             http://www.haskell.org/__mailman/listinfo/libraries
>             <http://www.haskell.org/mailman/listinfo/libraries>
>
>
>         _________________________________________________
>         Libraries mailing list
>         [hidden email] <mailto:[hidden email]>
>         http://www.haskell.org/__mailman/listinfo/libraries
>         <http://www.haskell.org/mailman/listinfo/libraries>
>
>
>     _______________________________________________
>     Libraries mailing list
>     [hidden email] <mailto:[hidden email]>
>     http://www.haskell.org/mailman/listinfo/libraries
>
>

--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Alexey Khudyakov
On 8 November 2014 13:42, Andreas Abel <[hidden email]> wrote:

> I am a bit alert about this discussion because it seems that we have quite
> different ideas about how the AMP implementation should affect the base
> libraries.
>
> 1. Where can we see and discuss the proposed changes?
>
> Not on
> https://www.haskell.org/haskellwiki/Functor-Applicative-Monad_Proposal
>
> Not on https://ghc.haskell.org/trac/ghc/ticket/9586
>
> 2. Imho, the reasonable thing is to
>
>   rewrite all of F/A/M base functions such that they use the minimal F/A/M
> constraints.
>
> This of course includes
>
>   liftM  :: (Functor m) => (a -> b) -> m a -> m b
>   liftM2 :: (Applicative m) => (a -> b -> c) -> m a -> m b -> m c
>
I don't think it's wise to rewrite _all_ functions. In particular liftM and ap
shoudl stay as they are. Those are implementations of fmap and <*> using
monadic bind and thus useful for writing instances like:

> instance Functor T where
>   fmap = liftM
> instance Applicative T where
>   pure = return; (<*>) = ap
> instance Monad T where ...

Changing ap will break a lot of code.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Andreas Abel-2
On 08.11.2014 13:52, Aleksey Khudyakov wrote:

>  In particular liftM and ap
> shoudl stay as they are. Those are implementations of fmap and <*> using
> monadic bind and thus useful for writing instances like:
>
>> instance Functor T where
>>    fmap = liftM
>> instance Applicative T where
>>    pure = return; (<*>) = ap
>> instance Monad T where ...
>
> Changing ap will break a lot of code.

Fair enough.  The functions for "default implementations" of Functor and
Applicative from Monad and the like should of course stay.

I forgot that AMP does not / cannot give you these default
implementations for free.


--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Conal Elliott
In reply to this post by Edward Kmett-2
Strongly +1.

liftAn are partial-application-friendly. They're also very handy to compose with *no arguments* in the style of semantic editor combinators. For instance, `(liftA2.liftA2.liftA2)` lifts a binary function to a binary function that targets three levels deep in applicative functor nesting.

-- Conal

On Fri, Nov 7, 2014 at 10:00 AM, Edward Kmett <[hidden email]> wrote:
If you want to partially apply a lifted function the f <$> x <*>y <*> z approach doesn't work.

liftMn and liftAn still have a place.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

David Feuer

I think it's sufficiently clear that enough people want liftA4 and liftA5 to justify adding them. The remaining question is whether to save on code size by defining

liftM = liftA --not = fmap, because fmap may be defined as liftM/liftA
liftM2 = liftA2 -- I made this possible already by defining ap directly, so this won't cause problems for the (<*>) = ap bunch
liftM[345]=liftA[345]

The code size impact is larger than it might otherwise appear because of some SPECIALISE pragmas.

On Nov 8, 2014 11:28 AM, "Conal Elliott" <[hidden email]> wrote:
Strongly +1.

liftAn are partial-application-friendly. They're also very handy to compose with *no arguments* in the style of semantic editor combinators. For instance, `(liftA2.liftA2.liftA2)` lifts a binary function to a binary function that targets three levels deep in applicative functor nesting.

-- Conal

On Fri, Nov 7, 2014 at 10:00 AM, Edward Kmett <[hidden email]> wrote:
If you want to partially apply a lifted function the f <$> x <*>y <*> z approach doesn't work.

liftMn and liftAn still have a place.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Edward Kmett-2
In reply to this post by Andreas Abel-2
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."

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.

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.

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.

-Edward

On Sat, Nov 8, 2014 at 7:42 AM, Andreas Abel <[hidden email]> wrote:
I am a bit alert about this discussion because it seems that we have quite different ideas about how the AMP implementation should affect the base libraries.

1. Where can we see and discuss the proposed changes?

Not on https://www.haskell.org/haskellwiki/Functor-Applicative-Monad_Proposal

Not on https://ghc.haskell.org/trac/ghc/ticket/9586

2. Imho, the reasonable thing is to

  rewrite all of F/A/M base functions such that they use the minimal F/A/M constraints.

This of course includes

  liftM  :: (Functor m) => (a -> b) -> m a -> m b
  liftM2 :: (Applicative m) => (a -> b -> c) -> m a -> m b -> m c

and sequence and friends even if the M postfix can then "only explained historically" (HT).

One can say "M" stands for "effectful", but the minimal type class to realize the effect is chosen from F/A/M.

If we burn bridges, we should do it properly.

Cheers,
Andreas


On 07.11.2014 20:35, Edward Kmett wrote:
I don't want them for rewriting liftM4 and liftM5, I want them in their
own right.

It doesn't do anyone any good to just have random asymmetries in the API
like that.

It just means a user goes to reach for a tool, doesn't find it and
flails around.

-Edward

On Fri, Nov 7, 2014 at 1:37 PM, John Lato <[hidden email]
<mailto:[hidden email]>> wrote:

    I still don't think it's worth adding liftA4 and liftA5 just so that
    liftM4+ can be rewritten.

    Very weakly -0.1

    On Fri Nov 07 2014 at 10:24:27 AM David Feuer <[hidden email]
    <mailto:[hidden email]>> wrote:

        Another point: using `liftA` or `liftM`, specialized to the
        relevant type, may reduce code size in some cases. With f <$> a
        <*> b <*> c and such, you have to hope that you either get some
        benefit from the inlining or that CSE is able to save you from
        the duplication.

        On Fri, Nov 7, 2014 at 7:47 AM, Jacques Carette
        <[hidden email] <mailto:[hidden email]>> wrote:

            On 2014-11-07 5:30 AM, Henning Thielemann wrote:


                On Fri, 7 Nov 2014, Andreas Abel wrote:

                    I hope the same happens for sequence, mapM and the like!

                      sequence :: (Applicative m) => [m a] -> m [a]
                      sequence = foldr (\ x xs -> (:) <$> x <*> xs)
                    (pure [])


                Actually, this is an example, where liftA2 shows its
                advantage:

                   sequence = foldr (liftA2 (:)) (pure [])

                This looks much clearer to me than decoding the mixture
                of infix and uninfixed infix operators. It simply says,
                that 'sequence' is like 'id = foldr (:) []' but with
                everything lifted to an applicative functor.


            I agree.  I have lots of code which looks really clean
            because I can use liftA2 (and even liftA3) in exactly the
            way above.  Having to eta expand everything obscures the
            real meat of what is going on.

            Jacques

            _________________________________________________
            Libraries mailing list
            [hidden email] <mailto:[hidden email]>
            http://www.haskell.org/__mailman/listinfo/libraries
            <http://www.haskell.org/mailman/listinfo/libraries>


        _________________________________________________
        Libraries mailing list
        [hidden email] <mailto:[hidden email]>
        http://www.haskell.org/__mailman/listinfo/libraries
        <http://www.haskell.org/mailman/listinfo/libraries>


    _______________________________________________
    Libraries mailing list
    [hidden email] <mailto:[hidden email]>
    http://www.haskell.org/mailman/listinfo/libraries



--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

David Feuer
On Sat, Nov 8, 2014 at 2:39 PM, Edward Kmett <[hidden email]> 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

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Andreas Abel-2
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 <[hidden email]
> <mailto:[hidden email]>> 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

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Edward Kmett-2
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 <[hidden email]> 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 <[hidden email]
<mailto:[hidden email]>> 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

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Conal Elliott
In reply to this post by Edward Kmett-2
Any recent thoughts on adding liftA4 and liftA5 to Control.Applicative?

On Sat, Nov 8, 2014 at 11:39 AM, Edward Kmett <[hidden email]> 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."

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.

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.

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.

-Edward

On Sat, Nov 8, 2014 at 7:42 AM, Andreas Abel <[hidden email]> wrote:
I am a bit alert about this discussion because it seems that we have quite different ideas about how the AMP implementation should affect the base libraries.

1. Where can we see and discuss the proposed changes?

Not on https://www.haskell.org/haskellwiki/Functor-Applicative-Monad_Proposal

Not on https://ghc.haskell.org/trac/ghc/ticket/9586

2. Imho, the reasonable thing is to

  rewrite all of F/A/M base functions such that they use the minimal F/A/M constraints.

This of course includes

  liftM  :: (Functor m) => (a -> b) -> m a -> m b
  liftM2 :: (Applicative m) => (a -> b -> c) -> m a -> m b -> m c

and sequence and friends even if the M postfix can then "only explained historically" (HT).

One can say "M" stands for "effectful", but the minimal type class to realize the effect is chosen from F/A/M.

If we burn bridges, we should do it properly.

Cheers,
Andreas


On 07.11.2014 20:35, Edward Kmett wrote:
I don't want them for rewriting liftM4 and liftM5, I want them in their
own right.

It doesn't do anyone any good to just have random asymmetries in the API
like that.

It just means a user goes to reach for a tool, doesn't find it and
flails around.

-Edward

On Fri, Nov 7, 2014 at 1:37 PM, John Lato <[hidden email]
<mailto:[hidden email]>> wrote:

    I still don't think it's worth adding liftA4 and liftA5 just so that
    liftM4+ can be rewritten.

    Very weakly -0.1

    On Fri Nov 07 2014 at 10:24:27 AM David Feuer <[hidden email]
    <mailto:[hidden email]>> wrote:

        Another point: using `liftA` or `liftM`, specialized to the
        relevant type, may reduce code size in some cases. With f <$> a
        <*> b <*> c and such, you have to hope that you either get some
        benefit from the inlining or that CSE is able to save you from
        the duplication.

        On Fri, Nov 7, 2014 at 7:47 AM, Jacques Carette
        <[hidden email] <mailto:[hidden email]>> wrote:

            On 2014-11-07 5:30 AM, Henning Thielemann wrote:


                On Fri, 7 Nov 2014, Andreas Abel wrote:

                    I hope the same happens for sequence, mapM and the like!

                      sequence :: (Applicative m) => [m a] -> m [a]
                      sequence = foldr (\ x xs -> (:) <$> x <*> xs)
                    (pure [])


                Actually, this is an example, where liftA2 shows its
                advantage:

                   sequence = foldr (liftA2 (:)) (pure [])

                This looks much clearer to me than decoding the mixture
                of infix and uninfixed infix operators. It simply says,
                that 'sequence' is like 'id = foldr (:) []' but with
                everything lifted to an applicative functor.


            I agree.  I have lots of code which looks really clean
            because I can use liftA2 (and even liftA3) in exactly the
            way above.  Having to eta expand everything obscures the
            real meat of what is going on.

            Jacques

            _________________________________________________
            Libraries mailing list
            [hidden email] <mailto:[hidden email]>
            http://www.haskell.org/__mailman/listinfo/libraries
            <http://www.haskell.org/mailman/listinfo/libraries>


        _________________________________________________
        Libraries mailing list
        [hidden email] <mailto:[hidden email]>
        http://www.haskell.org/__mailman/listinfo/libraries
        <http://www.haskell.org/mailman/listinfo/libraries>


    _______________________________________________
    Libraries mailing list
    [hidden email] <mailto:[hidden email]>
    http://www.haskell.org/mailman/listinfo/libraries



--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add liftA4 and liftA5 to match liftM4 and liftM5

Edward Kmett-2
Given the long discussion we've had here, I'll make a call from the standpoint of the CLC and say we'd happily accept a patch that added them.

-Edward

On Thu, Jul 14, 2016 at 2:38 PM, Conal Elliott <[hidden email]> wrote:
Any recent thoughts on adding liftA4 and liftA5 to Control.Applicative?

On Sat, Nov 8, 2014 at 11:39 AM, Edward Kmett <[hidden email]> 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."

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.

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.

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.

-Edward

On Sat, Nov 8, 2014 at 7:42 AM, Andreas Abel <[hidden email]> wrote:
I am a bit alert about this discussion because it seems that we have quite different ideas about how the AMP implementation should affect the base libraries.

1. Where can we see and discuss the proposed changes?

Not on https://www.haskell.org/haskellwiki/Functor-Applicative-Monad_Proposal

Not on https://ghc.haskell.org/trac/ghc/ticket/9586

2. Imho, the reasonable thing is to

  rewrite all of F/A/M base functions such that they use the minimal F/A/M constraints.

This of course includes

  liftM  :: (Functor m) => (a -> b) -> m a -> m b
  liftM2 :: (Applicative m) => (a -> b -> c) -> m a -> m b -> m c

and sequence and friends even if the M postfix can then "only explained historically" (HT).

One can say "M" stands for "effectful", but the minimal type class to realize the effect is chosen from F/A/M.

If we burn bridges, we should do it properly.

Cheers,
Andreas


On 07.11.2014 20:35, Edward Kmett wrote:
I don't want them for rewriting liftM4 and liftM5, I want them in their
own right.

It doesn't do anyone any good to just have random asymmetries in the API
like that.

It just means a user goes to reach for a tool, doesn't find it and
flails around.

-Edward

On Fri, Nov 7, 2014 at 1:37 PM, John Lato <[hidden email]
<mailto:[hidden email]>> wrote:

    I still don't think it's worth adding liftA4 and liftA5 just so that
    liftM4+ can be rewritten.

    Very weakly -0.1

    On Fri Nov 07 2014 at 10:24:27 AM David Feuer <[hidden email]
    <mailto:[hidden email]>> wrote:

        Another point: using `liftA` or `liftM`, specialized to the
        relevant type, may reduce code size in some cases. With f <$> a
        <*> b <*> c and such, you have to hope that you either get some
        benefit from the inlining or that CSE is able to save you from
        the duplication.

        On Fri, Nov 7, 2014 at 7:47 AM, Jacques Carette
        <[hidden email] <mailto:[hidden email]>> wrote:

            On 2014-11-07 5:30 AM, Henning Thielemann wrote:


                On Fri, 7 Nov 2014, Andreas Abel wrote:

                    I hope the same happens for sequence, mapM and the like!

                      sequence :: (Applicative m) => [m a] -> m [a]
                      sequence = foldr (\ x xs -> (:) <$> x <*> xs)
                    (pure [])


                Actually, this is an example, where liftA2 shows its
                advantage:

                   sequence = foldr (liftA2 (:)) (pure [])

                This looks much clearer to me than decoding the mixture
                of infix and uninfixed infix operators. It simply says,
                that 'sequence' is like 'id = foldr (:) []' but with
                everything lifted to an applicative functor.


            I agree.  I have lots of code which looks really clean
            because I can use liftA2 (and even liftA3) in exactly the
            way above.  Having to eta expand everything obscures the
            real meat of what is going on.

            Jacques

            _________________________________________________
            Libraries mailing list
            [hidden email] <mailto:[hidden email]>
            http://www.haskell.org/__mailman/listinfo/libraries
            <http://www.haskell.org/mailman/listinfo/libraries>


        _________________________________________________
        Libraries mailing list
        [hidden email] <mailto:[hidden email]>
        http://www.haskell.org/__mailman/listinfo/libraries
        <http://www.haskell.org/mailman/listinfo/libraries>


    _______________________________________________
    Libraries mailing list
    [hidden email] <mailto:[hidden email]>
    http://www.haskell.org/mailman/listinfo/libraries



--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
12