-- |
--   Module      :  Data.Edison.Seq.ListSeq
--   Copyright   :  Copyright (c) 1998 Chris Okasaki
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  stable
--   Portability :  GHC, Hugs (MPTC and FD)
--
--   This module packages the standard prelude list type as a
--   sequence.  This is the baseline sequence implementation and
--   all methods have the default running times listed in
--   "Data.Edison.Seq", except for the following two trivial operations:
--
--   * toList, fromList     @O( 1 )@
--
module Data.Edison.Seq.ListSeq (
    -- * Sequence Type
    Seq,

    -- * Sequence Operations
    empty,singleton,lcons,rcons,append,lview,lhead,lheadM,ltail,ltailM,
    rview,rhead,rheadM,rtail,rtailM,
    null,size,concat,reverse,reverseOnto,fromList,toList,map,concatMap,
    fold,fold',fold1,fold1',foldr,foldr',foldl,foldl',foldr1,foldr1',foldl1,foldl1',
    reducer,reducer',reducel,reducel',reduce1,reduce1',
    copy,inBounds,lookup,lookupM,lookupWithDefault,update,adjust,
    mapWithIndex,foldrWithIndex,foldrWithIndex',foldlWithIndex,foldlWithIndex',
    take,drop,splitAt,subseq,filter,partition,takeWhile,dropWhile,splitWhile,
    zip,zip3,zipWith,zipWith3,unzip,unzip3,unzipWith,unzipWith3,
    strict,strictWith,

    -- * Unit testing
    structuralInvariant,

    -- * Documentation
    moduleName
) where

import Prelude hiding (concat,reverse,map,concatMap,foldr,foldl,foldr1,foldl1,
                       filter,takeWhile,dropWhile,lookup,take,drop,splitAt,
                       zip,zip3,zipWith,zipWith3,unzip,unzip3,null)
import qualified Control.Monad.Fail as Fail
import qualified Prelude
import Data.Edison.Prelude ( runFail_ )
import qualified Data.List
import Data.Monoid
import qualified Data.Edison.Seq as S ( Sequence(..) ) 

-- signatures for exported functions
moduleName     :: String
empty          :: [a]
singleton      :: a -> [a]
lcons          :: a -> [a] -> [a]
rcons          :: a -> [a] -> [a]
append         :: [a] -> [a] -> [a]
lview          :: (Fail.MonadFail rm) => [a] -> rm (a, [a])
lhead          :: [a] -> a
lheadM         :: (Fail.MonadFail rm) => [a] -> rm a
ltail          :: [a] -> [a]
ltailM         :: (Fail.MonadFail rm) => [a] -> rm [a]
rview          :: (Fail.MonadFail rm) => [a] -> rm (a, [a])
rhead          :: [a] -> a
rheadM         :: (Fail.MonadFail rm) => [a] -> rm a
rtail          :: [a] -> [a]
rtailM         :: (Fail.MonadFail rm) => [a] -> rm [a]
null           :: [a] -> Bool
size           :: [a] -> Int
concat         :: [[a]] -> [a]
reverse        :: [a] -> [a]
reverseOnto    :: [a] -> [a] -> [a]
fromList       :: [a] -> [a]
toList         :: [a] -> [a]
map            :: (a -> b) -> [a] -> [b]
concatMap      :: (a -> [b]) -> [a] -> [b]
fold           :: (a -> b -> b) -> b -> [a] -> b
fold'          :: (a -> b -> b) -> b -> [a] -> b
fold1          :: (a -> a -> a) -> [a] -> a
fold1'         :: (a -> a -> a) -> [a] -> a
foldr          :: (a -> b -> b) -> b -> [a] -> b
foldl          :: (b -> a -> b) -> b -> [a] -> b
foldr1         :: (a -> a -> a) -> [a] -> a
foldl1         :: (a -> a -> a) -> [a] -> a
reducer        :: (a -> a -> a) -> a -> [a] -> a
reducel        :: (a -> a -> a) -> a -> [a] -> a
reduce1        :: (a -> a -> a) -> [a] -> a
foldl'         :: (b -> a -> b) -> b -> [a] -> b
foldl1'        :: (a -> a -> a) -> [a] -> a
reducer'       :: (a -> a -> a) -> a -> [a] -> a
reducel'       :: (a -> a -> a) -> a -> [a] -> a
reduce1'       :: (a -> a -> a) -> [a] -> a
copy           :: Int -> a -> [a]
inBounds       :: Int -> [a] -> Bool
lookup         :: Int -> [a] -> a
lookupM        :: (Fail.MonadFail m) => Int -> [a] -> m a
lookupWithDefault :: a -> Int -> [a] -> a
update         :: Int -> a -> [a] -> [a]
adjust         :: (a -> a) -> Int -> [a] -> [a]
mapWithIndex   :: (Int -> a -> b) -> [a] -> [b]
foldrWithIndex :: (Int -> a -> b -> b) -> b -> [a] -> b
foldlWithIndex :: (b -> Int -> a -> b) -> b -> [a] -> b
foldlWithIndex' :: (b -> Int -> a -> b) -> b -> [a] -> b
take           :: Int -> [a] -> [a]
drop           :: Int -> [a] -> [a]
splitAt        :: Int -> [a] -> ([a], [a])
subseq         :: Int -> Int -> [a] -> [a]
filter         :: (a -> Bool) -> [a] -> [a]
partition      :: (a -> Bool) -> [a] -> ([a], [a])
takeWhile      :: (a -> Bool) -> [a] -> [a]
dropWhile      :: (a -> Bool) -> [a] -> [a]
splitWhile     :: (a -> Bool) -> [a] -> ([a], [a])
zip            :: [a] -> [b] -> [(a,b)]
zip3           :: [a] -> [b] -> [c] -> [(a,b,c)]
zipWith        :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith3       :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
unzip          :: [(a,b)] -> ([a], [b])
unzip3         :: [(a,b,c)] -> ([a], [b], [c])
unzipWith      :: (a -> b) -> (a -> c) -> [a] -> ([b], [c])
unzipWith3     :: (a -> b) -> (a -> c) -> (a -> d) -> [a] -> ([b], [c], [d])
strict         :: [a] -> [a]
strictWith     :: (a -> b) -> [a] -> [a]
structuralInvariant :: [a] -> Bool

moduleName :: String
moduleName = String
"Data.Edison.Seq.ListSeq"

type Seq a = [a]

empty :: forall a. [a]
empty = []
singleton :: forall a. a -> [a]
singleton a
x = [a
x]
lcons :: forall a. a -> [a] -> [a]
lcons = (:)
rcons :: forall a. a -> [a] -> [a]
rcons a
x [a]
s = [a]
s forall a. [a] -> [a] -> [a]
++ [a
x]
append :: forall a. [a] -> [a] -> [a]
append = forall a. [a] -> [a] -> [a]
(++)

lview :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm (a, [a])
lview [] = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"ListSeq.lview: empty sequence"
lview (a
x:[a]
xs) = forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, [a]
xs)

lheadM :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm a
lheadM [] = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"ListSeq.lheadM: empty sequence"
lheadM (a
x:[a]
xs) = forall (m :: * -> *) a. Monad m => a -> m a
return a
x

lhead :: forall a. [a] -> a
lhead [] = forall a. HasCallStack => String -> a
error String
"ListSeq.lhead: empty sequence"
lhead (a
x:[a]
xs) = a
x

ltailM :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm [a]
ltailM [] = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"ListSeq.ltailM: empty sequence"
ltailM (a
x:[a]
xs) = forall (m :: * -> *) a. Monad m => a -> m a
return [a]
xs

ltail :: forall a. [a] -> [a]
ltail [] = forall a. HasCallStack => String -> a
error String
"ListSeq.ltail: empty sequence"
ltail (a
x:[a]
xs) = [a]
xs

rview :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm (a, [a])
rview [] = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"ListSeq.rview: empty sequence"
rview [a]
xs = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. [a] -> a
rhead [a]
xs, forall a. [a] -> [a]
rtail [a]
xs)

rheadM :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm a
rheadM [] = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"ListSeq.rheadM: empty sequence"
rheadM (a
x:[a]
xs) = forall {m :: * -> *} {t}. Monad m => t -> [t] -> m t
rh a
x [a]
xs
  where rh :: t -> [t] -> m t
rh t
y [] = forall (m :: * -> *) a. Monad m => a -> m a
return t
y
        rh t
y (t
x:[t]
xs) = t -> [t] -> m t
rh t
x [t]
xs

rhead :: forall a. [a] -> a
rhead [] = forall a. HasCallStack => String -> a
error String
"ListSeq.rhead: empty sequence"
rhead (a
x:[a]
xs) = forall {t}. t -> [t] -> t
rh a
x [a]
xs
  where rh :: t -> [t] -> t
rh t
y [] = t
y
        rh t
y (t
x:[t]
xs) = t -> [t] -> t
rh t
x [t]
xs

rtailM :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm [a]
rtailM [] = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"ListSeq.rtailM: empty sequence"
rtailM (a
x:[a]
xs) = forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> [a] -> [a]
rt a
x [a]
xs)
  where rt :: t -> [t] -> [t]
rt t
y [] = []
        rt t
y (t
x:[t]
xs) = t
y forall a. a -> [a] -> [a]
: t -> [t] -> [t]
rt t
x [t]
xs

rtail :: forall a. [a] -> [a]
rtail [] = forall a. HasCallStack => String -> a
error String
"ListSeq.rtail: empty sequence"
rtail (a
x:[a]
xs) = forall a. a -> [a] -> [a]
rt a
x [a]
xs
  where rt :: t -> [t] -> [t]
rt t
y [] = []
        rt t
y (t
x:[t]
xs) = t
y forall a. a -> [a] -> [a]
: t -> [t] -> [t]
rt t
x [t]
xs

null :: forall a. [a] -> Bool
null = forall (t :: * -> *) a. Foldable t => t a -> Bool
Prelude.null
size :: forall a. [a] -> Int
size = forall (t :: * -> *) a. Foldable t => t a -> Int
length
concat :: forall a. [[a]] -> [a]
concat = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr forall a. [a] -> [a] -> [a]
append forall a. [a]
empty
reverse :: forall a. [a] -> [a]
reverse = forall a. [a] -> [a]
Prelude.reverse

reverseOnto :: forall a. [a] -> [a] -> [a]
reverseOnto [] [a]
ys = [a]
ys
reverseOnto (a
x:[a]
xs) [a]
ys = forall a. [a] -> [a] -> [a]
reverseOnto [a]
xs (a
xforall a. a -> [a] -> [a]
:[a]
ys)

fromList :: forall a. [a] -> [a]
fromList [a]
xs = [a]
xs
toList :: forall a. [a] -> [a]
toList [a]
xs = [a]
xs
map :: forall a b. (a -> b) -> [a] -> [b]
map = forall a b. (a -> b) -> [a] -> [b]
Data.List.map

concatMap :: forall a b. (a -> [b]) -> [a] -> [b]
concatMap = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
Data.List.concatMap

fold :: forall a b. (a -> b -> b) -> b -> [a] -> b
fold  = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr
fold' :: forall a b. (a -> b -> b) -> b -> [a] -> b
fold' a -> b -> b
f = forall b a. (b -> a -> b) -> b -> [a] -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
f)

fold1 :: forall a. (a -> a -> a) -> [a] -> a
fold1 a -> a -> a
f []      = forall a. HasCallStack => String -> a
error String
"ListSeq.fold1: empty sequence"
fold1 a -> a -> a
f (a
x:[a]
xs)  = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr a -> a -> a
f a
x [a]
xs

fold1' :: forall a. (a -> a -> a) -> [a] -> a
fold1' a -> a -> a
f []     = forall a. HasCallStack => String -> a
error String
"ListSeq.fold1': empty sequence"
fold1' a -> a -> a
f (a
x:[a]
xs) = forall b a. (b -> a -> b) -> b -> [a] -> b
foldl' a -> a -> a
f a
x [a]
xs

foldr :: forall a b. (a -> b -> b) -> b -> [a] -> b
foldr = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Data.List.foldr
foldl :: forall b a. (b -> a -> b) -> b -> [a] -> b
foldl = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Data.List.foldl

foldr' :: (t -> a -> a) -> a -> [t] -> a
foldr' t -> a -> a
f a
e [] = a
e
foldr' t -> a -> a
f a
e (t
x:[t]
xs) = t -> a -> a
f t
x forall a b. (a -> b) -> a -> b
$! (t -> a -> a) -> a -> [t] -> a
foldr' t -> a -> a
f a
e [t]
xs

foldl' :: forall b a. (b -> a -> b) -> b -> [a] -> b
foldl' b -> a -> b
f b
e [] = b
e
foldl' b -> a -> b
f b
e (a
x:[a]
xs) = b
e seq :: forall a b. a -> b -> b
`seq` forall b a. (b -> a -> b) -> b -> [a] -> b
foldl' b -> a -> b
f (b -> a -> b
f b
e a
x) [a]
xs

foldr1 :: forall a. (a -> a -> a) -> [a] -> a
foldr1 a -> a -> a
f [] = forall a. HasCallStack => String -> a
error String
"ListSeq.foldr1: empty sequence"
foldr1 a -> a -> a
f [a]
xs = [a] -> a
fr [a]
xs
  where fr :: [a] -> a
fr [a
x]    = a
x
        fr (a
x:[a]
xs) = a -> a -> a
f a
x forall a b. (a -> b) -> a -> b
$ [a] -> a
fr [a]
xs
        fr [a]
_ = forall a. HasCallStack => String -> a
error String
"ListSeq.foldr1: bug!"

foldr1' :: (a -> a -> a) -> [a] -> a
foldr1' a -> a -> a
f [] = forall a. HasCallStack => String -> a
error String
"ListSeq.foldr1': empty sequence"
foldr1' a -> a -> a
f [a]
xs = [a] -> a
fr [a]
xs
  where fr :: [a] -> a
fr [a
x]    = a
x
        fr (a
x:[a]
xs) = a -> a -> a
f a
x forall a b. (a -> b) -> a -> b
$! [a] -> a
fr [a]
xs
        fr [a]
_  = forall a. HasCallStack => String -> a
error String
"ListSeq.foldr1': bug!"

foldl1 :: forall a. (a -> a -> a) -> [a] -> a
foldl1 a -> a -> a
f [] = forall a. HasCallStack => String -> a
error String
"ListSeq.foldl1: empty sequence"
foldl1 a -> a -> a
f (a
x:[a]
xs) = forall b a. (b -> a -> b) -> b -> [a] -> b
foldl a -> a -> a
f a
x [a]
xs

foldl1' :: forall a. (a -> a -> a) -> [a] -> a
foldl1' a -> a -> a
f [] = forall a. HasCallStack => String -> a
error String
"ListSeq.foldl1': empty sequence"
foldl1' a -> a -> a
f (a
x:[a]
xs) = forall b a. (b -> a -> b) -> b -> [a] -> b
foldl' a -> a -> a
f a
x [a]
xs

reducer :: forall a. (a -> a -> a) -> a -> [a] -> a
reducer a -> a -> a
f a
e [] = a
e
reducer a -> a -> a
f a
e [a]
xs = a -> a -> a
f (forall a. (a -> a -> a) -> [a] -> a
reduce1 a -> a -> a
f [a]
xs) a
e

reducer' :: forall a. (a -> a -> a) -> a -> [a] -> a
reducer' a -> a -> a
f a
e [] = a
e
reducer' a -> a -> a
f a
e [a]
xs = (a -> a -> a
f forall a b. (a -> b) -> a -> b
$! (forall a. (a -> a -> a) -> [a] -> a
reduce1' a -> a -> a
f [a]
xs)) forall a b. (a -> b) -> a -> b
$! a
e

reducel :: forall a. (a -> a -> a) -> a -> [a] -> a
reducel a -> a -> a
f a
e [] = a
e
reducel a -> a -> a
f a
e [a]
xs = a -> a -> a
f a
e (forall a. (a -> a -> a) -> [a] -> a
reduce1 a -> a -> a
f [a]
xs)

reducel' :: forall a. (a -> a -> a) -> a -> [a] -> a
reducel' a -> a -> a
f a
e [] = a
e
reducel' a -> a -> a
f a
e [a]
xs = (a -> a -> a
f forall a b. (a -> b) -> a -> b
$! a
e) forall a b. (a -> b) -> a -> b
$! (forall a. (a -> a -> a) -> [a] -> a
reduce1' a -> a -> a
f [a]
xs)

reduce1 :: forall a. (a -> a -> a) -> [a] -> a
reduce1 a -> a -> a
f [] = forall a. HasCallStack => String -> a
error String
"ListSeq.reduce1: empty sequence"
reduce1 a -> a -> a
f [a
x] = a
x
reduce1 a -> a -> a
f (a
x1 : a
x2 : [a]
xs) = forall a. (a -> a -> a) -> [a] -> a
reduce1 a -> a -> a
f (a -> a -> a
f a
x1 a
x2 forall a. a -> [a] -> [a]
: [a] -> [a]
pairup [a]
xs)
  where pairup :: [a] -> [a]
pairup (a
x1 : a
x2 : [a]
xs) = a -> a -> a
f a
x1 a
x2 forall a. a -> [a] -> [a]
: [a] -> [a]
pairup [a]
xs
        pairup [a]
xs = [a]
xs
  -- can be improved using a counter and bit ops!

reduce1' :: forall a. (a -> a -> a) -> [a] -> a
reduce1' a -> a -> a
f [] = forall a. HasCallStack => String -> a
error String
"ListSeq.reduce1': empty sequence"
reduce1' a -> a -> a
f [a
x] = a
x
reduce1' a -> a -> a
f (a
x1 : a
x2 : [a]
xs) = a
x1 seq :: forall a b. a -> b -> b
`seq` a
x2 seq :: forall a b. a -> b -> b
`seq` forall a. (a -> a -> a) -> [a] -> a
reduce1' a -> a -> a
f (a -> a -> a
f a
x1 a
x2 forall a. a -> [a] -> [a]
: [a] -> [a]
pairup [a]
xs)
  where pairup :: [a] -> [a]
pairup (a
x1 : a
x2 : [a]
xs) = a
x1 seq :: forall a b. a -> b -> b
`seq` a
x2 seq :: forall a b. a -> b -> b
`seq` (a -> a -> a
f a
x1 a
x2 forall a. a -> [a] -> [a]
: [a] -> [a]
pairup [a]
xs)
        pairup [a]
xs = [a]
xs

copy :: forall a. Int -> a -> [a]
copy Int
n a
x | Int
n forall a. Ord a => a -> a -> Bool
<= Int
0 = []
         | Bool
otherwise = a
x forall a. a -> [a] -> [a]
: forall a. Int -> a -> [a]
copy (Int
nforall a. Num a => a -> a -> a
-Int
1) a
x
  -- depends on n to be unboxed, should test this!

inBounds :: forall a. Int -> [a] -> Bool
inBounds Int
i [a]
xs
  | Int
i forall a. Ord a => a -> a -> Bool
>= Int
0    = Bool -> Bool
not (forall a. [a] -> Bool
null (forall a. Int -> [a] -> [a]
drop Int
i [a]
xs))
  | Bool
otherwise = Bool
False

lookup :: forall a. Int -> [a] -> a
lookup Int
i [a]
xs = forall a. Fail a -> a
runFail_ (forall (m :: * -> *) a. MonadFail m => Int -> [a] -> m a
lookupM Int
i [a]
xs)

lookupM :: forall (m :: * -> *) a. MonadFail m => Int -> [a] -> m a
lookupM Int
i [a]
xs
  | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 = forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"ListSeq.lookup: not found"
  | Bool
otherwise = case forall a. Int -> [a] -> [a]
drop Int
i [a]
xs of
                  [] -> forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"ListSeq.lookup: not found"
                  (a
x:[a]
_) -> forall (m :: * -> *) a. Monad m => a -> m a
return a
x

lookupWithDefault :: forall a. a -> Int -> [a] -> a
lookupWithDefault a
d Int
i [a]
xs
  | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 = a
d
  | Bool
otherwise = case forall a. Int -> [a] -> [a]
drop Int
i [a]
xs of
                  [] -> a
d
                  (a
x:[a]
_) -> a
x

update :: forall a. Int -> a -> [a] -> [a]
update Int
i a
y [a]
xs 
    | Int
i forall a. Ord a => a -> a -> Bool
< Int
0     = [a]
xs
    | Bool
otherwise = forall {t}. (Ord t, Num t) => t -> [a] -> [a]
upd Int
i [a]
xs
  where upd :: t -> [a] -> [a]
upd t
_ [] = []
        upd t
i (a
x:[a]
xs)
          | t
i forall a. Ord a => a -> a -> Bool
> t
0     = a
x forall a. a -> [a] -> [a]
: t -> [a] -> [a]
upd (t
i forall a. Num a => a -> a -> a
- t
1) [a]
xs
          | Bool
otherwise = a
y forall a. a -> [a] -> [a]
: [a]
xs

adjust :: forall a. (a -> a) -> Int -> [a] -> [a]
adjust a -> a
f Int
i [a]
xs 
    | Int
i forall a. Ord a => a -> a -> Bool
< Int
0     = [a]
xs
    | Bool
otherwise = forall {t}. (Ord t, Num t) => t -> [a] -> [a]
adj Int
i [a]
xs
  where adj :: t -> [a] -> [a]
adj t
_ [] = []
        adj t
i (a
x:[a]
xs)
          | t
i forall a. Ord a => a -> a -> Bool
> t
0     = a
x forall a. a -> [a] -> [a]
: t -> [a] -> [a]
adj (t
i forall a. Num a => a -> a -> a
- t
1) [a]
xs
          | Bool
otherwise = a -> a
f a
x forall a. a -> [a] -> [a]
: [a]
xs

mapWithIndex :: forall a b. (Int -> a -> b) -> [a] -> [b]
mapWithIndex Int -> a -> b
f = Int -> [a] -> [b]
mapi Int
0
  where mapi :: Int -> [a] -> [b]
mapi Int
i [] = []
        mapi Int
i (a
x:[a]
xs) = Int -> a -> b
f Int
i a
x forall a. a -> [a] -> [a]
: Int -> [a] -> [b]
mapi (forall a. Enum a => a -> a
succ Int
i) [a]
xs

foldrWithIndex :: forall a b. (Int -> a -> b -> b) -> b -> [a] -> b
foldrWithIndex Int -> a -> b -> b
f b
e = Int -> [a] -> b
foldi Int
0
  where foldi :: Int -> [a] -> b
foldi Int
i [] = b
e
        foldi Int
i (a
x:[a]
xs) = Int -> a -> b -> b
f Int
i a
x (Int -> [a] -> b
foldi (forall a. Enum a => a -> a
succ Int
i) [a]
xs)

foldrWithIndex' :: (t -> t -> a -> a) -> a -> [t] -> a
foldrWithIndex' t -> t -> a -> a
f a
e = t -> [t] -> a
foldi t
0
  where foldi :: t -> [t] -> a
foldi t
i [] = a
e
        foldi t
i (t
x:[t]
xs) = t -> t -> a -> a
f t
i t
x forall a b. (a -> b) -> a -> b
$! (t -> [t] -> a
foldi (forall a. Enum a => a -> a
succ t
i) [t]
xs)

foldlWithIndex :: forall b a. (b -> Int -> a -> b) -> b -> [a] -> b
foldlWithIndex b -> Int -> a -> b
f = Int -> b -> [a] -> b
foldi Int
0
  where foldi :: Int -> b -> [a] -> b
foldi Int
i b
e [] = b
e
        foldi Int
i b
e (a
x:[a]
xs) = Int -> b -> [a] -> b
foldi (forall a. Enum a => a -> a
succ Int
i) (b -> Int -> a -> b
f b
e Int
i a
x) [a]
xs

foldlWithIndex' :: forall b a. (b -> Int -> a -> b) -> b -> [a] -> b
foldlWithIndex' b -> Int -> a -> b
f = Int -> b -> [a] -> b
foldi Int
0
  where foldi :: Int -> b -> [a] -> b
foldi Int
i b
e [] = b
e
        foldi Int
i b
e (a
x:[a]
xs) = b
e seq :: forall a b. a -> b -> b
`seq` Int -> b -> [a] -> b
foldi (forall a. Enum a => a -> a
succ Int
i) (b -> Int -> a -> b
f b
e Int
i a
x) [a]
xs


take :: forall a. Int -> [a] -> [a]
take Int
i [a]
xs | Int
i forall a. Ord a => a -> a -> Bool
<= Int
0 = []
          | Bool
otherwise = forall a. Int -> [a] -> [a]
Data.List.take Int
i [a]
xs

drop :: forall a. Int -> [a] -> [a]
drop Int
i [a]
xs | Int
i forall a. Ord a => a -> a -> Bool
<= Int
0 = [a]
xs
          | Bool
otherwise = forall a. Int -> [a] -> [a]
Data.List.drop Int
i [a]
xs

splitAt :: forall a. Int -> [a] -> ([a], [a])
splitAt Int
i [a]
xs | Int
i forall a. Ord a => a -> a -> Bool
<= Int
0 = ([], [a]
xs)
             | Bool
otherwise = forall a. Int -> [a] -> ([a], [a])
Data.List.splitAt Int
i [a]
xs

subseq :: forall a. Int -> Int -> [a] -> [a]
subseq Int
i Int
len [a]
xs = forall a. Int -> [a] -> [a]
take Int
len (forall a. Int -> [a] -> [a]
drop Int
i [a]
xs)
        
strict :: forall a. [a] -> [a]
strict l :: [a]
l@[] = [a]
l
strict l :: [a]
l@(a
_:[a]
xs) = forall a. [a] -> [a]
strict [a]
xs seq :: forall a b. a -> b -> b
`seq` [a]
l

strictWith :: forall a b. (a -> b) -> [a] -> [a]
strictWith a -> b
f l :: [a]
l@[] = [a]
l
strictWith a -> b
f l :: [a]
l@(a
x:[a]
xs) = a -> b
f a
x seq :: forall a b. a -> b -> b
`seq` forall a b. (a -> b) -> [a] -> [a]
strictWith a -> b
f [a]
xs seq :: forall a b. a -> b -> b
`seq` [a]
l

filter :: forall a. (a -> Bool) -> [a] -> [a]
filter = forall a. (a -> Bool) -> [a] -> [a]
Data.List.filter
partition :: forall a. (a -> Bool) -> [a] -> ([a], [a])
partition = forall a. (a -> Bool) -> [a] -> ([a], [a])
Data.List.partition
takeWhile :: forall a. (a -> Bool) -> [a] -> [a]
takeWhile = forall a. (a -> Bool) -> [a] -> [a]
Data.List.takeWhile
dropWhile :: forall a. (a -> Bool) -> [a] -> [a]
dropWhile = forall a. (a -> Bool) -> [a] -> [a]
Data.List.dropWhile
splitWhile :: forall a. (a -> Bool) -> [a] -> ([a], [a])
splitWhile = forall a. (a -> Bool) -> [a] -> ([a], [a])
Data.List.span

zip :: forall a b. [a] -> [b] -> [(a, b)]
zip = forall a b. [a] -> [b] -> [(a, b)]
Data.List.zip
zip3 :: forall a b c. [a] -> [b] -> [c] -> [(a, b, c)]
zip3 = forall a b c. [a] -> [b] -> [c] -> [(a, b, c)]
Data.List.zip3
zipWith :: forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith = forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
Data.List.zipWith
zipWith3 :: forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3 = forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
Data.List.zipWith3
unzip :: forall a b. [(a, b)] -> ([a], [b])
unzip = forall a b. [(a, b)] -> ([a], [b])
Data.List.unzip
unzip3 :: forall a b c. [(a, b, c)] -> ([a], [b], [c])
unzip3 = forall a b c. [(a, b, c)] -> ([a], [b], [c])
Data.List.unzip3

unzipWith :: forall a b c. (a -> b) -> (a -> c) -> [a] -> ([b], [c])
unzipWith a -> b
f a -> c
g = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr a -> ([b], [c]) -> ([b], [c])
consfg ([], [])
  where consfg :: a -> ([b], [c]) -> ([b], [c])
consfg a
a ([b]
bs, [c]
cs) = (a -> b
f a
a forall a. a -> [a] -> [a]
: [b]
bs, a -> c
g a
a forall a. a -> [a] -> [a]
: [c]
cs)
  -- could put ~ on tuple

unzipWith3 :: forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> [a] -> ([b], [c], [d])
unzipWith3 a -> b
f a -> c
g a -> d
h = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr a -> ([b], [c], [d]) -> ([b], [c], [d])
consfgh ([], [], [])
  where consfgh :: a -> ([b], [c], [d]) -> ([b], [c], [d])
consfgh a
a ([b]
bs, [c]
cs, [d]
ds) = (a -> b
f a
a forall a. a -> [a] -> [a]
: [b]
bs, a -> c
g a
a forall a. a -> [a] -> [a]
: [c]
cs, a -> d
h a
a forall a. a -> [a] -> [a]
: [d]
ds)
  -- could put ~ on tuple

-- no invariants
structuralInvariant :: forall a. [a] -> Bool
structuralInvariant = forall a b. a -> b -> a
const Bool
True

-- declare the instance

instance S.Sequence [] where
  {lcons :: forall a. a -> [a] -> [a]
lcons = forall a. a -> [a] -> [a]
lcons; rcons :: forall a. a -> [a] -> [a]
rcons = forall a. a -> [a] -> [a]
rcons; null :: forall a. [a] -> Bool
null = forall a. [a] -> Bool
null;
   lview :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm (a, [a])
lview = forall (rm :: * -> *) a. MonadFail rm => [a] -> rm (a, [a])
lview; lhead :: forall a. [a] -> a
lhead = forall a. [a] -> a
lhead; ltail :: forall a. [a] -> [a]
ltail = forall a. [a] -> [a]
ltail;
   lheadM :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm a
lheadM = forall (rm :: * -> *) a. MonadFail rm => [a] -> rm a
lheadM; ltailM :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm [a]
ltailM = forall (rm :: * -> *) a. MonadFail rm => [a] -> rm [a]
ltailM;
   rview :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm (a, [a])
rview = forall (rm :: * -> *) a. MonadFail rm => [a] -> rm (a, [a])
rview; rhead :: forall a. [a] -> a
rhead = forall a. [a] -> a
rhead; rtail :: forall a. [a] -> [a]
rtail = forall a. [a] -> [a]
rtail;
   rheadM :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm a
rheadM = forall (rm :: * -> *) a. MonadFail rm => [a] -> rm a
rheadM; rtailM :: forall (rm :: * -> *) a. MonadFail rm => [a] -> rm [a]
rtailM = forall (rm :: * -> *) a. MonadFail rm => [a] -> rm [a]
rtailM;
   size :: forall a. [a] -> Int
size = forall a. [a] -> Int
size; concat :: forall a. [[a]] -> [a]
concat = forall a. [[a]] -> [a]
concat; reverse :: forall a. [a] -> [a]
reverse = forall a. [a] -> [a]
reverse;
   reverseOnto :: forall a. [a] -> [a] -> [a]
reverseOnto = forall a. [a] -> [a] -> [a]
reverseOnto; fromList :: forall a. [a] -> [a]
fromList = forall a. [a] -> [a]
fromList; toList :: forall a. [a] -> [a]
toList = forall a. [a] -> [a]
toList;
   fold :: forall a b. (a -> b -> b) -> b -> [a] -> b
fold = forall a b. (a -> b -> b) -> b -> [a] -> b
fold; fold' :: forall a b. (a -> b -> b) -> b -> [a] -> b
fold' = forall a b. (a -> b -> b) -> b -> [a] -> b
fold'; fold1 :: forall a. (a -> a -> a) -> [a] -> a
fold1 = forall a. (a -> a -> a) -> [a] -> a
fold1; fold1' :: forall a. (a -> a -> a) -> [a] -> a
fold1' = forall a. (a -> a -> a) -> [a] -> a
fold1';
   foldr :: forall a b. (a -> b -> b) -> b -> [a] -> b
foldr = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr; foldr' :: forall a b. (a -> b -> b) -> b -> [a] -> b
foldr' = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr'; foldl :: forall b a. (b -> a -> b) -> b -> [a] -> b
foldl = forall b a. (b -> a -> b) -> b -> [a] -> b
foldl; foldl' :: forall b a. (b -> a -> b) -> b -> [a] -> b
foldl' = forall b a. (b -> a -> b) -> b -> [a] -> b
foldl';
   foldr1 :: forall a. (a -> a -> a) -> [a] -> a
foldr1 = forall a. (a -> a -> a) -> [a] -> a
foldr1; foldr1' :: forall a. (a -> a -> a) -> [a] -> a
foldr1' = forall a. (a -> a -> a) -> [a] -> a
foldr1'; foldl1 :: forall a. (a -> a -> a) -> [a] -> a
foldl1 = forall a. (a -> a -> a) -> [a] -> a
foldl1; foldl1' :: forall a. (a -> a -> a) -> [a] -> a
foldl1' = forall a. (a -> a -> a) -> [a] -> a
foldl1';
   reducer :: forall a. (a -> a -> a) -> a -> [a] -> a
reducer = forall a. (a -> a -> a) -> a -> [a] -> a
reducer; reducel :: forall a. (a -> a -> a) -> a -> [a] -> a
reducel = forall a. (a -> a -> a) -> a -> [a] -> a
reducel; reduce1 :: forall a. (a -> a -> a) -> [a] -> a
reduce1 = forall a. (a -> a -> a) -> [a] -> a
reduce1;
   reducel' :: forall a. (a -> a -> a) -> a -> [a] -> a
reducel' = forall a. (a -> a -> a) -> a -> [a] -> a
reducel'; reducer' :: forall a. (a -> a -> a) -> a -> [a] -> a
reducer' = forall a. (a -> a -> a) -> a -> [a] -> a
reducer'; reduce1' :: forall a. (a -> a -> a) -> [a] -> a
reduce1' = forall a. (a -> a -> a) -> [a] -> a
reduce1';
   copy :: forall a. Int -> a -> [a]
copy = forall a. Int -> a -> [a]
copy; inBounds :: forall a. Int -> [a] -> Bool
inBounds = forall a. Int -> [a] -> Bool
inBounds; lookup :: forall a. Int -> [a] -> a
lookup = forall a. Int -> [a] -> a
lookup;
   lookupM :: forall (m :: * -> *) a. MonadFail m => Int -> [a] -> m a
lookupM = forall (m :: * -> *) a. MonadFail m => Int -> [a] -> m a
lookupM; lookupWithDefault :: forall a. a -> Int -> [a] -> a
lookupWithDefault = forall a. a -> Int -> [a] -> a
lookupWithDefault;
   update :: forall a. Int -> a -> [a] -> [a]
update = forall a. Int -> a -> [a] -> [a]
update; adjust :: forall a. (a -> a) -> Int -> [a] -> [a]
adjust = forall a. (a -> a) -> Int -> [a] -> [a]
adjust; mapWithIndex :: forall a b. (Int -> a -> b) -> [a] -> [b]
mapWithIndex = forall a b. (Int -> a -> b) -> [a] -> [b]
mapWithIndex; 
   foldrWithIndex :: forall a b. (Int -> a -> b -> b) -> b -> [a] -> b
foldrWithIndex = forall a b. (Int -> a -> b -> b) -> b -> [a] -> b
foldrWithIndex; foldrWithIndex' :: forall a b. (Int -> a -> b -> b) -> b -> [a] -> b
foldrWithIndex' = forall {t} {t} {a}.
(Num t, Enum t) =>
(t -> t -> a -> a) -> a -> [t] -> a
foldrWithIndex';
   foldlWithIndex :: forall b a. (b -> Int -> a -> b) -> b -> [a] -> b
foldlWithIndex = forall b a. (b -> Int -> a -> b) -> b -> [a] -> b
foldlWithIndex; foldlWithIndex' :: forall b a. (b -> Int -> a -> b) -> b -> [a] -> b
foldlWithIndex' = forall b a. (b -> Int -> a -> b) -> b -> [a] -> b
foldlWithIndex';
   take :: forall a. Int -> [a] -> [a]
take = forall a. Int -> [a] -> [a]
take; drop :: forall a. Int -> [a] -> [a]
drop = forall a. Int -> [a] -> [a]
drop; splitAt :: forall a. Int -> [a] -> ([a], [a])
splitAt = forall a. Int -> [a] -> ([a], [a])
splitAt; subseq :: forall a. Int -> Int -> [a] -> [a]
subseq = forall a. Int -> Int -> [a] -> [a]
subseq;
   filter :: forall a. (a -> Bool) -> [a] -> [a]
filter = forall a. (a -> Bool) -> [a] -> [a]
filter; partition :: forall a. (a -> Bool) -> [a] -> ([a], [a])
partition = forall a. (a -> Bool) -> [a] -> ([a], [a])
partition; takeWhile :: forall a. (a -> Bool) -> [a] -> [a]
takeWhile = forall a. (a -> Bool) -> [a] -> [a]
takeWhile;
   dropWhile :: forall a. (a -> Bool) -> [a] -> [a]
dropWhile = forall a. (a -> Bool) -> [a] -> [a]
dropWhile; splitWhile :: forall a. (a -> Bool) -> [a] -> ([a], [a])
splitWhile = forall a. (a -> Bool) -> [a] -> ([a], [a])
splitWhile; zip :: forall a b. [a] -> [b] -> [(a, b)]
zip = forall a b. [a] -> [b] -> [(a, b)]
zip;
   zip3 :: forall a b c. [a] -> [b] -> [c] -> [(a, b, c)]
zip3 = forall a b c. [a] -> [b] -> [c] -> [(a, b, c)]
zip3; zipWith :: forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith = forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith; zipWith3 :: forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3 = forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3; unzip :: forall a b. [(a, b)] -> ([a], [b])
unzip = forall a b. [(a, b)] -> ([a], [b])
unzip;
   unzip3 :: forall a b c. [(a, b, c)] -> ([a], [b], [c])
unzip3 = forall a b c. [(a, b, c)] -> ([a], [b], [c])
unzip3; unzipWith :: forall a b c. (a -> b) -> (a -> c) -> [a] -> ([b], [c])
unzipWith = forall a b c. (a -> b) -> (a -> c) -> [a] -> ([b], [c])
unzipWith; unzipWith3 :: forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> [a] -> ([b], [c], [d])
unzipWith3 = forall a b c d.
(a -> b) -> (a -> c) -> (a -> d) -> [a] -> ([b], [c], [d])
unzipWith3;
   strict :: forall a. [a] -> [a]
strict = forall a. [a] -> [a]
strict; strictWith :: forall a b. (a -> b) -> [a] -> [a]
strictWith = forall a b. (a -> b) -> [a] -> [a]
strictWith;
   structuralInvariant :: forall a. [a] -> Bool
structuralInvariant = forall a. [a] -> Bool
structuralInvariant; instanceName :: forall a. [a] -> String
instanceName [a]
s = String
moduleName}