# module Data.List (  
#     (++),  head,  last,  tail,  init,  null,  length,  map,  reverse,  
#     intersperse,  intercalate,  transpose,  subsequences,  permutations,  
#     foldl,  foldl',  foldl1,  foldl1',  foldr,  foldr1,  concat,  concatMap,  
#     and,  or,  any,  all,  sum,  product,  maximum,  minimum,  scanl,  scanl1,  
#     scanr,  scanr1,  mapAccumL,  mapAccumR,  iterate,  repeat,  replicate,  
#     cycle,  unfoldr,  take,  drop,  splitAt,  takeWhile,  dropWhile,  span,  
#     break,  stripPrefix,  group,  inits,  tails,  isPrefixOf,  isSuffixOf,  
#     isInfixOf,  elem,  notElem,  lookup,  find,  filter,  partition,  (!!),  
#     elemIndex,  elemIndices,  findIndex,  findIndices,  zip,  zip3,  zip4,  
#     zip5,  zip6,  zip7,  zipWith,  zipWith3,  zipWith4,  zipWith5,  zipWith6,  
#     zipWith7,  unzip,  unzip3,  unzip4,  unzip5,  unzip6,  unzip7,  lines,  
#     words,  unlines,  unwords,  nub,  delete,  (\\),  union,  intersect,  sort,  
#     insert,  nubBy,  deleteBy,  deleteFirstsBy,  unionBy,  intersectBy,  
#     groupBy,  sortBy,  insertBy,  maximumBy,  minimumBy,  genericLength,  
#     genericTake,  genericDrop,  genericSplitAt,  genericIndex,  genericReplicate  
#   ) where
# list
nil = \ c n . n
cons = \ x xs c n . c x xs
null = \ l . l (\x xs . false) true
head = \ l . l (\x xs . x) (error head)
tail = \ l . l (\x xs . xs) (error tail)
map = \ f l . l (\x xs . cons (f x) (map f xs)) nil
append = \ us vs . us (\x xs . cons x (append xs vs)) vs
filter = \ p l . l (\x xs . p x (cons x) id (filter p xs)) nil
index = \ l n . n (\p . l (\x xs . index xs p) (error index)) (l (\x xs . x) (error index))
reverse = \ l . l (\x xs . append (reverse xs) (cons x nil)) nil
foldr = \ f e l . l (\x xs . f x (foldr f e xs)) e
length = foldr (const succ) zero
ands = foldr and true
ors = foldr or false
concat = foldr append nil
all = \f . compose ands (map f)
any = \f . compose ors (map f)
concatMap = \f . compose concat (map f)
composes = foldr compose id
sum = foldr add zero
product = foldr mul (succ zero)
repeat = \x . cons x (repeat x)
cycle = compose concat repeat
zipWith = \f l r . l (\x xs . r (\y ys . cons (f x y) (zipWith f xs ys)) nil) nil
partition = \p l . l (\x xs . p x first second (cons x) (partition p xs)) (pair nil nil)
partitionEithers = \l . l (\e es . e (compose first cons) (compose second cons) (partitionEithers es)) (pair nil nil)
take = \n l . n (\p . l (\x xs . cons x (take p xs)) nil) nil
drop = \n l . n (\p . l (\x xs . drop p xs) nil) l
transpose = \l . l (\xs xss . xs (\y ys . cons (cons y (concatMap (take 1) xss)) (transpose (cons ys (map (drop 1) xss)))) (transpose xss)) nil
catMaybes = \l . l (\x xs . maybe id cons x (catMaybes xs)) nil
iterate = \f . \x ! cons x (iterate f (f x))
last = \l . l (\x xs . xs (\y ys . last xs) x) (error last)
replicate = \n x . take n (repeat x)
rotate = \n bs . splitAt n bs \xs ys . append ys xs