{-# OPTIONS_GHC -O2 -fbang-patterns -fdicts-cheap #-}
-- |
-- Module      : Data.List.Stream
-- Copyright   : (c) Duncan Coutts 2007
--               (c) Don Stewart   2007
-- License     : BSD-style
-- Maintainer  : dons@cse.unsw.edu.au
-- Stability   : experimental
-- Portability : portable
--
-- A reimplementation of the standard Haskell list library to take advantage of
-- stream fusion, and new GHC optimisations. The fusion mechanism is
-- based on stream fusion for sequences. Described in: 
--
-- *    /Stream Fusion: From Lists to Streams to Nothing at All/, by
--      Duncan Coutts, Roman Leshchinskiy and Don Stwwart, ICFP 2007.
--      <http://www.cse.unsw.edu.au/~dons/papers/CLS07.html>
--
-- *    /Rewriting Haskell Strings/, by Duncan Coutts, Don Stewart and
--      Roman Leshchinskiy, Practical Aspects of Declarative Languages
--      8th International Symposium, PADL 2007, 2007.
--      <http://www.cse.unsw.edu.au/~dons/papers/CSL06.html>
--
-- See the source for the complete story:
--
-- * <http://www.cse.unsw.edu.au/~dons/code/streams/list/Data/Stream.hs>
--
-- This library is a drop in replacement for "Data.List".
--
module Data.List.Stream (

    -- $fusion_intro

    -- * Basic interface
    (++),                   -- :: [a] -> [a] -> [a]
    head,                   -- :: [a] -> a
    last,                   -- :: [a] -> a
    tail,                   -- :: [a] -> [a]
    init,                   -- :: [a] -> [a]
    null,                   -- :: [a] -> Bool
    length,                 -- :: [a] -> Int

    -- * List transformations
    map,                    -- :: (a -> b) -> [a] -> [b]
    reverse,                -- :: [a] -> [a]
    intersperse,            -- :: a -> [a] -> [a]
    intercalate,            -- :: [a] -> [[a]] -> [a]
    transpose,              -- :: [[a]] -> [[a]]

    -- * Reducing lists (folds)
    foldl,                  -- :: (a -> b -> a) -> a -> [b] -> a
    foldl',                 -- :: (a -> b -> a) -> a -> [b] -> a
    foldl1,                 -- :: (a -> a -> a) -> [a] -> a
    foldl1',                -- :: (a -> a -> a) -> [a] -> a
    foldr,                  -- :: (a -> b -> b) -> b -> [a] -> b
    foldr1,                 -- :: (a -> a -> a) -> [a] -> a

    -- ** Special folds
    concat,                 -- :: [[a]] -> [a]
    concatMap,              -- :: (a -> [b]) -> [a] -> [b]
    and,                    -- :: [Bool] -> Bool
    or,                     -- :: [Bool] -> Bool
    any,                    -- :: (a -> Bool) -> [a] -> Bool
    all,                    -- :: (a -> Bool) -> [a] -> Bool
    sum,                    -- :: Num a => [a] -> a
    product,                -- :: Num a => [a] -> a
    maximum,                -- :: Ord a => [a] -> a
    minimum,                -- :: Ord a => [a] -> a

    -- * Building lists
    -- ** Scans
    scanl,                  -- :: (a -> b -> a) -> a -> [b] -> [a]
    scanl1,                 -- :: (a -> a -> a) -> [a] -> [a]
    scanr,                  -- :: (a -> b -> b) -> b -> [a] -> [b]
    scanr1,                 -- :: (a -> a -> a) -> [a] -> [a]

    -- ** Accumulating maps
    mapAccumL,              -- :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
    mapAccumR,              -- :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])

    -- ** Infinite lists
    iterate,                -- :: (a -> a) -> a -> [a]
    repeat,                 -- :: a -> [a]
    replicate,              -- :: Int -> a -> [a]
    cycle,                  -- :: [a] -> [a]

    -- ** Unfolding
    unfoldr,                -- :: (b -> Maybe (a, b)) -> b -> [a]

    -- * Sublists
    -- ** Extracting sublists
    take,                   -- :: Int -> [a] -> [a]
    drop,                   -- :: Int -> [a] -> [a]
    splitAt,                -- :: Int -> [a] -> ([a], [a])
    takeWhile,              -- :: (a -> Bool) -> [a] -> [a]
    dropWhile,              -- :: (a -> Bool) -> [a] -> [a]
    span,                   -- :: (a -> Bool) -> [a] -> ([a], [a])
    break,                  -- :: (a -> Bool) -> [a] -> ([a], [a])
    group,                  -- :: Eq a => [a] -> [[a]]
    inits,                  -- :: [a] -> [[a]]
    tails,                  -- :: [a] -> [[a]]

    -- * Predicates
    isPrefixOf,             -- :: Eq a => [a] -> [a] -> Bool
    isSuffixOf,             -- :: Eq a => [a] -> [a] -> Bool
    isInfixOf,              -- :: Eq a => [a] -> [a] -> Bool

    -- * Searching lists
    -- ** Searching by equality
    elem,                   -- :: Eq a => a -> [a] -> Bool
    notElem,                -- :: Eq a => a -> [a] -> Bool
    lookup,                 -- :: Eq a => a -> [(a, b)] -> Maybe b

    -- ** Searching with a predicate
    find,                   -- :: (a -> Bool) -> [a] -> Maybe a
    filter,                 -- :: (a -> Bool) -> [a] -> [a]
    partition,              -- :: (a -> Bool) -> [a] -> ([a], [a])

    -- * Indexing lists

    -- | These functions treat a list @xs@ as a indexed collection,
    -- with indices ranging from 0 to @'length' xs - 1@.
    (!!),                   -- :: [a] -> Int -> a
    elemIndex,              -- :: Eq a => a -> [a] -> Maybe Int
    elemIndices,            -- :: Eq a => a -> [a] -> [Int]
    findIndex,              -- :: (a -> Bool) -> [a] -> Maybe Int
    findIndices,            -- :: (a -> Bool) -> [a] -> [Int]

    -- * Zipping and unzipping lists
    zip,                    -- :: [a] -> [b] -> [(a, b)]
    zip3,                   -- :: [a] -> [b] -> [c] -> [(a, b, c)]
    zip4,
    zip5,
    zip6,
    zip7,

    -- | The zipWith family generalises the zip family by zipping with the
    -- function given as the first argument, instead of a tupling function.
    zipWith,                -- :: (a -> b -> c) -> [a] -> [b] -> [c]
    zipWith3,               -- :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
    zipWith4,
    zipWith5,
    zipWith6,
    zipWith7,

    unzip,                  -- :: [(a, b)] -> ([a], [b])
    unzip3,                 -- :: [(a, b, c)] -> ([a], [b], [c])
    unzip4,
    unzip5,
    unzip6,
    unzip7,

    -- * Special lists
    -- ** Functions on strings
    lines,                  -- :: String -> [String]
    words,                  -- :: String -> [String]
    unlines,                -- :: [String] -> String
    unwords,                -- :: [String] -> String

    -- ** \"Set\" operations
    nub,                    -- :: Eq a => [a] -> [a]
    delete,                 -- :: Eq a => a -> [a] -> [a]
    (\\),                   -- :: Eq a => [a] -> [a] -> [a]
    union,                  -- :: Eq a => [a] -> [a] -> [a]
    intersect,              -- :: Eq a => [a] -> [a] -> [a]

    -- ** Ordered lists 
    sort,                   -- :: Ord a => [a] -> [a]
    insert,                 -- :: Ord a => a -> [a] -> [a]

    -- * Generalized functions
    -- ** The \"By\" operations

    -- | By convention, overloaded functions have a non-overloaded
    -- counterpart whose name is suffixed with \`@By@\'.
    --
    -- It is often convenient to use these functions together with
    -- 'Data.Function.on', for instance @'sortBy' ('compare'
    -- \`on\` 'fst')@.

    -- *** User-supplied equality (replacing an Eq context)

    -- | The predicate is assumed to define an equivalence.
    nubBy,                  -- :: (a -> a -> Bool) -> [a] -> [a]
    deleteBy,               -- :: (a -> a -> Bool) -> a -> [a] -> [a]
    deleteFirstsBy,         -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
    unionBy,                -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
    intersectBy,            -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
    groupBy,                -- :: (a -> a -> Bool) -> [a] -> [[a]]

    -- *** User-supplied comparison (replacing an Ord context)
    sortBy,                 -- :: (a -> a -> Ordering) -> [a] -> [a]
    insertBy,               -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
    maximumBy,              -- :: (a -> a -> Ordering) -> [a] -> a
    minimumBy,              -- :: (a -> a -> Ordering) -> [a] -> a

    -- * The \"generic\" operations
    -- | The prefix \`@generic@\' indicates an overloaded function that
    -- is a generalized version of a "Prelude" function.
    genericLength,          -- :: Num i => [b] -> i
    genericTake,            -- :: Integral i => i -> [a] -> [a]
    genericDrop,            -- :: Integral i => i -> [a] -> [a]
    genericSplitAt,         -- :: Integral i => i -> [a] -> ([a], [a])
    genericIndex,           -- :: Integral a => [b] -> a -> b
    genericReplicate,       -- :: Integral i => i -> a -> [a]

    -- helper for GHC.List
    errorEmptyList          -- :: String -> a

  ) where

#ifndef EXTERNAL_PACKAGE

import {-# SOURCE #-} GHC.Err      ( error )
import {-# SOURCE #-} GHC.Real     (Integral)
import {-# SOURCE #-} GHC.Num      (Num(..))
import {-# SOURCE #-} GHC.Unicode  (isSpace)

import GHC.Base (Int, Eq(..), Ord(..), Ordering(..),
                 Bool(..), not, Ordering(..),
                 seq, otherwise, flip,
                 Monad(..),
                 Char, String,
                 Int(I#), Int#, (+#),
                 -- we just reuse these:
                 foldr, (++), map
                )

import Data.Maybe   (Maybe(..))

#else

import GHC.Exts (Int(I#), Int#, (+#))
import Prelude (Int,
                Integral,
                Num(..), Eq(..), Ord(..), Ordering(..),
                Bool(..), not, Maybe(..), Char, String,
                error, seq, otherwise, flip)

import Data.Char (isSpace)

#endif


import qualified Data.Stream as Stream
import Data.Stream (stream ,unstream)

-- -----------------------------------------------------------------------------

#ifdef EXTERNAL_PACKAGE
infixr 5 ++
#endif

infix  5 \\ -- comment to fool cpp
infixl 9 !!
infix  4 `elem`, `notElem`

-- -----------------------------------------------------------------------------

-- $fusion_intro
--
-- The functions in this library marked with /fusion/ are
-- (transparently) rewritten by the compiler to stream functions, using
-- the fusion framework described in /Rewriting Haskell Strings/.
--
-- For example:
--
-- > map f xs
-- 
-- is transformed via rewrite rules to:
--
-- > (unstream . mapS f . stream) xs
--
-- The 'unstream' and 'stream' functions identify the allocation points
-- for each function.
--
-- When two or more fusible functions are in close proximity (i.e.
-- directly composed, or with only intermediate lets and cases), the
-- fusion rule will fire, removing the intermediate structures.
--
-- Consider:
--
-- > map f . map g
-- 
-- The rewrite engine will transform this code to:
--
-- > unstream . mapS f . stream . unstream . mapS g . stream
--
-- The fusion rule will then fire:
--
-- > unstream . mapS f . mapS g . stream
--
-- Removing the intermeidate list that is allocated. The compiler then
-- optimises the result.
--
-- Functions that fail to fuse are not left in stream form. In the final
-- simplifier phase any remaining unfused functions of the form:
--
-- > unstream . g . stream
--
-- Will be transformed back to their original list implementation.
--

--
-- Notes on simplifer phasing
--
-- * api functions should be rewritten to fusible forms as soon as possble
-- * This implies a NOINLINE [1] on the top level functions, so if ghc wants
--      to inline them they'll only have their bodies inlined at the end.
-- * These rewrite rules can then fire in any but the last phase:
--      "++ -> fusible" [~1] forall xs ys.
-- * Finally, if we reach the final phase, rewrite back to best effort [a] forms:
--      "++ -> unfused" [1] forall xs ys.
-- * And then inline the result.
--
-- If fusion occurs though, hang on to those 'stream' and 'unstream' pairs:
--  {-# INLINE [0] unstream #-} -- hmm?
--
-- Todo: notes on the phasing of Streams
--

-- -----------------------------------------------------------------------------
-- Fusion for the constructors:

--
-- We do not enable fusion for (:), as it leads to a massive massive
-- slow down in compilation time.
--
{- RULES
"(:) -> fusible" [~1] forall x xs.
    x : xs = unstream (Stream.cons x (stream xs))
"(:) -> unfused" [1] forall x xs.
    unstream (Stream.cons x (stream xs)) = x : xs
  -}

-- -----------------------------------------------------------------------------
-- Basic interface

-- | /O(n)/, /fusion/. Append two lists, i.e.,
--
-- > [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
-- > [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
--
-- If the first list is not finite, the result is the first list.
-- The spine of the first list argument must be copied.

#ifdef EXTERNAL_PACKAGE
(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys
{-# NOINLINE [1] (++) #-}
#endif

-- NOTE: This is quite subtle as we do not want to copy the last list in
--
-- xs1 ++ xs2 ++ ... ++ xsn
--
-- Indeed, we don't really want to fuse the above at all unless at least 
-- one of the arguments has the form (unstream s) or the result of the
-- concatenation is streamed. The rules below do precisely that. Note they
-- really fuse instead of just rewriting things into a fusible form so there
-- is no need to rewrite back.

{-# RULES
"++ -> fused on 1st arg" [~1] forall xs ys.
    unstream xs ++ ys = Stream.append1 xs ys
"++ -> fused on 2nd arg" [~1] forall xs ys.
    Stream.append1 xs (unstream ys) = unstream (Stream.append xs ys)
"++ -> fused (1)" [~1] forall xs ys.
    stream (xs ++ ys) = Stream.append (stream xs) (stream ys)
"++ -> fused (2)" [~1] forall xs ys.
    stream (Stream.append1 xs ys) = Stream.append xs (stream ys)

"++ -> 1st arg empty" forall xs.
    [] ++ xs = xs
"++ -> 2nd arg empty" forall xs.
    xs ++ [] = xs
"++ / :" forall x xs ys.
    (x:xs) ++ ys = x : (xs ++ ys)
 #-}

-- | /O(1)/, /fusion/. Extract the first element of a list, which must be
-- non-empty.
head :: [a] -> a
head (x:_) = x
head []    = errorEmptyList "head"
{-# NOINLINE [1] head #-}

{-# RULES
"head -> fusible" [~1] forall xs.
    head xs = Stream.head (stream xs)
"head -> unfused" [1] forall xs.
    Stream.head (stream xs) = head xs
  #-}

-- | /O(n)/, /fusion/. Extract the last element of a list, which must be finite
-- and non-empty.
last :: [a] -> a
last []     = errorEmptyList "last"
last (x:xs) = last' x xs
  where
    last' y []     = y
    last' _ (y:ys) = last' y ys
{-# NOINLINE [1] last #-}

{-# RULES
"last -> fusible" [~1] forall xs.
    last xs = Stream.last (stream xs)
"last -> unfused" [1] forall xs.
    Stream.last (stream xs) = last xs
  #-}

-- | /O(1)/, /fusion/. Extract the elements after the head of a list, which
-- must be non-empty.
tail :: [a] -> [a]
tail (_:xs) = xs
tail []     = errorEmptyList "tail"
{-# NOINLINE [1] tail #-}

{-# RULES
"tail -> fusible" [~1] forall xs.
    tail xs = unstream (Stream.tail (stream xs))
"tail -> unfused" [1] forall xs.
    unstream (Stream.tail (stream xs)) = tail xs
  #-}

-- | /O(n)/, /fusion/. Return all the elements of a list except the last one.
-- The list must be finite and non-empty.
init :: [a] -> [a]
init []     = errorEmptyList "init"
init (x:xs) = init' x xs
  where
    init' _ []     = []
    init' y (z:zs) = y : init' z zs
{-# NOINLINE [1] init #-}

{-# RULES
"init -> fusible" [~1] forall xs.
    init xs = unstream (Stream.init (stream xs))
"init -> unfused" [1] forall xs.
    unstream (Stream.init (stream xs)) = init xs
  #-}

-- | /O(1)/, /fusion/. Test whether a list is empty.
null :: [a] -> Bool
null []    = True
null (_:_) = False
{-# NOINLINE [1] null #-}

{-# RULES
"null -> fusible" [~1] forall xs.
    null xs = Stream.null (stream xs)
"null -> unfused" [1] forall xs.
    Stream.null (stream xs) = null xs
  #-}

-- | /O(n)/, /fusion/. 'length' returns the length of a finite list as an 'Int'.
-- It is an instance of the more general 'Data.List.genericLength',
-- the result type of which may be any kind of number.
length :: [a] -> Int
length xs0 = len xs0 0#
#ifndef __HADDOCK__
  where
    len :: [a] -> Int# -> Int
    len []     a# = I# a#
    len (_:xs) a# = len xs (a# +# 1#)
#endif
{-# NOINLINE [1] length #-}

{-# RULES
"length -> fusible" [~1] forall xs.
    length xs = Stream.length (stream xs)
"length -> unfused" [1] forall xs.
    Stream.length (stream xs) = length xs
  #-}

-- ---------------------------------------------------------------------
-- List transformations

-- | /O(n)/, /fusion/. 'map' @f xs@ is the list obtained by applying @f@ to each element
-- of @xs@, i.e.,
--
-- > map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
-- > map f [x1, x2, ...] == [f x1, f x2, ...]
--
-- Properties:
--
-- > map f . map g         = map (f . g)
-- > map f (repeat x)      = repeat (f x)
-- > map f (replicate n x) = replicate n (f x)

#ifdef EXTERNAL_PACKAGE
map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs
{-# NOINLINE [1] map #-}
#endif

{-# RULES
"map -> fusible" [~1] forall f xs.
    map f xs = unstream (Stream.map f (stream xs))
"map -> unfused" [1] forall f xs.
    unstream (Stream.map f (stream xs)) = map f xs
  #-}

-- | /O(n)/, /fusion/. 'reverse' @xs@ returns the elements of @xs@ in reverse order.
-- @xs@ must be finite. Will fuse as a consumer only.
reverse :: [a] -> [a]
reverse = foldl' (flip (:)) []
{-# INLINE reverse #-}

{-
reverse l = rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
-}

{-
--TODO: I'm sure there are some cunning things we can do with optimising
-- reverse. Of course if we try and fuse we may need to still force the
-- sping of the list: eg reverse . reverse = forceSpine

forceSpine :: [a] -> [a]
forceSpine xs = forceSpine' xs `seq` xs
{-# INLINE forceSpine #-}

-- The idea of this slightly odd construction is that we inline the above form
-- and in the context we may then be able to use xs directly and just keep
-- around the fact that xs must be forced at some point. Remember, seq does not
-- imply any evaluation order.

forceSpine' :: [a] -> ()
forceSpine' []      = ()
forceSpine' (_:xs') = forceSpine' xs'
{-# NOINLINE forceSpine' #-}
-}

-- | /O(n)/, /fusion/. The 'intersperse' function takes an element and a list and
-- \`intersperses\' that element between the elements of the list.
-- For example,
--
-- > intersperse ',' "abcde" == "a,b,c,d,e"
--
intersperse :: a -> [a] -> [a]
intersperse _   []       = []
intersperse sep (x0:xs0) = x0 : go xs0
  where
    go []     = []
    go (x:xs) = sep : x : go xs
{-# NOINLINE [1] intersperse #-}

{- RULES
"intersperse -> fusible" [~1] forall x xs.
    intersperse x xs = unstream (Stream.intersperse x (stream xs))
"intersperse -> unfused" [1] forall x xs.
    unstream (Stream.intersperse x (stream xs)) = intersperse x xs
  -}

-- | /O(n)/, /fusion/. 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
-- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
-- result.
--
-- > intercalate = concat . intersperse
--
intercalate :: [a] -> [[a]] -> [a]
intercalate sep xss = go (intersperse sep xss)
  where
    go []     = []
    go (y:ys) = y ++ go ys
{-# NOINLINE [1] intercalate #-}

{-
intercalate _   []         = []
intercalate sep (xs0:xss0) = go xs0 xss0
  where
    go []     xss = to xss
    go (x:xs) xss = x : go xs xss

    to []       = []
    to (xs:xss) = go' sep xs xss

    go' []     xs xss = go xs xss
    go' (s:ss) xs xss = s : go' ss xs xss
{-# NOINLINE [1] intercalate #-}
-}

-- fusion rule based on:
--      intercalate = concat . intersperse
--
{- RULES
"intercalate -> fusible" [~1] forall x xs.
    intercalate x xs = Stream.concat (Stream.intersperse x (stream xs))
"intercalate -> unfused" [1] forall x xs.
    Stream.concat (Stream.intersperse x (stream xs)) = intercalate x xs
  -}

-- | The 'transpose' function transposes the rows and columns of its argument.
-- For example,
--
-- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
--
transpose :: [[a]] -> [[a]]
transpose []             = []
transpose ([]     : xss) = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:_t) <- xss])
                         : transpose (xs : [ t | (_h:t) <- xss])

-- TODO fuse

-- ---------------------------------------------------------------------
-- Reducing lists (folds)

-- | /O(n)/, /fusion/. 'foldl', applied to a binary operator, a starting value (typically
-- the left-identity of the operator), and a list, reduces the list
-- using the binary operator, from left to right:
--
-- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--
-- The list must be finite.
--
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = go z0 xs0
  where
    go z []     = z
    go z (x:xs) = go (f z x) xs
{-# INLINE [1] foldl #-}

{-# RULES
"foldl -> fusible"  [~1] forall f z xs.
    foldl f z xs = Stream.foldl f z (stream xs)
"foldl -> unfused" [1] forall f z xs.
    Stream.foldl f z (stream xs) = foldl f z xs
  #-}

-- | /O(n)/, /fusion/. A strict version of 'foldl'.
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f z0 xs0 = go z0 xs0
#ifndef __HADDOCK__
  where
    go !z []     = z
    go !z (x:xs) = go (f z x) xs
#endif
{-# INLINE [1] foldl' #-}

{-# RULES
"foldl' -> fusible"  [~1] forall f z xs.
    foldl' f z xs = Stream.foldl' f z (stream xs)
"foldl' -> unfused" [1] forall f z xs.
    Stream.foldl' f z (stream xs) = foldl' f z xs
  #-}

-- | /O(n)/, /fusion/. 'foldl1' is a variant of 'foldl' that has no starting value argument,
-- and thus must be applied to non-empty lists.
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 _ []       = errorEmptyList "foldl1"
foldl1 f (x0:xs0) = go x0 xs0
  where
    go z []     = z
    go z (x:xs) = go (f z x) xs
{-# INLINE [1] foldl1 #-}

{-# RULES
"foldl1 -> fusible"  [~1] forall f xs.
    foldl1 f xs = Stream.foldl1 f (stream xs)
"foldl1 -> unfused" [1] forall f xs.
    Stream.foldl1 f (stream xs) = foldl1 f xs
  #-}

-- | /O(n)/, /fusion/. A strict version of 'foldl1'
foldl1' :: (a -> a -> a) -> [a] -> a
foldl1' _ []       = errorEmptyList "foldl1'"
foldl1' f (x0:xs0) = go x0 xs0
#ifndef __HADDOCK__
  where
    go !z []     = z
    go !z (x:xs) = go (f z x) xs
#endif
{-# INLINE [1] foldl1' #-}

{-# RULES
"foldl1' -> fusible"  [~1] forall f xs.
    foldl1' f xs = Stream.foldl1' f (stream xs)
"foldl1 -> unfused" [1] forall f xs.
    Stream.foldl1' f (stream xs) = foldl1' f xs
  #-}

-- | /O(n)/, /fusion/. 'foldr', applied to a binary operator, a starting value (typically
-- the right-identity of the operator), and a list, reduces the list
-- using the binary operator, from right to left:
--
-- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

#ifdef EXTERNAL_PACKAGE
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z xs = go xs
  where
    go []     = z
    go (y:ys) = y `k` go ys
{-# INLINE [0] foldr #-}
#endif

{-# RULES
"foldr -> fusible"  [~1] forall f z xs.
    foldr f z xs = Stream.foldr f z (stream xs)
"foldr -> unfused" [1] forall f z xs.
    Stream.foldr f z (stream xs) = foldr f z xs
  #-}

-- | /O(n)/, /fusion/. 'foldr1' is a variant of 'foldr' that has no starting value argument,
-- and thus must be applied to non-empty lists.
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 _ []          = errorEmptyList "foldr1"
foldr1 k (x0:xs0)    = go x0 xs0
  where go x []      = x
        go x (x':xs) = k x (go x' xs)
{-# INLINE [1] foldr1 #-}

{-# RULES
"foldr1 -> fusible"  [~1] forall f xs.
    foldr1 f xs = Stream.foldr1 f (stream xs)
"foldr1 -> unfused" [1] forall f xs.
    Stream.foldr1 f (stream xs) = foldr1 f xs
  #-}

-- ---------------------------------------------------------------------
-- Special folds

-- | /O(n)/, /fusion/. Concatenate a list of lists.
concat :: [[a]] -> [a]
concat xss0 = to xss0
  where go []     xss = to xss
        go (x:xs) xss = x : go xs xss

        to []       = []
        to (xs:xss) = go xs xss -- hmm, this is slower than the old concat?
{-# NOINLINE [1] concat #-}

--
-- fuse via concatMap, as the Stream (Stream a) is too hard to construct
-- 
-- or via foldr (++) ?
--
{-# RULES
"concat -> fused"  [~1] forall xs.
    concat xs = Stream.concat (stream xs)
"concat -> unfused" [1] forall xs.
    Stream.concat (stream xs) = concat xs
  #-}

-- | /O(n)/, /fusion/. Map a function over a list and concatenate the results.
concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f = foldr (\x y -> f x ++ y) [] -- at least it will fuse.
{-# INLINE concatMap #-}

{-
concatMap f as0 = to as0
  where
    go []     as = to as
    go (b:bs) as = b : go bs as

    to []     = []
    to (a:as) = go (f a) as
{-# NOINLINE [1] concatMap #-}
-}
{- RULES
"concatMap -> fusible"  [~1] forall f xs.
    concatMap f xs = Stream.concatMap f (stream xs)
"concatMap -> unfused"  [1] forall f xs.
    Stream.concatMap f (stream xs) = concatMap f xs
  -}

-- | /O(n)/, /fusion/. 'and' returns the conjunction of a Boolean list.  For the result to be
-- 'True', the list must be finite; 'False', however, results from a 'False'
-- value at a finite index of a finite or infinite list.
--
and :: [Bool] -> Bool
and []         = True
and (False:_ ) = False
and (_    :xs) = and xs
{-# NOINLINE [1] and #-}

{-# RULES
"and -> fused"  [~1] forall xs.
    and xs = Stream.and (stream xs)
"and -> unfused" [1] forall xs.
    Stream.and (stream xs) = and xs
  #-}

-- | /O(n)/, /fusion/. 'or' returns the disjunction of a Boolean list.  For the result to be
-- 'False', the list must be finite; 'True', however, results from a 'True'
-- value at a finite index of a finite or infinite list.
or :: [Bool] -> Bool
or []        = False
or (True:_ ) = True
or (_   :xs) = or xs
{-# NOINLINE [1] or #-}

{-# RULES
"or -> fused"  [~1] forall xs.
    or xs = Stream.or (stream xs)
"or -> unfused" [1] forall xs.
    Stream.or (stream xs) = or xs
  #-}

-- | /O(n)/, /fusion/. Applied to a predicate and a list, 'any' determines if any element
-- of the list satisfies the predicate.
any :: (a -> Bool) -> [a] -> Bool
any p xs0 = go xs0
  where go []     = False
        go (x:xs) = case p x of
                      True  -> True
                      False -> go xs
{-# NOINLINE [1] any #-}

--TODO: check if being lazy in p is a cost,
--      should we do [] as a special case and then strictly evaluate p?

{-# RULES
"any -> fusible"  [~1] forall f xs.
    any f xs = Stream.any f (stream xs)
"any -> unfused" [1] forall f xs.
    Stream.any f (stream xs) = any f xs
  #-}

-- | Applied to a predicate and a list, 'all' determines if all elements
-- of the list satisfy the predicate.
all :: (a -> Bool) -> [a] -> Bool
all p xs0 = go xs0
  where go []     = True
        go (x:xs) = case p x of
                      True  -> go xs
                      False -> False
{-# NOINLINE [1] all #-}

{-# RULES
"all -> fusible"  [~1] forall f xs.
    all f xs = Stream.all f (stream xs)
"all -> unfused" [1] forall f xs.
    Stream.all f (stream xs) = all f xs
  #-}

-- | /O(n)/, /fusion/. The 'sum' function computes the sum of a finite list of numbers.
sum :: Num a => [a] -> a
sum l = sum' l 0
#ifndef __HADDOCK__
  where
    sum' []     a = a
    sum' (x:xs) a = sum' xs (a+x)
#endif
{-# NOINLINE [1] sum #-}

sumInt :: [Int] -> Int
sumInt l = sum' l 0
#ifndef __HADDOCK__
  where
    sum' []      a = a
    sum' (x:xs) !a = sum' xs (a+x)
#endif
{-# NOINLINE [1] sumInt #-}

{-# RULES
"sum spec Int" sum = sumInt :: [Int] -> Int
  #-}

{-# RULES
"sum -> fusible"  [~1] forall xs.
    sum xs = Stream.sum (stream xs)
"sum -> unfused" [1] forall xs.
    Stream.sum (stream xs) = sum xs
  #-}

{-# RULES
"sumInt -> fusible"  [~1] forall (xs :: [Int]).
    sumInt xs = Stream.sum (stream xs)
"sumInt -> unfused" [1] forall (xs :: [Int]).
    Stream.sum (stream xs) = sumInt xs
  #-}

-- | /O(n)/,/fusion/. The 'product' function computes the product of a finite list of numbers.
product :: Num a => [a] -> a
product l = prod l 1
#ifndef __HADDOCK__
  where
    prod []     a = a
    prod (x:xs) a = prod xs (a*x)
#endif
{-# NOINLINE [1] product #-}

productInt :: [Int] -> Int
productInt l = product' l 0
#ifndef __HADDOCK__
  where
    product' []      a = a
    product' (x:xs) !a = product' xs (a*x)
#endif
{-# NOINLINE [1] productInt #-}

{-# RULES
"product spec Int" product = productInt :: [Int] -> Int
  #-}

{-# RULES
"product -> fused"  [~1] forall xs.
    product xs = Stream.product (stream xs)
"product -> unfused" [1] forall xs.
    Stream.product (stream xs) = product xs
  #-}

{-# RULES
"productInt -> fusible"  [~1] forall (xs :: [Int]).
    productInt xs = Stream.product (stream xs)
"productInt -> unfused" [1] forall (xs :: [Int]).
    Stream.product (stream xs) = productInt xs
  #-}

-- | /O(n)/,/fusion/. 'maximum' returns the maximum value from a list,
-- which must be non-empty, finite, and of an ordered type.
-- It is a special case of 'Data.List.maximumBy', which allows the
-- programmer to supply their own comparison function.
maximum :: Ord a => [a] -> a
maximum []       = errorEmptyList "maximum"
maximum xs       = foldl1 max xs
{-# NOINLINE [1] maximum #-}

{-# RULES
"maximum -> fused"  [~1] forall xs.
    maximum xs = Stream.maximum (stream xs)
"maximum -> unfused" [1] forall xs.
    Stream.maximum (stream xs) = maximum xs
  #-}

-- We can't make the overloaded version of maximum strict without
-- changing its semantics (max might not be strict), but we can for
-- the version specialised to 'Int'.

{-# RULES
  "maximumInt"     maximum = (strictMaximum :: [Int] -> Int);
  "maximumChar"    maximum = (strictMaximum :: [Char] -> Char)
  #-}

strictMaximum :: (Ord a) => [a] -> a
strictMaximum [] =  errorEmptyList "maximum"
strictMaximum xs =  foldl1' max xs
{-# NOINLINE [1] strictMaximum #-}

{-# RULES
"strictMaximum -> fused"  [~1] forall xs.
    maximum xs = Stream.strictMaximum (stream xs)
"strictMaximum -> unfused" [1] forall xs.
    Stream.strictMaximum (stream xs) = strictMaximum xs
  #-}

-- | /O(n)/,/fusion/. 'minimum' returns the minimum value from a list,
-- which must be non-empty, finite, and of an ordered type.
-- It is a special case of 'Data.List.minimumBy', which allows the
-- programmer to supply their own comparison function.
minimum :: Ord a => [a] -> a
minimum [] = errorEmptyList "minimum"
minimum xs = foldl1 min xs
{-# NOINLINE [1] minimum #-}

{-# RULES
"minimum -> fused"  [~1] forall xs.
    minimum xs = Stream.minimum (stream xs)
"minimum -> unfused" [1] forall xs.
    Stream.minimum (stream xs) = minimum xs
  #-}

{-# RULES
  "minimumInt"     minimum = (strictMinimum :: [Int]  -> Int);
  "minimumChar"    minimum = (strictMinimum :: [Char] -> Char)
  #-}

strictMinimum :: (Ord a) => [a] -> a
strictMinimum [] = errorEmptyList "maximum"
strictMinimum xs = foldl1' min xs
{-# NOINLINE [1] strictMinimum #-}

{-# RULES
"strictMinimum -> fused"  [~1] forall xs.
    maximum xs = Stream.strictMinimum (stream xs)
"strictMinimum -> unfused" [1] forall xs.
    Stream.strictMinimum (stream xs) = strictMinimum xs
  #-}

-- ---------------------------------------------------------------------
-- * Building lists
-- ** Scans

-- | /O(n)/, /fusion/. 'scanl' is similar to 'foldl', but returns a list of successive
-- reduced values from the left:
--
-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
--
-- Properties:
--
-- > last (scanl f z xs) == foldl f z x
--
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl f q ls = q : case ls of
                      []   -> []
                      x:xs -> scanl f (f q x) xs
{-# INLINE [1] scanl #-}

{- or perhaps:
scanl f q xs0 = q : go q xs0
  where go q []     = []
        go q (x:xs) = let q' = f q x
                       in q' : go q' xs
-}

-- 
-- note: Haskell's 'scan' is a bit weird, as it always puts the initial
-- state as a prefix. this complicates the rules.
--

{-# RULES
"scanl -> fusible"  [~1] forall f z xs.
    scanl f z xs = unstream (Stream.scanl f z (Stream.snoc (stream xs) bottom))
"scanl -> unfused" [1] forall f z xs.
    unstream (Stream.scanl f z (Stream.snoc (stream xs) bottom)) = scanl f z xs
  #-}

-- | /O(n)/,/fusion/. 'scanl1' is a variant of 'scanl' that has no starting value argument:
--
-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
--
scanl1 :: (a -> a -> a) -> [a] -> [a]
scanl1 f (x:xs) = scanl f x xs
scanl1 _ []     = []
{-# INLINE [1] scanl1 #-}

{-# RULES
"scanl1 -> fusible"  [~1] forall f xs.
    scanl1 f xs = unstream (Stream.scanl1 f (Stream.snoc (stream xs) bottom))
"scanl1 -> unfused" [1] forall f xs.
    unstream (Stream.scanl1 f (Stream.snoc (stream xs) bottom)) = scanl1 f xs
  #-}


-- | /O(n)/. 'scanr' is the right-to-left dual of 'scanl'.
-- Properties:
--
-- > head (scanr f z xs) == foldr f z xs
--
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr _ q0 []     = [q0]
scanr f q0 (x:xs) = f x q : qs
                    where qs@(q:_) = scanr f q0 xs
{-# INLINE [1] scanr #-}

{- RULES
"scanr -> fusible"  [~1] forall f z xs.
    scanr f z xs = unstream (Stream.scanr f z (Stream.cons bottom (stream xs)))
"scanr -> unfused" [1] forall f z xs.
    unstream (Stream.scanr f z (Stream.cons bottom (stream xs))) = scanr f z xs
  -}

-- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
scanr1 :: (a -> a -> a) -> [a] -> [a]
scanr1 _ []     = []
scanr1 _ [x]    = [x]
scanr1 f (x:xs) = f x q : qs
                  where qs@(q:_) = scanr1 f xs

-- TODO fuse

-- ---------------------------------------------------------------------
-- ** Accumulating maps

-- | The 'mapAccumL' function behaves like a combination of 'map' and
-- 'foldl'; it applies a function to each element of a list, passing
-- an accumulating parameter from left to right, and returning a final
-- value of this accumulator together with the new list.
--
mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
mapAccumL _ s []     = (s, [])
mapAccumL f s (x:xs) = (s'',y:ys)
                       where (s', y ) = f s x
                             (s'',ys) = mapAccumL f s' xs

-- TODO fuse

-- | The 'mapAccumR' function behaves like a combination of 'map' and
-- 'foldr'; it applies a function to each element of a list, passing
-- an accumulating parameter from right to left, and returning a final
-- value of this accumulator together with the new list.
--
mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
mapAccumR _ s []     = (s, [])
mapAccumR f s (x:xs) = (s'', y:ys)
                       where (s'',y ) = f s' x
                             (s', ys) = mapAccumR f s xs

-- TODO fuse

------------------------------------------------------------------------
-- ** Infinite lists

-- | /fusion/. 'iterate' @f x@ returns an infinite list of repeated applications
-- of @f@ to @x@:
--
-- > iterate f x == [x, f x, f (f x), ...]
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
{-# NOINLINE [1] iterate #-}

{-# RULES
"iterate -> fusible" [~1] forall f x.
    iterate f x = unstream (Stream.iterate f x)
"iterate -> unfused" [1] forall f x.
    unstream (Stream.iterate f x) = iterate f x
  #-}

-- | /fusion/. 'repeat' @x@ is an infinite list, with @x@ the value of every element.
repeat :: a -> [a]
repeat x = xs where xs = x : xs
{-# INLINE [1] repeat #-}

{-# RULES
"repeat -> fusible" [~1] forall x.
    repeat x = unstream (Stream.repeat x)
"repeat -> unfused" [1] forall x.
    unstream (Stream.repeat x) = repeat x
  #-}

-- | /O(n)/, /fusion/. 'replicate' @n x@ is a list of length @n@ with @x@ the value of
-- every element.
-- It is an instance of the more general 'Data.List.genericReplicate',
-- in which @n@ may be of any integral type.
--
replicate :: Int -> a -> [a]
replicate n0 _ | n0 <= 0 = []
replicate n0 x           = go n0
  where
    go 0 = []
    go n = x : go (n-1)
{-# NOINLINE [1] replicate #-}

{-# RULES
"replicate -> fusible" [~1]
    replicate = \n x -> unstream (Stream.replicate n x)
"replicate -> unfused" [1] forall n x.
    unstream (Stream.replicate n x) = replicate n x
  #-}

-- | /fusion/. 'cycle' ties a finite list into a circular one, or equivalently,
-- the infinite repetition of the original list.  It is the identity
-- on infinite lists.
--
cycle :: [a] -> [a]
cycle [] = error "Prelude.cycle: empty list"
cycle xs0 = go xs0
  where
    go []     = go xs0
    go (x:xs) = x : go xs
{-# NOINLINE [1] cycle #-}

{-# RULES
"cycle -> fusible" [~1] forall xs.
    cycle xs = unstream (Stream.cycle (stream xs))
"cycle -> unfused" [1] forall xs.
    unstream (Stream.cycle (stream xs)) = cycle xs
  #-}

-- ---------------------------------------------------------------------
-- ** Unfolding

-- | /fusion/. The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
-- reduces a list to a summary value, 'unfoldr' builds a list from
-- a seed value.  The function takes the element and returns 'Nothing'
-- if it is done producing the list or returns 'Just' @(a,b)@, in which
-- case, @a@ is a prepended to the list and @b@ is used as the next
-- element in a recursive call.  For example,
--
-- > iterate f == unfoldr (\x -> Just (x, f x))
--
-- In some cases, 'unfoldr' can undo a 'foldr' operation:
--
-- > unfoldr f' (foldr f z xs) == xs
--
-- if the following holds:
--
-- > f' (f x y) = Just (x,y)
-- > f' z       = Nothing
--
-- A simple use of unfoldr:
--
-- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
-- >  [10,9,8,7,6,5,4,3,2,1]
--
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b0 = unfold b0
  where
    unfold b = case f b of
      Just (a,b') -> a : unfold b'
      Nothing     -> []
{-# INLINE [1] unfoldr #-}

{-# RULES
"unfoldr -> fusible" [~1] forall f x.
    unfoldr f x = unstream (Stream.unfoldr f x)
"unfoldr -> unfused" [1] forall f x.
    unstream (Stream.unfoldr f x) = unfoldr f x
  #-}

------------------------------------------------------------------------
-- * Sublists
-- ** Extracting sublists

-- | /O(n)/,/fusion/. 'take' @n@, applied to a list @xs@, returns the prefix of @xs@
-- of length @n@, or @xs@ itself if @n > 'length' xs@:
--
-- > take 5 "Hello World!" == "Hello"
-- > take 3 [1,2,3,4,5] == [1,2,3]
-- > take 3 [1,2] == [1,2]
-- > take 3 [] == []
-- > take (-1) [1,2] == []
-- > take 0 [1,2] == []
--
-- It is an instance of the more general 'Data.List.genericTake',
-- in which @n@ may be of any integral type.
--
take :: Int -> [a] -> [a]
take i _ | i <= 0 = []
take i ls = take' i ls
  where
    take' :: Int -> [a] -> [a]
    take' 0 _      = []
    take' _ []     = []
    take' n (x:xs) = x : take' (n-1) xs
{-# NOINLINE [1] take #-}

{-# RULES
"take -> fusible" [~1] forall n x.
    take n x = unstream (Stream.take n (stream x))
"take -> unfused" [1] forall n x.
    unstream (Stream.take n (stream x)) = take n x
  #-}

{-
take :: Int -> [a] -> [a]
take (I# n#) xs = takeUInt n# xs

takeUInt :: Int# -> [b] -> [b]
takeUInt n xs
    | n >=# 0#  =  take_unsafe_UInt n xs
    | otherwise =  []

take_unsafe_UInt :: Int# -> [b] -> [b]
take_unsafe_UInt 0#  _  = []
take_unsafe_UInt m   ls =
  case ls of
    []     -> []
    (x:xs) -> x : take_unsafe_UInt (m -# 1#) xs
-}

-- | /O(n)/,/fusion/. 'drop' @n xs@ returns the suffix of @xs@
-- after the first @n@ elements, or @[]@ if @n > 'length' xs@:
--
-- > drop 6 "Hello World!" == "World!"
-- > drop 3 [1,2,3,4,5] == [4,5]
-- > drop 3 [1,2] == []
-- > drop 3 [] == []
-- > drop (-1) [1,2] == [1,2]
-- > drop 0 [1,2] == [1,2]
--
-- It is an instance of the more general 'Data.List.genericDrop',
-- in which @n@ may be of any integral type.
--
drop :: Int -> [a] -> [a]
drop n ls
  | n < 0     = ls
  | otherwise = drop' n ls
  where
    drop' :: Int -> [a] -> [a]
    drop' 0 xs      = xs
    drop' _  xs@[]  = xs
    drop' m (_:xs)  = drop' (m-1) xs
{-# NOINLINE [1] drop #-}

{-# RULES
"drop -> fusible" [~1] forall n x.
    drop n x = unstream (Stream.drop n (stream x))
"drop -> unfused" [1] forall n x.
    unstream (Stream.drop n (stream x)) = drop n x
  #-}

-- | 'splitAt' @n xs@ returns a tuple where first element is @xs@ prefix of
-- length @n@ and second element is the remainder of the list:
--
-- > splitAt 6 "Hello World!" == ("Hello ","World!")
-- > splitAt 3 [1,2,3,4,5] == ([1,2,3],[4,5])
-- > splitAt 1 [1,2,3] == ([1],[2,3])
-- > splitAt 3 [1,2,3] == ([1,2,3],[])
-- > splitAt 4 [1,2,3] == ([1,2,3],[])
-- > splitAt 0 [1,2,3] == ([],[1,2,3])
-- > splitAt (-1) [1,2,3] == ([],[1,2,3])
--
-- It is equivalent to @('take' n xs, 'drop' n xs)@.
-- 'splitAt' is an instance of the more general 'Data.List.genericSplitAt',
-- in which @n@ may be of any integral type.
--
splitAt :: Int -> [a] -> ([a], [a])
splitAt n ls
  | n < 0     = ([], ls)
  | otherwise = splitAt' n ls
  where
    splitAt' :: Int -> [a] -> ([a], [a])
    splitAt' 0 xs     = ([], xs)
    splitAt' _  xs@[] = (xs, xs)
    splitAt' m (x:xs) = (x:xs', xs'')
      where
        (xs', xs'') = splitAt' (m-1) xs
{-# NOINLINE [1] splitAt #-}

{-
splitAt n xs | n <= 0 = ([], xs)
splitAt _ []          = ([], [])
splitAt n (x:xs)      = (x:xs', xs'')
  where
    (xs', xs'') = splitAt (n-1) xs
-}

{-# RULES
"splitAt -> fusible" [~1] forall n xs.
    splitAt n xs = Stream.splitAt n (stream xs)
"splitAt -> unfused" [1] forall n xs.
    Stream.splitAt n (stream xs) = splitAt n xs
  #-}

-- | /O(n)/,/fusion/. 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the
-- longest prefix (possibly empty) of @xs@ of elements that satisfy @p@:
--
-- > takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
-- > takeWhile (< 9) [1,2,3] == [1,2,3]
-- > takeWhile (< 0) [1,2,3] == []
--
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ []    = []
takeWhile p xs0   = go xs0
  where
    go []         = []
    go (x:xs)
      | p x       = x : go xs
      | otherwise = []
{-# NOINLINE [1] takeWhile #-}

{-# RULES
"takeWhile -> fusible" [~1] forall f xs.
    takeWhile f xs = unstream (Stream.takeWhile f (stream xs))
"takeWhile -> unfused" [1] forall f xs.
    unstream (Stream.takeWhile f (stream xs)) = takeWhile f xs
  #-}

-- | /O(n)/,/fusion/. 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@:
--
-- > dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3]
-- > dropWhile (< 9) [1,2,3] == []
-- > dropWhile (< 0) [1,2,3] == [1,2,3]
--
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ []    = []
dropWhile p xs0   = go xs0
  where
    go []         = []
    go xs@(x:xs')
      | p x       = go xs'
      | otherwise = xs
{-# NOINLINE [1] dropWhile #-}

{-# RULES
"dropWhile -> fusible" [~1] forall f xs.
    dropWhile f xs = unstream (Stream.dropWhile f (stream xs))
"dropWhile -> unfused" [1] forall f xs.
    unstream (Stream.dropWhile f (stream xs)) = dropWhile f xs
  #-}

-- | 'span', applied to a predicate @p@ and a list @xs@, returns a tuple where
-- first element is longest prefix (possibly empty) of @xs@ of elements that
-- satisfy @p@ and second element is the remainder of the list:
-- 
-- > span (< 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4])
-- > span (< 9) [1,2,3] == ([1,2,3],[])
-- > span (< 0) [1,2,3] == ([],[1,2,3])
-- 
-- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
span :: (a -> Bool) -> [a] -> ([a], [a])
span _ []         = ([], [])
span p xs0        = go xs0
  where
    go []         = ([], [])
    go xs@(x:xs')
      | p x       = let (ys,zs) = go xs'
                     in (x:ys,zs)
      | otherwise = ([],xs)

-- TODO fuse
-- Hmm, these do a lot of sharing, but is it worth it?

-- | 'break', applied to a predicate @p@ and a list @xs@, returns a tuple where
-- first element is longest prefix (possibly empty) of @xs@ of elements that
-- /do not satisfy/ @p@ and second element is the remainder of the list:
-- 
-- > break (> 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4])
-- > break (< 9) [1,2,3] == ([],[1,2,3])
-- > break (> 9) [1,2,3] == ([1,2,3],[])
--
-- 'break' @p@ is equivalent to @'span' ('not' . p)@.
--
break :: (a -> Bool) -> [a] -> ([a], [a])
break _ []        = ([], [])
break p xs0       = go xs0
  where
    go []         = ([], [])
    go xs@(x:xs')
      | p x       = ([],xs)
      | otherwise = let (ys,zs) = go xs'
                    in (x:ys,zs)

-- TODO fuse

-- | The 'group' function takes a list and returns a list of lists such
-- that the concatenation of the result is equal to the argument.  Moreover,
-- each sublist in the result contains only equal elements.  For example,
--
-- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
--
-- It is a special case of 'groupBy', which allows the programmer to supply
-- their own equality test.
group :: Eq a => [a] -> [[a]]
group []     = []
group (x:xs) = (x:ys) : group zs
               where (ys,zs) = span (x ==) xs

-- TODO fuse

-- | The 'inits' function returns all initial segments of the argument,
-- shortest first.  For example,
--
-- > inits "abc" == ["","a","ab","abc"]
--
inits :: [a] -> [[a]]
inits []     = [] : []
inits (x:xs) = [] : map (x:) (inits xs)

-- TODO fuse

-- | The 'tails' function returns all final segments of the argument,
-- longest first.  For example,
--
-- > tails "abc" == ["abc", "bc", "c",""]
--
tails :: [a] -> [[a]]
tails []         = []  : []
tails xxs@(_:xs) = xxs : tails xs

-- TODO fuse

------------------------------------------------------------------------
-- * Predicates

-- | /O(n)/,/fusion/. The 'isPrefixOf' function takes two lists and
-- returns 'True' iff the first list is a prefix of the second.
--
isPrefixOf :: Eq a => [a] -> [a] -> Bool
isPrefixOf [] _                      = True
isPrefixOf _  []                     = False
isPrefixOf (x:xs) (y:ys) | x == y    = isPrefixOf xs ys
                         | otherwise = False
{-# NOINLINE [1] isPrefixOf #-}

{-# RULES
"isPrefixOf -> fusible" [~1] forall xs ys.
    isPrefixOf xs ys = Stream.isPrefixOf (stream xs) (stream ys)
"isPrefixOf -> unfused" [1]  forall xs ys.
    Stream.isPrefixOf (stream xs) (stream ys) = isPrefixOf xs ys
  #-}

-- | The 'isSuffixOf' function takes two lists and returns 'True'
-- iff the first list is a suffix of the second.
-- Both lists must be finite.
isSuffixOf :: Eq a => [a] -> [a] -> Bool
isSuffixOf x y = reverse x `isPrefixOf` reverse y

-- TODO fuse

-- | The 'isInfixOf' function takes two lists and returns 'True'
-- iff the first list is contained, wholly and intact,
-- anywhere within the second.
--
-- Example:
--
-- > isInfixOf "Haskell" "I really like Haskell." -> True
-- > isInfixOf "Ial" "I really like Haskell." -> False
--
isInfixOf :: Eq a => [a] -> [a] -> Bool
isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)

-- TODO fuse

-- ---------------------------------------------------------------------
-- * Searching lists
-- ** Searching by equality

-- | /O(n)/, /fusion/. 'elem' is the list membership predicate, usually written
-- in infix form, e.g., @x `elem` xs@.
--
elem :: Eq a => a -> [a] -> Bool
elem _ []     = False
elem x (y:ys)
  | x == y    = True
  | otherwise = elem x ys
{-# NOINLINE [1] elem #-}

{-# RULES
"elem -> fusible" [~1] forall x xs.
    elem x xs = Stream.elem x (stream xs)
"elem -> unfused" [1] forall x xs.
    Stream.elem x (stream xs) = elem x xs
  #-}

-- | /O(n)/, /fusion/. 'notElem' is the negation of 'elem'.
notElem :: Eq a => a -> [a] -> Bool
notElem x xs = not (elem x xs)
{-# INLINE notElem #-}

{- RULES
-- We don't provide an expicilty fusible version, since not . elem is
-- just as good.

"notElem -> fusible" [~1] forall x xs.
    notElem x xs = Stream.notElem x (stream xs)
"notElem -> unfused" [1] forall x xs.
    Stream.notElem x (stream xs) = notElem x xs
  -}

-- | /O(n)/,/fusion/. 'lookup' @key assocs@ looks up a key in an association list.
lookup :: Eq a => a -> [(a, b)] -> Maybe b
lookup _   []       = Nothing
lookup key xys0     = go xys0
  where
    go []           = Nothing
    go ((x,y):xys)
      | key == x    = Just y
      | otherwise   = lookup key xys
{-# NOINLINE [1] lookup #-}

{-# RULES
"lookup -> fusible" [~1] forall x xs.
    lookup x xs = Stream.lookup x (stream xs)
"lookup -> unfused" [1] forall x xs.
    Stream.lookup x (stream xs) = lookup x xs
  #-}

-- | /O(n)/,/fusion/. 'filter', applied to a predicate and a list, returns the list of
-- those elements that satisfy the predicate; i.e.,
--
-- > filter p xs = [ x | x <- xs, p x]
--
-- Properties:
--
-- > filter p (filter q s) = filter (\x -> q x && p x) s
--
filter :: (a -> Bool) -> [a] -> [a]
filter _ []       = []
filter p xs0      = go xs0
  where
    go []         = []
    go (x:xs)
      | p x       = x : go xs
      | otherwise =     go xs
{-# NOINLINE [1] filter #-}

{-# RULES
"filter -> fusible" [~1] forall f xs.
    filter f xs = unstream (Stream.filter f (stream xs))
"filter -> unfused" [1] forall f xs.
    unstream (Stream.filter f (stream xs)) = filter f xs
  #-}

------------------------------------------------------------------------
-- ** Searching with a predicate

-- | /O(n)/,/fusion/. The 'find' function takes a predicate and a list and returns the
-- first element in the list matching the predicate, or 'Nothing' if
-- there is no such element.
find :: (a -> Bool) -> [a] -> Maybe a
find _ []       = Nothing
find p xs0      = go xs0
  where
    go []                 = Nothing
    go (x:xs) | p x       = Just x
              | otherwise = go xs
{-# NOINLINE [1] find #-}

{-# RULES
"find -> fusible" [~1] forall f xs.
    find f xs = Stream.find f (stream xs)
"find -> unfused" [1] forall f xs.
    Stream.find f (stream xs) = find f xs
  #-}

-- | The 'partition' function takes a predicate a list and returns
-- the pair of lists of elements which do and do not satisfy the
-- predicate, respectively; i.e.,
--
-- > partition p xs == (filter p xs, filter (not . p) xs)
partition :: (a -> Bool) -> [a] -> ([a], [a])
partition p xs = foldr (select p) ([],[]) xs
{-# INLINE partition #-}

-- TODO fuse

select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select p x ~(ts,fs) | p x       = (x:ts,fs)
                    | otherwise = (ts, x:fs)

------------------------------------------------------------------------
-- * Indexing lists

-- | /O(n)/,/fusion/. List index (subscript) operator, starting from 0.
-- It is an instance of the more general 'Data.List.genericIndex',
-- which takes an index of any integral type.
(!!) :: [a] -> Int -> a
xs0 !! n0
  | n0 < 0    = error "Prelude.(!!): negative index"
  | otherwise = index xs0 n0
#ifndef __HADDOCK__
  where
    index []     _ = error "Prelude.(!!): index too large"
    index (y:ys) n = if n == 0 then y else index ys (n-1)
#endif
{-# NOINLINE [1] (!!) #-}

{-# RULES
"!! -> fusible" [~1] forall xs n.
    xs !! n = Stream.index (stream xs) n
"!! -> unfused" [1] forall  xs n.
    Stream.index (stream xs) n = xs !! n
  #-}

-- | The 'elemIndex' function returns the index of the first element
-- in the given list which is equal (by '==') to the query element,
-- or 'Nothing' if there is no such element.
-- 
-- Properties:
--
-- > elemIndex x xs = listToMaybe [ n | (n,a) <- zip [0..] xs, a == x ]
-- > elemIndex x xs = findIndex (x==) xs
--
elemIndex	:: Eq a => a -> [a] -> Maybe Int
elemIndex x     = findIndex (x==)
{-# INLINE elemIndex #-}
{-
elemIndex :: Eq a => a -> [a] -> Maybe Int
elemIndex y xs0 = loop_elemIndex xs0 0
#ifndef __HADDOCK__
  where
    loop_elemIndex []     !_ = Nothing
    loop_elemIndex (x:xs) !n
      | p x       = Just n
      | otherwise = loop_elemIndex xs (n + 1)
    p = (y ==)
#endif
{-# NOINLINE [1] elemIndex #-}
-}
{- RULES
"elemIndex -> fusible" [~1] forall x xs.
    elemIndex x xs = Stream.elemIndex x (stream xs)
"elemIndex -> unfused" [1] forall x xs.
    Stream.elemIndex x (stream xs) = elemIndex x xs
  -}

-- | /O(n)/,/fusion/. The 'elemIndices' function extends 'elemIndex', by
-- returning the indices of all elements equal to the query element, in
-- ascending order.
--
-- Properties:
--
-- > length (filter (==a) xs) = length (elemIndices a xs)
--
elemIndices     :: Eq a => a -> [a] -> [Int]
elemIndices x   = findIndices (x==)
{-# INLINE elemIndices #-}

{-
elemIndices :: Eq a => a -> [a] -> [Int]
elemIndices y xs0 = loop_elemIndices xs0 0
#ifndef __HADDOCK__
  where
    loop_elemIndices []     !_  = []
    loop_elemIndices (x:xs) !n
      | p x       = n : loop_elemIndices xs (n + 1)
      | otherwise =     loop_elemIndices xs (n + 1)
    p = (y ==)
#endif
{-# NOINLINE [1] elemIndices #-}
-}
{- RULES
"elemIndices -> fusible" [~1] forall x xs.
    elemIndices x xs = unstream (Stream.elemIndices x (stream xs))
"elemIndices -> unfused" [1] forall x xs.
    unstream (Stream.elemIndices x (stream xs)) = elemIndices x xs
  -}

-- | The 'findIndex' function takes a predicate and a list and returns
-- the index of the first element in the list satisfying the predicate,
-- or 'Nothing' if there is no such element.
--
-- Properties:
--
-- > findIndex p xs = listToMaybe [ n | (n,x) <- zip [0..] xs, p x ]
--
findIndex :: (a -> Bool) -> [a] -> Maybe Int
findIndex p ls    = loop_findIndex ls 0#
  where
    loop_findIndex []   _ = Nothing
    loop_findIndex (x:xs) n
      | p x       = Just (I# n)
      | otherwise = loop_findIndex xs (n +# 1#)
{-# NOINLINE [1] findIndex #-}

{-# RULES
"findIndex -> fusible" [~1] forall f xs.
    findIndex f xs = Stream.findIndex f (stream xs)
"findIndex -> unfused" [1] forall f xs.
    Stream.findIndex f (stream xs) = findIndex f xs
  #-}

-- | /O(n)/,/fusion/. The 'findIndices' function extends 'findIndex', by
-- returning the indices of all elements satisfying the predicate, in
-- ascending order.
--
-- Properties:
--
-- > length (filter p xs) = length (findIndices p xs)
--
findIndices :: (a -> Bool) -> [a] -> [Int]
findIndices p ls  = loop_findIndices ls 0#
  where
    loop_findIndices []     _ = []
    loop_findIndices (x:xs) n
      | p x       = I# n : loop_findIndices xs (n +# 1#)
      | otherwise =        loop_findIndices xs (n +# 1#)
{-# NOINLINE [1] findIndices #-}

{-# RULES
"findIndices -> fusible" [~1] forall p xs.
    findIndices p xs = unstream (Stream.findIndices p (stream xs))
"findIndices -> unfused" [1]  forall p xs.
    unstream (Stream.findIndices p (stream xs)) = findIndices p xs
  #-}

------------------------------------------------------------------------
-- * Zipping and unzipping lists

-- | /O(n)/,/fusion/. 'zip' takes two lists and returns a list of
-- corresponding pairs. If one input list is short, excess elements of
-- the longer list are discarded.
--
-- Properties:
--
-- > zip a b = zipWith (,) a b
--
zip :: [a] -> [b] -> [(a, b)]
zip (a:as) (b:bs) = (a,b) : zip as bs
zip _      _      = []
{-# NOINLINE [1] zip #-}

{-# RULES
"zip -> fusible" [~1] forall xs ys.
    zip xs ys = unstream (Stream.zip (stream xs) (stream ys))
"zip -> unfused" [1]  forall xs ys.
    unstream (Stream.zip (stream xs) (stream ys)) = zip xs ys
  #-}

-- | /O(n)/,/fusion/. 'zip3' takes three lists and returns a list of
-- triples, analogous to 'zip'.
--
-- Properties:
--
-- > zip3 a b c = zipWith (,,) a b c
--
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
zip3 _      _      _      = []
{-# NOINLINE [1] zip3 #-}

{-# RULES
"zip3 -> fusible" [~1] forall xs ys zs.
    zip3 xs ys zs = unstream (Stream.zipWith3 (,,) (stream xs) (stream ys) (stream zs))
"zip3 -> unfused" [1]  forall xs ys zs.
    unstream (Stream.zipWith3 (,,) (stream xs) (stream ys) (stream zs)) = zip3 xs ys zs
  #-}

-- | /O(n)/,/fusion/. The 'zip4' function takes four lists and returns a list of
-- quadruples, analogous to 'zip'.
zip4 :: [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)]
zip4 = zipWith4 (,,,)
{-# INLINE zip4 #-}

-- | The 'zip5' function takes five lists and returns a list of
-- five-tuples, analogous to 'zip'.
zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a, b, c, d, e)]
zip5 = zipWith5 (,,,,)

-- | The 'zip6' function takes six lists and returns a list of six-tuples,
-- analogous to 'zip'.
zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [(a, b, c, d, e, f)]
zip6 = zipWith6 (,,,,,)

-- | The 'zip7' function takes seven lists and returns a list of
-- seven-tuples, analogous to 'zip'.
zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [(a, b, c, d, e, f, g)]
zip7 = zipWith7 (,,,,,,)

-- | /O(n)/,/fusion/. 'zipWith' generalises 'zip' by zipping with the
-- function given as the first argument, instead of a tupling function.
-- For example, @'zipWith' (+)@ is applied to two lists to produce the
-- list of corresponding sums.
-- Properties:
--
-- > zipWith (,) = zip
--
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = []
{-# INLINE [1] zipWith #-}

--FIXME: If we change the above INLINE to NOINLINE then ghc goes into
--       a loop, why? Do we have some dodgy recursive rules somewhere?

{-# RULES
"zipWith -> fusible" [~1] forall f xs ys.
    zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
"zipWith -> unfused" [1]  forall f xs ys.
    unstream (Stream.zipWith f (stream xs) (stream ys)) = zipWith f xs ys
  #-}

-- | /O(n)/,/fusion/. The 'zipWith3' function takes a function which
-- combines three elements, as well as three lists and returns a list of
-- their point-wise combination, analogous to 'zipWith'.
--
-- Properties:
--
-- > zipWith3 (,,) = zip3
--
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3 z (a:as) (b:bs) (c:cs) = z a b c : zipWith3 z as bs cs
zipWith3 _ _ _ _                = []
{-# NOINLINE [1] zipWith3 #-}

{-# RULES
"zipWith3 -> fusible" [~1] forall f xs ys zs.
    zipWith3 f xs ys zs = unstream (Stream.zipWith3 f (stream xs) (stream ys) (stream zs))
"zipWith3 -> unfused" [1]  forall f xs ys zs.
    unstream (Stream.zipWith3 f (stream xs) (stream ys) (stream zs)) = zipWith3 f xs ys zs
  #-}

-- | /O(n)/,/fusion/. The 'zipWith4' function takes a function which combines four
-- elements, as well as four lists and returns a list of their point-wise
-- combination, analogous to 'zipWith'.
zipWith4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]
zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
                        = z a b c d : zipWith4 z as bs cs ds
zipWith4 _ _ _ _ _      = []
{-# NOINLINE [1] zipWith4 #-}

{-# RULES
"zipWith4 -> fusible" [~1] forall f ws xs ys zs.
    zipWith4 f ws xs ys zs = unstream (Stream.zipWith4 f (stream ws) (stream xs) (stream ys) (stream zs))
"zipWith4 -> unfused" [1]  forall f ws xs ys zs.
    unstream (Stream.zipWith4 f (stream ws) (stream xs) (stream ys) (stream zs)) = zipWith4 f ws xs ys zs
  #-}

-- | The 'zipWith5' function takes a function which combines five
-- elements, as well as five lists and returns a list of their point-wise
-- combination, analogous to 'zipWith'.
zipWith5 :: (a -> b -> c -> d -> e -> f)
         -> [a] -> [b] -> [c] -> [d] -> [e] -> [f]
zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
                        = z a b c d e : zipWith5 z as bs cs ds es
zipWith5 _ _ _ _ _ _    = []

-- TODO fuse

-- | The 'zipWith6' function takes a function which combines six
-- elements, as well as six lists and returns a list of their point-wise
-- combination, analogous to 'zipWith'.
zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
         -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g]
zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
                        = z a b c d e f : zipWith6 z as bs cs ds es fs
zipWith6 _ _ _ _ _ _ _  = []

-- TODO fuse

-- | The 'zipWith7' function takes a function which combines seven
-- elements, as well as seven lists and returns a list of their point-wise
-- combination, analogous to 'zipWith'.
zipWith7 :: (a -> b -> c -> d -> e -> f -> g -> h)
         -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [h]
zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
                         = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
zipWith7 _ _ _ _ _ _ _ _ = []

-- TODO fuse

------------------------------------------------------------------------
-- unzips

-- | 'unzip' transforms a list of pairs into a list of first components
-- and a list of second components.
unzip :: [(a, b)] -> ([a], [b])
unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])

-- TODO fuse

-- | The 'unzip3' function takes a list of triples and returns three
-- lists, analogous to 'unzip'.
unzip3 :: [(a, b, c)] -> ([a], [b], [c])
unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs)) ([],[],[])

-- TODO fuse

-- | The 'unzip4' function takes a list of quadruples and returns four
-- lists, analogous to 'unzip'.
unzip4 :: [(a, b, c, d)] -> ([a], [b], [c], [d])
unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
                      (a:as,b:bs,c:cs,d:ds))
               ([],[],[],[])

-- TODO fuse

-- | The 'unzip5' function takes a list of five-tuples and returns five
-- lists, analogous to 'unzip'.
unzip5 :: [(a, b, c, d, e)] -> ([a], [b], [c], [d], [e])
unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
                      (a:as,b:bs,c:cs,d:ds,e:es))
               ([],[],[],[],[])

-- TODO fuse

-- | The 'unzip6' function takes a list of six-tuples and returns six
-- lists, analogous to 'unzip'.
unzip6 :: [(a, b, c, d, e, f)] -> ([a], [b], [c], [d], [e], [f])
unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
                      (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
               ([],[],[],[],[],[])

-- TODO fuse

-- | The 'unzip7' function takes a list of seven-tuples and returns
-- seven lists, analogous to 'unzip'.
unzip7 :: [(a, b, c, d, e, f, g)] -> ([a], [b], [c], [d], [e], [f], [g])
unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
                      (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
               ([],[],[],[],[],[],[])

-- TODO fuse

------------------------------------------------------------------------
-- * Special lists
-- ** Functions on strings

-- | /O(O)/,/fusion/. 'lines' breaks a string up into a list of strings
-- at newline characters. The resulting strings do not contain
-- newlines.
lines :: String -> [String]
lines [] = []
lines s  = let (l, s') = break (== '\n') s
            in l : case s' of
                     []      -> []
                     (_:s'') -> lines s''
--TODO: can we do better than this and preserve the same strictness?

{-
-- This implementation is fast but too strict :-(
-- it doesn't yield each line until it has seen the ending '\n'

lines :: String -> [String]
lines []  = []
lines cs0 = go [] cs0
  where
    go l []        = reverse l : []
    go l ('\n':cs) = reverse l : case cs of
                                   [] -> []
                                   _  -> go [] cs
    go l (  c :cs) = go (c:l) cs
-}
{-# INLINE [1] lines #-}

{- RULES
"lines -> fusible" [~1] forall xs.
    lines xs = unstream (Stream.lines (stream xs))
"lines -> unfused" [1]  forall xs.
    unstream (Stream.lines (stream xs)) = lines xs
  -}

-- | 'words' breaks a string up into a list of words, which were delimited
-- by white space.
words :: String -> [String]
words s = case dropWhile isSpace s of
            "" -> []
            s' -> w : words s''
                  where (w, s'') = break isSpace s'
-- TODO fuse
--TODO: can we do better than this and preserve the same strictness?

{-
-- This implementation is fast but too strict :-(
-- it doesn't yield each word until it has seen the ending space

words cs0 = dropSpaces cs0
  where
    dropSpaces :: String -> [String]
    dropSpaces []         = []
    dropSpaces (c:cs)
         | isSpace c = dropSpaces cs
         | otherwise      = munchWord [c] cs

    munchWord :: String -> String -> [String]
    munchWord w []     = reverse w : []
    munchWord w (c:cs)
      | isSpace c = reverse w : dropSpaces cs
      | otherwise      = munchWord (c:w) cs
-}

-- | /O(n)/,/fusion/. 'unlines' is an inverse operation to 'lines'.
-- It joins lines, after appending a terminating newline to each.
--
-- > unlines xs = concatMap (++"\n")
--
unlines :: [String] -> String
unlines css0 = to css0
  where go []     css = '\n' : to css
        go (c:cs) css =   c  : go cs css

        to []       = []
        to (cs:css) = go cs css
{-# NOINLINE [1] unlines #-}

--
-- fuse via:
--      unlines xs = concatMap (snoc xs '\n')
--
{- RULES
"unlines -> fusible" [~1] forall xs.
    unlines xs = unstream (Stream.concatMap (\x -> Stream.snoc (stream x) '\n') (stream xs))
"unlines -> unfused" [1]  forall xs.
    unstream (Stream.concatMap (\x -> Stream.snoc (stream x) '\n') (stream xs)) = unlines xs
  -}

-- | 'unwords' is an inverse operation to 'words'.
-- It joins words with separating spaces.
unwords :: [String] -> String
unwords []         = []
unwords (cs0:css0) = go cs0 css0
  where go []     css = to css
        go (c:cs) css = c : go cs css

        to []       = []
        to (cs:ccs) = ' ' : go cs ccs

-- TODO fuse

------------------------------------------------------------------------
-- ** \"Set\" operations

-- | The 'nub' function removes duplicate elements from a list.
-- In particular, it keeps only the first occurrence of each element.
-- (The name 'nub' means \`essence\'.)
-- It is a special case of 'nubBy', which allows the programmer to supply
-- their own equality test.
--
nub :: Eq a => [a] -> [a]
nub l               = nub' l []
  where
    nub' [] _       = []
    nub' (x:xs) ls
      | x `elem` ls = nub' xs ls
      | otherwise   = x : nub' xs (x:ls)

{- RULES
-- ndm's optimisation
"sort/nub" forall xs.  sort (nub xs) = map head (group (sort xs))
  -}

-- TODO fuse

-- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
-- For example,
--
-- > delete 'a' "banana" == "bnana"
--
-- It is a special case of 'deleteBy', which allows the programmer to
-- supply their own equality test.
--
delete :: Eq a => a -> [a] -> [a]
delete = deleteBy (==)

-- TODO fuse

-- | The '\\' function is list difference ((non-associative).
-- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
-- @ys@ in turn (if any) has been removed from @xs@.  Thus
--
-- > (xs ++ ys) \\ xs == ys.
--
-- It is a special case of 'deleteFirstsBy', which allows the programmer
-- to supply their own equality test.
(\\) :: Eq a => [a] -> [a] -> [a]
(\\) = foldl (flip delete)

-- | The 'union' function returns the list union of the two lists.
-- For example,
--
-- > "dog" `union` "cow" == "dogcw"
--
-- Duplicates, and elements of the first list, are removed from the
-- the second list, but if the first list contains duplicates, so will
-- the result.
-- It is a special case of 'unionBy', which allows the programmer to supply
-- their own equality test.
--
union :: Eq a => [a] -> [a] -> [a]
union = unionBy (==)

-- TODO fuse

-- | The 'intersect' function takes the list intersection of two lists.
-- For example,
--
-- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
--
-- If the first list contains duplicates, so will the result.
-- It is a special case of 'intersectBy', which allows the programmer to
-- supply their own equality test.
--
intersect :: Eq a => [a] -> [a] -> [a]
intersect = intersectBy (==)

-- TODO fuse

------------------------------------------------------------------------
-- ** Ordered lists 

-- TODO stuff in Ord can use Map/IntMap
-- TODO Hooray, an Ord constraint! we could use a better structure.

-- | The 'sort' function implements a stable sorting algorithm.
-- It is a special case of 'sortBy', which allows the programmer to supply
-- their own comparison function.
--
-- Properties:
--
-- > not (null x) ==> (head . sort) x = minimum x
-- > not (null x) ==> (last . sort) x = maximum x
--
sort :: Ord a => [a] -> [a]
sort l = mergesort compare l

-- TODO fuse, we have an Ord constraint!

-- | /O(n)/,/fusion/. The 'insert' function takes an element and a list and inserts the
-- element into the list at the last position where it is still less
-- than or equal to the next element.  In particular, if the list
-- is sorted before the call, the result will also be sorted.
-- It is a special case of 'insertBy', which allows the programmer to
-- supply their own comparison function.
--
insert :: Ord a => a -> [a] -> [a]
insert e ls = insertBy (compare) e ls
{-# INLINE insert #-}

------------------------------------------------------------------------
-- * Generalized functions
-- ** The \"By\" operations
-- *** User-supplied equality (replacing an Eq context)

-- | The 'nubBy' function behaves just like 'nub', except it uses a
-- user-supplied equality predicate instead of the overloaded '=='
-- function.
nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq l              = nubBy' l []
  where
    nubBy' [] _         = []
    nubBy' (y:ys) xs
      | elem_by eq y xs = nubBy' ys xs
      | otherwise       = y : nubBy' ys (y:xs)

-- TODO fuse

-- Not exported:
-- Note that we keep the call to `eq` with arguments in the
-- same order as in the reference implementation
-- 'xs' is the list of things we've seen so far, 
-- 'y' is the potential new element
--
elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
elem_by _  _ []         = False
elem_by eq y (x:xs)     = if x `eq` y then True else elem_by eq y xs

-- | The 'deleteBy' function behaves like 'delete', but takes a
-- user-supplied equality predicate.
deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
deleteBy _  _ []        = []
deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys

-- TODO fuse

deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
deleteFirstsBy eq       = foldl (flip (deleteBy eq))


-- | The 'unionBy' function is the non-overloaded version of 'union'.
unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
unionBy eq xs ys        = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs

-- TODO fuse

-- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
intersectBy eq xs ys    = [x | x <- xs, any (eq x) ys]

-- TODO fuse

-- | The 'groupBy' function is the non-overloaded version of 'group'.
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []     = []
groupBy eq (x:xs) = (x:ys) : groupBy eq zs
                    where (ys,zs) = span (eq x) xs

-- TODO fuse

------------------------------------------------------------------------
-- *** User-supplied comparison (replacing an Ord context)

-- | The 'sortBy' function is the non-overloaded version of 'sort'.
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy cmp l = mergesort cmp l

-- TODO fuse

mergesort :: (a -> a -> Ordering) -> [a] -> [a]
mergesort cmp xs = mergesort' cmp (map wrap xs)

mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
mergesort' _ []    = []
mergesort' _ [xs]  = xs
mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)

merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
merge_pairs _   []          = []
merge_pairs _   [xs]        = [xs]
merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss

merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
merge _   xs [] = xs
merge _   [] ys = ys
merge cmp (x:xs) (y:ys)
 = case x `cmp` y of
        GT -> y : merge cmp (x:xs)   ys
        _  -> x : merge cmp    xs (y:ys)

wrap :: a -> [a]
wrap x = [x]

-- | /O(n)/,/fusion/. The non-overloaded version of 'insert'.
insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
insertBy _   x [] = [x]
insertBy cmp x ys@(y:ys')
    = case cmp x y of
        GT -> y : insertBy cmp x ys'
        _  -> x : ys
{-# NOINLINE [1] insertBy #-}

{-# RULES
"insertBy -> fusible" [~1] forall f x xs.
    insertBy f x xs = unstream (Stream.insertBy f x (stream xs))
"insertBy -> unfused" [1]  forall f x xs.
    unstream (Stream.insertBy f x (stream xs)) = insertBy f x xs
  #-}

-- | /O(n)/,/fusion/. The 'maximumBy' function takes a comparison function and a list
-- and returns the greatest element of the list by the comparison function.
-- The list must be finite and non-empty.
--
maximumBy :: (a -> a -> Ordering) -> [a] -> a
maximumBy _ []   = error "List.maximumBy: empty list"
maximumBy cmp xs = foldl1 max' xs
    where
       max' x y = case cmp x y of
                    GT -> x
                    _  -> y
{-# NOINLINE [1] maximumBy #-}

{-# RULES
"maximumBy -> fused"  [~1] forall p xs.
    maximumBy p xs = Stream.maximumBy p (stream xs)
"maximumBy -> unfused" [1] forall p xs.
    Stream.maximumBy p (stream xs) = maximumBy p xs
  #-}

-- | /O(n)/,/fusion/. The 'minimumBy' function takes a comparison function and a list
-- and returns the least element of the list by the comparison function.
-- The list must be finite and non-empty.
minimumBy :: (a -> a -> Ordering) -> [a] -> a
minimumBy _ []   = error "List.minimumBy: empty list"
minimumBy cmp xs = foldl1 min' xs
    where
        min' x y = case cmp x y of
                        GT -> y
                        _  -> x
{-# NOINLINE [1] minimumBy #-}

{-# RULES
"minimumBy -> fused"  [~1] forall p xs.
    minimumBy p xs = Stream.minimumBy p (stream xs)
"minimumBy -> unfused" [1] forall p xs.
    Stream.minimumBy p (stream xs) = minimumBy p xs
  #-}

------------------------------------------------------------------------
-- * The \"generic\" operations

-- | The 'genericLength' function is an overloaded version of 'length'.  In
-- particular, instead of returning an 'Int', it returns any type which is
-- an instance of 'Num'.  It is, however, less efficient than 'length'.
--
genericLength :: Num i => [b] -> i
genericLength []    = 0
genericLength (_:l) = 1 + genericLength l
{-# NOINLINE [1] genericLength #-}

{-# RULES
"genericLength -> fusible" [~1] forall xs.
    genericLength xs = Stream.genericLength (stream xs)
"genericLength -> unfused" [1] forall xs.
    Stream.genericLength (stream xs) = genericLength xs
  #-}

{-# RULES
"genericLength -> length/Int" genericLength = length :: [a] -> Int
  #-}

-- | /O(n)/,/fusion/. The 'genericTake' function is an overloaded version of 'take', which
-- accepts any 'Integral' value as the number of elements to take.
genericTake :: Integral i => i -> [a] -> [a]
genericTake 0 _      = []
genericTake _ []     = []
genericTake n (x:xs)
             | n > 0 = x : genericTake (n-1) xs
             | otherwise = error "List.genericTake: negative argument"
{-# NOINLINE [1] genericTake #-}

{-# RULES
"genericTake -> fusible" [~1] forall xs n.
    genericTake n xs = unstream (Stream.genericTake n (stream xs))
"genericTake -> unfused" [1]  forall xs n.
    unstream (Stream.genericTake n (stream xs)) = genericTake n xs
  #-}

{-# RULES
"genericTake -> take/Int" genericTake = take :: Int -> [a] -> [a]
  #-}

-- | /O(n)/,/fusion/. The 'genericDrop' function is an overloaded version of 'drop', which
-- accepts any 'Integral' value as the number of elements to drop.
genericDrop :: Integral i => i -> [a] -> [a]
genericDrop 0 xs        = xs
genericDrop _ []        = []
genericDrop n (_:xs) | n > 0  = genericDrop (n-1) xs
genericDrop _ _         = error "List.genericDrop: negative argument"
{-# NOINLINE [1] genericDrop #-}

{-# RULES
"genericDrop -> fusible" [~1] forall xs n.
    genericDrop n xs = unstream (Stream.genericDrop n (stream xs))
"genericDrop -> unfused" [1]  forall xs n.
    unstream (Stream.genericDrop n (stream xs)) = genericDrop n xs
  #-}

{-# RULES
"genericDrop -> drop/Int" genericDrop = drop :: Int -> [a] -> [a]
  #-}

-- | /O(n)/,/fusion/. The 'genericIndex' function is an overloaded version of '!!', which
-- accepts any 'Integral' value as the index.
genericIndex :: Integral a => [b] -> a -> b
genericIndex (x:_)  0 = x
genericIndex (_:xs) n
    | n > 0           = genericIndex xs (n-1)
    | otherwise       = error "List.genericIndex: negative argument."
genericIndex _ _      = error "List.genericIndex: index too large."
{-# NOINLINE [1] genericIndex #-}


-- can we pull the n > 0 test out and do it just once?
-- probably not since we don't know what n-1 does!!
-- can only specialise it for sane Integral instances :-(

{-# RULES
"genericIndex -> fusible" [~1] forall xs n.
    genericIndex xs n = Stream.genericIndex (stream xs) n
"genericIndex -> unfused" [1]  forall xs n.
    Stream.genericIndex (stream xs) n = genericIndex n xs
  #-}

{-# RULES
"genericIndex -> index/Int" genericIndex = (!!) :: [a] -> Int -> a
  #-}

-- | /O(n)/,/fusion/. The 'genericSplitAt' function is an overloaded
-- version of 'splitAt', which accepts any 'Integral' value as the
-- position at which to split.
--
genericSplitAt :: Integral i => i -> [a] -> ([a], [a])
genericSplitAt 0 xs     = ([],xs)
genericSplitAt _ []     = ([],[])
genericSplitAt n (x:xs) | n > 0  = (x:xs',xs'')
    where (xs',xs'') = genericSplitAt (n-1) xs
genericSplitAt _ _      = error "List.genericSplitAt: negative argument"

{-# RULES
"genericSplitAt -> fusible" [~1] forall xs n.
    genericSplitAt n xs = Stream.genericSplitAt n (stream xs)
"genericSplitAt -> unfused" [1]  forall xs n.
    Stream.genericSplitAt n (stream xs) = genericSplitAt n xs
  #-}

{-# RULES
"genericSplitAt -> splitAt/Int" genericSplitAt = splitAt :: Int -> [a] -> ([a], [a])
  #-}

-- | /O(n)/,/fusion/. The 'genericReplicate' function is an overloaded version of 'replicate',
-- which accepts any 'Integral' value as the number of repetitions to make.
--
genericReplicate :: Integral i => i -> a -> [a]
genericReplicate n x = genericTake n (repeat x)
{-# INLINE genericReplicate #-}

{-# RULES
"genericReplicate -> replicate/Int" genericReplicate = replicate :: Int -> a -> [a]
  #-}

-- ---------------------------------------------------------------------
-- Internal utilities

-- Common up near identical calls to `error' to reduce the number
-- constant strings created when compiled:
errorEmptyList :: String -> a
errorEmptyList fun = moduleError fun "empty list"
{-# NOINLINE errorEmptyList #-}

moduleError :: String -> String -> a
moduleError fun msg = error ("Data.List." ++ fun ++ ':':' ':msg)
{-# NOINLINE moduleError #-}

bottom :: a
bottom = error "Data.List.Stream: bottom"
{-# NOINLINE bottom #-}