-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Self optimizing container types -- -- Self optimizing polymorphic container types. -- -- Adaptive containers are polymorphic container types that use class -- associated data types to specialize particular element types to a more -- efficient container representation. The resulting structures tend to -- be both more time and space efficient. -- -- A self-optimizing pair, for example, will unpack the constructors, -- yielding a representation for (Int,Char) requiring 8 bytes, instead of -- 24. -- -- This difference can be visualized, here for the value: -- -- 
--   [ (x,y) | x <- [1..3], y <- [x..3] ]
--
-- -- -- -- Currently supported adaptive types: pairs, lists @package adaptive-containers @version 0.2 -- | Self optimzing pair types. -- -- This library statically adapts the polymorphic container -- representation of tuples to specific, more efficient representations, -- when instantiated with particular monomorphic types. It does this via -- an associated more efficient data type for each pair of elements you -- wish to store in your container. -- -- That is, instead of representing '(Int,Char)' as: -- -- 
--        (,)
--       /   \
--   I# 3#   C# x#
--
-- -- A self-optimizing pair will unpack the constructors, yielding this -- data representation: -- -- 
--   PairIntChar 3# x#
--
-- -- Saving two indirections. The resulting structure should be both more -- time and space efficient than the generic polymorphic container it is -- derived from. For example, adaptive pairs use 8 bytes to store an Int -- and Char pair, while a lazy pair uses 24 bytes. -- -- 
--   > Prelude Size> unsafeSizeof ((42, 'x') :: (Int,Char))
--   > 24
--
-- -- 
--   Prelude Size> unsafeSizeof (pair 42 'x' :: Pair Int Char)
--   > 8
--
-- -- You can inspect the size and layout of your adaptive structures using -- two scripts, one for measuring the size of a closure, described in -- http://ghcmutterings.wordpress.com/2009/02/, and vacuum-cairo, -- for rendering the heap structure explicitly -- http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vacuum-cairo -- -- Types that instantiate the Adapt class will self-adapt this way. -- -- Self adaptive polymorphic containers are able to unpack their -- components, something not possible with, for example, strict -- polymorphic containers. module Data.Adaptive.Tuple -- | Representation-improving polymorphic tuples. class AdaptPair a b where { data family Pair a b; } fst :: (AdaptPair a b) => Pair a b -> a snd :: (AdaptPair a b) => Pair a b -> b curry :: (AdaptPair a b) => (Pair a b -> c) -> a -> b -> c -- | Construct a new pair. pair :: (AdaptPair a b) => a -> b -> Pair a b -- | uncurry converts a curried function to a function on pairs. uncurry :: (AdaptPair a b) => (a -> b -> c) -> (Pair a b -> c) -- | Convert an adaptive pair to a regular polymorphic tuple fromPair :: (AdaptPair a b) => Pair a b -> (a, b) -- | Convert a regular polymorphic tuple to an adaptive pair toPair :: (AdaptPair a b) => (a, b) -> Pair a b instance [overlap ok] AdaptPair Char Char instance [overlap ok] AdaptPair Char Float instance [overlap ok] AdaptPair Char Double instance [overlap ok] AdaptPair Char Word64 instance [overlap ok] AdaptPair Char Word32 instance [overlap ok] AdaptPair Char Word16 instance [overlap ok] AdaptPair Char Word8 instance [overlap ok] AdaptPair Char Word instance [overlap ok] AdaptPair Char Int64 instance [overlap ok] AdaptPair Char Int32 instance [overlap ok] AdaptPair Char Int16 instance [overlap ok] AdaptPair Char Int8 instance [overlap ok] AdaptPair Char Integer instance [overlap ok] AdaptPair Char Int instance [overlap ok] AdaptPair Float Char instance [overlap ok] AdaptPair Float Float instance [overlap ok] AdaptPair Float Double instance [overlap ok] AdaptPair Float Word64 instance [overlap ok] AdaptPair Float Word32 instance [overlap ok] AdaptPair Float Word16 instance [overlap ok] AdaptPair Float Word8 instance [overlap ok] AdaptPair Float Word instance [overlap ok] AdaptPair Float Int64 instance [overlap ok] AdaptPair Float Int32 instance [overlap ok] AdaptPair Float Int16 instance [overlap ok] AdaptPair Float Int8 instance [overlap ok] AdaptPair Float Integer instance [overlap ok] AdaptPair Float Int instance [overlap ok] AdaptPair Double Char instance [overlap ok] AdaptPair Double Float instance [overlap ok] AdaptPair Double Double instance [overlap ok] AdaptPair Double Word64 instance [overlap ok] AdaptPair Double Word32 instance [overlap ok] AdaptPair Double Word16 instance [overlap ok] AdaptPair Double Word8 instance [overlap ok] AdaptPair Double Word instance [overlap ok] AdaptPair Double Int64 instance [overlap ok] AdaptPair Double Int32 instance [overlap ok] AdaptPair Double Int16 instance [overlap ok] AdaptPair Double Int8 instance [overlap ok] AdaptPair Double Integer instance [overlap ok] AdaptPair Double Int instance [overlap ok] AdaptPair Word64 Char instance [overlap ok] AdaptPair Word64 Float instance [overlap ok] AdaptPair Word64 Double instance [overlap ok] AdaptPair Word64 Word64 instance [overlap ok] AdaptPair Word64 Word32 instance [overlap ok] AdaptPair Word64 Word16 instance [overlap ok] AdaptPair Word64 Word8 instance [overlap ok] AdaptPair Word64 Word instance [overlap ok] AdaptPair Word64 Int64 instance [overlap ok] AdaptPair Word64 Int32 instance [overlap ok] AdaptPair Word64 Int16 instance [overlap ok] AdaptPair Word64 Int8 instance [overlap ok] AdaptPair Word64 Integer instance [overlap ok] AdaptPair Word64 Int instance [overlap ok] AdaptPair Word32 Char instance [overlap ok] AdaptPair Word32 Float instance [overlap ok] AdaptPair Word32 Double instance [overlap ok] AdaptPair Word32 Word64 instance [overlap ok] AdaptPair Word32 Word32 instance [overlap ok] AdaptPair Word32 Word16 instance [overlap ok] AdaptPair Word32 Word8 instance [overlap ok] AdaptPair Word32 Word instance [overlap ok] AdaptPair Word32 Int64 instance [overlap ok] AdaptPair Word32 Int32 instance [overlap ok] AdaptPair Word32 Int16 instance [overlap ok] AdaptPair Word32 Int8 instance [overlap ok] AdaptPair Word32 Integer instance [overlap ok] AdaptPair Word32 Int instance [overlap ok] AdaptPair Word16 Char instance [overlap ok] AdaptPair Word16 Float instance [overlap ok] AdaptPair Word16 Double instance [overlap ok] AdaptPair Word16 Word64 instance [overlap ok] AdaptPair Word16 Word32 instance [overlap ok] AdaptPair Word16 Word16 instance [overlap ok] AdaptPair Word16 Word8 instance [overlap ok] AdaptPair Word16 Word instance [overlap ok] AdaptPair Word16 Int64 instance [overlap ok] AdaptPair Word16 Int32 instance [overlap ok] AdaptPair Word16 Int16 instance [overlap ok] AdaptPair Word16 Int8 instance [overlap ok] AdaptPair Word16 Integer instance [overlap ok] AdaptPair Word16 Int instance [overlap ok] AdaptPair Word8 Char instance [overlap ok] AdaptPair Word8 Float instance [overlap ok] AdaptPair Word8 Double instance [overlap ok] AdaptPair Word8 Word64 instance [overlap ok] AdaptPair Word8 Word32 instance [overlap ok] AdaptPair Word8 Word16 instance [overlap ok] AdaptPair Word8 Word8 instance [overlap ok] AdaptPair Word8 Word instance [overlap ok] AdaptPair Word8 Int64 instance [overlap ok] AdaptPair Word8 Int32 instance [overlap ok] AdaptPair Word8 Int16 instance [overlap ok] AdaptPair Word8 Int8 instance [overlap ok] AdaptPair Word8 Integer instance [overlap ok] AdaptPair Word8 Int instance [overlap ok] AdaptPair Word Char instance [overlap ok] AdaptPair Word Float instance [overlap ok] AdaptPair Word Double instance [overlap ok] AdaptPair Word Word64 instance [overlap ok] AdaptPair Word Word32 instance [overlap ok] AdaptPair Word Word16 instance [overlap ok] AdaptPair Word Word8 instance [overlap ok] AdaptPair Word Word instance [overlap ok] AdaptPair Word Int64 instance [overlap ok] AdaptPair Word Int32 instance [overlap ok] AdaptPair Word Int16 instance [overlap ok] AdaptPair Word Int8 instance [overlap ok] AdaptPair Word Integer instance [overlap ok] AdaptPair Word Int instance [overlap ok] AdaptPair Int64 Char instance [overlap ok] AdaptPair Int64 Float instance [overlap ok] AdaptPair Int64 Double instance [overlap ok] AdaptPair Int64 Word64 instance [overlap ok] AdaptPair Int64 Word32 instance [overlap ok] AdaptPair Int64 Word16 instance [overlap ok] AdaptPair Int64 Word8 instance [overlap ok] AdaptPair Int64 Word instance [overlap ok] AdaptPair Int64 Int64 instance [overlap ok] AdaptPair Int64 Int32 instance [overlap ok] AdaptPair Int64 Int16 instance [overlap ok] AdaptPair Int64 Int8 instance [overlap ok] AdaptPair Int64 Integer instance [overlap ok] AdaptPair Int64 Int instance [overlap ok] AdaptPair Int32 Char instance [overlap ok] AdaptPair Int32 Float instance [overlap ok] AdaptPair Int32 Double instance [overlap ok] AdaptPair Int32 Word64 instance [overlap ok] AdaptPair Int32 Word32 instance [overlap ok] AdaptPair Int32 Word16 instance [overlap ok] AdaptPair Int32 Word8 instance [overlap ok] AdaptPair Int32 Word instance [overlap ok] AdaptPair Int32 Int64 instance [overlap ok] AdaptPair Int32 Int32 instance [overlap ok] AdaptPair Int32 Int16 instance [overlap ok] AdaptPair Int32 Int8 instance [overlap ok] AdaptPair Int32 Integer instance [overlap ok] AdaptPair Int32 Int instance [overlap ok] AdaptPair Int16 Char instance [overlap ok] AdaptPair Int16 Float instance [overlap ok] AdaptPair Int16 Double instance [overlap ok] AdaptPair Int16 Word64 instance [overlap ok] AdaptPair Int16 Word32 instance [overlap ok] AdaptPair Int16 Word16 instance [overlap ok] AdaptPair Int16 Word8 instance [overlap ok] AdaptPair Int16 Word instance [overlap ok] AdaptPair Int16 Int64 instance [overlap ok] AdaptPair Int16 Int32 instance [overlap ok] AdaptPair Int16 Int16 instance [overlap ok] AdaptPair Int16 Int8 instance [overlap ok] AdaptPair Int16 Integer instance [overlap ok] AdaptPair Int16 Int instance [overlap ok] AdaptPair Int8 Char instance [overlap ok] AdaptPair Int8 Float instance [overlap ok] AdaptPair Int8 Double instance [overlap ok] AdaptPair Int8 Word64 instance [overlap ok] AdaptPair Int8 Word32 instance [overlap ok] AdaptPair Int8 Word16 instance [overlap ok] AdaptPair Int8 Word8 instance [overlap ok] AdaptPair Int8 Word instance [overlap ok] AdaptPair Int8 Int64 instance [overlap ok] AdaptPair Int8 Int32 instance [overlap ok] AdaptPair Int8 Int16 instance [overlap ok] AdaptPair Int8 Int8 instance [overlap ok] AdaptPair Int8 Integer instance [overlap ok] AdaptPair Int8 Int instance [overlap ok] AdaptPair Integer Char instance [overlap ok] AdaptPair Integer Float instance [overlap ok] AdaptPair Integer Double instance [overlap ok] AdaptPair Integer Word64 instance [overlap ok] AdaptPair Integer Word32 instance [overlap ok] AdaptPair Integer Word16 instance [overlap ok] AdaptPair Integer Word8 instance [overlap ok] AdaptPair Integer Word instance [overlap ok] AdaptPair Integer Int64 instance [overlap ok] AdaptPair Integer Int32 instance [overlap ok] AdaptPair Integer Int16 instance [overlap ok] AdaptPair Integer Int8 instance [overlap ok] AdaptPair Integer Integer instance [overlap ok] AdaptPair Integer Int instance [overlap ok] AdaptPair Int Char instance [overlap ok] AdaptPair Int Float instance [overlap ok] AdaptPair Int Double instance [overlap ok] AdaptPair Int Word64 instance [overlap ok] AdaptPair Int Word32 instance [overlap ok] AdaptPair Int Word16 instance [overlap ok] AdaptPair Int Word8 instance [overlap ok] AdaptPair Int Word instance [overlap ok] AdaptPair Int Int64 instance [overlap ok] AdaptPair Int Int32 instance [overlap ok] AdaptPair Int Int16 instance [overlap ok] AdaptPair Int Int8 instance [overlap ok] AdaptPair Int Integer instance [overlap ok] AdaptPair Int Int instance [overlap ok] AdaptPair Bool Bool instance [overlap ok] AdaptPair () () instance [overlap ok] AdaptPair a b instance [overlap ok] (Show a, Show b, AdaptPair a b) => Show (Pair a b) instance [overlap ok] (Ord a, Ord b, AdaptPair a b) => Ord (Pair a b) instance [overlap ok] (Eq a, Eq b, AdaptPair a b) => Eq (Pair a b) instance [overlap ok] (Bounded a, Bounded b, AdaptPair a b) => Bounded (Pair a b) -- | Self adapting polymorphic lists. -- -- This library statically specializes the polymorphic container -- representation of lists to specific, more efficient representations, -- when instantiated with particular monomorphic types. It does this via -- an associated more efficient data type for each pair of elements you -- wish to store in your container. -- -- The resulting list structures use less space, and functions on them -- tend to be faster, than regular lists. -- -- Instead of representing '[1..5] :: [Int]' as: -- -- 
--        (:) 
--       /   \
--      /     \
--   I# 1#    (:)
--           /   \
--          /     \
--       I# 2#    (:)
--               /   \
--              /     \
--           I# 3#    []
--
-- -- The compiler will select an associated data type that packs better, -- via the class instances, resulting in: -- -- 
--   ConsInt 1#
--    |
--   ConsInt 2#
--    |
--   ConsInt 3#
--    |
--    []
--
-- -- The user however, still sees a polymorphic list type. -- -- This list type currently doesn't fuse. module Data.Adaptive.List -- | Representation-improving polymorphic lists. class AdaptList a where { data family List a; } empty :: (AdaptList a) => List a cons :: (AdaptList a) => a -> List a -> List a null :: (AdaptList a) => List a -> Bool head :: (AdaptList a) => List a -> a tail :: (AdaptList a) => List a -> List a -- | O(n), convert an adaptive list to a regular list toList :: (AdaptList a) => List a -> [a] -- | O(n), convert an adaptive list to a regular list fromList :: (AdaptList a) => [a] -> List a -- | O(n), construct a list by enumerating a range enumFromToList :: (AdaptList a, Ord a, Enum a) => a -> a -> List a -- | O(1), uncons, take apart a list into the head and tail. uncons :: (AdaptList a) => List a -> Maybe (a, List a) -- | O(n), 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. (++) :: (AdaptList a) => List a -> List a -> List a -- | O(n), Extract the last element of a list, which must be finite -- and non-empty. last :: (AdaptList a) => List a -> a -- | O(n). Return all the elements of a list except the last one. -- The list must be finite and non-empty. init :: (AdaptList a) => List a -> List a -- | O(n). 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 :: (AdaptList a) => List a -> Int -- | O(n). 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)
--
map :: (AdaptList a, AdaptList b) => (a -> b) -> List a -> List b -- | O(n). reverse xs returns the elements of -- xs in reverse order. xs must be finite. Will fuse as -- a consumer only. reverse :: (AdaptList a) => List a -> List a -- | O(n). 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 :: (AdaptList a) => a -> List a -> List a -- | O(n). 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 :: (AdaptList (List a), AdaptList a) => List a -> List (List a) -> List a -- | O(n). 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. The accumulator is whnf strict. foldl :: (AdaptList b) => (a -> b -> a) -> a -> List b -> a -- | O(n). foldl1 is a variant of foldl that has no -- starting value argument, and thus must be applied to non-empty lists. foldl1 :: (AdaptList a) => (a -> a -> a) -> List a -> a -- | O(n). 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)...)
--
foldr :: (AdaptList a) => (a -> b -> b) -> b -> List a -> b -- | O(n). foldr1 is a variant of foldr that has no -- starting value argument, and thus must be applied to non-empty lists. foldr1 :: (AdaptList a) => (a -> a -> a) -> List a -> a -- | O(n). Concatenate a list of lists. concat :: [[a]] -> [a] concat :: (AdaptList (List a), AdaptList a) => List (List a) -> List a -- | O(n), fusion. Map a function over a list and concatenate -- the results. concatMap :: (AdaptList a1, AdaptList a) => (a -> List a1) -> List a -> List a1 -- | O(n). 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 :: List Bool -> Bool -- | O(n). 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 :: List Bool -> Bool -- | O(n). Applied to a predicate and a list, any determines -- if any element of the list satisfies the predicate. any :: (AdaptList a) => (a -> Bool) -> List a -> Bool -- | Applied to a predicate and a list, all determines if all -- elements of the list satisfy the predicate. all :: (AdaptList a) => (a -> Bool) -> List a -> Bool -- | O(n), fusion. The sum function computes the sum -- of a finite list of numbers. sum :: (AdaptList a, Num a) => List a -> a -- | O(n),fusion. The product function computes the -- product of a finite list of numbers. product :: (AdaptList a, Num a) => List a -> a -- | O(n). 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 :: (AdaptList a, Ord a) => List a -> a -- | O(n). 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 :: (AdaptList a, Ord a) => List a -> a -- | O(n). 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 :: (AdaptList b, AdaptList a) => (a -> b -> a) -> a -> List b -> List a -- | O(n). scanl1 is a variant of scanl that has no -- starting value argument: -- -- 
--   scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
--
scanl1 :: (AdaptList a) => (a -> a -> a) -> List a -> List a -- | O(n). scanr is the right-to-left dual of scanl. -- Properties: -- -- 
--   head (scanr f z xs) == foldr f z xs
--
scanr :: (AdaptList a, AdaptList b) => (a -> b -> b) -> b -> List a -> List b -- | scanr1 is a variant of scanr that has no starting value -- argument. scanr1 :: (AdaptList a) => (a -> a -> a) -> List a -> List a -- | O(n), iterate f x returns an infinite list of -- repeated applications of f to x: -- -- 
--   iterate f x == [x, f x, f (f x), ...]
--
iterate :: (AdaptList a) => (a -> a) -> a -> List a -- | O(n). repeat x is an infinite list, with -- x the value of every element. repeat :: (AdaptList a) => a -> List a -- | O(n). 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 :: (AdaptList a) => Int -> a -> List a -- | 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 :: (AdaptList a) => List a -> List a -- | 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]
--
-- -- TODO: AdaptPair state. unfoldr :: (AdaptList a) => (b -> Maybe (a, b)) -> b -> List a -- | O(n). 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 :: (AdaptList a) => Int -> List a -> List a -- | O(n). 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 :: (AdaptList a) => Int -> List a -> List a -- | 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 :: (AdaptList a) => Int -> List a -> (List a, List a) -- | O(n). elem is the list membership predicate, usually -- written in infix form, e.g., x elem xs. elem :: (AdaptList a, Eq a) => a -> List a -> Bool -- | O(n). notElem is the negation of elem. notElem :: (AdaptList a, Eq a) => a -> List a -> Bool -- | O(n). 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 :: (AdaptList a) => (a -> Bool) -> List a -> List a -- | 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 :: (AdaptPair a b, AdaptList a, AdaptList b, AdaptList (Pair a b)) => List a -> List b -> List (Pair a b) errorEmptyList :: String -> a moduleError :: String -> String -> a bottom :: a instance [overlap ok] AdaptList Char instance [overlap ok] AdaptList Float instance [overlap ok] AdaptList Double instance [overlap ok] AdaptList Word64 instance [overlap ok] AdaptList Word32 instance [overlap ok] AdaptList Word16 instance [overlap ok] AdaptList Word8 instance [overlap ok] AdaptList Word instance [overlap ok] AdaptList Int64 instance [overlap ok] AdaptList Int32 instance [overlap ok] AdaptList Int16 instance [overlap ok] AdaptList Int8 instance [overlap ok] AdaptList Integer instance [overlap ok] AdaptList Int instance [overlap ok] AdaptList Bool instance [overlap ok] AdaptList (Pair Int Int) instance [overlap ok] (AdaptList a, Show a) => Show (List a) instance [overlap ok] (AdaptList a, Ord a) => Ord (List a) instance [overlap ok] (AdaptList a, Eq a) => Eq (List a)