{-# LANGUAGE TypeFamilies         #-}
{-# LANGUAGE BangPatterns         #-}
{-# LANGUAGE FlexibleContexts     #-}
{-# LANGUAGE FlexibleInstances    #-}

-- |
-- Module      : Data.Adaptive.List
-- Copyright   : (c) Duncan Coutts 2007
--               (c) Don Stewart   2007 .. 2009
-- License     : BSD-style
-- Maintainer  : dons@galois.com
-- Stability   : experimental
--
-- 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 where

import Data.Adaptive.Tuple

import qualified Prelude
import Prelude (Eq(..),Ord(..),Ordering(..), (.)
               ,Int,Char,Float,Double,Integer,Bool(..),otherwise,(-))
import Data.Int
import Data.Word
import Data.String

-- * The adaptive list class-associated type
--
-- | Representation-improving polymorphic lists.
--
class AdaptList a where

    data List a

    -- | The empty list
    empty   :: List a

    -- | Prepend a value onto a list
    cons    :: a -> List a -> List a

    -- | Is the list empty?
    null    :: List a -> Bool

    -- | The first element of the list
    head    :: List a -> a

    -- | The tail of the list
    tail    :: List a -> List a

------------------------------------------------------------------------
-- * Basic Interface

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

-- | /O(n)/, convert an adaptive list to a regular list
toList :: AdaptList a => List a -> [a]
toList xs
    | null xs   = []
    | otherwise = head xs : toList (tail xs)

-- | /O(n)/, convert an adaptive list to a regular list
fromList :: AdaptList a => [a] -> List a
fromList []     = empty
fromList (x:xs) = x `cons` fromList xs

-- | /O(n)/, construct a list by enumerating a range
enumFromToList :: (AdaptList a, Ord a, Prelude.Enum a) => a -> a ->List a
enumFromToList x0 y
            | x0 > y    = empty
            | otherwise = go x0
               where
                 go x = x `cons` if x == y then empty else go (Prelude.succ x)
{-# INLINE enumFromToList #-}

-- | /O(1)/, uncons, take apart a list into the head and tail.
--
uncons :: AdaptList a => List a -> Prelude.Maybe (a, List a)
uncons xs | null xs   = Prelude.Nothing
          | otherwise = Prelude.Just (head xs, tail xs)

-- | /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
(++) xs ys
    | null xs   = ys
    | otherwise = head xs `cons` tail xs ++ ys

-- | /O(n)/, Extract the last element of a list, which must be finite
-- and non-empty.
last :: AdaptList a => List a -> a
last xs
    | null xs   = errorEmptyList "last"
    | otherwise = go (head xs) (tail xs)
  where
    go y z
        | null z    = y
        | otherwise = go (head z) (tail z)
{-# INLINE last #-}

-- | /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
init xs
    | null xs   = errorEmptyList "init"
    | otherwise = go (head xs) (tail xs)
  where
    go y z
        | null z    = empty
        | otherwise = y `cons` go (head z) (tail z)
{-# INLINE init #-}

-- | /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
length xs0 = go xs0 0
  where
    go :: AdaptList a => List a -> Int -> Int
    go xs !a
        | null xs   = a
        | otherwise = go (tail xs) (a Prelude.+ 1)
{-# INLINE length #-}

-- ---------------------------------------------------------------------
-- * List transformations

-- | /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
map f as = go as
  where
    go xs
        | null xs   = empty
        | otherwise = f (head xs) `cons` go (tail xs)
{-# INLINE map #-}

-- | /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
reverse = foldl (Prelude.flip cons) empty
{-# INLINE reverse #-}

-- | /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
intersperse sep zs
    | null zs   = empty
    | otherwise = head zs `cons` go (tail zs)
  where
    go xs
        | null xs   = empty
        | otherwise = sep `cons` (head xs `cons` go (tail xs))
{-# INLINE intersperse #-}

-- | /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
intercalate sep xss = go (intersperse sep xss)
  where
    go ys
        | null ys   = empty
        | otherwise = head ys ++ go (tail ys)
{-# INLINE intercalate #-}

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

-- | /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
foldl f z0 xs0 = go z0 xs0
  where
    go !z xs
        | null xs   = z
        | otherwise = go (f z (head xs)) (tail xs)
{-# INLINE foldl #-}

-- | /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
foldl1 f zs
    | null zs   = errorEmptyList "foldl1"
    | otherwise = go (head zs) (tail zs)
  where
    go !z xs
        | null xs     = z
        | otherwise   = go (f z (head xs)) (tail xs)
{-# INLINE foldl1 #-}

-- | /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
foldr k z xs = go xs
  where
    go ys
        | null xs   = z
        | otherwise = head ys `k` go (tail ys)
{-# INLINE foldr #-}

-- | /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
foldr1 k xs
    | null xs   = errorEmptyList "foldr1"
    | otherwise = go (head xs) (tail xs)
  where
    go z ys
        | null ys   = z
        | otherwise = z `k` go (head ys) (tail ys)
{-# INLINE foldr1 #-}

-- ---------------------------------------------------------------------
-- * Special folds

-- | /O(n)/. Concatenate a list of lists.
-- concat :: [[a]] -> [a]
concat :: (AdaptList (List a), AdaptList a)
       => List (List a) -> List a
concat xss0 = to xss0
  where
    go xs xss
        | null xs   = to xss
        | otherwise = head xs `cons` go (tail xs) xss
    to xs
        | null xs   = empty
        | otherwise = go (head xs) (tail xs)
{-# INLINE concat #-}

-- | /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
concatMap f = foldr (\x y -> f x ++ y) empty
{-# INLINE concatMap #-}

-- | /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
and xs
    | null xs               = True
    | Prelude.not (head xs) = False
    | otherwise             = and (tail xs)
{-# INLINE and #-}

-- | /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
or xs
    | null xs   = False
    | head xs   = True
    | otherwise = or (tail xs)
{-# INLINE or #-}

-- | /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
any p xs0 = go xs0
  where
    go xs
        | null xs   = False
        | otherwise = case p (head xs) of
                        True -> True
                        _    -> go (tail xs)
{-# INLINE any #-}

-- | 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
all p xs0 = go xs0
  where
    go xs
        | null xs   = True
        | otherwise = case p (head xs) of
                        True -> go (tail xs)
                        _    -> False
{-# INLINE all #-}

-- | /O(n)/, /fusion/. The 'sum' function computes the sum of a finite list of numbers.
sum :: (AdaptList a, Prelude.Num a) => List a -> a
sum l = go l 0
  where
    go xs !a
        | null xs   = a
        | otherwise = go (tail xs) (a Prelude.+ head xs)
{-# INLINE sum #-}

-- | /O(n)/,/fusion/. The 'product' function computes the product of a finite list of numbers.
product :: (AdaptList a, Prelude.Num a) => List a -> a
product l = go l 1
  where
    go xs !a
        | null xs   = a
        | otherwise = go (tail xs) (a Prelude.* head xs)
{-# INLINE product #-}

-- | /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, Prelude.Ord a) => List a -> a
maximum xs
    | null xs   = errorEmptyList "maximum"
    | otherwise = foldl1 Prelude.max xs
{-# INLINE maximum #-}

-- | /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, Prelude.Ord a) => List a -> a
minimum xs
    | null xs   = errorEmptyList "minimum"
    | otherwise = foldl1 Prelude.min xs
{-# INLINE minimum #-}

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

-- | /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
scanl f q ls = q `cons` if null ls
                          then empty
                          else scanl f (f q (head ls)) (tail ls)
{-# INLINE scanl #-}

-- | /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
scanl1 f xs
    | null xs   = empty
    | otherwise = scanl f (head xs) (tail xs)
{-# INLINE scanl1 #-}

-- | /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
scanr f q0 xs
    | null xs    = cons q0 empty
    | otherwise  = f (head xs) (head qs) `cons` qs
                    where qs = scanr f q0 (tail xs)
{-# INLINE scanr #-}

-- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
scanr1 :: AdaptList a => (a -> a -> a) -> List a -> List a
scanr1 f xs
    | null xs        = empty
    | null (tail xs) = xs
    | otherwise      = f (head xs) (head qs) `cons` qs
                  where qs = scanr1 f (tail xs)

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

-- | /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
iterate f x = go x
    where go z = z `cons` go (f z)
{-# INLINE iterate #-}

-- | /O(n)/. 'repeat' @x@ is an infinite list, with @x@ the value of every element.
repeat :: AdaptList a => a -> List a
repeat x = xs where xs = x `cons` xs
{-# INLINE repeat #-}

-- | /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
replicate n0 _ | n0 <= 0 = empty
replicate n0 x           = go n0
  where
    go 0 = empty
    go n = x `cons` go (n-1)
{-# INLINE replicate #-}

-- | /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
cycle xs0
    | null xs0  = errorEmptyList "cycle"
    | otherwise = go xs0
  where
    go xs
        | null xs   = go xs0
        | otherwise = head xs `cons` go (tail xs)
{-# INLINE cycle #-}

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

-- | 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 -> Prelude.Maybe (a, b)) -> b -> List a
unfoldr f b0 = unfold b0
  where
    unfold b = case f b of
      Prelude.Just (a,b') -> a `cons` unfold b'
      Prelude.Nothing     -> empty
{-# INLINE unfoldr #-}

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

-- | /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
take i _ | i <= 0 = empty
take i ls = go i ls
  where
    go :: AdaptList a => Int -> List a -> List a
    go 0 _  = empty
    go n xs
        | null xs   = empty
        | otherwise = (head xs) `cons` go (n-1) (tail xs)
{-# INLINE take #-}

-- | /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
drop n ls
  | n Prelude.< 0 = ls
  | otherwise     = go n ls
  where
    go :: AdaptList a => Int -> List a -> List a
    go 0 xs      = xs
    go m xs
        | null xs   = empty
        | otherwise = go (m-1) (tail xs)
{-# INLINE drop #-}

-- | '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)
splitAt n ls
  | n Prelude.< 0  = (empty, ls)
  | otherwise      = go n ls
  where
    go :: AdaptList a => Int -> List a -> (List a, List a)
    go 0 xs     = (empty, xs)
    go m xs
        | null xs   = (empty, empty)
        | otherwise = (head xs `cons` xs', xs'')
      where
        (xs', xs'') = go (m-1) (tail xs)
{-# INLINE splitAt #-}

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

-- | /O(n)/. 'elem' is the list membership predicate, usually written
-- in infix form, e.g., @x `elem` xs@.
--
elem :: (AdaptList a, Prelude.Eq a) => a -> List a -> Bool
elem x ys
    | null ys              = False
    | x Prelude.== head ys = True
    | otherwise            = elem x (tail ys)
{-# INLINE elem #-}

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

-- | /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
filter p xs0
    | null xs0  = empty
    | otherwise = go xs0
  where
    go xs
        | null xs     = empty
        | p x         = x `cons` go ys
        | otherwise   =          go ys
            where x  = head xs
                  ys = tail xs
{-# INLINE filter #-}

------------------------------------------------------------------------
-- * 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 :: (AdaptPair a b, AdaptList a , AdaptList b, AdaptList (Pair a b))
    => List a -> List b -> List (Pair a b)
zip as bs
    | null as   = empty
    | null bs   = empty
    | otherwise = pair (head as) (head bs) `cons` zip (tail as) (tail bs)
{-# INLINE zip #-}

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

{-


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

{-
-- ---------------------------------------------------------------------
-- ** 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
-}

-- | /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

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

-- | /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 #-}

------------------------------------------------------------------------
-- ** 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 #-}

-- | /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 :: Prelude.String -> a
errorEmptyList fun = moduleError fun "empty list"
{-# NOINLINE errorEmptyList #-}

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

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

------------------------------------------------------------------------
-- Instances

instance (AdaptList a, Prelude.Eq a) => Prelude.Eq (List a) where
    xs == ys
        | null xs Prelude.&& null ys = True
        | null xs                    = False
        | null ys                    = False
        | otherwise                  = (head xs Prelude.== head ys)
                            Prelude.&& (tail xs Prelude.== tail ys)

instance (AdaptList a, Prelude.Ord a) => Prelude.Ord (List a) where
    compare xs ys
        | null xs Prelude.&& null ys = EQ
        | null xs                    = LT
        | null ys                    = GT
        | otherwise                  = case compare (head xs) (head ys) of
                                            EQ    -> compare (tail xs) (tail ys)
                                            other -> other

instance (AdaptList a, Prelude.Show a) => Prelude.Show (List a) where
    showsPrec _         = Prelude.showList . toList

instance IsString (List Char) where fromString = fromList

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

-- | We can unpack bools!
instance AdaptList Bool where
    data List Bool = EmptyBool | ConsBool {-# UNPACK #-}!Int (List Bool)

    empty                = EmptyBool
    cons x xs            = ConsBool (Prelude.fromEnum x) xs -- pack
    null EmptyBool       = True
    null _               = False

    head EmptyBool       = errorEmptyList "head"
    head (ConsBool x _)  = Prelude.toEnum x

    tail EmptyBool       = errorEmptyList "tail"
    tail (ConsBool _ xs) = xs

------------------------------------------------------------------------
-- Generated by scripts/derive-list.hs

instance AdaptList Int where
    data List Int = EmptyInt | ConsInt {-# UNPACK #-}!Int (List Int)
    empty = EmptyInt
    cons = ConsInt
    null EmptyInt = True
    null _ = False
    head EmptyInt = errorEmptyList "head"
    head (ConsInt x _) = x
    tail EmptyInt = errorEmptyList "tail"
    tail (ConsInt _ x) = x

instance AdaptList Integer where
    data List Integer = EmptyInteger | ConsInteger {-# UNPACK #-}!Integer (List Integer)
    empty = EmptyInteger
    cons = ConsInteger
    null EmptyInteger = True
    null _ = False
    head EmptyInteger = errorEmptyList "head"
    head (ConsInteger x _) = x
    tail EmptyInteger = errorEmptyList "tail"
    tail (ConsInteger _ x) = x

instance AdaptList Int8 where
    data List Int8 = EmptyInt8 | ConsInt8 {-# UNPACK #-}!Int8 (List Int8)
    empty = EmptyInt8
    cons = ConsInt8
    null EmptyInt8 = True
    null _ = False
    head EmptyInt8 = errorEmptyList "head"
    head (ConsInt8 x _) = x
    tail EmptyInt8 = errorEmptyList "tail"
    tail (ConsInt8 _ x) = x

instance AdaptList Int16 where
    data List Int16 = EmptyInt16 | ConsInt16 {-# UNPACK #-}!Int16 (List Int16)
    empty = EmptyInt16
    cons = ConsInt16
    null EmptyInt16 = True
    null _ = False
    head EmptyInt16 = errorEmptyList "head"
    head (ConsInt16 x _) = x
    tail EmptyInt16 = errorEmptyList "tail"
    tail (ConsInt16 _ x) = x

instance AdaptList Int32 where
    data List Int32 = EmptyInt32 | ConsInt32 {-# UNPACK #-}!Int32 (List Int32)
    empty = EmptyInt32
    cons = ConsInt32
    null EmptyInt32 = True
    null _ = False
    head EmptyInt32 = errorEmptyList "head"
    head (ConsInt32 x _) = x
    tail EmptyInt32 = errorEmptyList "tail"
    tail (ConsInt32 _ x) = x

instance AdaptList Int64 where
    data List Int64 = EmptyInt64 | ConsInt64 {-# UNPACK #-}!Int64 (List Int64)
    empty = EmptyInt64
    cons = ConsInt64
    null EmptyInt64 = True
    null _ = False
    head EmptyInt64 = errorEmptyList "head"
    head (ConsInt64 x _) = x
    tail EmptyInt64 = errorEmptyList "tail"
    tail (ConsInt64 _ x) = x

instance AdaptList Word where
    data List Word = EmptyWord | ConsWord {-# UNPACK #-}!Word (List Word)
    empty = EmptyWord
    cons = ConsWord
    null EmptyWord = True
    null _ = False
    head EmptyWord = errorEmptyList "head"
    head (ConsWord x _) = x
    tail EmptyWord = errorEmptyList "tail"
    tail (ConsWord _ x) = x

instance AdaptList Word8 where
    data List Word8 = EmptyWord8 | ConsWord8 {-# UNPACK #-}!Word8 (List Word8)
    empty = EmptyWord8
    cons = ConsWord8
    null EmptyWord8 = True
    null _ = False
    head EmptyWord8 = errorEmptyList "head"
    head (ConsWord8 x _) = x
    tail EmptyWord8 = errorEmptyList "tail"
    tail (ConsWord8 _ x) = x

instance AdaptList Word16 where
    data List Word16 = EmptyWord16 | ConsWord16 {-# UNPACK #-}!Word16 (List Word16)
    empty = EmptyWord16
    cons = ConsWord16
    null EmptyWord16 = True
    null _ = False
    head EmptyWord16 = errorEmptyList "head"
    head (ConsWord16 x _) = x
    tail EmptyWord16 = errorEmptyList "tail"
    tail (ConsWord16 _ x) = x

instance AdaptList Word32 where
    data List Word32 = EmptyWord32 | ConsWord32 {-# UNPACK #-}!Word32 (List Word32)
    empty = EmptyWord32
    cons = ConsWord32
    null EmptyWord32 = True
    null _ = False
    head EmptyWord32 = errorEmptyList "head"
    head (ConsWord32 x _) = x
    tail EmptyWord32 = errorEmptyList "tail"
    tail (ConsWord32 _ x) = x

instance AdaptList Word64 where
    data List Word64 = EmptyWord64 | ConsWord64 {-# UNPACK #-}!Word64 (List Word64)
    empty = EmptyWord64
    cons = ConsWord64
    null EmptyWord64 = True
    null _ = False
    head EmptyWord64 = errorEmptyList "head"
    head (ConsWord64 x _) = x
    tail EmptyWord64 = errorEmptyList "tail"
    tail (ConsWord64 _ x) = x

instance AdaptList Double where
    data List Double = EmptyDouble | ConsDouble {-# UNPACK #-}!Double (List Double)
    empty = EmptyDouble
    cons = ConsDouble
    null EmptyDouble = True
    null _ = False
    head EmptyDouble = errorEmptyList "head"
    head (ConsDouble x _) = x
    tail EmptyDouble = errorEmptyList "tail"
    tail (ConsDouble _ x) = x

instance AdaptList Float where
    data List Float = EmptyFloat | ConsFloat {-# UNPACK #-}!Float (List Float)
    empty = EmptyFloat
    cons = ConsFloat
    null EmptyFloat = True
    null _ = False
    head EmptyFloat = errorEmptyList "head"
    head (ConsFloat x _) = x
    tail EmptyFloat = errorEmptyList "tail"
    tail (ConsFloat _ x) = x

instance AdaptList Char where
    data List Char = EmptyChar | ConsChar {-# UNPACK #-}!Char (List Char)
    empty = EmptyChar
    cons = ConsChar
    null EmptyChar = True
    null _ = False
    head EmptyChar = errorEmptyList "head"
    head (ConsChar x _) = x
    tail EmptyChar = errorEmptyList "tail"
    tail (ConsChar _ x) = x


------------------------------------------------------------------------
--
-- Generic adaptive pair: won't flatten!
--
-- Unsound
-- Data/Adaptive/List.hs:1687:9:
--     Conflicting family instance declarations:
--       data instance List (Pair a b)
--         -- Defined at Data/Adaptive/List.hs:1687:9-12
--       data instance List (Pair Int Int)
--         -- Defined at Data/Adaptive/List.hs:1699:9-12
--

{-
    -- looks illegal?
instance AdaptPair a b => AdaptList (Pair a b) where
    data List (Pair a b) = EmptyPair | ConsPair {-# UNPACK #-}!(Pair a b) (List (Pair a b))
    empty                = EmptyPair
    cons x xs            = ConsPair x xs
    null EmptyPair       = True
    null _               = False
    head EmptyPair       = errorEmptyList "head"
    head (ConsPair x _)  = x
    tail EmptyPair       = errorEmptyList "tail"
    tail (ConsPair _ xs) = xs
-}


-- Monomorphic, but we have to flatten ourselves. GHC is doing something wrong.
--
--      | ConsPairIntInt {-# UNPACK #-}!(Pair Int Int) (List (Pair Int Int))
--                                      -- this isn't unpacking 
--
-- I think this should be ok, but it doesn't unpack.
--

{-
instance AdaptList (Pair Int Int) where
    data List (Pair Int Int)
        = EmptyPairIntInt


        | ConsPairIntInt {-# UNPACK #-}!Int {-# UNPACK #-}!Int (List (Pair Int Int))

    empty                = EmptyPairIntInt
    cons x xs            = ConsPairIntInt (fst x) (snd x) xs

    null EmptyPairIntInt = True
    null _               = False

    head EmptyPairIntInt         = errorEmptyList "head"
    head (ConsPairIntInt x y _)  = pair x y
    tail EmptyPairIntInt         = errorEmptyList "tail"
    tail (ConsPairIntInt _ _ xs) = xs
-}

------------------------------------------------------------------------
-- auto instances for lists of adaptive pairs 
--

instance AdaptList (Pair Int Int) where
    data List (Pair Int Int)
        = EmptyPairIntInt
        | ConsPairIntInt {-# UNPACK #-}!Int {-# UNPACK #-}!Int (List (Pair Int Int))
    empty = EmptyPairIntInt
    cons x z = ConsPairIntInt (fst x) (snd x) z
    null EmptyPairIntInt = True
    null _ = False
    head EmptyPairIntInt = errorEmptyList "head"
    head (ConsPairIntInt x y _) = pair x y
    tail EmptyPairIntInt = errorEmptyList "tail"
    tail (ConsPairIntInt _ _ x) = x

instance AdaptList (Pair Int Integer) where
    data List (Pair Int Integer)
        = EmptyPairIntInteger
        | ConsPairIntInteger {-# UNPACK #-}!Int {-# UNPACK #-}!Integer (List (Pair Int Integer))
    empty = EmptyPairIntInteger
    cons x z = ConsPairIntInteger (fst x) (snd x) z
    null EmptyPairIntInteger = True
    null _ = False
    head EmptyPairIntInteger = errorEmptyList "head"
    head (ConsPairIntInteger x y _) = pair x y
    tail EmptyPairIntInteger = errorEmptyList "tail"
    tail (ConsPairIntInteger _ _ x) = x

instance AdaptList (Pair Int Int8) where
    data List (Pair Int Int8)
        = EmptyPairIntInt8
        | ConsPairIntInt8 {-# UNPACK #-}!Int {-# UNPACK #-}!Int8 (List (Pair Int Int8))
    empty = EmptyPairIntInt8
    cons x z = ConsPairIntInt8 (fst x) (snd x) z
    null EmptyPairIntInt8 = True
    null _ = False
    head EmptyPairIntInt8 = errorEmptyList "head"
    head (ConsPairIntInt8 x y _) = pair x y
    tail EmptyPairIntInt8 = errorEmptyList "tail"
    tail (ConsPairIntInt8 _ _ x) = x

instance AdaptList (Pair Int Int16) where
    data List (Pair Int Int16)
        = EmptyPairIntInt16
        | ConsPairIntInt16 {-# UNPACK #-}!Int {-# UNPACK #-}!Int16 (List (Pair Int Int16))
    empty = EmptyPairIntInt16
    cons x z = ConsPairIntInt16 (fst x) (snd x) z
    null EmptyPairIntInt16 = True
    null _ = False
    head EmptyPairIntInt16 = errorEmptyList "head"
    head (ConsPairIntInt16 x y _) = pair x y
    tail EmptyPairIntInt16 = errorEmptyList "tail"
    tail (ConsPairIntInt16 _ _ x) = x

instance AdaptList (Pair Int Int32) where
    data List (Pair Int Int32)
        = EmptyPairIntInt32
        | ConsPairIntInt32 {-# UNPACK #-}!Int {-# UNPACK #-}!Int32 (List (Pair Int Int32))
    empty = EmptyPairIntInt32
    cons x z = ConsPairIntInt32 (fst x) (snd x) z
    null EmptyPairIntInt32 = True
    null _ = False
    head EmptyPairIntInt32 = errorEmptyList "head"
    head (ConsPairIntInt32 x y _) = pair x y
    tail EmptyPairIntInt32 = errorEmptyList "tail"
    tail (ConsPairIntInt32 _ _ x) = x

instance AdaptList (Pair Int Int64) where
    data List (Pair Int Int64)
        = EmptyPairIntInt64
        | ConsPairIntInt64 {-# UNPACK #-}!Int {-# UNPACK #-}!Int64 (List (Pair Int Int64))
    empty = EmptyPairIntInt64
    cons x z = ConsPairIntInt64 (fst x) (snd x) z
    null EmptyPairIntInt64 = True
    null _ = False
    head EmptyPairIntInt64 = errorEmptyList "head"
    head (ConsPairIntInt64 x y _) = pair x y
    tail EmptyPairIntInt64 = errorEmptyList "tail"
    tail (ConsPairIntInt64 _ _ x) = x

instance AdaptList (Pair Int Word) where
    data List (Pair Int Word)
        = EmptyPairIntWord
        | ConsPairIntWord {-# UNPACK #-}!Int {-# UNPACK #-}!Word (List (Pair Int Word))
    empty = EmptyPairIntWord
    cons x z = ConsPairIntWord (fst x) (snd x) z
    null EmptyPairIntWord = True
    null _ = False
    head EmptyPairIntWord = errorEmptyList "head"
    head (ConsPairIntWord x y _) = pair x y
    tail EmptyPairIntWord = errorEmptyList "tail"
    tail (ConsPairIntWord _ _ x) = x

instance AdaptList (Pair Int Word8) where
    data List (Pair Int Word8)
        = EmptyPairIntWord8
        | ConsPairIntWord8 {-# UNPACK #-}!Int {-# UNPACK #-}!Word8 (List (Pair Int Word8))
    empty = EmptyPairIntWord8
    cons x z = ConsPairIntWord8 (fst x) (snd x) z
    null EmptyPairIntWord8 = True
    null _ = False
    head EmptyPairIntWord8 = errorEmptyList "head"
    head (ConsPairIntWord8 x y _) = pair x y
    tail EmptyPairIntWord8 = errorEmptyList "tail"
    tail (ConsPairIntWord8 _ _ x) = x

instance AdaptList (Pair Int Word16) where
    data List (Pair Int Word16)
        = EmptyPairIntWord16
        | ConsPairIntWord16 {-# UNPACK #-}!Int {-# UNPACK #-}!Word16 (List (Pair Int Word16))
    empty = EmptyPairIntWord16
    cons x z = ConsPairIntWord16 (fst x) (snd x) z
    null EmptyPairIntWord16 = True
    null _ = False
    head EmptyPairIntWord16 = errorEmptyList "head"
    head (ConsPairIntWord16 x y _) = pair x y
    tail EmptyPairIntWord16 = errorEmptyList "tail"
    tail (ConsPairIntWord16 _ _ x) = x

instance AdaptList (Pair Int Word32) where
    data List (Pair Int Word32)
        = EmptyPairIntWord32
        | ConsPairIntWord32 {-# UNPACK #-}!Int {-# UNPACK #-}!Word32 (List (Pair Int Word32))
    empty = EmptyPairIntWord32
    cons x z = ConsPairIntWord32 (fst x) (snd x) z
    null EmptyPairIntWord32 = True
    null _ = False
    head EmptyPairIntWord32 = errorEmptyList "head"
    head (ConsPairIntWord32 x y _) = pair x y
    tail EmptyPairIntWord32 = errorEmptyList "tail"
    tail (ConsPairIntWord32 _ _ x) = x

instance AdaptList (Pair Int Word64) where
    data List (Pair Int Word64)
        = EmptyPairIntWord64
        | ConsPairIntWord64 {-# UNPACK #-}!Int {-# UNPACK #-}!Word64 (List (Pair Int Word64))
    empty = EmptyPairIntWord64
    cons x z = ConsPairIntWord64 (fst x) (snd x) z
    null EmptyPairIntWord64 = True
    null _ = False
    head EmptyPairIntWord64 = errorEmptyList "head"
    head (ConsPairIntWord64 x y _) = pair x y
    tail EmptyPairIntWord64 = errorEmptyList "tail"
    tail (ConsPairIntWord64 _ _ x) = x

instance AdaptList (Pair Int Double) where
    data List (Pair Int Double)
        = EmptyPairIntDouble
        | ConsPairIntDouble {-# UNPACK #-}!Int {-# UNPACK #-}!Double (List (Pair Int Double))
    empty = EmptyPairIntDouble
    cons x z = ConsPairIntDouble (fst x) (snd x) z
    null EmptyPairIntDouble = True
    null _ = False
    head EmptyPairIntDouble = errorEmptyList "head"
    head (ConsPairIntDouble x y _) = pair x y
    tail EmptyPairIntDouble = errorEmptyList "tail"
    tail (ConsPairIntDouble _ _ x) = x

instance AdaptList (Pair Int Float) where
    data List (Pair Int Float)
        = EmptyPairIntFloat
        | ConsPairIntFloat {-# UNPACK #-}!Int {-# UNPACK #-}!Float (List (Pair Int Float))
    empty = EmptyPairIntFloat
    cons x z = ConsPairIntFloat (fst x) (snd x) z
    null EmptyPairIntFloat = True
    null _ = False
    head EmptyPairIntFloat = errorEmptyList "head"
    head (ConsPairIntFloat x y _) = pair x y
    tail EmptyPairIntFloat = errorEmptyList "tail"
    tail (ConsPairIntFloat _ _ x) = x

instance AdaptList (Pair Int Char) where
    data List (Pair Int Char)
        = EmptyPairIntChar
        | ConsPairIntChar {-# UNPACK #-}!Int {-# UNPACK #-}!Char (List (Pair Int Char))
    empty = EmptyPairIntChar
    cons x z = ConsPairIntChar (fst x) (snd x) z
    null EmptyPairIntChar = True
    null _ = False
    head EmptyPairIntChar = errorEmptyList "head"
    head (ConsPairIntChar x y _) = pair x y
    tail EmptyPairIntChar = errorEmptyList "tail"
    tail (ConsPairIntChar _ _ x) = x

instance AdaptList (Pair Integer Int) where
    data List (Pair Integer Int)
        = EmptyPairIntegerInt
        | ConsPairIntegerInt {-# UNPACK #-}!Integer {-# UNPACK #-}!Int (List (Pair Integer Int))
    empty = EmptyPairIntegerInt
    cons x z = ConsPairIntegerInt (fst x) (snd x) z
    null EmptyPairIntegerInt = True
    null _ = False
    head EmptyPairIntegerInt = errorEmptyList "head"
    head (ConsPairIntegerInt x y _) = pair x y
    tail EmptyPairIntegerInt = errorEmptyList "tail"
    tail (ConsPairIntegerInt _ _ x) = x

instance AdaptList (Pair Integer Integer) where
    data List (Pair Integer Integer)
        = EmptyPairIntegerInteger
        | ConsPairIntegerInteger {-# UNPACK #-}!Integer {-# UNPACK #-}!Integer (List (Pair Integer Integer))
    empty = EmptyPairIntegerInteger
    cons x z = ConsPairIntegerInteger (fst x) (snd x) z
    null EmptyPairIntegerInteger = True
    null _ = False
    head EmptyPairIntegerInteger = errorEmptyList "head"
    head (ConsPairIntegerInteger x y _) = pair x y
    tail EmptyPairIntegerInteger = errorEmptyList "tail"
    tail (ConsPairIntegerInteger _ _ x) = x

instance AdaptList (Pair Integer Int8) where
    data List (Pair Integer Int8)
        = EmptyPairIntegerInt8
        | ConsPairIntegerInt8 {-# UNPACK #-}!Integer {-# UNPACK #-}!Int8 (List (Pair Integer Int8))
    empty = EmptyPairIntegerInt8
    cons x z = ConsPairIntegerInt8 (fst x) (snd x) z
    null EmptyPairIntegerInt8 = True
    null _ = False
    head EmptyPairIntegerInt8 = errorEmptyList "head"
    head (ConsPairIntegerInt8 x y _) = pair x y
    tail EmptyPairIntegerInt8 = errorEmptyList "tail"
    tail (ConsPairIntegerInt8 _ _ x) = x

instance AdaptList (Pair Integer Int16) where
    data List (Pair Integer Int16)
        = EmptyPairIntegerInt16
        | ConsPairIntegerInt16 {-# UNPACK #-}!Integer {-# UNPACK #-}!Int16 (List (Pair Integer Int16))
    empty = EmptyPairIntegerInt16
    cons x z = ConsPairIntegerInt16 (fst x) (snd x) z
    null EmptyPairIntegerInt16 = True
    null _ = False
    head EmptyPairIntegerInt16 = errorEmptyList "head"
    head (ConsPairIntegerInt16 x y _) = pair x y
    tail EmptyPairIntegerInt16 = errorEmptyList "tail"
    tail (ConsPairIntegerInt16 _ _ x) = x

instance AdaptList (Pair Integer Int32) where
    data List (Pair Integer Int32)
        = EmptyPairIntegerInt32
        | ConsPairIntegerInt32 {-# UNPACK #-}!Integer {-# UNPACK #-}!Int32 (List (Pair Integer Int32))
    empty = EmptyPairIntegerInt32
    cons x z = ConsPairIntegerInt32 (fst x) (snd x) z
    null EmptyPairIntegerInt32 = True
    null _ = False
    head EmptyPairIntegerInt32 = errorEmptyList "head"
    head (ConsPairIntegerInt32 x y _) = pair x y
    tail EmptyPairIntegerInt32 = errorEmptyList "tail"
    tail (ConsPairIntegerInt32 _ _ x) = x

instance AdaptList (Pair Integer Int64) where
    data List (Pair Integer Int64)
        = EmptyPairIntegerInt64
        | ConsPairIntegerInt64 {-# UNPACK #-}!Integer {-# UNPACK #-}!Int64 (List (Pair Integer Int64))
    empty = EmptyPairIntegerInt64
    cons x z = ConsPairIntegerInt64 (fst x) (snd x) z
    null EmptyPairIntegerInt64 = True
    null _ = False
    head EmptyPairIntegerInt64 = errorEmptyList "head"
    head (ConsPairIntegerInt64 x y _) = pair x y
    tail EmptyPairIntegerInt64 = errorEmptyList "tail"
    tail (ConsPairIntegerInt64 _ _ x) = x

instance AdaptList (Pair Integer Word) where
    data List (Pair Integer Word)
        = EmptyPairIntegerWord
        | ConsPairIntegerWord {-# UNPACK #-}!Integer {-# UNPACK #-}!Word (List (Pair Integer Word))
    empty = EmptyPairIntegerWord
    cons x z = ConsPairIntegerWord (fst x) (snd x) z
    null EmptyPairIntegerWord = True
    null _ = False
    head EmptyPairIntegerWord = errorEmptyList "head"
    head (ConsPairIntegerWord x y _) = pair x y
    tail EmptyPairIntegerWord = errorEmptyList "tail"
    tail (ConsPairIntegerWord _ _ x) = x

instance AdaptList (Pair Integer Word8) where
    data List (Pair Integer Word8)
        = EmptyPairIntegerWord8
        | ConsPairIntegerWord8 {-# UNPACK #-}!Integer {-# UNPACK #-}!Word8 (List (Pair Integer Word8))
    empty = EmptyPairIntegerWord8
    cons x z = ConsPairIntegerWord8 (fst x) (snd x) z
    null EmptyPairIntegerWord8 = True
    null _ = False
    head EmptyPairIntegerWord8 = errorEmptyList "head"
    head (ConsPairIntegerWord8 x y _) = pair x y
    tail EmptyPairIntegerWord8 = errorEmptyList "tail"
    tail (ConsPairIntegerWord8 _ _ x) = x

instance AdaptList (Pair Integer Word16) where
    data List (Pair Integer Word16)
        = EmptyPairIntegerWord16
        | ConsPairIntegerWord16 {-# UNPACK #-}!Integer {-# UNPACK #-}!Word16 (List (Pair Integer Word16))
    empty = EmptyPairIntegerWord16
    cons x z = ConsPairIntegerWord16 (fst x) (snd x) z
    null EmptyPairIntegerWord16 = True
    null _ = False
    head EmptyPairIntegerWord16 = errorEmptyList "head"
    head (ConsPairIntegerWord16 x y _) = pair x y
    tail EmptyPairIntegerWord16 = errorEmptyList "tail"
    tail (ConsPairIntegerWord16 _ _ x) = x

instance AdaptList (Pair Integer Word32) where
    data List (Pair Integer Word32)
        = EmptyPairIntegerWord32
        | ConsPairIntegerWord32 {-# UNPACK #-}!Integer {-# UNPACK #-}!Word32 (List (Pair Integer Word32))
    empty = EmptyPairIntegerWord32
    cons x z = ConsPairIntegerWord32 (fst x) (snd x) z
    null EmptyPairIntegerWord32 = True
    null _ = False
    head EmptyPairIntegerWord32 = errorEmptyList "head"
    head (ConsPairIntegerWord32 x y _) = pair x y
    tail EmptyPairIntegerWord32 = errorEmptyList "tail"
    tail (ConsPairIntegerWord32 _ _ x) = x

instance AdaptList (Pair Integer Word64) where
    data List (Pair Integer Word64)
        = EmptyPairIntegerWord64
        | ConsPairIntegerWord64 {-# UNPACK #-}!Integer {-# UNPACK #-}!Word64 (List (Pair Integer Word64))
    empty = EmptyPairIntegerWord64
    cons x z = ConsPairIntegerWord64 (fst x) (snd x) z
    null EmptyPairIntegerWord64 = True
    null _ = False
    head EmptyPairIntegerWord64 = errorEmptyList "head"
    head (ConsPairIntegerWord64 x y _) = pair x y
    tail EmptyPairIntegerWord64 = errorEmptyList "tail"
    tail (ConsPairIntegerWord64 _ _ x) = x

instance AdaptList (Pair Integer Double) where
    data List (Pair Integer Double)
        = EmptyPairIntegerDouble
        | ConsPairIntegerDouble {-# UNPACK #-}!Integer {-# UNPACK #-}!Double (List (Pair Integer Double))
    empty = EmptyPairIntegerDouble
    cons x z = ConsPairIntegerDouble (fst x) (snd x) z
    null EmptyPairIntegerDouble = True
    null _ = False
    head EmptyPairIntegerDouble = errorEmptyList "head"
    head (ConsPairIntegerDouble x y _) = pair x y
    tail EmptyPairIntegerDouble = errorEmptyList "tail"
    tail (ConsPairIntegerDouble _ _ x) = x

instance AdaptList (Pair Integer Float) where
    data List (Pair Integer Float)
        = EmptyPairIntegerFloat
        | ConsPairIntegerFloat {-# UNPACK #-}!Integer {-# UNPACK #-}!Float (List (Pair Integer Float))
    empty = EmptyPairIntegerFloat
    cons x z = ConsPairIntegerFloat (fst x) (snd x) z
    null EmptyPairIntegerFloat = True
    null _ = False
    head EmptyPairIntegerFloat = errorEmptyList "head"
    head (ConsPairIntegerFloat x y _) = pair x y
    tail EmptyPairIntegerFloat = errorEmptyList "tail"
    tail (ConsPairIntegerFloat _ _ x) = x

instance AdaptList (Pair Integer Char) where
    data List (Pair Integer Char)
        = EmptyPairIntegerChar
        | ConsPairIntegerChar {-# UNPACK #-}!Integer {-# UNPACK #-}!Char (List (Pair Integer Char))
    empty = EmptyPairIntegerChar
    cons x z = ConsPairIntegerChar (fst x) (snd x) z
    null EmptyPairIntegerChar = True
    null _ = False
    head EmptyPairIntegerChar = errorEmptyList "head"
    head (ConsPairIntegerChar x y _) = pair x y
    tail EmptyPairIntegerChar = errorEmptyList "tail"
    tail (ConsPairIntegerChar _ _ x) = x

instance AdaptList (Pair Int8 Int) where
    data List (Pair Int8 Int)
        = EmptyPairInt8Int
        | ConsPairInt8Int {-# UNPACK #-}!Int8 {-# UNPACK #-}!Int (List (Pair Int8 Int))
    empty = EmptyPairInt8Int
    cons x z = ConsPairInt8Int (fst x) (snd x) z
    null EmptyPairInt8Int = True
    null _ = False
    head EmptyPairInt8Int = errorEmptyList "head"
    head (ConsPairInt8Int x y _) = pair x y
    tail EmptyPairInt8Int = errorEmptyList "tail"
    tail (ConsPairInt8Int _ _ x) = x

instance AdaptList (Pair Int8 Integer) where
    data List (Pair Int8 Integer)
        = EmptyPairInt8Integer
        | ConsPairInt8Integer {-# UNPACK #-}!Int8 {-# UNPACK #-}!Integer (List (Pair Int8 Integer))
    empty = EmptyPairInt8Integer
    cons x z = ConsPairInt8Integer (fst x) (snd x) z
    null EmptyPairInt8Integer = True
    null _ = False
    head EmptyPairInt8Integer = errorEmptyList "head"
    head (ConsPairInt8Integer x y _) = pair x y
    tail EmptyPairInt8Integer = errorEmptyList "tail"
    tail (ConsPairInt8Integer _ _ x) = x

instance AdaptList (Pair Int8 Int8) where
    data List (Pair Int8 Int8)
        = EmptyPairInt8Int8
        | ConsPairInt8Int8 {-# UNPACK #-}!Int8 {-# UNPACK #-}!Int8 (List (Pair Int8 Int8))
    empty = EmptyPairInt8Int8
    cons x z = ConsPairInt8Int8 (fst x) (snd x) z
    null EmptyPairInt8Int8 = True
    null _ = False
    head EmptyPairInt8Int8 = errorEmptyList "head"
    head (ConsPairInt8Int8 x y _) = pair x y
    tail EmptyPairInt8Int8 = errorEmptyList "tail"
    tail (ConsPairInt8Int8 _ _ x) = x

instance AdaptList (Pair Int8 Int16) where
    data List (Pair Int8 Int16)
        = EmptyPairInt8Int16
        | ConsPairInt8Int16 {-# UNPACK #-}!Int8 {-# UNPACK #-}!Int16 (List (Pair Int8 Int16))
    empty = EmptyPairInt8Int16
    cons x z = ConsPairInt8Int16 (fst x) (snd x) z
    null EmptyPairInt8Int16 = True
    null _ = False
    head EmptyPairInt8Int16 = errorEmptyList "head"
    head (ConsPairInt8Int16 x y _) = pair x y
    tail EmptyPairInt8Int16 = errorEmptyList "tail"
    tail (ConsPairInt8Int16 _ _ x) = x

instance AdaptList (Pair Int8 Int32) where
    data List (Pair Int8 Int32)
        = EmptyPairInt8Int32
        | ConsPairInt8Int32 {-# UNPACK #-}!Int8 {-# UNPACK #-}!Int32 (List (Pair Int8 Int32))
    empty = EmptyPairInt8Int32
    cons x z = ConsPairInt8Int32 (fst x) (snd x) z
    null EmptyPairInt8Int32 = True
    null _ = False
    head EmptyPairInt8Int32 = errorEmptyList "head"
    head (ConsPairInt8Int32 x y _) = pair x y
    tail EmptyPairInt8Int32 = errorEmptyList "tail"
    tail (ConsPairInt8Int32 _ _ x) = x

instance AdaptList (Pair Int8 Int64) where
    data List (Pair Int8 Int64)
        = EmptyPairInt8Int64
        | ConsPairInt8Int64 {-# UNPACK #-}!Int8 {-# UNPACK #-}!Int64 (List (Pair Int8 Int64))
    empty = EmptyPairInt8Int64
    cons x z = ConsPairInt8Int64 (fst x) (snd x) z
    null EmptyPairInt8Int64 = True
    null _ = False
    head EmptyPairInt8Int64 = errorEmptyList "head"
    head (ConsPairInt8Int64 x y _) = pair x y
    tail EmptyPairInt8Int64 = errorEmptyList "tail"
    tail (ConsPairInt8Int64 _ _ x) = x

instance AdaptList (Pair Int8 Word) where
    data List (Pair Int8 Word)
        = EmptyPairInt8Word
        | ConsPairInt8Word {-# UNPACK #-}!Int8 {-# UNPACK #-}!Word (List (Pair Int8 Word))
    empty = EmptyPairInt8Word
    cons x z = ConsPairInt8Word (fst x) (snd x) z
    null EmptyPairInt8Word = True
    null _ = False
    head EmptyPairInt8Word = errorEmptyList "head"
    head (ConsPairInt8Word x y _) = pair x y
    tail EmptyPairInt8Word = errorEmptyList "tail"
    tail (ConsPairInt8Word _ _ x) = x

instance AdaptList (Pair Int8 Word8) where
    data List (Pair Int8 Word8)
        = EmptyPairInt8Word8
        | ConsPairInt8Word8 {-# UNPACK #-}!Int8 {-# UNPACK #-}!Word8 (List (Pair Int8 Word8))
    empty = EmptyPairInt8Word8
    cons x z = ConsPairInt8Word8 (fst x) (snd x) z
    null EmptyPairInt8Word8 = True
    null _ = False
    head EmptyPairInt8Word8 = errorEmptyList "head"
    head (ConsPairInt8Word8 x y _) = pair x y
    tail EmptyPairInt8Word8 = errorEmptyList "tail"
    tail (ConsPairInt8Word8 _ _ x) = x

instance AdaptList (Pair Int8 Word16) where
    data List (Pair Int8 Word16)
        = EmptyPairInt8Word16
        | ConsPairInt8Word16 {-# UNPACK #-}!Int8 {-# UNPACK #-}!Word16 (List (Pair Int8 Word16))
    empty = EmptyPairInt8Word16
    cons x z = ConsPairInt8Word16 (fst x) (snd x) z
    null EmptyPairInt8Word16 = True
    null _ = False
    head EmptyPairInt8Word16 = errorEmptyList "head"
    head (ConsPairInt8Word16 x y _) = pair x y
    tail EmptyPairInt8Word16 = errorEmptyList "tail"
    tail (ConsPairInt8Word16 _ _ x) = x

instance AdaptList (Pair Int8 Word32) where
    data List (Pair Int8 Word32)
        = EmptyPairInt8Word32
        | ConsPairInt8Word32 {-# UNPACK #-}!Int8 {-# UNPACK #-}!Word32 (List (Pair Int8 Word32))
    empty = EmptyPairInt8Word32
    cons x z = ConsPairInt8Word32 (fst x) (snd x) z
    null EmptyPairInt8Word32 = True
    null _ = False
    head EmptyPairInt8Word32 = errorEmptyList "head"
    head (ConsPairInt8Word32 x y _) = pair x y
    tail EmptyPairInt8Word32 = errorEmptyList "tail"
    tail (ConsPairInt8Word32 _ _ x) = x

instance AdaptList (Pair Int8 Word64) where
    data List (Pair Int8 Word64)
        = EmptyPairInt8Word64
        | ConsPairInt8Word64 {-# UNPACK #-}!Int8 {-# UNPACK #-}!Word64 (List (Pair Int8 Word64))
    empty = EmptyPairInt8Word64
    cons x z = ConsPairInt8Word64 (fst x) (snd x) z
    null EmptyPairInt8Word64 = True
    null _ = False
    head EmptyPairInt8Word64 = errorEmptyList "head"
    head (ConsPairInt8Word64 x y _) = pair x y
    tail EmptyPairInt8Word64 = errorEmptyList "tail"
    tail (ConsPairInt8Word64 _ _ x) = x

instance AdaptList (Pair Int8 Double) where
    data List (Pair Int8 Double)
        = EmptyPairInt8Double
        | ConsPairInt8Double {-# UNPACK #-}!Int8 {-# UNPACK #-}!Double (List (Pair Int8 Double))
    empty = EmptyPairInt8Double
    cons x z = ConsPairInt8Double (fst x) (snd x) z
    null EmptyPairInt8Double = True
    null _ = False
    head EmptyPairInt8Double = errorEmptyList "head"
    head (ConsPairInt8Double x y _) = pair x y
    tail EmptyPairInt8Double = errorEmptyList "tail"
    tail (ConsPairInt8Double _ _ x) = x

instance AdaptList (Pair Int8 Float) where
    data List (Pair Int8 Float)
        = EmptyPairInt8Float
        | ConsPairInt8Float {-# UNPACK #-}!Int8 {-# UNPACK #-}!Float (List (Pair Int8 Float))
    empty = EmptyPairInt8Float
    cons x z = ConsPairInt8Float (fst x) (snd x) z
    null EmptyPairInt8Float = True
    null _ = False
    head EmptyPairInt8Float = errorEmptyList "head"
    head (ConsPairInt8Float x y _) = pair x y
    tail EmptyPairInt8Float = errorEmptyList "tail"
    tail (ConsPairInt8Float _ _ x) = x

instance AdaptList (Pair Int8 Char) where
    data List (Pair Int8 Char)
        = EmptyPairInt8Char
        | ConsPairInt8Char {-# UNPACK #-}!Int8 {-# UNPACK #-}!Char (List (Pair Int8 Char))
    empty = EmptyPairInt8Char
    cons x z = ConsPairInt8Char (fst x) (snd x) z
    null EmptyPairInt8Char = True
    null _ = False
    head EmptyPairInt8Char = errorEmptyList "head"
    head (ConsPairInt8Char x y _) = pair x y
    tail EmptyPairInt8Char = errorEmptyList "tail"
    tail (ConsPairInt8Char _ _ x) = x

instance AdaptList (Pair Int16 Int) where
    data List (Pair Int16 Int)
        = EmptyPairInt16Int
        | ConsPairInt16Int {-# UNPACK #-}!Int16 {-# UNPACK #-}!Int (List (Pair Int16 Int))
    empty = EmptyPairInt16Int
    cons x z = ConsPairInt16Int (fst x) (snd x) z
    null EmptyPairInt16Int = True
    null _ = False
    head EmptyPairInt16Int = errorEmptyList "head"
    head (ConsPairInt16Int x y _) = pair x y
    tail EmptyPairInt16Int = errorEmptyList "tail"
    tail (ConsPairInt16Int _ _ x) = x

instance AdaptList (Pair Int16 Integer) where
    data List (Pair Int16 Integer)
        = EmptyPairInt16Integer
        | ConsPairInt16Integer {-# UNPACK #-}!Int16 {-# UNPACK #-}!Integer (List (Pair Int16 Integer))
    empty = EmptyPairInt16Integer
    cons x z = ConsPairInt16Integer (fst x) (snd x) z
    null EmptyPairInt16Integer = True
    null _ = False
    head EmptyPairInt16Integer = errorEmptyList "head"
    head (ConsPairInt16Integer x y _) = pair x y
    tail EmptyPairInt16Integer = errorEmptyList "tail"
    tail (ConsPairInt16Integer _ _ x) = x

instance AdaptList (Pair Int16 Int8) where
    data List (Pair Int16 Int8)
        = EmptyPairInt16Int8
        | ConsPairInt16Int8 {-# UNPACK #-}!Int16 {-# UNPACK #-}!Int8 (List (Pair Int16 Int8))
    empty = EmptyPairInt16Int8
    cons x z = ConsPairInt16Int8 (fst x) (snd x) z
    null EmptyPairInt16Int8 = True
    null _ = False
    head EmptyPairInt16Int8 = errorEmptyList "head"
    head (ConsPairInt16Int8 x y _) = pair x y
    tail EmptyPairInt16Int8 = errorEmptyList "tail"
    tail (ConsPairInt16Int8 _ _ x) = x

instance AdaptList (Pair Int16 Int16) where
    data List (Pair Int16 Int16)
        = EmptyPairInt16Int16
        | ConsPairInt16Int16 {-# UNPACK #-}!Int16 {-# UNPACK #-}!Int16 (List (Pair Int16 Int16))
    empty = EmptyPairInt16Int16
    cons x z = ConsPairInt16Int16 (fst x) (snd x) z
    null EmptyPairInt16Int16 = True
    null _ = False
    head EmptyPairInt16Int16 = errorEmptyList "head"
    head (ConsPairInt16Int16 x y _) = pair x y
    tail EmptyPairInt16Int16 = errorEmptyList "tail"
    tail (ConsPairInt16Int16 _ _ x) = x

instance AdaptList (Pair Int16 Int32) where
    data List (Pair Int16 Int32)
        = EmptyPairInt16Int32
        | ConsPairInt16Int32 {-# UNPACK #-}!Int16 {-# UNPACK #-}!Int32 (List (Pair Int16 Int32))
    empty = EmptyPairInt16Int32
    cons x z = ConsPairInt16Int32 (fst x) (snd x) z
    null EmptyPairInt16Int32 = True
    null _ = False
    head EmptyPairInt16Int32 = errorEmptyList "head"
    head (ConsPairInt16Int32 x y _) = pair x y
    tail EmptyPairInt16Int32 = errorEmptyList "tail"
    tail (ConsPairInt16Int32 _ _ x) = x

instance AdaptList (Pair Int16 Int64) where
    data List (Pair Int16 Int64)
        = EmptyPairInt16Int64
        | ConsPairInt16Int64 {-# UNPACK #-}!Int16 {-# UNPACK #-}!Int64 (List (Pair Int16 Int64))
    empty = EmptyPairInt16Int64
    cons x z = ConsPairInt16Int64 (fst x) (snd x) z
    null EmptyPairInt16Int64 = True
    null _ = False
    head EmptyPairInt16Int64 = errorEmptyList "head"
    head (ConsPairInt16Int64 x y _) = pair x y
    tail EmptyPairInt16Int64 = errorEmptyList "tail"
    tail (ConsPairInt16Int64 _ _ x) = x

instance AdaptList (Pair Int16 Word) where
    data List (Pair Int16 Word)
        = EmptyPairInt16Word
        | ConsPairInt16Word {-# UNPACK #-}!Int16 {-# UNPACK #-}!Word (List (Pair Int16 Word))
    empty = EmptyPairInt16Word
    cons x z = ConsPairInt16Word (fst x) (snd x) z
    null EmptyPairInt16Word = True
    null _ = False
    head EmptyPairInt16Word = errorEmptyList "head"
    head (ConsPairInt16Word x y _) = pair x y
    tail EmptyPairInt16Word = errorEmptyList "tail"
    tail (ConsPairInt16Word _ _ x) = x

instance AdaptList (Pair Int16 Word8) where
    data List (Pair Int16 Word8)
        = EmptyPairInt16Word8
        | ConsPairInt16Word8 {-# UNPACK #-}!Int16 {-# UNPACK #-}!Word8 (List (Pair Int16 Word8))
    empty = EmptyPairInt16Word8
    cons x z = ConsPairInt16Word8 (fst x) (snd x) z
    null EmptyPairInt16Word8 = True
    null _ = False
    head EmptyPairInt16Word8 = errorEmptyList "head"
    head (ConsPairInt16Word8 x y _) = pair x y
    tail EmptyPairInt16Word8 = errorEmptyList "tail"
    tail (ConsPairInt16Word8 _ _ x) = x

instance AdaptList (Pair Int16 Word16) where
    data List (Pair Int16 Word16)
        = EmptyPairInt16Word16
        | ConsPairInt16Word16 {-# UNPACK #-}!Int16 {-# UNPACK #-}!Word16 (List (Pair Int16 Word16))
    empty = EmptyPairInt16Word16
    cons x z = ConsPairInt16Word16 (fst x) (snd x) z
    null EmptyPairInt16Word16 = True
    null _ = False
    head EmptyPairInt16Word16 = errorEmptyList "head"
    head (ConsPairInt16Word16 x y _) = pair x y
    tail EmptyPairInt16Word16 = errorEmptyList "tail"
    tail (ConsPairInt16Word16 _ _ x) = x

instance AdaptList (Pair Int16 Word32) where
    data List (Pair Int16 Word32)
        = EmptyPairInt16Word32
        | ConsPairInt16Word32 {-# UNPACK #-}!Int16 {-# UNPACK #-}!Word32 (List (Pair Int16 Word32))
    empty = EmptyPairInt16Word32
    cons x z = ConsPairInt16Word32 (fst x) (snd x) z
    null EmptyPairInt16Word32 = True
    null _ = False
    head EmptyPairInt16Word32 = errorEmptyList "head"
    head (ConsPairInt16Word32 x y _) = pair x y
    tail EmptyPairInt16Word32 = errorEmptyList "tail"
    tail (ConsPairInt16Word32 _ _ x) = x

instance AdaptList (Pair Int16 Word64) where
    data List (Pair Int16 Word64)
        = EmptyPairInt16Word64
        | ConsPairInt16Word64 {-# UNPACK #-}!Int16 {-# UNPACK #-}!Word64 (List (Pair Int16 Word64))
    empty = EmptyPairInt16Word64
    cons x z = ConsPairInt16Word64 (fst x) (snd x) z
    null EmptyPairInt16Word64 = True
    null _ = False
    head EmptyPairInt16Word64 = errorEmptyList "head"
    head (ConsPairInt16Word64 x y _) = pair x y
    tail EmptyPairInt16Word64 = errorEmptyList "tail"
    tail (ConsPairInt16Word64 _ _ x) = x

instance AdaptList (Pair Int16 Double) where
    data List (Pair Int16 Double)
        = EmptyPairInt16Double
        | ConsPairInt16Double {-# UNPACK #-}!Int16 {-# UNPACK #-}!Double (List (Pair Int16 Double))
    empty = EmptyPairInt16Double
    cons x z = ConsPairInt16Double (fst x) (snd x) z
    null EmptyPairInt16Double = True
    null _ = False
    head EmptyPairInt16Double = errorEmptyList "head"
    head (ConsPairInt16Double x y _) = pair x y
    tail EmptyPairInt16Double = errorEmptyList "tail"
    tail (ConsPairInt16Double _ _ x) = x

instance AdaptList (Pair Int16 Float) where
    data List (Pair Int16 Float)
        = EmptyPairInt16Float
        | ConsPairInt16Float {-# UNPACK #-}!Int16 {-# UNPACK #-}!Float (List (Pair Int16 Float))
    empty = EmptyPairInt16Float
    cons x z = ConsPairInt16Float (fst x) (snd x) z
    null EmptyPairInt16Float = True
    null _ = False
    head EmptyPairInt16Float = errorEmptyList "head"
    head (ConsPairInt16Float x y _) = pair x y
    tail EmptyPairInt16Float = errorEmptyList "tail"
    tail (ConsPairInt16Float _ _ x) = x

instance AdaptList (Pair Int16 Char) where
    data List (Pair Int16 Char)
        = EmptyPairInt16Char
        | ConsPairInt16Char {-# UNPACK #-}!Int16 {-# UNPACK #-}!Char (List (Pair Int16 Char))
    empty = EmptyPairInt16Char
    cons x z = ConsPairInt16Char (fst x) (snd x) z
    null EmptyPairInt16Char = True
    null _ = False
    head EmptyPairInt16Char = errorEmptyList "head"
    head (ConsPairInt16Char x y _) = pair x y
    tail EmptyPairInt16Char = errorEmptyList "tail"
    tail (ConsPairInt16Char _ _ x) = x

instance AdaptList (Pair Int32 Int) where
    data List (Pair Int32 Int)
        = EmptyPairInt32Int
        | ConsPairInt32Int {-# UNPACK #-}!Int32 {-# UNPACK #-}!Int (List (Pair Int32 Int))
    empty = EmptyPairInt32Int
    cons x z = ConsPairInt32Int (fst x) (snd x) z
    null EmptyPairInt32Int = True
    null _ = False
    head EmptyPairInt32Int = errorEmptyList "head"
    head (ConsPairInt32Int x y _) = pair x y
    tail EmptyPairInt32Int = errorEmptyList "tail"
    tail (ConsPairInt32Int _ _ x) = x

instance AdaptList (Pair Int32 Integer) where
    data List (Pair Int32 Integer)
        = EmptyPairInt32Integer
        | ConsPairInt32Integer {-# UNPACK #-}!Int32 {-# UNPACK #-}!Integer (List (Pair Int32 Integer))
    empty = EmptyPairInt32Integer
    cons x z = ConsPairInt32Integer (fst x) (snd x) z
    null EmptyPairInt32Integer = True
    null _ = False
    head EmptyPairInt32Integer = errorEmptyList "head"
    head (ConsPairInt32Integer x y _) = pair x y
    tail EmptyPairInt32Integer = errorEmptyList "tail"
    tail (ConsPairInt32Integer _ _ x) = x

instance AdaptList (Pair Int32 Int8) where
    data List (Pair Int32 Int8)
        = EmptyPairInt32Int8
        | ConsPairInt32Int8 {-# UNPACK #-}!Int32 {-# UNPACK #-}!Int8 (List (Pair Int32 Int8))
    empty = EmptyPairInt32Int8
    cons x z = ConsPairInt32Int8 (fst x) (snd x) z
    null EmptyPairInt32Int8 = True
    null _ = False
    head EmptyPairInt32Int8 = errorEmptyList "head"
    head (ConsPairInt32Int8 x y _) = pair x y
    tail EmptyPairInt32Int8 = errorEmptyList "tail"
    tail (ConsPairInt32Int8 _ _ x) = x

instance AdaptList (Pair Int32 Int16) where
    data List (Pair Int32 Int16)
        = EmptyPairInt32Int16
        | ConsPairInt32Int16 {-# UNPACK #-}!Int32 {-# UNPACK #-}!Int16 (List (Pair Int32 Int16))
    empty = EmptyPairInt32Int16
    cons x z = ConsPairInt32Int16 (fst x) (snd x) z
    null EmptyPairInt32Int16 = True
    null _ = False
    head EmptyPairInt32Int16 = errorEmptyList "head"
    head (ConsPairInt32Int16 x y _) = pair x y
    tail EmptyPairInt32Int16 = errorEmptyList "tail"
    tail (ConsPairInt32Int16 _ _ x) = x

instance AdaptList (Pair Int32 Int32) where
    data List (Pair Int32 Int32)
        = EmptyPairInt32Int32
        | ConsPairInt32Int32 {-# UNPACK #-}!Int32 {-# UNPACK #-}!Int32 (List (Pair Int32 Int32))
    empty = EmptyPairInt32Int32
    cons x z = ConsPairInt32Int32 (fst x) (snd x) z
    null EmptyPairInt32Int32 = True
    null _ = False
    head EmptyPairInt32Int32 = errorEmptyList "head"
    head (ConsPairInt32Int32 x y _) = pair x y
    tail EmptyPairInt32Int32 = errorEmptyList "tail"
    tail (ConsPairInt32Int32 _ _ x) = x

instance AdaptList (Pair Int32 Int64) where
    data List (Pair Int32 Int64)
        = EmptyPairInt32Int64
        | ConsPairInt32Int64 {-# UNPACK #-}!Int32 {-# UNPACK #-}!Int64 (List (Pair Int32 Int64))
    empty = EmptyPairInt32Int64
    cons x z = ConsPairInt32Int64 (fst x) (snd x) z
    null EmptyPairInt32Int64 = True
    null _ = False
    head EmptyPairInt32Int64 = errorEmptyList "head"
    head (ConsPairInt32Int64 x y _) = pair x y
    tail EmptyPairInt32Int64 = errorEmptyList "tail"
    tail (ConsPairInt32Int64 _ _ x) = x

instance AdaptList (Pair Int32 Word) where
    data List (Pair Int32 Word)
        = EmptyPairInt32Word
        | ConsPairInt32Word {-# UNPACK #-}!Int32 {-# UNPACK #-}!Word (List (Pair Int32 Word))
    empty = EmptyPairInt32Word
    cons x z = ConsPairInt32Word (fst x) (snd x) z
    null EmptyPairInt32Word = True
    null _ = False
    head EmptyPairInt32Word = errorEmptyList "head"
    head (ConsPairInt32Word x y _) = pair x y
    tail EmptyPairInt32Word = errorEmptyList "tail"
    tail (ConsPairInt32Word _ _ x) = x

instance AdaptList (Pair Int32 Word8) where
    data List (Pair Int32 Word8)
        = EmptyPairInt32Word8
        | ConsPairInt32Word8 {-# UNPACK #-}!Int32 {-# UNPACK #-}!Word8 (List (Pair Int32 Word8))
    empty = EmptyPairInt32Word8
    cons x z = ConsPairInt32Word8 (fst x) (snd x) z
    null EmptyPairInt32Word8 = True
    null _ = False
    head EmptyPairInt32Word8 = errorEmptyList "head"
    head (ConsPairInt32Word8 x y _) = pair x y
    tail EmptyPairInt32Word8 = errorEmptyList "tail"
    tail (ConsPairInt32Word8 _ _ x) = x

instance AdaptList (Pair Int32 Word16) where
    data List (Pair Int32 Word16)
        = EmptyPairInt32Word16
        | ConsPairInt32Word16 {-# UNPACK #-}!Int32 {-# UNPACK #-}!Word16 (List (Pair Int32 Word16))
    empty = EmptyPairInt32Word16
    cons x z = ConsPairInt32Word16 (fst x) (snd x) z
    null EmptyPairInt32Word16 = True
    null _ = False
    head EmptyPairInt32Word16 = errorEmptyList "head"
    head (ConsPairInt32Word16 x y _) = pair x y
    tail EmptyPairInt32Word16 = errorEmptyList "tail"
    tail (ConsPairInt32Word16 _ _ x) = x

instance AdaptList (Pair Int32 Word32) where
    data List (Pair Int32 Word32)
        = EmptyPairInt32Word32
        | ConsPairInt32Word32 {-# UNPACK #-}!Int32 {-# UNPACK #-}!Word32 (List (Pair Int32 Word32))
    empty = EmptyPairInt32Word32
    cons x z = ConsPairInt32Word32 (fst x) (snd x) z
    null EmptyPairInt32Word32 = True
    null _ = False
    head EmptyPairInt32Word32 = errorEmptyList "head"
    head (ConsPairInt32Word32 x y _) = pair x y
    tail EmptyPairInt32Word32 = errorEmptyList "tail"
    tail (ConsPairInt32Word32 _ _ x) = x

instance AdaptList (Pair Int32 Word64) where
    data List (Pair Int32 Word64)
        = EmptyPairInt32Word64
        | ConsPairInt32Word64 {-# UNPACK #-}!Int32 {-# UNPACK #-}!Word64 (List (Pair Int32 Word64))
    empty = EmptyPairInt32Word64
    cons x z = ConsPairInt32Word64 (fst x) (snd x) z
    null EmptyPairInt32Word64 = True
    null _ = False
    head EmptyPairInt32Word64 = errorEmptyList "head"
    head (ConsPairInt32Word64 x y _) = pair x y
    tail EmptyPairInt32Word64 = errorEmptyList "tail"
    tail (ConsPairInt32Word64 _ _ x) = x

instance AdaptList (Pair Int32 Double) where
    data List (Pair Int32 Double)
        = EmptyPairInt32Double
        | ConsPairInt32Double {-# UNPACK #-}!Int32 {-# UNPACK #-}!Double (List (Pair Int32 Double))
    empty = EmptyPairInt32Double
    cons x z = ConsPairInt32Double (fst x) (snd x) z
    null EmptyPairInt32Double = True
    null _ = False
    head EmptyPairInt32Double = errorEmptyList "head"
    head (ConsPairInt32Double x y _) = pair x y
    tail EmptyPairInt32Double = errorEmptyList "tail"
    tail (ConsPairInt32Double _ _ x) = x

instance AdaptList (Pair Int32 Float) where
    data List (Pair Int32 Float)
        = EmptyPairInt32Float
        | ConsPairInt32Float {-# UNPACK #-}!Int32 {-# UNPACK #-}!Float (List (Pair Int32 Float))
    empty = EmptyPairInt32Float
    cons x z = ConsPairInt32Float (fst x) (snd x) z
    null EmptyPairInt32Float = True
    null _ = False
    head EmptyPairInt32Float = errorEmptyList "head"
    head (ConsPairInt32Float x y _) = pair x y
    tail EmptyPairInt32Float = errorEmptyList "tail"
    tail (ConsPairInt32Float _ _ x) = x

instance AdaptList (Pair Int32 Char) where
    data List (Pair Int32 Char)
        = EmptyPairInt32Char
        | ConsPairInt32Char {-# UNPACK #-}!Int32 {-# UNPACK #-}!Char (List (Pair Int32 Char))
    empty = EmptyPairInt32Char
    cons x z = ConsPairInt32Char (fst x) (snd x) z
    null EmptyPairInt32Char = True
    null _ = False
    head EmptyPairInt32Char = errorEmptyList "head"
    head (ConsPairInt32Char x y _) = pair x y
    tail EmptyPairInt32Char = errorEmptyList "tail"
    tail (ConsPairInt32Char _ _ x) = x

instance AdaptList (Pair Int64 Int) where
    data List (Pair Int64 Int)
        = EmptyPairInt64Int
        | ConsPairInt64Int {-# UNPACK #-}!Int64 {-# UNPACK #-}!Int (List (Pair Int64 Int))
    empty = EmptyPairInt64Int
    cons x z = ConsPairInt64Int (fst x) (snd x) z
    null EmptyPairInt64Int = True
    null _ = False
    head EmptyPairInt64Int = errorEmptyList "head"
    head (ConsPairInt64Int x y _) = pair x y
    tail EmptyPairInt64Int = errorEmptyList "tail"
    tail (ConsPairInt64Int _ _ x) = x

instance AdaptList (Pair Int64 Integer) where
    data List (Pair Int64 Integer)
        = EmptyPairInt64Integer
        | ConsPairInt64Integer {-# UNPACK #-}!Int64 {-# UNPACK #-}!Integer (List (Pair Int64 Integer))
    empty = EmptyPairInt64Integer
    cons x z = ConsPairInt64Integer (fst x) (snd x) z
    null EmptyPairInt64Integer = True
    null _ = False
    head EmptyPairInt64Integer = errorEmptyList "head"
    head (ConsPairInt64Integer x y _) = pair x y
    tail EmptyPairInt64Integer = errorEmptyList "tail"
    tail (ConsPairInt64Integer _ _ x) = x

instance AdaptList (Pair Int64 Int8) where
    data List (Pair Int64 Int8)
        = EmptyPairInt64Int8
        | ConsPairInt64Int8 {-# UNPACK #-}!Int64 {-# UNPACK #-}!Int8 (List (Pair Int64 Int8))
    empty = EmptyPairInt64Int8
    cons x z = ConsPairInt64Int8 (fst x) (snd x) z
    null EmptyPairInt64Int8 = True
    null _ = False
    head EmptyPairInt64Int8 = errorEmptyList "head"
    head (ConsPairInt64Int8 x y _) = pair x y
    tail EmptyPairInt64Int8 = errorEmptyList "tail"
    tail (ConsPairInt64Int8 _ _ x) = x

instance AdaptList (Pair Int64 Int16) where
    data List (Pair Int64 Int16)
        = EmptyPairInt64Int16
        | ConsPairInt64Int16 {-# UNPACK #-}!Int64 {-# UNPACK #-}!Int16 (List (Pair Int64 Int16))
    empty = EmptyPairInt64Int16
    cons x z = ConsPairInt64Int16 (fst x) (snd x) z
    null EmptyPairInt64Int16 = True
    null _ = False
    head EmptyPairInt64Int16 = errorEmptyList "head"
    head (ConsPairInt64Int16 x y _) = pair x y
    tail EmptyPairInt64Int16 = errorEmptyList "tail"
    tail (ConsPairInt64Int16 _ _ x) = x

instance AdaptList (Pair Int64 Int32) where
    data List (Pair Int64 Int32)
        = EmptyPairInt64Int32
        | ConsPairInt64Int32 {-# UNPACK #-}!Int64 {-# UNPACK #-}!Int32 (List (Pair Int64 Int32))
    empty = EmptyPairInt64Int32
    cons x z = ConsPairInt64Int32 (fst x) (snd x) z
    null EmptyPairInt64Int32 = True
    null _ = False
    head EmptyPairInt64Int32 = errorEmptyList "head"
    head (ConsPairInt64Int32 x y _) = pair x y
    tail EmptyPairInt64Int32 = errorEmptyList "tail"
    tail (ConsPairInt64Int32 _ _ x) = x

instance AdaptList (Pair Int64 Int64) where
    data List (Pair Int64 Int64)
        = EmptyPairInt64Int64
        | ConsPairInt64Int64 {-# UNPACK #-}!Int64 {-# UNPACK #-}!Int64 (List (Pair Int64 Int64))
    empty = EmptyPairInt64Int64
    cons x z = ConsPairInt64Int64 (fst x) (snd x) z
    null EmptyPairInt64Int64 = True
    null _ = False
    head EmptyPairInt64Int64 = errorEmptyList "head"
    head (ConsPairInt64Int64 x y _) = pair x y
    tail EmptyPairInt64Int64 = errorEmptyList "tail"
    tail (ConsPairInt64Int64 _ _ x) = x

instance AdaptList (Pair Int64 Word) where
    data List (Pair Int64 Word)
        = EmptyPairInt64Word
        | ConsPairInt64Word {-# UNPACK #-}!Int64 {-# UNPACK #-}!Word (List (Pair Int64 Word))
    empty = EmptyPairInt64Word
    cons x z = ConsPairInt64Word (fst x) (snd x) z
    null EmptyPairInt64Word = True
    null _ = False
    head EmptyPairInt64Word = errorEmptyList "head"
    head (ConsPairInt64Word x y _) = pair x y
    tail EmptyPairInt64Word = errorEmptyList "tail"
    tail (ConsPairInt64Word _ _ x) = x

instance AdaptList (Pair Int64 Word8) where
    data List (Pair Int64 Word8)
        = EmptyPairInt64Word8
        | ConsPairInt64Word8 {-# UNPACK #-}!Int64 {-# UNPACK #-}!Word8 (List (Pair Int64 Word8))
    empty = EmptyPairInt64Word8
    cons x z = ConsPairInt64Word8 (fst x) (snd x) z
    null EmptyPairInt64Word8 = True
    null _ = False
    head EmptyPairInt64Word8 = errorEmptyList "head"
    head (ConsPairInt64Word8 x y _) = pair x y
    tail EmptyPairInt64Word8 = errorEmptyList "tail"
    tail (ConsPairInt64Word8 _ _ x) = x

instance AdaptList (Pair Int64 Word16) where
    data List (Pair Int64 Word16)
        = EmptyPairInt64Word16
        | ConsPairInt64Word16 {-# UNPACK #-}!Int64 {-# UNPACK #-}!Word16 (List (Pair Int64 Word16))
    empty = EmptyPairInt64Word16
    cons x z = ConsPairInt64Word16 (fst x) (snd x) z
    null EmptyPairInt64Word16 = True
    null _ = False
    head EmptyPairInt64Word16 = errorEmptyList "head"
    head (ConsPairInt64Word16 x y _) = pair x y
    tail EmptyPairInt64Word16 = errorEmptyList "tail"
    tail (ConsPairInt64Word16 _ _ x) = x

instance AdaptList (Pair Int64 Word32) where
    data List (Pair Int64 Word32)
        = EmptyPairInt64Word32
        | ConsPairInt64Word32 {-# UNPACK #-}!Int64 {-# UNPACK #-}!Word32 (List (Pair Int64 Word32))
    empty = EmptyPairInt64Word32
    cons x z = ConsPairInt64Word32 (fst x) (snd x) z
    null EmptyPairInt64Word32 = True
    null _ = False
    head EmptyPairInt64Word32 = errorEmptyList "head"
    head (ConsPairInt64Word32 x y _) = pair x y
    tail EmptyPairInt64Word32 = errorEmptyList "tail"
    tail (ConsPairInt64Word32 _ _ x) = x

instance AdaptList (Pair Int64 Word64) where
    data List (Pair Int64 Word64)
        = EmptyPairInt64Word64
        | ConsPairInt64Word64 {-# UNPACK #-}!Int64 {-# UNPACK #-}!Word64 (List (Pair Int64 Word64))
    empty = EmptyPairInt64Word64
    cons x z = ConsPairInt64Word64 (fst x) (snd x) z
    null EmptyPairInt64Word64 = True
    null _ = False
    head EmptyPairInt64Word64 = errorEmptyList "head"
    head (ConsPairInt64Word64 x y _) = pair x y
    tail EmptyPairInt64Word64 = errorEmptyList "tail"
    tail (ConsPairInt64Word64 _ _ x) = x

instance AdaptList (Pair Int64 Double) where
    data List (Pair Int64 Double)
        = EmptyPairInt64Double
        | ConsPairInt64Double {-# UNPACK #-}!Int64 {-# UNPACK #-}!Double (List (Pair Int64 Double))
    empty = EmptyPairInt64Double
    cons x z = ConsPairInt64Double (fst x) (snd x) z
    null EmptyPairInt64Double = True
    null _ = False
    head EmptyPairInt64Double = errorEmptyList "head"
    head (ConsPairInt64Double x y _) = pair x y
    tail EmptyPairInt64Double = errorEmptyList "tail"
    tail (ConsPairInt64Double _ _ x) = x

instance AdaptList (Pair Int64 Float) where
    data List (Pair Int64 Float)
        = EmptyPairInt64Float
        | ConsPairInt64Float {-# UNPACK #-}!Int64 {-# UNPACK #-}!Float (List (Pair Int64 Float))
    empty = EmptyPairInt64Float
    cons x z = ConsPairInt64Float (fst x) (snd x) z
    null EmptyPairInt64Float = True
    null _ = False
    head EmptyPairInt64Float = errorEmptyList "head"
    head (ConsPairInt64Float x y _) = pair x y
    tail EmptyPairInt64Float = errorEmptyList "tail"
    tail (ConsPairInt64Float _ _ x) = x

instance AdaptList (Pair Int64 Char) where
    data List (Pair Int64 Char)
        = EmptyPairInt64Char
        | ConsPairInt64Char {-# UNPACK #-}!Int64 {-# UNPACK #-}!Char (List (Pair Int64 Char))
    empty = EmptyPairInt64Char
    cons x z = ConsPairInt64Char (fst x) (snd x) z
    null EmptyPairInt64Char = True
    null _ = False
    head EmptyPairInt64Char = errorEmptyList "head"
    head (ConsPairInt64Char x y _) = pair x y
    tail EmptyPairInt64Char = errorEmptyList "tail"
    tail (ConsPairInt64Char _ _ x) = x

instance AdaptList (Pair Word Int) where
    data List (Pair Word Int)
        = EmptyPairWordInt
        | ConsPairWordInt {-# UNPACK #-}!Word {-# UNPACK #-}!Int (List (Pair Word Int))
    empty = EmptyPairWordInt
    cons x z = ConsPairWordInt (fst x) (snd x) z
    null EmptyPairWordInt = True
    null _ = False
    head EmptyPairWordInt = errorEmptyList "head"
    head (ConsPairWordInt x y _) = pair x y
    tail EmptyPairWordInt = errorEmptyList "tail"
    tail (ConsPairWordInt _ _ x) = x

instance AdaptList (Pair Word Integer) where
    data List (Pair Word Integer)
        = EmptyPairWordInteger
        | ConsPairWordInteger {-# UNPACK #-}!Word {-# UNPACK #-}!Integer (List (Pair Word Integer))
    empty = EmptyPairWordInteger
    cons x z = ConsPairWordInteger (fst x) (snd x) z
    null EmptyPairWordInteger = True
    null _ = False
    head EmptyPairWordInteger = errorEmptyList "head"
    head (ConsPairWordInteger x y _) = pair x y
    tail EmptyPairWordInteger = errorEmptyList "tail"
    tail (ConsPairWordInteger _ _ x) = x

instance AdaptList (Pair Word Int8) where
    data List (Pair Word Int8)
        = EmptyPairWordInt8
        | ConsPairWordInt8 {-# UNPACK #-}!Word {-# UNPACK #-}!Int8 (List (Pair Word Int8))
    empty = EmptyPairWordInt8
    cons x z = ConsPairWordInt8 (fst x) (snd x) z
    null EmptyPairWordInt8 = True
    null _ = False
    head EmptyPairWordInt8 = errorEmptyList "head"
    head (ConsPairWordInt8 x y _) = pair x y
    tail EmptyPairWordInt8 = errorEmptyList "tail"
    tail (ConsPairWordInt8 _ _ x) = x

instance AdaptList (Pair Word Int16) where
    data List (Pair Word Int16)
        = EmptyPairWordInt16
        | ConsPairWordInt16 {-# UNPACK #-}!Word {-# UNPACK #-}!Int16 (List (Pair Word Int16))
    empty = EmptyPairWordInt16
    cons x z = ConsPairWordInt16 (fst x) (snd x) z
    null EmptyPairWordInt16 = True
    null _ = False
    head EmptyPairWordInt16 = errorEmptyList "head"
    head (ConsPairWordInt16 x y _) = pair x y
    tail EmptyPairWordInt16 = errorEmptyList "tail"
    tail (ConsPairWordInt16 _ _ x) = x

instance AdaptList (Pair Word Int32) where
    data List (Pair Word Int32)
        = EmptyPairWordInt32
        | ConsPairWordInt32 {-# UNPACK #-}!Word {-# UNPACK #-}!Int32 (List (Pair Word Int32))
    empty = EmptyPairWordInt32
    cons x z = ConsPairWordInt32 (fst x) (snd x) z
    null EmptyPairWordInt32 = True
    null _ = False
    head EmptyPairWordInt32 = errorEmptyList "head"
    head (ConsPairWordInt32 x y _) = pair x y
    tail EmptyPairWordInt32 = errorEmptyList "tail"
    tail (ConsPairWordInt32 _ _ x) = x

instance AdaptList (Pair Word Int64) where
    data List (Pair Word Int64)
        = EmptyPairWordInt64
        | ConsPairWordInt64 {-# UNPACK #-}!Word {-# UNPACK #-}!Int64 (List (Pair Word Int64))
    empty = EmptyPairWordInt64
    cons x z = ConsPairWordInt64 (fst x) (snd x) z
    null EmptyPairWordInt64 = True
    null _ = False
    head EmptyPairWordInt64 = errorEmptyList "head"
    head (ConsPairWordInt64 x y _) = pair x y
    tail EmptyPairWordInt64 = errorEmptyList "tail"
    tail (ConsPairWordInt64 _ _ x) = x

instance AdaptList (Pair Word Word) where
    data List (Pair Word Word)
        = EmptyPairWordWord
        | ConsPairWordWord {-# UNPACK #-}!Word {-# UNPACK #-}!Word (List (Pair Word Word))
    empty = EmptyPairWordWord
    cons x z = ConsPairWordWord (fst x) (snd x) z
    null EmptyPairWordWord = True
    null _ = False
    head EmptyPairWordWord = errorEmptyList "head"
    head (ConsPairWordWord x y _) = pair x y
    tail EmptyPairWordWord = errorEmptyList "tail"
    tail (ConsPairWordWord _ _ x) = x

instance AdaptList (Pair Word Word8) where
    data List (Pair Word Word8)
        = EmptyPairWordWord8
        | ConsPairWordWord8 {-# UNPACK #-}!Word {-# UNPACK #-}!Word8 (List (Pair Word Word8))
    empty = EmptyPairWordWord8
    cons x z = ConsPairWordWord8 (fst x) (snd x) z
    null EmptyPairWordWord8 = True
    null _ = False
    head EmptyPairWordWord8 = errorEmptyList "head"
    head (ConsPairWordWord8 x y _) = pair x y
    tail EmptyPairWordWord8 = errorEmptyList "tail"
    tail (ConsPairWordWord8 _ _ x) = x

instance AdaptList (Pair Word Word16) where
    data List (Pair Word Word16)
        = EmptyPairWordWord16
        | ConsPairWordWord16 {-# UNPACK #-}!Word {-# UNPACK #-}!Word16 (List (Pair Word Word16))
    empty = EmptyPairWordWord16
    cons x z = ConsPairWordWord16 (fst x) (snd x) z
    null EmptyPairWordWord16 = True
    null _ = False
    head EmptyPairWordWord16 = errorEmptyList "head"
    head (ConsPairWordWord16 x y _) = pair x y
    tail EmptyPairWordWord16 = errorEmptyList "tail"
    tail (ConsPairWordWord16 _ _ x) = x

instance AdaptList (Pair Word Word32) where
    data List (Pair Word Word32)
        = EmptyPairWordWord32
        | ConsPairWordWord32 {-# UNPACK #-}!Word {-# UNPACK #-}!Word32 (List (Pair Word Word32))
    empty = EmptyPairWordWord32
    cons x z = ConsPairWordWord32 (fst x) (snd x) z
    null EmptyPairWordWord32 = True
    null _ = False
    head EmptyPairWordWord32 = errorEmptyList "head"
    head (ConsPairWordWord32 x y _) = pair x y
    tail EmptyPairWordWord32 = errorEmptyList "tail"
    tail (ConsPairWordWord32 _ _ x) = x

instance AdaptList (Pair Word Word64) where
    data List (Pair Word Word64)
        = EmptyPairWordWord64
        | ConsPairWordWord64 {-# UNPACK #-}!Word {-# UNPACK #-}!Word64 (List (Pair Word Word64))
    empty = EmptyPairWordWord64
    cons x z = ConsPairWordWord64 (fst x) (snd x) z
    null EmptyPairWordWord64 = True
    null _ = False
    head EmptyPairWordWord64 = errorEmptyList "head"
    head (ConsPairWordWord64 x y _) = pair x y
    tail EmptyPairWordWord64 = errorEmptyList "tail"
    tail (ConsPairWordWord64 _ _ x) = x

instance AdaptList (Pair Word Double) where
    data List (Pair Word Double)
        = EmptyPairWordDouble
        | ConsPairWordDouble {-# UNPACK #-}!Word {-# UNPACK #-}!Double (List (Pair Word Double))
    empty = EmptyPairWordDouble
    cons x z = ConsPairWordDouble (fst x) (snd x) z
    null EmptyPairWordDouble = True
    null _ = False
    head EmptyPairWordDouble = errorEmptyList "head"
    head (ConsPairWordDouble x y _) = pair x y
    tail EmptyPairWordDouble = errorEmptyList "tail"
    tail (ConsPairWordDouble _ _ x) = x

instance AdaptList (Pair Word Float) where
    data List (Pair Word Float)
        = EmptyPairWordFloat
        | ConsPairWordFloat {-# UNPACK #-}!Word {-# UNPACK #-}!Float (List (Pair Word Float))
    empty = EmptyPairWordFloat
    cons x z = ConsPairWordFloat (fst x) (snd x) z
    null EmptyPairWordFloat = True
    null _ = False
    head EmptyPairWordFloat = errorEmptyList "head"
    head (ConsPairWordFloat x y _) = pair x y
    tail EmptyPairWordFloat = errorEmptyList "tail"
    tail (ConsPairWordFloat _ _ x) = x

instance AdaptList (Pair Word Char) where
    data List (Pair Word Char)
        = EmptyPairWordChar
        | ConsPairWordChar {-# UNPACK #-}!Word {-# UNPACK #-}!Char (List (Pair Word Char))
    empty = EmptyPairWordChar
    cons x z = ConsPairWordChar (fst x) (snd x) z
    null EmptyPairWordChar = True
    null _ = False
    head EmptyPairWordChar = errorEmptyList "head"
    head (ConsPairWordChar x y _) = pair x y
    tail EmptyPairWordChar = errorEmptyList "tail"
    tail (ConsPairWordChar _ _ x) = x

instance AdaptList (Pair Word8 Int) where
    data List (Pair Word8 Int)
        = EmptyPairWord8Int
        | ConsPairWord8Int {-# UNPACK #-}!Word8 {-# UNPACK #-}!Int (List (Pair Word8 Int))
    empty = EmptyPairWord8Int
    cons x z = ConsPairWord8Int (fst x) (snd x) z
    null EmptyPairWord8Int = True
    null _ = False
    head EmptyPairWord8Int = errorEmptyList "head"
    head (ConsPairWord8Int x y _) = pair x y
    tail EmptyPairWord8Int = errorEmptyList "tail"
    tail (ConsPairWord8Int _ _ x) = x

instance AdaptList (Pair Word8 Integer) where
    data List (Pair Word8 Integer)
        = EmptyPairWord8Integer
        | ConsPairWord8Integer {-# UNPACK #-}!Word8 {-# UNPACK #-}!Integer (List (Pair Word8 Integer))
    empty = EmptyPairWord8Integer
    cons x z = ConsPairWord8Integer (fst x) (snd x) z
    null EmptyPairWord8Integer = True
    null _ = False
    head EmptyPairWord8Integer = errorEmptyList "head"
    head (ConsPairWord8Integer x y _) = pair x y
    tail EmptyPairWord8Integer = errorEmptyList "tail"
    tail (ConsPairWord8Integer _ _ x) = x

instance AdaptList (Pair Word8 Int8) where
    data List (Pair Word8 Int8)
        = EmptyPairWord8Int8
        | ConsPairWord8Int8 {-# UNPACK #-}!Word8 {-# UNPACK #-}!Int8 (List (Pair Word8 Int8))
    empty = EmptyPairWord8Int8
    cons x z = ConsPairWord8Int8 (fst x) (snd x) z
    null EmptyPairWord8Int8 = True
    null _ = False
    head EmptyPairWord8Int8 = errorEmptyList "head"
    head (ConsPairWord8Int8 x y _) = pair x y
    tail EmptyPairWord8Int8 = errorEmptyList "tail"
    tail (ConsPairWord8Int8 _ _ x) = x

instance AdaptList (Pair Word8 Int16) where
    data List (Pair Word8 Int16)
        = EmptyPairWord8Int16
        | ConsPairWord8Int16 {-# UNPACK #-}!Word8 {-# UNPACK #-}!Int16 (List (Pair Word8 Int16))
    empty = EmptyPairWord8Int16
    cons x z = ConsPairWord8Int16 (fst x) (snd x) z
    null EmptyPairWord8Int16 = True
    null _ = False
    head EmptyPairWord8Int16 = errorEmptyList "head"
    head (ConsPairWord8Int16 x y _) = pair x y
    tail EmptyPairWord8Int16 = errorEmptyList "tail"
    tail (ConsPairWord8Int16 _ _ x) = x

instance AdaptList (Pair Word8 Int32) where
    data List (Pair Word8 Int32)
        = EmptyPairWord8Int32
        | ConsPairWord8Int32 {-# UNPACK #-}!Word8 {-# UNPACK #-}!Int32 (List (Pair Word8 Int32))
    empty = EmptyPairWord8Int32
    cons x z = ConsPairWord8Int32 (fst x) (snd x) z
    null EmptyPairWord8Int32 = True
    null _ = False
    head EmptyPairWord8Int32 = errorEmptyList "head"
    head (ConsPairWord8Int32 x y _) = pair x y
    tail EmptyPairWord8Int32 = errorEmptyList "tail"
    tail (ConsPairWord8Int32 _ _ x) = x

instance AdaptList (Pair Word8 Int64) where
    data List (Pair Word8 Int64)
        = EmptyPairWord8Int64
        | ConsPairWord8Int64 {-# UNPACK #-}!Word8 {-# UNPACK #-}!Int64 (List (Pair Word8 Int64))
    empty = EmptyPairWord8Int64
    cons x z = ConsPairWord8Int64 (fst x) (snd x) z
    null EmptyPairWord8Int64 = True
    null _ = False
    head EmptyPairWord8Int64 = errorEmptyList "head"
    head (ConsPairWord8Int64 x y _) = pair x y
    tail EmptyPairWord8Int64 = errorEmptyList "tail"
    tail (ConsPairWord8Int64 _ _ x) = x

instance AdaptList (Pair Word8 Word) where
    data List (Pair Word8 Word)
        = EmptyPairWord8Word
        | ConsPairWord8Word {-# UNPACK #-}!Word8 {-# UNPACK #-}!Word (List (Pair Word8 Word))
    empty = EmptyPairWord8Word
    cons x z = ConsPairWord8Word (fst x) (snd x) z
    null EmptyPairWord8Word = True
    null _ = False
    head EmptyPairWord8Word = errorEmptyList "head"
    head (ConsPairWord8Word x y _) = pair x y
    tail EmptyPairWord8Word = errorEmptyList "tail"
    tail (ConsPairWord8Word _ _ x) = x

instance AdaptList (Pair Word8 Word8) where
    data List (Pair Word8 Word8)
        = EmptyPairWord8Word8
        | ConsPairWord8Word8 {-# UNPACK #-}!Word8 {-# UNPACK #-}!Word8 (List (Pair Word8 Word8))
    empty = EmptyPairWord8Word8
    cons x z = ConsPairWord8Word8 (fst x) (snd x) z
    null EmptyPairWord8Word8 = True
    null _ = False
    head EmptyPairWord8Word8 = errorEmptyList "head"
    head (ConsPairWord8Word8 x y _) = pair x y
    tail EmptyPairWord8Word8 = errorEmptyList "tail"
    tail (ConsPairWord8Word8 _ _ x) = x

instance AdaptList (Pair Word8 Word16) where
    data List (Pair Word8 Word16)
        = EmptyPairWord8Word16
        | ConsPairWord8Word16 {-# UNPACK #-}!Word8 {-# UNPACK #-}!Word16 (List (Pair Word8 Word16))
    empty = EmptyPairWord8Word16
    cons x z = ConsPairWord8Word16 (fst x) (snd x) z
    null EmptyPairWord8Word16 = True
    null _ = False
    head EmptyPairWord8Word16 = errorEmptyList "head"
    head (ConsPairWord8Word16 x y _) = pair x y
    tail EmptyPairWord8Word16 = errorEmptyList "tail"
    tail (ConsPairWord8Word16 _ _ x) = x

instance AdaptList (Pair Word8 Word32) where
    data List (Pair Word8 Word32)
        = EmptyPairWord8Word32
        | ConsPairWord8Word32 {-# UNPACK #-}!Word8 {-# UNPACK #-}!Word32 (List (Pair Word8 Word32))
    empty = EmptyPairWord8Word32
    cons x z = ConsPairWord8Word32 (fst x) (snd x) z
    null EmptyPairWord8Word32 = True
    null _ = False
    head EmptyPairWord8Word32 = errorEmptyList "head"
    head (ConsPairWord8Word32 x y _) = pair x y
    tail EmptyPairWord8Word32 = errorEmptyList "tail"
    tail (ConsPairWord8Word32 _ _ x) = x

instance AdaptList (Pair Word8 Word64) where
    data List (Pair Word8 Word64)
        = EmptyPairWord8Word64
        | ConsPairWord8Word64 {-# UNPACK #-}!Word8 {-# UNPACK #-}!Word64 (List (Pair Word8 Word64))
    empty = EmptyPairWord8Word64
    cons x z = ConsPairWord8Word64 (fst x) (snd x) z
    null EmptyPairWord8Word64 = True
    null _ = False
    head EmptyPairWord8Word64 = errorEmptyList "head"
    head (ConsPairWord8Word64 x y _) = pair x y
    tail EmptyPairWord8Word64 = errorEmptyList "tail"
    tail (ConsPairWord8Word64 _ _ x) = x

instance AdaptList (Pair Word8 Double) where
    data List (Pair Word8 Double)
        = EmptyPairWord8Double
        | ConsPairWord8Double {-# UNPACK #-}!Word8 {-# UNPACK #-}!Double (List (Pair Word8 Double))
    empty = EmptyPairWord8Double
    cons x z = ConsPairWord8Double (fst x) (snd x) z
    null EmptyPairWord8Double = True
    null _ = False
    head EmptyPairWord8Double = errorEmptyList "head"
    head (ConsPairWord8Double x y _) = pair x y
    tail EmptyPairWord8Double = errorEmptyList "tail"
    tail (ConsPairWord8Double _ _ x) = x

instance AdaptList (Pair Word8 Float) where
    data List (Pair Word8 Float)
        = EmptyPairWord8Float
        | ConsPairWord8Float {-# UNPACK #-}!Word8 {-# UNPACK #-}!Float (List (Pair Word8 Float))
    empty = EmptyPairWord8Float
    cons x z = ConsPairWord8Float (fst x) (snd x) z
    null EmptyPairWord8Float = True
    null _ = False
    head EmptyPairWord8Float = errorEmptyList "head"
    head (ConsPairWord8Float x y _) = pair x y
    tail EmptyPairWord8Float = errorEmptyList "tail"
    tail (ConsPairWord8Float _ _ x) = x

instance AdaptList (Pair Word8 Char) where
    data List (Pair Word8 Char)
        = EmptyPairWord8Char
        | ConsPairWord8Char {-# UNPACK #-}!Word8 {-# UNPACK #-}!Char (List (Pair Word8 Char))
    empty = EmptyPairWord8Char
    cons x z = ConsPairWord8Char (fst x) (snd x) z
    null EmptyPairWord8Char = True
    null _ = False
    head EmptyPairWord8Char = errorEmptyList "head"
    head (ConsPairWord8Char x y _) = pair x y
    tail EmptyPairWord8Char = errorEmptyList "tail"
    tail (ConsPairWord8Char _ _ x) = x

instance AdaptList (Pair Word16 Int) where
    data List (Pair Word16 Int)
        = EmptyPairWord16Int
        | ConsPairWord16Int {-# UNPACK #-}!Word16 {-# UNPACK #-}!Int (List (Pair Word16 Int))
    empty = EmptyPairWord16Int
    cons x z = ConsPairWord16Int (fst x) (snd x) z
    null EmptyPairWord16Int = True
    null _ = False
    head EmptyPairWord16Int = errorEmptyList "head"
    head (ConsPairWord16Int x y _) = pair x y
    tail EmptyPairWord16Int = errorEmptyList "tail"
    tail (ConsPairWord16Int _ _ x) = x

instance AdaptList (Pair Word16 Integer) where
    data List (Pair Word16 Integer)
        = EmptyPairWord16Integer
        | ConsPairWord16Integer {-# UNPACK #-}!Word16 {-# UNPACK #-}!Integer (List (Pair Word16 Integer))
    empty = EmptyPairWord16Integer
    cons x z = ConsPairWord16Integer (fst x) (snd x) z
    null EmptyPairWord16Integer = True
    null _ = False
    head EmptyPairWord16Integer = errorEmptyList "head"
    head (ConsPairWord16Integer x y _) = pair x y
    tail EmptyPairWord16Integer = errorEmptyList "tail"
    tail (ConsPairWord16Integer _ _ x) = x

instance AdaptList (Pair Word16 Int8) where
    data List (Pair Word16 Int8)
        = EmptyPairWord16Int8
        | ConsPairWord16Int8 {-# UNPACK #-}!Word16 {-# UNPACK #-}!Int8 (List (Pair Word16 Int8))
    empty = EmptyPairWord16Int8
    cons x z = ConsPairWord16Int8 (fst x) (snd x) z
    null EmptyPairWord16Int8 = True
    null _ = False
    head EmptyPairWord16Int8 = errorEmptyList "head"
    head (ConsPairWord16Int8 x y _) = pair x y
    tail EmptyPairWord16Int8 = errorEmptyList "tail"
    tail (ConsPairWord16Int8 _ _ x) = x

instance AdaptList (Pair Word16 Int16) where
    data List (Pair Word16 Int16)
        = EmptyPairWord16Int16
        | ConsPairWord16Int16 {-# UNPACK #-}!Word16 {-# UNPACK #-}!Int16 (List (Pair Word16 Int16))
    empty = EmptyPairWord16Int16
    cons x z = ConsPairWord16Int16 (fst x) (snd x) z
    null EmptyPairWord16Int16 = True
    null _ = False
    head EmptyPairWord16Int16 = errorEmptyList "head"
    head (ConsPairWord16Int16 x y _) = pair x y
    tail EmptyPairWord16Int16 = errorEmptyList "tail"
    tail (ConsPairWord16Int16 _ _ x) = x

instance AdaptList (Pair Word16 Int32) where
    data List (Pair Word16 Int32)
        = EmptyPairWord16Int32
        | ConsPairWord16Int32 {-# UNPACK #-}!Word16 {-# UNPACK #-}!Int32 (List (Pair Word16 Int32))
    empty = EmptyPairWord16Int32
    cons x z = ConsPairWord16Int32 (fst x) (snd x) z
    null EmptyPairWord16Int32 = True
    null _ = False
    head EmptyPairWord16Int32 = errorEmptyList "head"
    head (ConsPairWord16Int32 x y _) = pair x y
    tail EmptyPairWord16Int32 = errorEmptyList "tail"
    tail (ConsPairWord16Int32 _ _ x) = x

instance AdaptList (Pair Word16 Int64) where
    data List (Pair Word16 Int64)
        = EmptyPairWord16Int64
        | ConsPairWord16Int64 {-# UNPACK #-}!Word16 {-# UNPACK #-}!Int64 (List (Pair Word16 Int64))
    empty = EmptyPairWord16Int64
    cons x z = ConsPairWord16Int64 (fst x) (snd x) z
    null EmptyPairWord16Int64 = True
    null _ = False
    head EmptyPairWord16Int64 = errorEmptyList "head"
    head (ConsPairWord16Int64 x y _) = pair x y
    tail EmptyPairWord16Int64 = errorEmptyList "tail"
    tail (ConsPairWord16Int64 _ _ x) = x

instance AdaptList (Pair Word16 Word) where
    data List (Pair Word16 Word)
        = EmptyPairWord16Word
        | ConsPairWord16Word {-# UNPACK #-}!Word16 {-# UNPACK #-}!Word (List (Pair Word16 Word))
    empty = EmptyPairWord16Word
    cons x z = ConsPairWord16Word (fst x) (snd x) z
    null EmptyPairWord16Word = True
    null _ = False
    head EmptyPairWord16Word = errorEmptyList "head"
    head (ConsPairWord16Word x y _) = pair x y
    tail EmptyPairWord16Word = errorEmptyList "tail"
    tail (ConsPairWord16Word _ _ x) = x

instance AdaptList (Pair Word16 Word8) where
    data List (Pair Word16 Word8)
        = EmptyPairWord16Word8
        | ConsPairWord16Word8 {-# UNPACK #-}!Word16 {-# UNPACK #-}!Word8 (List (Pair Word16 Word8))
    empty = EmptyPairWord16Word8
    cons x z = ConsPairWord16Word8 (fst x) (snd x) z
    null EmptyPairWord16Word8 = True
    null _ = False
    head EmptyPairWord16Word8 = errorEmptyList "head"
    head (ConsPairWord16Word8 x y _) = pair x y
    tail EmptyPairWord16Word8 = errorEmptyList "tail"
    tail (ConsPairWord16Word8 _ _ x) = x

instance AdaptList (Pair Word16 Word16) where
    data List (Pair Word16 Word16)
        = EmptyPairWord16Word16
        | ConsPairWord16Word16 {-# UNPACK #-}!Word16 {-# UNPACK #-}!Word16 (List (Pair Word16 Word16))
    empty = EmptyPairWord16Word16
    cons x z = ConsPairWord16Word16 (fst x) (snd x) z
    null EmptyPairWord16Word16 = True
    null _ = False
    head EmptyPairWord16Word16 = errorEmptyList "head"
    head (ConsPairWord16Word16 x y _) = pair x y
    tail EmptyPairWord16Word16 = errorEmptyList "tail"
    tail (ConsPairWord16Word16 _ _ x) = x

instance AdaptList (Pair Word16 Word32) where
    data List (Pair Word16 Word32)
        = EmptyPairWord16Word32
        | ConsPairWord16Word32 {-# UNPACK #-}!Word16 {-# UNPACK #-}!Word32 (List (Pair Word16 Word32))
    empty = EmptyPairWord16Word32
    cons x z = ConsPairWord16Word32 (fst x) (snd x) z
    null EmptyPairWord16Word32 = True
    null _ = False
    head EmptyPairWord16Word32 = errorEmptyList "head"
    head (ConsPairWord16Word32 x y _) = pair x y
    tail EmptyPairWord16Word32 = errorEmptyList "tail"
    tail (ConsPairWord16Word32 _ _ x) = x

instance AdaptList (Pair Word16 Word64) where
    data List (Pair Word16 Word64)
        = EmptyPairWord16Word64
        | ConsPairWord16Word64 {-# UNPACK #-}!Word16 {-# UNPACK #-}!Word64 (List (Pair Word16 Word64))
    empty = EmptyPairWord16Word64
    cons x z = ConsPairWord16Word64 (fst x) (snd x) z
    null EmptyPairWord16Word64 = True
    null _ = False
    head EmptyPairWord16Word64 = errorEmptyList "head"
    head (ConsPairWord16Word64 x y _) = pair x y
    tail EmptyPairWord16Word64 = errorEmptyList "tail"
    tail (ConsPairWord16Word64 _ _ x) = x

instance AdaptList (Pair Word16 Double) where
    data List (Pair Word16 Double)
        = EmptyPairWord16Double
        | ConsPairWord16Double {-# UNPACK #-}!Word16 {-# UNPACK #-}!Double (List (Pair Word16 Double))
    empty = EmptyPairWord16Double
    cons x z = ConsPairWord16Double (fst x) (snd x) z
    null EmptyPairWord16Double = True
    null _ = False
    head EmptyPairWord16Double = errorEmptyList "head"
    head (ConsPairWord16Double x y _) = pair x y
    tail EmptyPairWord16Double = errorEmptyList "tail"
    tail (ConsPairWord16Double _ _ x) = x

instance AdaptList (Pair Word16 Float) where
    data List (Pair Word16 Float)
        = EmptyPairWord16Float
        | ConsPairWord16Float {-# UNPACK #-}!Word16 {-# UNPACK #-}!Float (List (Pair Word16 Float))
    empty = EmptyPairWord16Float
    cons x z = ConsPairWord16Float (fst x) (snd x) z
    null EmptyPairWord16Float = True
    null _ = False
    head EmptyPairWord16Float = errorEmptyList "head"
    head (ConsPairWord16Float x y _) = pair x y
    tail EmptyPairWord16Float = errorEmptyList "tail"
    tail (ConsPairWord16Float _ _ x) = x

instance AdaptList (Pair Word16 Char) where
    data List (Pair Word16 Char)
        = EmptyPairWord16Char
        | ConsPairWord16Char {-# UNPACK #-}!Word16 {-# UNPACK #-}!Char (List (Pair Word16 Char))
    empty = EmptyPairWord16Char
    cons x z = ConsPairWord16Char (fst x) (snd x) z
    null EmptyPairWord16Char = True
    null _ = False
    head EmptyPairWord16Char = errorEmptyList "head"
    head (ConsPairWord16Char x y _) = pair x y
    tail EmptyPairWord16Char = errorEmptyList "tail"
    tail (ConsPairWord16Char _ _ x) = x

instance AdaptList (Pair Word32 Int) where
    data List (Pair Word32 Int)
        = EmptyPairWord32Int
        | ConsPairWord32Int {-# UNPACK #-}!Word32 {-# UNPACK #-}!Int (List (Pair Word32 Int))
    empty = EmptyPairWord32Int
    cons x z = ConsPairWord32Int (fst x) (snd x) z
    null EmptyPairWord32Int = True
    null _ = False
    head EmptyPairWord32Int = errorEmptyList "head"
    head (ConsPairWord32Int x y _) = pair x y
    tail EmptyPairWord32Int = errorEmptyList "tail"
    tail (ConsPairWord32Int _ _ x) = x

instance AdaptList (Pair Word32 Integer) where
    data List (Pair Word32 Integer)
        = EmptyPairWord32Integer
        | ConsPairWord32Integer {-# UNPACK #-}!Word32 {-# UNPACK #-}!Integer (List (Pair Word32 Integer))
    empty = EmptyPairWord32Integer
    cons x z = ConsPairWord32Integer (fst x) (snd x) z
    null EmptyPairWord32Integer = True
    null _ = False
    head EmptyPairWord32Integer = errorEmptyList "head"
    head (ConsPairWord32Integer x y _) = pair x y
    tail EmptyPairWord32Integer = errorEmptyList "tail"
    tail (ConsPairWord32Integer _ _ x) = x

instance AdaptList (Pair Word32 Int8) where
    data List (Pair Word32 Int8)
        = EmptyPairWord32Int8
        | ConsPairWord32Int8 {-# UNPACK #-}!Word32 {-# UNPACK #-}!Int8 (List (Pair Word32 Int8))
    empty = EmptyPairWord32Int8
    cons x z = ConsPairWord32Int8 (fst x) (snd x) z
    null EmptyPairWord32Int8 = True
    null _ = False
    head EmptyPairWord32Int8 = errorEmptyList "head"
    head (ConsPairWord32Int8 x y _) = pair x y
    tail EmptyPairWord32Int8 = errorEmptyList "tail"
    tail (ConsPairWord32Int8 _ _ x) = x

instance AdaptList (Pair Word32 Int16) where
    data List (Pair Word32 Int16)
        = EmptyPairWord32Int16
        | ConsPairWord32Int16 {-# UNPACK #-}!Word32 {-# UNPACK #-}!Int16 (List (Pair Word32 Int16))
    empty = EmptyPairWord32Int16
    cons x z = ConsPairWord32Int16 (fst x) (snd x) z
    null EmptyPairWord32Int16 = True
    null _ = False
    head EmptyPairWord32Int16 = errorEmptyList "head"
    head (ConsPairWord32Int16 x y _) = pair x y
    tail EmptyPairWord32Int16 = errorEmptyList "tail"
    tail (ConsPairWord32Int16 _ _ x) = x

instance AdaptList (Pair Word32 Int32) where
    data List (Pair Word32 Int32)
        = EmptyPairWord32Int32
        | ConsPairWord32Int32 {-# UNPACK #-}!Word32 {-# UNPACK #-}!Int32 (List (Pair Word32 Int32))
    empty = EmptyPairWord32Int32
    cons x z = ConsPairWord32Int32 (fst x) (snd x) z
    null EmptyPairWord32Int32 = True
    null _ = False
    head EmptyPairWord32Int32 = errorEmptyList "head"
    head (ConsPairWord32Int32 x y _) = pair x y
    tail EmptyPairWord32Int32 = errorEmptyList "tail"
    tail (ConsPairWord32Int32 _ _ x) = x

instance AdaptList (Pair Word32 Int64) where
    data List (Pair Word32 Int64)
        = EmptyPairWord32Int64
        | ConsPairWord32Int64 {-# UNPACK #-}!Word32 {-# UNPACK #-}!Int64 (List (Pair Word32 Int64))
    empty = EmptyPairWord32Int64
    cons x z = ConsPairWord32Int64 (fst x) (snd x) z
    null EmptyPairWord32Int64 = True
    null _ = False
    head EmptyPairWord32Int64 = errorEmptyList "head"
    head (ConsPairWord32Int64 x y _) = pair x y
    tail EmptyPairWord32Int64 = errorEmptyList "tail"
    tail (ConsPairWord32Int64 _ _ x) = x

instance AdaptList (Pair Word32 Word) where
    data List (Pair Word32 Word)
        = EmptyPairWord32Word
        | ConsPairWord32Word {-# UNPACK #-}!Word32 {-# UNPACK #-}!Word (List (Pair Word32 Word))
    empty = EmptyPairWord32Word
    cons x z = ConsPairWord32Word (fst x) (snd x) z
    null EmptyPairWord32Word = True
    null _ = False
    head EmptyPairWord32Word = errorEmptyList "head"
    head (ConsPairWord32Word x y _) = pair x y
    tail EmptyPairWord32Word = errorEmptyList "tail"
    tail (ConsPairWord32Word _ _ x) = x

instance AdaptList (Pair Word32 Word8) where
    data List (Pair Word32 Word8)
        = EmptyPairWord32Word8
        | ConsPairWord32Word8 {-# UNPACK #-}!Word32 {-# UNPACK #-}!Word8 (List (Pair Word32 Word8))
    empty = EmptyPairWord32Word8
    cons x z = ConsPairWord32Word8 (fst x) (snd x) z
    null EmptyPairWord32Word8 = True
    null _ = False
    head EmptyPairWord32Word8 = errorEmptyList "head"
    head (ConsPairWord32Word8 x y _) = pair x y
    tail EmptyPairWord32Word8 = errorEmptyList "tail"
    tail (ConsPairWord32Word8 _ _ x) = x

instance AdaptList (Pair Word32 Word16) where
    data List (Pair Word32 Word16)
        = EmptyPairWord32Word16
        | ConsPairWord32Word16 {-# UNPACK #-}!Word32 {-# UNPACK #-}!Word16 (List (Pair Word32 Word16))
    empty = EmptyPairWord32Word16
    cons x z = ConsPairWord32Word16 (fst x) (snd x) z
    null EmptyPairWord32Word16 = True
    null _ = False
    head EmptyPairWord32Word16 = errorEmptyList "head"
    head (ConsPairWord32Word16 x y _) = pair x y
    tail EmptyPairWord32Word16 = errorEmptyList "tail"
    tail (ConsPairWord32Word16 _ _ x) = x

instance AdaptList (Pair Word32 Word32) where
    data List (Pair Word32 Word32)
        = EmptyPairWord32Word32
        | ConsPairWord32Word32 {-# UNPACK #-}!Word32 {-# UNPACK #-}!Word32 (List (Pair Word32 Word32))
    empty = EmptyPairWord32Word32
    cons x z = ConsPairWord32Word32 (fst x) (snd x) z
    null EmptyPairWord32Word32 = True
    null _ = False
    head EmptyPairWord32Word32 = errorEmptyList "head"
    head (ConsPairWord32Word32 x y _) = pair x y
    tail EmptyPairWord32Word32 = errorEmptyList "tail"
    tail (ConsPairWord32Word32 _ _ x) = x

instance AdaptList (Pair Word32 Word64) where
    data List (Pair Word32 Word64)
        = EmptyPairWord32Word64
        | ConsPairWord32Word64 {-# UNPACK #-}!Word32 {-# UNPACK #-}!Word64 (List (Pair Word32 Word64))
    empty = EmptyPairWord32Word64
    cons x z = ConsPairWord32Word64 (fst x) (snd x) z
    null EmptyPairWord32Word64 = True
    null _ = False
    head EmptyPairWord32Word64 = errorEmptyList "head"
    head (ConsPairWord32Word64 x y _) = pair x y
    tail EmptyPairWord32Word64 = errorEmptyList "tail"
    tail (ConsPairWord32Word64 _ _ x) = x

instance AdaptList (Pair Word32 Double) where
    data List (Pair Word32 Double)
        = EmptyPairWord32Double
        | ConsPairWord32Double {-# UNPACK #-}!Word32 {-# UNPACK #-}!Double (List (Pair Word32 Double))
    empty = EmptyPairWord32Double
    cons x z = ConsPairWord32Double (fst x) (snd x) z
    null EmptyPairWord32Double = True
    null _ = False
    head EmptyPairWord32Double = errorEmptyList "head"
    head (ConsPairWord32Double x y _) = pair x y
    tail EmptyPairWord32Double = errorEmptyList "tail"
    tail (ConsPairWord32Double _ _ x) = x

instance AdaptList (Pair Word32 Float) where
    data List (Pair Word32 Float)
        = EmptyPairWord32Float
        | ConsPairWord32Float {-# UNPACK #-}!Word32 {-# UNPACK #-}!Float (List (Pair Word32 Float))
    empty = EmptyPairWord32Float
    cons x z = ConsPairWord32Float (fst x) (snd x) z
    null EmptyPairWord32Float = True
    null _ = False
    head EmptyPairWord32Float = errorEmptyList "head"
    head (ConsPairWord32Float x y _) = pair x y
    tail EmptyPairWord32Float = errorEmptyList "tail"
    tail (ConsPairWord32Float _ _ x) = x

instance AdaptList (Pair Word32 Char) where
    data List (Pair Word32 Char)
        = EmptyPairWord32Char
        | ConsPairWord32Char {-# UNPACK #-}!Word32 {-# UNPACK #-}!Char (List (Pair Word32 Char))
    empty = EmptyPairWord32Char
    cons x z = ConsPairWord32Char (fst x) (snd x) z
    null EmptyPairWord32Char = True
    null _ = False
    head EmptyPairWord32Char = errorEmptyList "head"
    head (ConsPairWord32Char x y _) = pair x y
    tail EmptyPairWord32Char = errorEmptyList "tail"
    tail (ConsPairWord32Char _ _ x) = x

instance AdaptList (Pair Word64 Int) where
    data List (Pair Word64 Int)
        = EmptyPairWord64Int
        | ConsPairWord64Int {-# UNPACK #-}!Word64 {-# UNPACK #-}!Int (List (Pair Word64 Int))
    empty = EmptyPairWord64Int
    cons x z = ConsPairWord64Int (fst x) (snd x) z
    null EmptyPairWord64Int = True
    null _ = False
    head EmptyPairWord64Int = errorEmptyList "head"
    head (ConsPairWord64Int x y _) = pair x y
    tail EmptyPairWord64Int = errorEmptyList "tail"
    tail (ConsPairWord64Int _ _ x) = x

instance AdaptList (Pair Word64 Integer) where
    data List (Pair Word64 Integer)
        = EmptyPairWord64Integer
        | ConsPairWord64Integer {-# UNPACK #-}!Word64 {-# UNPACK #-}!Integer (List (Pair Word64 Integer))
    empty = EmptyPairWord64Integer
    cons x z = ConsPairWord64Integer (fst x) (snd x) z
    null EmptyPairWord64Integer = True
    null _ = False
    head EmptyPairWord64Integer = errorEmptyList "head"
    head (ConsPairWord64Integer x y _) = pair x y
    tail EmptyPairWord64Integer = errorEmptyList "tail"
    tail (ConsPairWord64Integer _ _ x) = x

instance AdaptList (Pair Word64 Int8) where
    data List (Pair Word64 Int8)
        = EmptyPairWord64Int8
        | ConsPairWord64Int8 {-# UNPACK #-}!Word64 {-# UNPACK #-}!Int8 (List (Pair Word64 Int8))
    empty = EmptyPairWord64Int8
    cons x z = ConsPairWord64Int8 (fst x) (snd x) z
    null EmptyPairWord64Int8 = True
    null _ = False
    head EmptyPairWord64Int8 = errorEmptyList "head"
    head (ConsPairWord64Int8 x y _) = pair x y
    tail EmptyPairWord64Int8 = errorEmptyList "tail"
    tail (ConsPairWord64Int8 _ _ x) = x

instance AdaptList (Pair Word64 Int16) where
    data List (Pair Word64 Int16)
        = EmptyPairWord64Int16
        | ConsPairWord64Int16 {-# UNPACK #-}!Word64 {-# UNPACK #-}!Int16 (List (Pair Word64 Int16))
    empty = EmptyPairWord64Int16
    cons x z = ConsPairWord64Int16 (fst x) (snd x) z
    null EmptyPairWord64Int16 = True
    null _ = False
    head EmptyPairWord64Int16 = errorEmptyList "head"
    head (ConsPairWord64Int16 x y _) = pair x y
    tail EmptyPairWord64Int16 = errorEmptyList "tail"
    tail (ConsPairWord64Int16 _ _ x) = x

instance AdaptList (Pair Word64 Int32) where
    data List (Pair Word64 Int32)
        = EmptyPairWord64Int32
        | ConsPairWord64Int32 {-# UNPACK #-}!Word64 {-# UNPACK #-}!Int32 (List (Pair Word64 Int32))
    empty = EmptyPairWord64Int32
    cons x z = ConsPairWord64Int32 (fst x) (snd x) z
    null EmptyPairWord64Int32 = True
    null _ = False
    head EmptyPairWord64Int32 = errorEmptyList "head"
    head (ConsPairWord64Int32 x y _) = pair x y
    tail EmptyPairWord64Int32 = errorEmptyList "tail"
    tail (ConsPairWord64Int32 _ _ x) = x

instance AdaptList (Pair Word64 Int64) where
    data List (Pair Word64 Int64)
        = EmptyPairWord64Int64
        | ConsPairWord64Int64 {-# UNPACK #-}!Word64 {-# UNPACK #-}!Int64 (List (Pair Word64 Int64))
    empty = EmptyPairWord64Int64
    cons x z = ConsPairWord64Int64 (fst x) (snd x) z
    null EmptyPairWord64Int64 = True
    null _ = False
    head EmptyPairWord64Int64 = errorEmptyList "head"
    head (ConsPairWord64Int64 x y _) = pair x y
    tail EmptyPairWord64Int64 = errorEmptyList "tail"
    tail (ConsPairWord64Int64 _ _ x) = x

instance AdaptList (Pair Word64 Word) where
    data List (Pair Word64 Word)
        = EmptyPairWord64Word
        | ConsPairWord64Word {-# UNPACK #-}!Word64 {-# UNPACK #-}!Word (List (Pair Word64 Word))
    empty = EmptyPairWord64Word
    cons x z = ConsPairWord64Word (fst x) (snd x) z
    null EmptyPairWord64Word = True
    null _ = False
    head EmptyPairWord64Word = errorEmptyList "head"
    head (ConsPairWord64Word x y _) = pair x y
    tail EmptyPairWord64Word = errorEmptyList "tail"
    tail (ConsPairWord64Word _ _ x) = x

instance AdaptList (Pair Word64 Word8) where
    data List (Pair Word64 Word8)
        = EmptyPairWord64Word8
        | ConsPairWord64Word8 {-# UNPACK #-}!Word64 {-# UNPACK #-}!Word8 (List (Pair Word64 Word8))
    empty = EmptyPairWord64Word8
    cons x z = ConsPairWord64Word8 (fst x) (snd x) z
    null EmptyPairWord64Word8 = True
    null _ = False
    head EmptyPairWord64Word8 = errorEmptyList "head"
    head (ConsPairWord64Word8 x y _) = pair x y
    tail EmptyPairWord64Word8 = errorEmptyList "tail"
    tail (ConsPairWord64Word8 _ _ x) = x

instance AdaptList (Pair Word64 Word16) where
    data List (Pair Word64 Word16)
        = EmptyPairWord64Word16
        | ConsPairWord64Word16 {-# UNPACK #-}!Word64 {-# UNPACK #-}!Word16 (List (Pair Word64 Word16))
    empty = EmptyPairWord64Word16
    cons x z = ConsPairWord64Word16 (fst x) (snd x) z
    null EmptyPairWord64Word16 = True
    null _ = False
    head EmptyPairWord64Word16 = errorEmptyList "head"
    head (ConsPairWord64Word16 x y _) = pair x y
    tail EmptyPairWord64Word16 = errorEmptyList "tail"
    tail (ConsPairWord64Word16 _ _ x) = x

instance AdaptList (Pair Word64 Word32) where
    data List (Pair Word64 Word32)
        = EmptyPairWord64Word32
        | ConsPairWord64Word32 {-# UNPACK #-}!Word64 {-# UNPACK #-}!Word32 (List (Pair Word64 Word32))
    empty = EmptyPairWord64Word32
    cons x z = ConsPairWord64Word32 (fst x) (snd x) z
    null EmptyPairWord64Word32 = True
    null _ = False
    head EmptyPairWord64Word32 = errorEmptyList "head"
    head (ConsPairWord64Word32 x y _) = pair x y
    tail EmptyPairWord64Word32 = errorEmptyList "tail"
    tail (ConsPairWord64Word32 _ _ x) = x

instance AdaptList (Pair Word64 Word64) where
    data List (Pair Word64 Word64)
        = EmptyPairWord64Word64
        | ConsPairWord64Word64 {-# UNPACK #-}!Word64 {-# UNPACK #-}!Word64 (List (Pair Word64 Word64))
    empty = EmptyPairWord64Word64
    cons x z = ConsPairWord64Word64 (fst x) (snd x) z
    null EmptyPairWord64Word64 = True
    null _ = False
    head EmptyPairWord64Word64 = errorEmptyList "head"
    head (ConsPairWord64Word64 x y _) = pair x y
    tail EmptyPairWord64Word64 = errorEmptyList "tail"
    tail (ConsPairWord64Word64 _ _ x) = x

instance AdaptList (Pair Word64 Double) where
    data List (Pair Word64 Double)
        = EmptyPairWord64Double
        | ConsPairWord64Double {-# UNPACK #-}!Word64 {-# UNPACK #-}!Double (List (Pair Word64 Double))
    empty = EmptyPairWord64Double
    cons x z = ConsPairWord64Double (fst x) (snd x) z
    null EmptyPairWord64Double = True
    null _ = False
    head EmptyPairWord64Double = errorEmptyList "head"
    head (ConsPairWord64Double x y _) = pair x y
    tail EmptyPairWord64Double = errorEmptyList "tail"
    tail (ConsPairWord64Double _ _ x) = x

instance AdaptList (Pair Word64 Float) where
    data List (Pair Word64 Float)
        = EmptyPairWord64Float
        | ConsPairWord64Float {-# UNPACK #-}!Word64 {-# UNPACK #-}!Float (List (Pair Word64 Float))
    empty = EmptyPairWord64Float
    cons x z = ConsPairWord64Float (fst x) (snd x) z
    null EmptyPairWord64Float = True
    null _ = False
    head EmptyPairWord64Float = errorEmptyList "head"
    head (ConsPairWord64Float x y _) = pair x y
    tail EmptyPairWord64Float = errorEmptyList "tail"
    tail (ConsPairWord64Float _ _ x) = x

instance AdaptList (Pair Word64 Char) where
    data List (Pair Word64 Char)
        = EmptyPairWord64Char
        | ConsPairWord64Char {-# UNPACK #-}!Word64 {-# UNPACK #-}!Char (List (Pair Word64 Char))
    empty = EmptyPairWord64Char
    cons x z = ConsPairWord64Char (fst x) (snd x) z
    null EmptyPairWord64Char = True
    null _ = False
    head EmptyPairWord64Char = errorEmptyList "head"
    head (ConsPairWord64Char x y _) = pair x y
    tail EmptyPairWord64Char = errorEmptyList "tail"
    tail (ConsPairWord64Char _ _ x) = x

instance AdaptList (Pair Double Int) where
    data List (Pair Double Int)
        = EmptyPairDoubleInt
        | ConsPairDoubleInt {-# UNPACK #-}!Double {-# UNPACK #-}!Int (List (Pair Double Int))
    empty = EmptyPairDoubleInt
    cons x z = ConsPairDoubleInt (fst x) (snd x) z
    null EmptyPairDoubleInt = True
    null _ = False
    head EmptyPairDoubleInt = errorEmptyList "head"
    head (ConsPairDoubleInt x y _) = pair x y
    tail EmptyPairDoubleInt = errorEmptyList "tail"
    tail (ConsPairDoubleInt _ _ x) = x

instance AdaptList (Pair Double Integer) where
    data List (Pair Double Integer)
        = EmptyPairDoubleInteger
        | ConsPairDoubleInteger {-# UNPACK #-}!Double {-# UNPACK #-}!Integer (List (Pair Double Integer))
    empty = EmptyPairDoubleInteger
    cons x z = ConsPairDoubleInteger (fst x) (snd x) z
    null EmptyPairDoubleInteger = True
    null _ = False
    head EmptyPairDoubleInteger = errorEmptyList "head"
    head (ConsPairDoubleInteger x y _) = pair x y
    tail EmptyPairDoubleInteger = errorEmptyList "tail"
    tail (ConsPairDoubleInteger _ _ x) = x

instance AdaptList (Pair Double Int8) where
    data List (Pair Double Int8)
        = EmptyPairDoubleInt8
        | ConsPairDoubleInt8 {-# UNPACK #-}!Double {-# UNPACK #-}!Int8 (List (Pair Double Int8))
    empty = EmptyPairDoubleInt8
    cons x z = ConsPairDoubleInt8 (fst x) (snd x) z
    null EmptyPairDoubleInt8 = True
    null _ = False
    head EmptyPairDoubleInt8 = errorEmptyList "head"
    head (ConsPairDoubleInt8 x y _) = pair x y
    tail EmptyPairDoubleInt8 = errorEmptyList "tail"
    tail (ConsPairDoubleInt8 _ _ x) = x

instance AdaptList (Pair Double Int16) where
    data List (Pair Double Int16)
        = EmptyPairDoubleInt16
        | ConsPairDoubleInt16 {-# UNPACK #-}!Double {-# UNPACK #-}!Int16 (List (Pair Double Int16))
    empty = EmptyPairDoubleInt16
    cons x z = ConsPairDoubleInt16 (fst x) (snd x) z
    null EmptyPairDoubleInt16 = True
    null _ = False
    head EmptyPairDoubleInt16 = errorEmptyList "head"
    head (ConsPairDoubleInt16 x y _) = pair x y
    tail EmptyPairDoubleInt16 = errorEmptyList "tail"
    tail (ConsPairDoubleInt16 _ _ x) = x

instance AdaptList (Pair Double Int32) where
    data List (Pair Double Int32)
        = EmptyPairDoubleInt32
        | ConsPairDoubleInt32 {-# UNPACK #-}!Double {-# UNPACK #-}!Int32 (List (Pair Double Int32))
    empty = EmptyPairDoubleInt32
    cons x z = ConsPairDoubleInt32 (fst x) (snd x) z
    null EmptyPairDoubleInt32 = True
    null _ = False
    head EmptyPairDoubleInt32 = errorEmptyList "head"
    head (ConsPairDoubleInt32 x y _) = pair x y
    tail EmptyPairDoubleInt32 = errorEmptyList "tail"
    tail (ConsPairDoubleInt32 _ _ x) = x

instance AdaptList (Pair Double Int64) where
    data List (Pair Double Int64)
        = EmptyPairDoubleInt64
        | ConsPairDoubleInt64 {-# UNPACK #-}!Double {-# UNPACK #-}!Int64 (List (Pair Double Int64))
    empty = EmptyPairDoubleInt64
    cons x z = ConsPairDoubleInt64 (fst x) (snd x) z
    null EmptyPairDoubleInt64 = True
    null _ = False
    head EmptyPairDoubleInt64 = errorEmptyList "head"
    head (ConsPairDoubleInt64 x y _) = pair x y
    tail EmptyPairDoubleInt64 = errorEmptyList "tail"
    tail (ConsPairDoubleInt64 _ _ x) = x

instance AdaptList (Pair Double Word) where
    data List (Pair Double Word)
        = EmptyPairDoubleWord
        | ConsPairDoubleWord {-# UNPACK #-}!Double {-# UNPACK #-}!Word (List (Pair Double Word))
    empty = EmptyPairDoubleWord
    cons x z = ConsPairDoubleWord (fst x) (snd x) z
    null EmptyPairDoubleWord = True
    null _ = False
    head EmptyPairDoubleWord = errorEmptyList "head"
    head (ConsPairDoubleWord x y _) = pair x y
    tail EmptyPairDoubleWord = errorEmptyList "tail"
    tail (ConsPairDoubleWord _ _ x) = x

instance AdaptList (Pair Double Word8) where
    data List (Pair Double Word8)
        = EmptyPairDoubleWord8
        | ConsPairDoubleWord8 {-# UNPACK #-}!Double {-# UNPACK #-}!Word8 (List (Pair Double Word8))
    empty = EmptyPairDoubleWord8
    cons x z = ConsPairDoubleWord8 (fst x) (snd x) z
    null EmptyPairDoubleWord8 = True
    null _ = False
    head EmptyPairDoubleWord8 = errorEmptyList "head"
    head (ConsPairDoubleWord8 x y _) = pair x y
    tail EmptyPairDoubleWord8 = errorEmptyList "tail"
    tail (ConsPairDoubleWord8 _ _ x) = x

instance AdaptList (Pair Double Word16) where
    data List (Pair Double Word16)
        = EmptyPairDoubleWord16
        | ConsPairDoubleWord16 {-# UNPACK #-}!Double {-# UNPACK #-}!Word16 (List (Pair Double Word16))
    empty = EmptyPairDoubleWord16
    cons x z = ConsPairDoubleWord16 (fst x) (snd x) z
    null EmptyPairDoubleWord16 = True
    null _ = False
    head EmptyPairDoubleWord16 = errorEmptyList "head"
    head (ConsPairDoubleWord16 x y _) = pair x y
    tail EmptyPairDoubleWord16 = errorEmptyList "tail"
    tail (ConsPairDoubleWord16 _ _ x) = x

instance AdaptList (Pair Double Word32) where
    data List (Pair Double Word32)
        = EmptyPairDoubleWord32
        | ConsPairDoubleWord32 {-# UNPACK #-}!Double {-# UNPACK #-}!Word32 (List (Pair Double Word32))
    empty = EmptyPairDoubleWord32
    cons x z = ConsPairDoubleWord32 (fst x) (snd x) z
    null EmptyPairDoubleWord32 = True
    null _ = False
    head EmptyPairDoubleWord32 = errorEmptyList "head"
    head (ConsPairDoubleWord32 x y _) = pair x y
    tail EmptyPairDoubleWord32 = errorEmptyList "tail"
    tail (ConsPairDoubleWord32 _ _ x) = x

instance AdaptList (Pair Double Word64) where
    data List (Pair Double Word64)
        = EmptyPairDoubleWord64
        | ConsPairDoubleWord64 {-# UNPACK #-}!Double {-# UNPACK #-}!Word64 (List (Pair Double Word64))
    empty = EmptyPairDoubleWord64
    cons x z = ConsPairDoubleWord64 (fst x) (snd x) z
    null EmptyPairDoubleWord64 = True
    null _ = False
    head EmptyPairDoubleWord64 = errorEmptyList "head"
    head (ConsPairDoubleWord64 x y _) = pair x y
    tail EmptyPairDoubleWord64 = errorEmptyList "tail"
    tail (ConsPairDoubleWord64 _ _ x) = x

instance AdaptList (Pair Double Double) where
    data List (Pair Double Double)
        = EmptyPairDoubleDouble
        | ConsPairDoubleDouble {-# UNPACK #-}!Double {-# UNPACK #-}!Double (List (Pair Double Double))
    empty = EmptyPairDoubleDouble
    cons x z = ConsPairDoubleDouble (fst x) (snd x) z
    null EmptyPairDoubleDouble = True
    null _ = False
    head EmptyPairDoubleDouble = errorEmptyList "head"
    head (ConsPairDoubleDouble x y _) = pair x y
    tail EmptyPairDoubleDouble = errorEmptyList "tail"
    tail (ConsPairDoubleDouble _ _ x) = x

instance AdaptList (Pair Double Float) where
    data List (Pair Double Float)
        = EmptyPairDoubleFloat
        | ConsPairDoubleFloat {-# UNPACK #-}!Double {-# UNPACK #-}!Float (List (Pair Double Float))
    empty = EmptyPairDoubleFloat
    cons x z = ConsPairDoubleFloat (fst x) (snd x) z
    null EmptyPairDoubleFloat = True
    null _ = False
    head EmptyPairDoubleFloat = errorEmptyList "head"
    head (ConsPairDoubleFloat x y _) = pair x y
    tail EmptyPairDoubleFloat = errorEmptyList "tail"
    tail (ConsPairDoubleFloat _ _ x) = x

instance AdaptList (Pair Double Char) where
    data List (Pair Double Char)
        = EmptyPairDoubleChar
        | ConsPairDoubleChar {-# UNPACK #-}!Double {-# UNPACK #-}!Char (List (Pair Double Char))
    empty = EmptyPairDoubleChar
    cons x z = ConsPairDoubleChar (fst x) (snd x) z
    null EmptyPairDoubleChar = True
    null _ = False
    head EmptyPairDoubleChar = errorEmptyList "head"
    head (ConsPairDoubleChar x y _) = pair x y
    tail EmptyPairDoubleChar = errorEmptyList "tail"
    tail (ConsPairDoubleChar _ _ x) = x

instance AdaptList (Pair Float Int) where
    data List (Pair Float Int)
        = EmptyPairFloatInt
        | ConsPairFloatInt {-# UNPACK #-}!Float {-# UNPACK #-}!Int (List (Pair Float Int))
    empty = EmptyPairFloatInt
    cons x z = ConsPairFloatInt (fst x) (snd x) z
    null EmptyPairFloatInt = True
    null _ = False
    head EmptyPairFloatInt = errorEmptyList "head"
    head (ConsPairFloatInt x y _) = pair x y
    tail EmptyPairFloatInt = errorEmptyList "tail"
    tail (ConsPairFloatInt _ _ x) = x

instance AdaptList (Pair Float Integer) where
    data List (Pair Float Integer)
        = EmptyPairFloatInteger
        | ConsPairFloatInteger {-# UNPACK #-}!Float {-# UNPACK #-}!Integer (List (Pair Float Integer))
    empty = EmptyPairFloatInteger
    cons x z = ConsPairFloatInteger (fst x) (snd x) z
    null EmptyPairFloatInteger = True
    null _ = False
    head EmptyPairFloatInteger = errorEmptyList "head"
    head (ConsPairFloatInteger x y _) = pair x y
    tail EmptyPairFloatInteger = errorEmptyList "tail"
    tail (ConsPairFloatInteger _ _ x) = x

instance AdaptList (Pair Float Int8) where
    data List (Pair Float Int8)
        = EmptyPairFloatInt8
        | ConsPairFloatInt8 {-# UNPACK #-}!Float {-# UNPACK #-}!Int8 (List (Pair Float Int8))
    empty = EmptyPairFloatInt8
    cons x z = ConsPairFloatInt8 (fst x) (snd x) z
    null EmptyPairFloatInt8 = True
    null _ = False
    head EmptyPairFloatInt8 = errorEmptyList "head"
    head (ConsPairFloatInt8 x y _) = pair x y
    tail EmptyPairFloatInt8 = errorEmptyList "tail"
    tail (ConsPairFloatInt8 _ _ x) = x

instance AdaptList (Pair Float Int16) where
    data List (Pair Float Int16)
        = EmptyPairFloatInt16
        | ConsPairFloatInt16 {-# UNPACK #-}!Float {-# UNPACK #-}!Int16 (List (Pair Float Int16))
    empty = EmptyPairFloatInt16
    cons x z = ConsPairFloatInt16 (fst x) (snd x) z
    null EmptyPairFloatInt16 = True
    null _ = False
    head EmptyPairFloatInt16 = errorEmptyList "head"
    head (ConsPairFloatInt16 x y _) = pair x y
    tail EmptyPairFloatInt16 = errorEmptyList "tail"
    tail (ConsPairFloatInt16 _ _ x) = x

instance AdaptList (Pair Float Int32) where
    data List (Pair Float Int32)
        = EmptyPairFloatInt32
        | ConsPairFloatInt32 {-# UNPACK #-}!Float {-# UNPACK #-}!Int32 (List (Pair Float Int32))
    empty = EmptyPairFloatInt32
    cons x z = ConsPairFloatInt32 (fst x) (snd x) z
    null EmptyPairFloatInt32 = True
    null _ = False
    head EmptyPairFloatInt32 = errorEmptyList "head"
    head (ConsPairFloatInt32 x y _) = pair x y
    tail EmptyPairFloatInt32 = errorEmptyList "tail"
    tail (ConsPairFloatInt32 _ _ x) = x

instance AdaptList (Pair Float Int64) where
    data List (Pair Float Int64)
        = EmptyPairFloatInt64
        | ConsPairFloatInt64 {-# UNPACK #-}!Float {-# UNPACK #-}!Int64 (List (Pair Float Int64))
    empty = EmptyPairFloatInt64
    cons x z = ConsPairFloatInt64 (fst x) (snd x) z
    null EmptyPairFloatInt64 = True
    null _ = False
    head EmptyPairFloatInt64 = errorEmptyList "head"
    head (ConsPairFloatInt64 x y _) = pair x y
    tail EmptyPairFloatInt64 = errorEmptyList "tail"
    tail (ConsPairFloatInt64 _ _ x) = x

instance AdaptList (Pair Float Word) where
    data List (Pair Float Word)
        = EmptyPairFloatWord
        | ConsPairFloatWord {-# UNPACK #-}!Float {-# UNPACK #-}!Word (List (Pair Float Word))
    empty = EmptyPairFloatWord
    cons x z = ConsPairFloatWord (fst x) (snd x) z
    null EmptyPairFloatWord = True
    null _ = False
    head EmptyPairFloatWord = errorEmptyList "head"
    head (ConsPairFloatWord x y _) = pair x y
    tail EmptyPairFloatWord = errorEmptyList "tail"
    tail (ConsPairFloatWord _ _ x) = x

instance AdaptList (Pair Float Word8) where
    data List (Pair Float Word8)
        = EmptyPairFloatWord8
        | ConsPairFloatWord8 {-# UNPACK #-}!Float {-# UNPACK #-}!Word8 (List (Pair Float Word8))
    empty = EmptyPairFloatWord8
    cons x z = ConsPairFloatWord8 (fst x) (snd x) z
    null EmptyPairFloatWord8 = True
    null _ = False
    head EmptyPairFloatWord8 = errorEmptyList "head"
    head (ConsPairFloatWord8 x y _) = pair x y
    tail EmptyPairFloatWord8 = errorEmptyList "tail"
    tail (ConsPairFloatWord8 _ _ x) = x

instance AdaptList (Pair Float Word16) where
    data List (Pair Float Word16)
        = EmptyPairFloatWord16
        | ConsPairFloatWord16 {-# UNPACK #-}!Float {-# UNPACK #-}!Word16 (List (Pair Float Word16))
    empty = EmptyPairFloatWord16
    cons x z = ConsPairFloatWord16 (fst x) (snd x) z
    null EmptyPairFloatWord16 = True
    null _ = False
    head EmptyPairFloatWord16 = errorEmptyList "head"
    head (ConsPairFloatWord16 x y _) = pair x y
    tail EmptyPairFloatWord16 = errorEmptyList "tail"
    tail (ConsPairFloatWord16 _ _ x) = x

instance AdaptList (Pair Float Word32) where
    data List (Pair Float Word32)
        = EmptyPairFloatWord32
        | ConsPairFloatWord32 {-# UNPACK #-}!Float {-# UNPACK #-}!Word32 (List (Pair Float Word32))
    empty = EmptyPairFloatWord32
    cons x z = ConsPairFloatWord32 (fst x) (snd x) z
    null EmptyPairFloatWord32 = True
    null _ = False
    head EmptyPairFloatWord32 = errorEmptyList "head"
    head (ConsPairFloatWord32 x y _) = pair x y
    tail EmptyPairFloatWord32 = errorEmptyList "tail"
    tail (ConsPairFloatWord32 _ _ x) = x

instance AdaptList (Pair Float Word64) where
    data List (Pair Float Word64)
        = EmptyPairFloatWord64
        | ConsPairFloatWord64 {-# UNPACK #-}!Float {-# UNPACK #-}!Word64 (List (Pair Float Word64))
    empty = EmptyPairFloatWord64
    cons x z = ConsPairFloatWord64 (fst x) (snd x) z
    null EmptyPairFloatWord64 = True
    null _ = False
    head EmptyPairFloatWord64 = errorEmptyList "head"
    head (ConsPairFloatWord64 x y _) = pair x y
    tail EmptyPairFloatWord64 = errorEmptyList "tail"
    tail (ConsPairFloatWord64 _ _ x) = x

instance AdaptList (Pair Float Double) where
    data List (Pair Float Double)
        = EmptyPairFloatDouble
        | ConsPairFloatDouble {-# UNPACK #-}!Float {-# UNPACK #-}!Double (List (Pair Float Double))
    empty = EmptyPairFloatDouble
    cons x z = ConsPairFloatDouble (fst x) (snd x) z
    null EmptyPairFloatDouble = True
    null _ = False
    head EmptyPairFloatDouble = errorEmptyList "head"
    head (ConsPairFloatDouble x y _) = pair x y
    tail EmptyPairFloatDouble = errorEmptyList "tail"
    tail (ConsPairFloatDouble _ _ x) = x

instance AdaptList (Pair Float Float) where
    data List (Pair Float Float)
        = EmptyPairFloatFloat
        | ConsPairFloatFloat {-# UNPACK #-}!Float {-# UNPACK #-}!Float (List (Pair Float Float))
    empty = EmptyPairFloatFloat
    cons x z = ConsPairFloatFloat (fst x) (snd x) z
    null EmptyPairFloatFloat = True
    null _ = False
    head EmptyPairFloatFloat = errorEmptyList "head"
    head (ConsPairFloatFloat x y _) = pair x y
    tail EmptyPairFloatFloat = errorEmptyList "tail"
    tail (ConsPairFloatFloat _ _ x) = x

instance AdaptList (Pair Float Char) where
    data List (Pair Float Char)
        = EmptyPairFloatChar
        | ConsPairFloatChar {-# UNPACK #-}!Float {-# UNPACK #-}!Char (List (Pair Float Char))
    empty = EmptyPairFloatChar
    cons x z = ConsPairFloatChar (fst x) (snd x) z
    null EmptyPairFloatChar = True
    null _ = False
    head EmptyPairFloatChar = errorEmptyList "head"
    head (ConsPairFloatChar x y _) = pair x y
    tail EmptyPairFloatChar = errorEmptyList "tail"
    tail (ConsPairFloatChar _ _ x) = x

instance AdaptList (Pair Char Int) where
    data List (Pair Char Int)
        = EmptyPairCharInt
        | ConsPairCharInt {-# UNPACK #-}!Char {-# UNPACK #-}!Int (List (Pair Char Int))
    empty = EmptyPairCharInt
    cons x z = ConsPairCharInt (fst x) (snd x) z
    null EmptyPairCharInt = True
    null _ = False
    head EmptyPairCharInt = errorEmptyList "head"
    head (ConsPairCharInt x y _) = pair x y
    tail EmptyPairCharInt = errorEmptyList "tail"
    tail (ConsPairCharInt _ _ x) = x

instance AdaptList (Pair Char Integer) where
    data List (Pair Char Integer)
        = EmptyPairCharInteger
        | ConsPairCharInteger {-# UNPACK #-}!Char {-# UNPACK #-}!Integer (List (Pair Char Integer))
    empty = EmptyPairCharInteger
    cons x z = ConsPairCharInteger (fst x) (snd x) z
    null EmptyPairCharInteger = True
    null _ = False
    head EmptyPairCharInteger = errorEmptyList "head"
    head (ConsPairCharInteger x y _) = pair x y
    tail EmptyPairCharInteger = errorEmptyList "tail"
    tail (ConsPairCharInteger _ _ x) = x

instance AdaptList (Pair Char Int8) where
    data List (Pair Char Int8)
        = EmptyPairCharInt8
        | ConsPairCharInt8 {-# UNPACK #-}!Char {-# UNPACK #-}!Int8 (List (Pair Char Int8))
    empty = EmptyPairCharInt8
    cons x z = ConsPairCharInt8 (fst x) (snd x) z
    null EmptyPairCharInt8 = True
    null _ = False
    head EmptyPairCharInt8 = errorEmptyList "head"
    head (ConsPairCharInt8 x y _) = pair x y
    tail EmptyPairCharInt8 = errorEmptyList "tail"
    tail (ConsPairCharInt8 _ _ x) = x

instance AdaptList (Pair Char Int16) where
    data List (Pair Char Int16)
        = EmptyPairCharInt16
        | ConsPairCharInt16 {-# UNPACK #-}!Char {-# UNPACK #-}!Int16 (List (Pair Char Int16))
    empty = EmptyPairCharInt16
    cons x z = ConsPairCharInt16 (fst x) (snd x) z
    null EmptyPairCharInt16 = True
    null _ = False
    head EmptyPairCharInt16 = errorEmptyList "head"
    head (ConsPairCharInt16 x y _) = pair x y
    tail EmptyPairCharInt16 = errorEmptyList "tail"
    tail (ConsPairCharInt16 _ _ x) = x

instance AdaptList (Pair Char Int32) where
    data List (Pair Char Int32)
        = EmptyPairCharInt32
        | ConsPairCharInt32 {-# UNPACK #-}!Char {-# UNPACK #-}!Int32 (List (Pair Char Int32))
    empty = EmptyPairCharInt32
    cons x z = ConsPairCharInt32 (fst x) (snd x) z
    null EmptyPairCharInt32 = True
    null _ = False
    head EmptyPairCharInt32 = errorEmptyList "head"
    head (ConsPairCharInt32 x y _) = pair x y
    tail EmptyPairCharInt32 = errorEmptyList "tail"
    tail (ConsPairCharInt32 _ _ x) = x

instance AdaptList (Pair Char Int64) where
    data List (Pair Char Int64)
        = EmptyPairCharInt64
        | ConsPairCharInt64 {-# UNPACK #-}!Char {-# UNPACK #-}!Int64 (List (Pair Char Int64))
    empty = EmptyPairCharInt64
    cons x z = ConsPairCharInt64 (fst x) (snd x) z
    null EmptyPairCharInt64 = True
    null _ = False
    head EmptyPairCharInt64 = errorEmptyList "head"
    head (ConsPairCharInt64 x y _) = pair x y
    tail EmptyPairCharInt64 = errorEmptyList "tail"
    tail (ConsPairCharInt64 _ _ x) = x

instance AdaptList (Pair Char Word) where
    data List (Pair Char Word)
        = EmptyPairCharWord
        | ConsPairCharWord {-# UNPACK #-}!Char {-# UNPACK #-}!Word (List (Pair Char Word))
    empty = EmptyPairCharWord
    cons x z = ConsPairCharWord (fst x) (snd x) z
    null EmptyPairCharWord = True
    null _ = False
    head EmptyPairCharWord = errorEmptyList "head"
    head (ConsPairCharWord x y _) = pair x y
    tail EmptyPairCharWord = errorEmptyList "tail"
    tail (ConsPairCharWord _ _ x) = x

instance AdaptList (Pair Char Word8) where
    data List (Pair Char Word8)
        = EmptyPairCharWord8
        | ConsPairCharWord8 {-# UNPACK #-}!Char {-# UNPACK #-}!Word8 (List (Pair Char Word8))
    empty = EmptyPairCharWord8
    cons x z = ConsPairCharWord8 (fst x) (snd x) z
    null EmptyPairCharWord8 = True
    null _ = False
    head EmptyPairCharWord8 = errorEmptyList "head"
    head (ConsPairCharWord8 x y _) = pair x y
    tail EmptyPairCharWord8 = errorEmptyList "tail"
    tail (ConsPairCharWord8 _ _ x) = x

instance AdaptList (Pair Char Word16) where
    data List (Pair Char Word16)
        = EmptyPairCharWord16
        | ConsPairCharWord16 {-# UNPACK #-}!Char {-# UNPACK #-}!Word16 (List (Pair Char Word16))
    empty = EmptyPairCharWord16
    cons x z = ConsPairCharWord16 (fst x) (snd x) z
    null EmptyPairCharWord16 = True
    null _ = False
    head EmptyPairCharWord16 = errorEmptyList "head"
    head (ConsPairCharWord16 x y _) = pair x y
    tail EmptyPairCharWord16 = errorEmptyList "tail"
    tail (ConsPairCharWord16 _ _ x) = x

instance AdaptList (Pair Char Word32) where
    data List (Pair Char Word32)
        = EmptyPairCharWord32
        | ConsPairCharWord32 {-# UNPACK #-}!Char {-# UNPACK #-}!Word32 (List (Pair Char Word32))
    empty = EmptyPairCharWord32
    cons x z = ConsPairCharWord32 (fst x) (snd x) z
    null EmptyPairCharWord32 = True
    null _ = False
    head EmptyPairCharWord32 = errorEmptyList "head"
    head (ConsPairCharWord32 x y _) = pair x y
    tail EmptyPairCharWord32 = errorEmptyList "tail"
    tail (ConsPairCharWord32 _ _ x) = x

instance AdaptList (Pair Char Word64) where
    data List (Pair Char Word64)
        = EmptyPairCharWord64
        | ConsPairCharWord64 {-# UNPACK #-}!Char {-# UNPACK #-}!Word64 (List (Pair Char Word64))
    empty = EmptyPairCharWord64
    cons x z = ConsPairCharWord64 (fst x) (snd x) z
    null EmptyPairCharWord64 = True
    null _ = False
    head EmptyPairCharWord64 = errorEmptyList "head"
    head (ConsPairCharWord64 x y _) = pair x y
    tail EmptyPairCharWord64 = errorEmptyList "tail"
    tail (ConsPairCharWord64 _ _ x) = x

instance AdaptList (Pair Char Double) where
    data List (Pair Char Double)
        = EmptyPairCharDouble
        | ConsPairCharDouble {-# UNPACK #-}!Char {-# UNPACK #-}!Double (List (Pair Char Double))
    empty = EmptyPairCharDouble
    cons x z = ConsPairCharDouble (fst x) (snd x) z
    null EmptyPairCharDouble = True
    null _ = False
    head EmptyPairCharDouble = errorEmptyList "head"
    head (ConsPairCharDouble x y _) = pair x y
    tail EmptyPairCharDouble = errorEmptyList "tail"
    tail (ConsPairCharDouble _ _ x) = x

instance AdaptList (Pair Char Float) where
    data List (Pair Char Float)
        = EmptyPairCharFloat
        | ConsPairCharFloat {-# UNPACK #-}!Char {-# UNPACK #-}!Float (List (Pair Char Float))
    empty = EmptyPairCharFloat
    cons x z = ConsPairCharFloat (fst x) (snd x) z
    null EmptyPairCharFloat = True
    null _ = False
    head EmptyPairCharFloat = errorEmptyList "head"
    head (ConsPairCharFloat x y _) = pair x y
    tail EmptyPairCharFloat = errorEmptyList "tail"
    tail (ConsPairCharFloat _ _ x) = x

instance AdaptList (Pair Char Char) where
    data List (Pair Char Char)
        = EmptyPairCharChar
        | ConsPairCharChar {-# UNPACK #-}!Char {-# UNPACK #-}!Char (List (Pair Char Char))
    empty = EmptyPairCharChar
    cons x z = ConsPairCharChar (fst x) (snd x) z
    null EmptyPairCharChar = True
    null _ = False
    head EmptyPairCharChar = errorEmptyList "head"
    head (ConsPairCharChar x y _) = pair x y
    tail EmptyPairCharChar = errorEmptyList "tail"
    tail (ConsPairCharChar _ _ x) = x