Small ZipList optimisation

In (<|>) for ZipList, avoid processing the first argument twice (both as first
argument of (++) and for its length in drop count of the second argument).

Previously, the entire first argument was forced into memory, now (<|>) can run
in constant space even with long inputs.

1 files changed, 6 insertions, 2 deletions

diff --git a/libraries/base/Control/Applicative.hs b/libraries/base/Control/Applicative.hs
index ebfb00d3c1..bb49d2131c 100644
--- a/libraries/base/Control/Applicative.hs
+++ b/libraries/base/Control/Applicative.hs
@@ -60,7 +60,7 @@ import Data.Functor.Const (Const(..))
 
 import GHC.Base
 import GHC.Generics
-import GHC.List (repeat, zipWith, drop)
+import GHC.List (repeat, zipWith)
 import GHC.Read (Read)
 import GHC.Show (Show)
 
@@ -140,7 +140,11 @@ instance Applicative ZipList where
 -- | @since 4.11.0.0
 instance Alternative ZipList where
    empty = ZipList []
-   ZipList xs <|> ZipList ys = ZipList (xs ++ drop (length xs) ys)
+   ZipList xs0 <|> ZipList ys0 = ZipList $ go xs0 ys0
+     where
+       go (x:xs) (_:ys) = x : go xs ys
+       go    []     ys  = ys
+       go    xs      _  = xs
 
 -- extra functions