#10892: ApplicativeDo should use *> and <* -------------------------------------+------------------------------------- Reporter: simonmar | Owner: simonmar Type: task | Status: new Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ekmett): Consider `Data.Sequence`. There `(<$>)` is `O(n)`, but `(<$)` is `O(log n)`. For any `Functor` that is representable, which is to say there exists `x` such that that `f a` is isomorphic to `x -> a`, you build a 'zipping' applicative that is isomorphic to reader. For that you can show that `(m *> _ = m)` and `(_ <* m = m)`. So `(<*)` and `(*>)` are `O(1)` while the `(<*>)` pays for every point used. In the case of something like {{{#!hs data Stream a = a :- Stream a }}} which is isomorphic to `Natural -> a`, if we look at the zipping applicative (which behaves like `ZipList`)` such an (*>) operation is O(1), but `(<*>)` incurs an ongoing cost O(n) in the length of the prefix of the result stream you inspect. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10892#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler