    {-# LANGUAGE BangPatterns #-}
    {-# LANGUAGE CPP #-}

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Control.Parallel.SeqStrategies
    -- Copyright   :  (c) The University of Glasgow 2001-2009
    -- License     :  BSD-style (see the file libraries/base/LICENSE)
    --
    -- Maintainer  :  libraries@haskell.org
    -- Stability   :  experimental
    -- Portability :  portable
    --
    -- Sequential strategies provide ways to compositionally specify
    -- the degree of evaluation of a data type between the extremes of
    -- no evaluation and full evaluation.
    -- Sequential strategies may be viewed as complimentary to the parallel
    -- ones (see module "Control.Parallel.Strategies").
    --

    module Control.Seq
           (
             -- * The sequential strategy type
             Strategy

             -- * Application of sequential strategies
           , using            -- :: a -> Strategy a -> a
           , withStrategy     -- :: Strategy a -> a -> a

             -- * Basic sequential strategies
           , r0               -- :: Strategy a
           , rseq
           , rdeepseq         -- :: NFData a => Strategy a

             -- * Sequential strategies for lists
           , seqList          -- :: Strategy a -> Strategy [a]
           , seqListN         -- :: Int -> Strategy a -> Strategy [a]
           , seqListNth

             -- * Sequential strategies for foldable data types
           , seqFoldable      -- :: Foldable t => Strategy a -> Strategy (t a)
           , seqMap           -- :: Strategy k -> Strategy v -> Strategy (Map k v)
           , seqArray         -- :: Ix i => Strategy a -> Strategy (Array i a)
           , seqArrayBounds   -- :: Ix i => Strategy i -> Strategy (Array i a)

             -- * Sequential strategies for tuples

             -- | Evaluate the components of a tuple according to the given strategies.
             -- No guarantee is given as to the order of evaluation.

           , seqTuple2        -- :: Strategy a -> ... -> Strategy (a,...)
           , seqTuple3
           , seqTuple4
           , seqTuple5
           , seqTuple6
           , seqTuple7
           , seqTuple8
           , seqTuple9
           ) where

    import Control.DeepSeq (NFData, deepseq)
    #if MIN_VERSION_base(4,8,0)
    import Data.Foldable (toList)
    #else
    import Data.Foldable (Foldable, toList)
    #endif
    import Data.Map (Map)
    import qualified Data.Map (toList)
    #if !((__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1))
    import Data.Ix (Ix)
    #endif
    import Data.Array (Array)
    import qualified Data.Array (bounds, elems)

    infixl 0 `using`   -- lowest precedence and associate to the left

    -- --------------------------------------------------------------------------
    -- Sequential strategies

    -- | The type @'Strategy' a@ is @a -> ()@.
    -- Thus, a strategy is a function whose sole purpose it is to evaluate
    -- its argument (either in full or in part).
    type Strategy a = a -> ()

    -- | Evaluate a value using the given strategy.
    using :: a -> Strategy a -> a
    a
    x using :: forall a. a -> Strategy a -> a
    `using` Strategy a
    strat = Strategy a
    strat a
    x () -> a -> a
    forall a b. a -> b -> b
    `seq` a
    x

    -- | Evaluate a value using the given strategy.
    -- This is simply 'using' with arguments reversed.
    withStrategy :: Strategy a -> a -> a
    withStrategy :: forall a. Strategy a -> a -> a
    withStrategy = (a -> Strategy a -> a) -> Strategy a -> a -> a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip a -> Strategy a -> a
    forall a. a -> Strategy a -> a
    using

    -- --------------------------------------------------------------------------
    -- Basic sequential strategies

    -- | 'r0' performs *no* evaluation.
    r0 :: Strategy a
    r0 :: forall a. Strategy a
    r0 a
    _ = ()

    -- | 'rseq' evaluates its argument to weak head normal form.
    rseq :: Strategy a
    rseq :: forall a. Strategy a
    rseq a
    x = a
    x a -> () -> ()
    forall a b. a -> b -> b
    `seq` ()

    -- | 'rdeepseq' fully evaluates its argument.
    -- Relies on class 'NFData' from module "Control.DeepSeq".
    rdeepseq :: NFData a => Strategy a
    rdeepseq :: forall a. NFData a => Strategy a
    rdeepseq a
    x = a
    x a -> () -> ()
    forall a b. NFData a => a -> b -> b
    `deepseq` ()

    -- --------------------------------------------------------------------------
    -- Sequential strategies for lists

    -- | Evaluate each element of a list according to the given strategy.
    -- This function is a specialisation of 'seqFoldable' to lists.
    seqList :: Strategy a -> Strategy [a]
    seqList :: forall a. Strategy a -> Strategy [a]
    seqList Strategy a
    _strat []    = ()
    seqList Strategy a
    strat (a
    x:[a]
    xs) = Strategy a
    strat a
    x () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy a -> Strategy [a]
    forall a. Strategy a -> Strategy [a]
    seqList Strategy a
    strat [a]
    xs
    -- Alternative definition via seqFoldable:
    -- seqList = seqFoldable

    -- | Evaluate the first n elements of a list according to the given strategy.
    seqListN :: Int -> Strategy a -> Strategy [a]
    seqListN :: forall a. Int -> Strategy a -> Strategy [a]
    seqListN Int
    0  Strategy a
    _strat [a]
    _     = ()
    seqListN !Int
    _ Strategy a
    _strat []    = ()
    seqListN !Int
    n Strategy a
    strat (a
    x:[a]
    xs) = Strategy a
    strat a
    x () -> () -> ()
    forall a b. a -> b -> b
    `seq` Int -> Strategy a -> Strategy [a]
    forall a. Int -> Strategy a -> Strategy [a]
    seqListN (Int
    nInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1) Strategy a
    strat [a]
    xs

    -- | Evaluate the nth element of a list (if there is such) according to
    -- the given strategy.
    -- The spine of the list up to the nth element is evaluated as a side effect.
    seqListNth :: Int -> Strategy a -> Strategy [a]
    seqListNth :: forall a. Int -> Strategy a -> Strategy [a]
    seqListNth Int
    0  Strategy a
    strat  (a
    x:[a]
    _)  = Strategy a
    strat a
    x
    seqListNth !Int
    _ Strategy a
    _strat []     = ()
    seqListNth !Int
    n Strategy a
    strat  (a
    _:[a]
    xs) = Int -> Strategy a -> Strategy [a]
    forall a. Int -> Strategy a -> Strategy [a]
    seqListNth (Int
    nInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1) Strategy a
    strat [a]
    xs

    -- --------------------------------------------------------------------------
    -- Sequential strategies for foldable data types

    -- | Evaluate the elements of a foldable data structure according to
    -- the given strategy.
    seqFoldable :: Foldable t => Strategy a -> Strategy (t a)
    seqFoldable :: forall (t :: * -> *) a. Foldable t => Strategy a -> Strategy (t a)
    seqFoldable Strategy a
    strat = Strategy a -> Strategy [a]
    forall a. Strategy a -> Strategy [a]
    seqList Strategy a
    strat Strategy [a] -> (t a -> [a]) -> t a -> ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . t a -> [a]
    forall a. t a -> [a]
    forall (t :: * -> *) a. Foldable t => t a -> [a]
    toList
    -- Alternative definition via foldl':
    -- seqFoldable strat = foldl' (const strat) ()

    {-# SPECIALISE seqFoldable :: Strategy a -> Strategy [a] #-}

    -- | Evaluate the elements of an array according to the given strategy.
    -- Evaluation of the array bounds may be triggered as a side effect.
    #if (__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1)
    seqArray :: Strategy a -> Strategy (Array i a)
    #else
    seqArray :: Ix i => Strategy a -> Strategy (Array i a)
    #endif
    seqArray :: forall a i. Strategy a -> Strategy (Array i a)
    seqArray Strategy a
    strat = Strategy a -> Strategy [a]
    forall a. Strategy a -> Strategy [a]
    seqList Strategy a
    strat Strategy [a] -> (Array i a -> [a]) -> Array i a -> ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Array i a -> [a]
    forall i e. Array i e -> [e]
    Data.Array.elems

    -- | Evaluate the bounds of an array according to the given strategy.
    #if (__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1)
    seqArrayBounds :: Strategy i -> Strategy (Array i a)
    #else
    seqArrayBounds :: Ix i => Strategy i -> Strategy (Array i a)
    #endif
    seqArrayBounds :: forall i a. Strategy i -> Strategy (Array i a)
    seqArrayBounds Strategy i
    strat = Strategy i -> Strategy i -> Strategy (i, i)
    forall a b. Strategy a -> Strategy b -> Strategy (a, b)
    seqTuple2 Strategy i
    strat Strategy i
    strat Strategy (i, i) -> (Array i a -> (i, i)) -> Array i a -> ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Array i a -> (i, i)
    forall i e. Array i e -> (i, i)
    Data.Array.bounds

    -- | Evaluate the keys and values of a map according to the given strategies.
    seqMap :: Strategy k -> Strategy v -> Strategy (Map k v)
    seqMap :: forall k v. Strategy k -> Strategy v -> Strategy (Map k v)
    seqMap Strategy k
    stratK Strategy v
    stratV = Strategy (k, v) -> Strategy [(k, v)]
    forall a. Strategy a -> Strategy [a]
    seqList (Strategy k -> Strategy v -> Strategy (k, v)
    forall a b. Strategy a -> Strategy b -> Strategy (a, b)
    seqTuple2 Strategy k
    stratK Strategy v
    stratV) Strategy [(k, v)] -> (Map k v -> [(k, v)]) -> Map k v -> ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map k v -> [(k, v)]
    forall k a. Map k a -> [(k, a)]
    Data.Map.toList

    -- --------------------------------------------------------------------------
    -- Sequential strategies for tuples

    seqTuple2 :: Strategy a -> Strategy b -> Strategy (a,b)
    seqTuple2 :: forall a b. Strategy a -> Strategy b -> Strategy (a, b)
    seqTuple2 Strategy a
    strat1 Strategy b
    strat2 (a
    x1,b
    x2) =
      Strategy a
    strat1 a
    x1 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy b
    strat2 b
    x2

    seqTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
    seqTuple3 :: forall a b c.
    Strategy a -> Strategy b -> Strategy c -> Strategy (a, b, c)
    seqTuple3 Strategy a
    strat1 Strategy b
    strat2 Strategy c
    strat3 (a
    x1,b
    x2,c
    x3) =
      Strategy a
    strat1 a
    x1 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy b
    strat2 b
    x2 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy c
    strat3 c
    x3

    seqTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a,b,c,d)
    seqTuple4 :: forall a b c d.
    Strategy a
    -> Strategy b -> Strategy c -> Strategy d -> Strategy (a, b, c, d)
    seqTuple4 Strategy a
    strat1 Strategy b
    strat2 Strategy c
    strat3 Strategy d
    strat4 (a
    x1,b
    x2,c
    x3,d
    x4) =
      Strategy a
    strat1 a
    x1 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy b
    strat2 b
    x2 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy c
    strat3 c
    x3 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy d
    strat4 d
    x4

    seqTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a,b,c,d,e)
    seqTuple5 :: forall a b c d e.
    Strategy a
    -> Strategy b
    -> Strategy c
    -> Strategy d
    -> Strategy e
    -> Strategy (a, b, c, d, e)
    seqTuple5 Strategy a
    strat1 Strategy b
    strat2 Strategy c
    strat3 Strategy d
    strat4 Strategy e
    strat5 (a
    x1,b
    x2,c
    x3,d
    x4,e
    x5) =
      Strategy a
    strat1 a
    x1 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy b
    strat2 b
    x2 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy c
    strat3 c
    x3 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy d
    strat4 d
    x4 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy e
    strat5 e
    x5

    seqTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a,b,c,d,e,f)
    seqTuple6 :: forall a b c d e f.
    Strategy a
    -> Strategy b
    -> Strategy c
    -> Strategy d
    -> Strategy e
    -> Strategy f
    -> Strategy (a, b, c, d, e, f)
    seqTuple6 Strategy a
    strat1 Strategy b
    strat2 Strategy c
    strat3 Strategy d
    strat4 Strategy e
    strat5 Strategy f
    strat6 (a
    x1,b
    x2,c
    x3,d
    x4,e
    x5,f
    x6) =
      Strategy a
    strat1 a
    x1 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy b
    strat2 b
    x2 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy c
    strat3 c
    x3 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy d
    strat4 d
    x4 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy e
    strat5 e
    x5 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy f
    strat6 f
    x6

    seqTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a,b,c,d,e,f,g)
    seqTuple7 :: forall a b c d e f g.
    Strategy a
    -> Strategy b
    -> Strategy c
    -> Strategy d
    -> Strategy e
    -> Strategy f
    -> Strategy g
    -> Strategy (a, b, c, d, e, f, g)
    seqTuple7 Strategy a
    strat1 Strategy b
    strat2 Strategy c
    strat3 Strategy d
    strat4 Strategy e
    strat5 Strategy f
    strat6 Strategy g
    strat7 (a
    x1,b
    x2,c
    x3,d
    x4,e
    x5,f
    x6,g
    x7) =
      Strategy a
    strat1 a
    x1 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy b
    strat2 b
    x2 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy c
    strat3 c
    x3 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy d
    strat4 d
    x4 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy e
    strat5 e
    x5 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy f
    strat6 f
    x6 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy g
    strat7 g
    x7

    seqTuple8 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy (a,b,c,d,e,f,g,h)
    seqTuple8 :: forall a b c d e f g h.
    Strategy a
    -> Strategy b
    -> Strategy c
    -> Strategy d
    -> Strategy e
    -> Strategy f
    -> Strategy g
    -> Strategy h
    -> Strategy (a, b, c, d, e, f, g, h)
    seqTuple8 Strategy a
    strat1 Strategy b
    strat2 Strategy c
    strat3 Strategy d
    strat4 Strategy e
    strat5 Strategy f
    strat6 Strategy g
    strat7 Strategy h
    strat8 (a
    x1,b
    x2,c
    x3,d
    x4,e
    x5,f
    x6,g
    x7,h
    x8) =
      Strategy a
    strat1 a
    x1 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy b
    strat2 b
    x2 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy c
    strat3 c
    x3 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy d
    strat4 d
    x4 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy e
    strat5 e
    x5 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy f
    strat6 f
    x6 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy g
    strat7 g
    x7 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy h
    strat8 h
    x8

    seqTuple9 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy i -> Strategy (a,b,c,d,e,f,g,h,i)
    seqTuple9 :: forall a b c d e f g h i.
    Strategy a
    -> Strategy b
    -> Strategy c
    -> Strategy d
    -> Strategy e
    -> Strategy f
    -> Strategy g
    -> Strategy h
    -> Strategy i
    -> Strategy (a, b, c, d, e, f, g, h, i)
    seqTuple9 Strategy a
    strat1 Strategy b
    strat2 Strategy c
    strat3 Strategy d
    strat4 Strategy e
    strat5 Strategy f
    strat6 Strategy g
    strat7 Strategy h
    strat8 Strategy i
    strat9 (a
    x1,b
    x2,c
    x3,d
    x4,e
    x5,f
    x6,g
    x7,h
    x8,i
    x9) =
      Strategy a
    strat1 a
    x1 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy b
    strat2 b
    x2 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy c
    strat3 c
    x3 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy d
    strat4 d
    x4 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy e
    strat5 e
    x5 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy f
    strat6 f
    x6 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy g
    strat7 g
    x7 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy h
    strat8 h
    x8 () -> () -> ()
    forall a b. a -> b -> b
    `seq` Strategy i
    strat9 i
    x9