#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: None/Unknown | Unknown/Multiple Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by gidyn): * cc: gidyn (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: ekmett Type: bug | Status: patch Priority: normal | Milestone: Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: None/Unknown | Unknown/Multiple Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by fumieval): +1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: ekmett Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by strake888): * milestone: => 8.0.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by ekmett): For the record there is no objection here. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: infoneeded Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => infoneeded Comment: strake888, do you think you could put this up on Phabricator when you have a patch addressing dfeuer's comment? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: infoneeded Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): -------------------------------------+------------------------------------- Changes (by strake888): * Attachment "0001-generalize-filterM-mapAndUnzipM-zipWithM- zipWithM_-r.patch" added. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:1324 Wiki Page: | -------------------------------------+------------------------------------- Changes (by hvr): * differential: 1324 => Phab:1324 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1324 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"741cf18a5e4ee5d0aa8afcab813441e7bcd4050c/ghc" 741cf18/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="741cf18a5e4ee5d0aa8afcab813441e7bcd4050c" Weaken monadic list operations to Applicative Generalize `filterM`, `mapAndUnzipM`, `zipWithM`, `zipWithM_`, `replicateM`, and `replicateM_`. Reviewers: ekmett, #core_libraries_committee, austin, hvr, bgamari Reviewed By: ekmett, #core_libraries_committee, bgamari Subscribers: ekmett, glguy, thomie Projects: #ghc Differential Revision: https://phabricator.haskell.org/D1324 GHC Trac Issues: #10168 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1324 Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:14 ekmett]:

@strake888:

The notion I think dfeuer was trying to get at there was that `replicateM` can do 'peasant multiplication' like `(^)` does to get away with O(log n) distinct calls to `(<*>)`.

Don't give me so much credit; I was just thinking about eliminating the need for list fusion rules to fire to prevent GHC from building an intermediate list. The peasant multiplication idea is quite an interesting one. It would sometimes be good, and I don't think it could ever be terrible, but it certainly could be ''worse'' in some cases. I'd probably prefer separate combinators for fast exponentiation of `Monoid`s and `Applicative`s. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1324 Wiki Page: | -------------------------------------+------------------------------------- Comment (by ekmett): The difference is it can only be worse by a O(log n) factor worth of stack usage. On the other hand it can be better by an O(n / log n) factor in terms of both time and space. The upside dwarfs the downside. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1324 Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): My concern is that it will add that tiny factor to tight loops in `IO` and `ST` where every tiny little bit counts. Admittedly, the fact that I can't use an `STRef s Int` counter and get GHC to put it in a register rules out the use of `replicateM_` for a significant class of such loops, but I suspect my point is still valid. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1324 Wiki Page: | -------------------------------------+------------------------------------- Comment (by ekmett):

I doubt too many things offer a Wasserman special like that replicateA.

Consumption of the result with a Writer, Const, Reader, update monads, all benefit rather disproportionally. The Const case in particular is relevant as it basically shows how we'd foldMap and it and the writer case bring in every Monoid as something that can be folded over optimally. In general the idea of randomly inducing a bias here ensure that nothing smart _can_ be done by the consumer. You enforce worst-case asymptotic behavior by losing sharing. One option to compromise might be to look at a way that RULES can try out the biased association and then write back if it doesn't fuse away? Or even simpler, add RULES to rewrite the IO / ST cases into the biased form. We provably get no benefit from the tree for that style of effect and can't observe the difference in associativity for these concrete cases. As you note basically any transformer is going to have enough overhead to swamp this concern, so it is really only those sorts of things that are problematic. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10168: generalize filterM, mapAndUnzipM, zipWithM, zipWithM_, replicateM, replicateM_ -------------------------------------+------------------------------------- Reporter: strake888 | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Core Libraries | Version: 7.10.1-rc1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1324 Wiki Page: | -------------------------------------+------------------------------------- Comment (by rwbarton): I would be worried about not just IO but also some kind of structure that is intended to be produced and consumed in a streaming fashion, in O(1) space. Seems like that could blow up space usage arbitrarily with a repeated-squaring implementation. Including separate versions that use repeated squaring would make more sense (if we should include them at all; the use cases seem obscure and anyone can (already) just provide them in a package outside base). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10168#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler