[GHC] #10892: ApplicativeDo should use *> and <*

[GHC]

#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