Define list monad operations using comprehensions
ClosedPublic

Authored by dfeuer on Nov 7 2014, 2:00 AM.

Details

Summary

Define list monad operations using list comprehensions. Code using monad operations with lists did not fuse fully. Writing list code with do notation or (>>=) and (>>) operations could allocate more than equivalent code using list comprehensions.

Define mapM directly, instead of using sequence and map. This leads to substantially less allocation in cryptarithm2.

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 1311.Nov 7 2014, 2:00 AM
dfeuer retitled this revision from to Define list monad operations using comprehensions.
dfeuer updated this object.
dfeuer edited the test plan for this revision. (Show Details)
dfeuer added reviewers: austin, hvr.
hvr edited edge metadata.Nov 7 2014, 2:41 AM

more generally, what's the motivation for this change?

libraries/base/GHC/Base.lhs
542–544 ↗(On Diff #1311)

why is this in this patch?

720–722 ↗(On Diff #1311)

can we have a source-note somewhere about INLINEing methods? I'm always forgetting why we want that

dfeuer added a comment.Nov 7 2014, 3:20 AM

More generally, the motivation for this change is to make list monad operations fuse as well as list comprehensions. See Trac #9781, which I just filed.

libraries/base/GHC/Base.lhs
542–544 ↗(On Diff #1311)

Probably not strictly necessary, but it should save the simplifier some work.

720–722 ↗(On Diff #1311)

Yeah, I'm not sure exactly which ones should and which ones shouldn't in general, but in this case, I want to do it because build forms don't really tend to inline well at all if we don't force the inliner's hand.

dfeuer added a project: GHC.
dfeuer updated the Trac tickets for this revision.
nomeata added inline comments.Nov 7 2014, 4:33 AM
libraries/base/GHC/Base.lhs
259 ↗(On Diff #1311)

Why not mconcat = concat. Sureley concat should be at least as efficient as mconcat?

544 ↗(On Diff #1311)

I think we should keep the code tidy if the tidy code is sufficiently fast. We want our users to be able to write nice code, that also applies to ourself (being user after all).

732 ↗(On Diff #1311)

Again, shouldn’t that be (>>=) = concatMap?

dfeuer added inline comments.Nov 7 2014, 6:57 AM
libraries/base/GHC/Base.lhs
259 ↗(On Diff #1311)

Remember where we are. There is no concat!

544 ↗(On Diff #1311)

Maybe.

732 ↗(On Diff #1311)

xs >>= f = concatMap f xs was actually my original approach. The problem is that we then need to move concatMap from GHC.List into Base and hide it from a few additional import lists. It works; it's just not as clean as one might like. I realized this go-round that we could just take advantage of the list comprehension desugaring to do the work for us. Now I do seem to recall that there is/was some kind of weird option to desugar via concatMap that this would break (if it's not already broken). Do you know about that?

nomeata accepted this revision.Nov 7 2014, 8:53 AM
nomeata edited edge metadata.
nomeata added inline comments.
libraries/base/GHC/Base.lhs
259 ↗(On Diff #1311)

Hmm. Weird new word^Hlist module order... *shrug*

Maybe add a comment -- cannot use concat here yet to that line? Surely people will wander when reading that code.

732 ↗(On Diff #1311)

No, doesn’t ring a bell.

dfeuer added inline comments.Nov 7 2014, 11:26 AM
libraries/base/GHC/Base.lhs
732 ↗(On Diff #1311)

Yeah, I think I got confused there. I think this should be safe.

ekmett accepted this revision.Nov 7 2014, 12:03 PM
ekmett added a reviewer: ekmett.
ekmett added a subscriber: ekmett.

LGTM

dfeuer updated this revision to Diff 1323.Nov 7 2014, 12:29 PM
dfeuer edited edge metadata.

Add list specialization for lifts; add comments; back off the
mapM change as requested.

dfeuer added a comment.Nov 7 2014, 1:29 PM

Something about the latest change caused a cryptarithm2 regression. I'm trying to see which.

dfeuer updated this revision to Diff 1324.Nov 7 2014, 1:56 PM

Put the mapM change back; it makes a big difference for
cryptarithm2

dfeuer updated this revision to Diff 1342.Nov 8 2014, 11:35 AM

Rebase following lhs->hs

dfeuer updated this revision to Diff 1395.Nov 10 2014, 11:24 PM

Remove list specialization pragmas as irrelevant and of unknown
value.

dfeuer updated this object.Nov 10 2014, 11:29 PM
This revision was automatically updated to reflect the committed changes.