[GHC] #13520: instance Alternative ZipList

[GHC]

#13520: instance Alternative ZipList
-------------------------------------+-------------------------------------
        Reporter:  Iceland_jack      |                Owner:  (none)
            Type:  feature request   |               Status:  closed
        Priority:  normal            |            Milestone:  8.4.1
       Component:  libraries/base    |              Version:  8.0.1
      Resolution:  fixed             |             Keywords:  newcomer
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D3416
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by Zemyla):

 The instance for `(<|>)` would probably be more efficient as:

 {{{
 #!haskell
 ZipList xs <|> ZipList ys = ZipList $ go (0 :: Int) xs where
   go n _ | n `seq` False = undefined
   go n [] = drop n ys
   go n (x:xs) = x:go (n + 1) xs
 }}}

 This way, it only has to iterate over xs once.

 Or, you could do it in `build`/`foldr` style:

 {{{
 #!haskell
 ZipList xs <|> ZipList ys = ZipList (build $ zipListPlusBF xs ys)

 zipListPlusBF :: [a] -> [a] -> (a -> b -> b) -> b -> b
 zipListPlusBF xs ys c z = foldr goX endX xs 0# where
   goX x r n# = c x $ r (n# +# 1#)
   endX n# = foldr goY endY ys n#
   goY y r n#
     | isTrue# (n# ># 0#) = r (n# -# 1#)
     | otherwise          = c y $ r 0#
   endY _ = z
 }}}

 This would have the advantage that it should ideally realize, for
 instance, that pure x <|> anything = pure x, or at the very least doesn't
 reference the right-hand side at all.

 We could probably use both and switch between them with `RULES` like is
 done for most of the algorithms in `Data.List`.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13520#comment:9>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler