Add liftA2 to Applicative class
ClosedPublic

Authored by dfeuer on Jan 26 2017, 7:20 PM.

Details

Summary
  • Make liftA2 a method of Applicative.
  • Add explicit liftA2 definitions to instances in base.
  • Add explicit invocations in base.

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
dfeuer updated this revision to Diff 10742.Jan 26 2017, 7:20 PM
dfeuer retitled this revision from to Add liftA2 to Applicative class.
dfeuer updated this object.
dfeuer edited the test plan for this revision. (Show Details)

Why? This surely deserves some explanation somewhere.

bgamari edited edge metadata.Jan 26 2017, 7:44 PM

I would think that we would at least want to consult the CLC for a change like this. Moreover, what is the motivation for this? There are a few notes in the Haddock documentation for (*>), but something like this really deserves a note.

I would think that we would at least want to consult the CLC for a change like this. Moreover, what is the motivation for this? There are a few notes in the Haddock documentation for (*>), but something like this really deserves a note.

There's been some discussion on the libraries list, with some positive response and no negative response. I'd be happy to shoot a message to CLC as well. And yes, there should be a Trac ticket too. There are two important reasons:

  1. liftA2 can sometimes be considerably faster than its default definition. Using <*> as the fundamental operation is gratuitously inefficient.
  1. A number of people (including myself) see liftA2 as offering better insight into what Applicative is really about than <*> can.

Indeed, you should at the very least:

  1. Link to the actual Haskell libraries mailing list thread where this was discussed
  2. Open a Trac ticket for this issue
RyanGlScott requested changes to this revision.Jan 26 2017, 8:56 PM
RyanGlScott added a reviewer: RyanGlScott.

Oops, I didn't catch that you said you'd open a Trac issue in https://phabricator.haskell.org/D3031#88747. Splendid.

Now, to discuss the actual patch itself: this needs some more documentation! In particular, I don't see:

  1. Notes in the base changelog and the 8.2 release notes
  2. A note in docs/users_guide/bugs.rst (in particular, the Numbers, basic types, and built-in classes section) explaining this deviation from the Haskell Report
  3. A blurb in the Haddocks for liftA2 explaining when defining it manually would be more efficient that the default definition in terms of (<*>)
This revision now requires changes to proceed.Jan 26 2017, 8:56 PM
dfeuer edited edge metadata.Jan 26 2017, 9:12 PM
dfeuer updated the Trac tickets for this revision.

Oops, I didn't catch that you said you'd open a Trac issue in https://phabricator.haskell.org/D3031#88747. Splendid.

It's open now, and properly linked.

Now, to discuss the actual patch itself: this needs some more documentation! In particular, I don't see:

  1. Notes in the base changelog and the 8.2 release notes

I will add them.

  1. A note in docs/users_guide/bugs.rst (in particular, the Numbers, basic types, and built-in classes section) explaining this deviation from the Haskell Report

Certainly. Semi-relatedly, we have to decide whether to expose liftA2 from the Prelude or require users to import it explicitly from Control.Applicative.

  1. A blurb in the Haddocks for liftA2 explaining when defining it manually would be more efficient than the default definition in terms of (<*>)

Indeed.

dfeuer updated this revision to Diff 10748.Jan 26 2017, 11:36 PM
dfeuer edited edge metadata.

Hopefully make this build

dfeuer updated this revision to Diff 10751.Jan 27 2017, 2:20 AM
dfeuer edited edge metadata.
  • Use liftA2 in derived Traversable instances
ekmett added a subscriber: ekmett.Jan 27 2017, 2:36 AM

The core libraries discussion about this patch is still on-going.

dfeuer updated this revision to Diff 10753.Jan 27 2017, 7:25 AM
dfeuer edited edge metadata.
  • Accept new test result for T8848

The map2 rule still fires as required.

dfeuer updated this revision to Diff 10759.Jan 27 2017, 2:20 PM
dfeuer edited edge metadata.
  • Update documentation

@RyanGlScott, you're absolutely right that we need a note explaining the deviation from the Haskell Report, but in fact that note is overdue. Applicative is not in Haskell2010 at all, and the deviation was not noted as part of AMP. So we need a note about that, which probably doesn't need to be part of this patch. I'll open a ticket to do so.

bgamari requested changes to this revision.Jan 27 2017, 2:47 PM
bgamari edited edge metadata.

Generally looks good but a few comments inline.

compiler/typecheck/TcGenFunctor.hs
626

This deserves a comment since you aren't doing what the comment above claims.

libraries/base/Control/Applicative.hs
114

Are you sure we can drop the (<*>) definition?

libraries/base/Data/Functor/Identity.hs
119

Good catch.

This revision now requires changes to proceed.Jan 27 2017, 2:47 PM
dfeuer marked an inline comment as done.Jan 27 2017, 2:55 PM
dfeuer added inline comments.
compiler/typecheck/TcGenFunctor.hs
626

I'll edit the comment. Thanks.

libraries/base/Control/Applicative.hs
114

I'm pretty confident, yes. The default definition will fill in id for f, which passes it to zipWith. I believe the inliner would have to be having an exceptionally bad day for that to cause any trouble.

libraries/base/Data/Functor/Identity.hs
119

Actually, I just realized it's silly. Inlining should take care of this one for us. I'll revert.

How about a perf test or two that shows that all this makes a difference?

dfeuer marked an inline comment as done.Jan 27 2017, 3:02 PM

How about a perf test or two that shows that all this makes a difference?

Sure. Strict-spined ziplists without custom rewrite rules should make a convincing example Applicative, I think, combined with a binary leaf tree as a sample Traversable. You want one in the test suite?

In D3031#88900, @dfeuer wrote:

How about a perf test or two that shows that all this makes a difference?

Sure. Strict-spined ziplists without custom rewrite rules should make a convincing example Applicative, I think, combined with a binary leaf tree as a sample Traversable. You want one in the test suite?

Might as well. It doesn't have to be anything fancy. But I'll take numbers over "generally postive response on the libraries list" any day.

Ideally, the test would have a large (on the order of 2x) decrease in allocations, while still being realistic (but simple) code.

dfeuer marked 2 inline comments as done.Jan 28 2017, 6:06 PM

Hopefully everything's fixed now.

dfeuer updated this revision to Diff 10782.Jan 28 2017, 6:06 PM
dfeuer edited edge metadata.
  • Fix comments
dfeuer added a comment.Feb 4 2017, 5:17 PM

We have CLC approval, but I need to make a couple minor changes before
merging. In particular, I made liftA2 known-key, which I'm pretty sure is
overkill.

dfeuer updated this revision to Diff 10952.Feb 4 2017, 11:06 PM
dfeuer edited edge metadata.
  • Fix up
RyanGlScott requested changes to this revision.Feb 5 2017, 9:09 AM
RyanGlScott edited edge metadata.

Looks generally good. What about @rwbarton's comment which asks to add a performance test?

docs/users_guide/8.2.1-notes.rst
301–303

You might want to mention here that liftA2 is not yet in the Prelude, and must be imported from Control.Applicative for now, but that liftA2 will eventually be moved into the Prelude in the future.

libraries/base/changelog.md
52–55

Same here.

This revision now requires changes to proceed.Feb 5 2017, 9:09 AM
dfeuer updated this revision to Diff 10971.Feb 5 2017, 3:41 PM
dfeuer edited edge metadata.

Add perf test; add further info to change log

dfeuer added a comment.Feb 5 2017, 3:43 PM

Looks generally good. What about @rwbarton's comment which asks to add a performance test?

Done. And I've added some more documentation and such.

dfeuer updated this revision to Diff 10973.Feb 5 2017, 4:58 PM

Add stdout file for test.

RyanGlScott accepted this revision.Feb 5 2017, 5:03 PM

Assuming it validates, LGTM.

This revision was automatically updated to reflect the committed changes.