{-# LANGUAGE NoImplicitPrelude #-}
module AOPPrelude
  ( -- Standard combinators
    (.), const, id
  , outl, outr, swap
  , assocl, assocr
  , dupl, dupr
  , pair, cross, cond
  , curry, uncurry
    -- Boolean functions
  , false, true
  , (&&)
  , (||)
  , not
  , otherwise
    -- Relations
  , leq, less, eql, neq, gtr, geq
  , meet, join, wok
    -- Numerical functions
  , zero, succ, pred
  , plus, minus, times, divide
  , negative, positive
    -- List-processing functions
  , (++)
  , null
  , nil, wrap, cons, cat, concat, snoc
  , head, tail, split
  , last, init
  , inits, tails, splits
  , cpp, cpl, cpr, cplist
  , minlist, bmin
  , maxlist, bmax
  , thinlist
  , length, sum, trans, list, filter
  , catalist
  , cata1list
  , cata2list
  , loop
  , merge
  , zip
  , unzip
    -- Word and line processing functions
  , words
  , lines
  , unwords
  , unlines
    -- Essentials and built-in primitives
  , ord, chr
  , (==), (/=), (<=), (<), (>=), (>)
  , (+), (-), (/), div, mod, (*)
  , negate, primPrint, strict, error
  , show
  , flip
    -- Re-exports
  , String
  , Eq
  , Ord
  , Num
  , Fractional
  , Show
  , Integer
  , Natural
  , module GHC.Types
  ) where
---------------------------------------------------------------------
-- Prelude for `Algebra of Programming' -----------------------------
-- Original created 14 Sept, 1995, by Richard Bird ------------------
---------------------------------------------------------------------

-- Operator precedence table: ---------------------------------------
import GHC.Base ((==), (/=), (<), (<=), (>=), (>), ($!), String)
import GHC.Err (error)
import GHC.Num ((+), (-), (*), negate, Num)
import GHC.Real ((/), div, mod, Fractional)
import GHC.Show (Show, show)
import GHC.Classes hiding (not, (&&), (||))
import GHC.Integer (Integer)
import GHC.Types

import Numeric.Natural (Natural)
import Data.Char (ord, chr)
import System.IO (print)

infixr 9 .
infixr 5 ++
infixr 3 &&
infixr 2 ||

-- Standard combinators: --------------------------------------------
(.) :: (b -> c) -> (a -> b) -> a -> c
(b -> c
f . :: (b -> c) -> (a -> b) -> a -> c
. a -> b
g) a
x = b -> c
f (a -> b
g a
x)
const :: a -> b -> a
const :: a -> b -> a
const a
k b
a = a
k
id :: a -> a
id :: a -> a
id a
a      = a
a

outl :: (a, b) -> a
outl :: (a, b) -> a
outl (a
a, b
_) = a
a
outr :: (a, b) -> b
outr :: (a, b) -> b
outr (a
_, b
b) = b
b
swap :: (a, b) -> (b, a)
swap :: (a, b) -> (b, a)
swap (a
a, b
b) = (b
b, a
a)

assocl :: (a, (b, c)) -> ((a, b), c)
assocl :: (a, (b, c)) -> ((a, b), c)
assocl (a
a, (b
b, c
c)) = ((a
a, b
b), c
c)
assocr :: ((a, b), c) -> (a, (b, c))
assocr :: ((a, b), c) -> (a, (b, c))
assocr ((a
a, b
b), c
c) = (a
a, (b
b, c
c))

dupl :: (a, (b, c)) -> ((a, b), (a, c))
dupl :: (a, (b, c)) -> ((a, b), (a, c))
dupl (a
a, (b
b, c
c)) = ((a
a, b
b), (a
a, c
c))
dupr :: ((a, b), c) -> ((a, c), (b, c))
dupr :: ((a, b), c) -> ((a, c), (b, c))
dupr ((a
a, b
b), c
c) = ((a
a, c
c), (b
b, c
c))

pair :: (a -> b, a -> c) -> a -> (b, c)
pair :: (a -> b, a -> c) -> a -> (b, c)
pair (a -> b
f, a -> c
g) a
a       = (a -> b
f a
a, a -> c
g a
a)
cross :: (a -> c, b -> d) -> (a, b) -> (c, d)
cross :: (a -> c, b -> d) -> (a, b) -> (c, d)
cross (a -> c
f, b -> d
g) (a
a, b
b) = (a -> c
f a
a, b -> d
g b
b)
cond :: (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond :: (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond a -> Bool
p (a -> b
f, a -> b
g) a
a     = if a -> Bool
p a
a then a -> b
f a
a else a -> b
g a
a

curry :: ((a, b) -> c) -> a -> b -> c
curry :: ((a, b) -> c) -> a -> b -> c
curry (a, b) -> c
f a
a b
b      = (a, b) -> c
f (a
a, b
b)
uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry a -> b -> c
f (a
a, b
b) = a -> b -> c
f a
a b
b

-- Boolean functions: -----------------------------------------------
false :: a -> Bool
false :: a -> Bool
false = Bool -> a -> Bool
forall a b. a -> b -> a
const Bool
False
true  :: a -> Bool
true :: a -> Bool
true  = Bool -> a -> Bool
forall a b. a -> b -> a
const Bool
True

(&&) :: Bool -> Bool -> Bool
Bool
False && :: Bool -> Bool -> Bool
&& Bool
_ = Bool
False
Bool
True  && Bool
x = Bool
x

(||) :: Bool -> Bool -> Bool
Bool
False || :: Bool -> Bool -> Bool
|| Bool
x = Bool
x
Bool
True  || Bool
_ = Bool
True

not :: Bool -> Bool
not :: Bool -> Bool
not Bool
True   = Bool
False
not Bool
False  = Bool
True

otherwise :: Bool
otherwise :: Bool
otherwise  = Bool
True

-- Relations: -------------------------------------------------------
leq :: Ord a => (a, a) -> Bool
leq :: (a, a) -> Bool
leq  = (a -> a -> Bool) -> (a, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Bool
forall a. Ord a => a -> a -> Bool
(<=)
less :: Ord a => (a, a) -> Bool
less :: (a, a) -> Bool
less = (a -> a -> Bool) -> (a, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Bool
forall a. Ord a => a -> a -> Bool
(<)
eql :: Ord a => (a, a) -> Bool
eql :: (a, a) -> Bool
eql  = (a -> a -> Bool) -> (a, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
neq :: Ord a => (a, a) -> Bool
neq :: (a, a) -> Bool
neq  = (a -> a -> Bool) -> (a, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(/=)
gtr :: Ord a => (a, a) -> Bool
gtr :: (a, a) -> Bool
gtr  = (a -> a -> Bool) -> (a, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Bool
forall a. Ord a => a -> a -> Bool
(>)
geq :: Ord a => (a, a) -> Bool
geq :: (a, a) -> Bool
geq  = (a -> a -> Bool) -> (a, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Bool
forall a. Ord a => a -> a -> Bool
(>=)

meet :: (a -> Bool, a -> Bool) -> a -> Bool
meet :: (a -> Bool, a -> Bool) -> a -> Bool
meet (a -> Bool
r, a -> Bool
s) = (a -> Bool) -> (a -> Bool, a -> Bool) -> a -> Bool
forall a b. (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond a -> Bool
r (a -> Bool
s, a -> Bool
forall a. a -> Bool
false)
join :: (a -> Bool, a -> Bool) -> a -> Bool
join :: (a -> Bool, a -> Bool) -> a -> Bool
join (a -> Bool
r, a -> Bool
s) = (a -> Bool) -> (a -> Bool, a -> Bool) -> a -> Bool
forall a b. (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond a -> Bool
r (a -> Bool
forall a. a -> Bool
true, a -> Bool
s)
wok :: ((b, a) -> c) -> (a, b) -> c
wok :: ((b, a) -> c) -> (a, b) -> c
wok (b, a) -> c
r       = (b, a) -> c
r ((b, a) -> c) -> ((a, b) -> (b, a)) -> (a, b) -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, b) -> (b, a)
forall a b. (a, b) -> (b, a)
swap

-- Numerical functions: ---------------------------------------------
zero   :: Num a => t -> a
zero :: t -> a
zero   = a -> t -> a
forall a b. a -> b -> a
const a
0
succ   :: Num a => a -> a
succ :: a -> a
succ   = (a -> a -> a
forall a. Num a => a -> a -> a
+a
1)
pred   :: Num a => a -> a
pred :: a -> a
pred a
n = a
n a -> a -> a
forall a. Num a => a -> a -> a
- a
1

plus   :: Num a => (a, a) -> a
plus :: (a, a) -> a
plus   = (a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
forall a. Num a => a -> a -> a
(+)
minus  :: Num a => (a, a) -> a
minus :: (a, a) -> a
minus  = (a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (-)
times  :: Num a => (a, a) -> a
times :: (a, a) -> a
times  = (a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
forall a. Num a => a -> a -> a
(*)
divide :: Fractional a => (a, a) -> a
divide :: (a, a) -> a
divide = (a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
forall a. Fractional a => a -> a -> a
(/)

negative :: (Ord a, Num a) => a -> Bool
negative :: a -> Bool
negative = (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0)
positive :: (Ord a, Num a) => a -> Bool
positive :: a -> Bool
positive = (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
0)

-- List-processing functions: ---------------------------------------
(++) :: [a] -> [a] -> [a]
[] ++ :: [a] -> [a] -> [a]
++ [a]
y    = [a]
y
(a
a:[a]
x) ++ [a]
y = a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: ([a]
x [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
y)

null :: [a] -> Bool
null :: [a] -> Bool
null []    = Bool
True
null (a
_:[a]
_) = Bool
False

nil :: t -> [a]
nil :: t -> [a]
nil    = [a] -> t -> [a]
forall a b. a -> b -> a
const []
wrap :: a -> [a]
wrap :: a -> [a]
wrap   = (a, [a]) -> [a]
forall a. (a, [a]) -> [a]
cons ((a, [a]) -> [a]) -> (a -> (a, [a])) -> a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a, a -> [a]) -> a -> (a, [a])
forall a b c. (a -> b, a -> c) -> a -> (b, c)
pair (a -> a
forall a. a -> a
id, a -> [a]
forall t a. t -> [a]
nil)
cons :: (a, [a]) -> [a]
cons :: (a, [a]) -> [a]
cons   = (a -> [a] -> [a]) -> (a, [a]) -> [a]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (:)
cat :: ([a], [a]) -> [a]
cat :: ([a], [a]) -> [a]
cat    = ([a] -> [a] -> [a]) -> ([a], [a]) -> [a]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
(++)
concat :: [[a]] -> [a]
concat :: [[a]] -> [a]
concat = ([a], ([a], [a]) -> [a]) -> [[a]] -> [a]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([], ([a], [a]) -> [a]
forall a. ([a], [a]) -> [a]
cat)
snoc :: ([a], a) -> [a]
snoc :: ([a], a) -> [a]
snoc   = ([a], [a]) -> [a]
forall a. ([a], [a]) -> [a]
cat (([a], [a]) -> [a]) -> (([a], a) -> ([a], [a])) -> ([a], a) -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [a], a -> [a]) -> ([a], a) -> ([a], [a])
forall a c b d. (a -> c, b -> d) -> (a, b) -> (c, d)
cross ([a] -> [a]
forall a. a -> a
id, a -> [a]
forall a. a -> [a]
wrap)

head :: [a] -> a
head :: [a] -> a
head (a
a:[a]
_) = a
a
tail :: [a] -> [a]
tail :: [a] -> [a]
tail (a
_:[a]
x) = [a]
x
split :: [a] -> (a, [a])
split :: [a] -> (a, [a])
split      = ([a] -> a, [a] -> [a]) -> [a] -> (a, [a])
forall a b c. (a -> b, a -> c) -> a -> (b, c)
pair ([a] -> a
forall a. [a] -> a
head, [a] -> [a]
forall a. [a] -> [a]
tail)

last :: [a] -> a
last :: [a] -> a
last = (a -> a, (a, a) -> a) -> [a] -> a
forall a b. (a -> b, (a, b) -> b) -> [a] -> b
cata1list (a -> a
forall a. a -> a
id, (a, a) -> a
forall a b. (a, b) -> b
outr)
init :: [a] -> [a]
init :: [a] -> [a]
init = (a -> [a], (a, [a]) -> [a]) -> [a] -> [a]
forall a b. (a -> b, (a, b) -> b) -> [a] -> b
cata1list (a -> [a]
forall t a. t -> [a]
nil, (a, [a]) -> [a]
forall a. (a, [a]) -> [a]
cons)

inits :: [a] -> [[a]]
inits :: [a] -> [[a]]
inits = ([[a]], (a, [[a]]) -> [[a]]) -> [a] -> [[a]]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([[]], (a, [[a]]) -> [[a]]
forall a. (a, [[a]]) -> [[a]]
extend)
  where extend :: (a, [[a]]) -> [[a]]
extend (a
a, [[a]]
xs) = [[]] [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
list (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) [[a]]
xs
tails :: [a] -> [[a]]
tails :: [a] -> [[a]]
tails = ([[a]], (a, [[a]]) -> [[a]]) -> [a] -> [[a]]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([[]], (a, [[a]]) -> [[a]]
forall a. (a, [[a]]) -> [[a]]
extend)
  where extend :: (a, [[a]]) -> [[a]]
extend (a
a, [a]
x:[[a]]
xs) = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
x)[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[a]
x[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
xs
splits :: [a] -> [([a], [a])]
splits :: [a] -> [([a], [a])]
splits = ([[a]], [[a]]) -> [([a], [a])]
forall a b. ([a], [b]) -> [(a, b)]
zip (([[a]], [[a]]) -> [([a], [a])])
-> ([a] -> ([[a]], [[a]])) -> [a] -> [([a], [a])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [[a]], [a] -> [[a]]) -> [a] -> ([[a]], [[a]])
forall a b c. (a -> b, a -> c) -> a -> (b, c)
pair ([a] -> [[a]]
forall a. [a] -> [[a]]
inits, [a] -> [[a]]
forall a. [a] -> [[a]]
tails)

cpp :: ([a], [b]) -> [(a, b)]
cpp :: ([a], [b]) -> [(a, b)]
cpp ([a]
x, [b]
y) = [(a
a, b
b) | a
a <- [a]
x, b
b <- [b]
y]
cpl :: ([a], b) -> [(a, b)]
cpl :: ([a], b) -> [(a, b)]
cpl ([a]
x, b
b) = [(a
a, b
b) | a
a <- [a]
x]
cpr :: (a, [b]) -> [(a, b)]
cpr :: (a, [b]) -> [(a, b)]
cpr (a
a, [b]
y) = [(a
a, b
b) | b
b <- [b]
y]
cplist :: [[a]] -> [[a]]
cplist :: [[a]] -> [[a]]
cplist     = ([[a]], ([a], [[a]]) -> [[a]]) -> [[a]] -> [[a]]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([[]], ((a, [a]) -> [a]) -> [(a, [a])] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
list (a, [a]) -> [a]
forall a. (a, [a]) -> [a]
cons ([(a, [a])] -> [[a]])
-> (([a], [[a]]) -> [(a, [a])]) -> ([a], [[a]]) -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a], [[a]]) -> [(a, [a])]
forall a b. ([a], [b]) -> [(a, b)]
cpp)

minlist :: ((a, a) -> Bool) -> [a] -> a
minlist :: ((a, a) -> Bool) -> [a] -> a
minlist (a, a) -> Bool
r = (a -> a, (a, a) -> a) -> [a] -> a
forall a b. (a -> b, (a, b) -> b) -> [a] -> b
cata1list (a -> a
forall a. a -> a
id, ((a, a) -> Bool) -> (a, a) -> a
forall a. ((a, a) -> Bool) -> (a, a) -> a
bmin (a, a) -> Bool
r)
bmin :: ((a, a) -> Bool) -> (a, a) -> a
bmin :: ((a, a) -> Bool) -> (a, a) -> a
bmin (a, a) -> Bool
r    = ((a, a) -> Bool) -> ((a, a) -> a, (a, a) -> a) -> (a, a) -> a
forall a b. (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond (a, a) -> Bool
r ((a, a) -> a
forall a b. (a, b) -> a
outl, (a, a) -> a
forall a b. (a, b) -> b
outr)

maxlist :: ((a, a) -> Bool) -> [a] -> a
maxlist :: ((a, a) -> Bool) -> [a] -> a
maxlist (a, a) -> Bool
r = (a -> a, (a, a) -> a) -> [a] -> a
forall a b. (a -> b, (a, b) -> b) -> [a] -> b
cata1list (a -> a
forall a. a -> a
id, ((a, a) -> Bool) -> (a, a) -> a
forall a. ((a, a) -> Bool) -> (a, a) -> a
bmax (a, a) -> Bool
r)
bmax :: ((a, a) -> Bool) -> (a, a) -> a
bmax :: ((a, a) -> Bool) -> (a, a) -> a
bmax (a, a) -> Bool
r    = ((a, a) -> Bool) -> ((a, a) -> a, (a, a) -> a) -> (a, a) -> a
forall a b. (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond ((a, a) -> Bool
r ((a, a) -> Bool) -> ((a, a) -> (a, a)) -> (a, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> (a, a)
forall a b. (a, b) -> (b, a)
swap) ((a, a) -> a
forall a b. (a, b) -> a
outl, (a, a) -> a
forall a b. (a, b) -> b
outr)

thinlist :: ((a, a) -> Bool) -> [a] -> [a]
thinlist :: ((a, a) -> Bool) -> [a] -> [a]
thinlist (a, a) -> Bool
r = ([a], (a, [a]) -> [a]) -> [a] -> [a]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([], ((a, a) -> Bool) -> (a, [a]) -> [a]
forall a. ((a, a) -> Bool) -> (a, [a]) -> [a]
bump (a, a) -> Bool
r)
  where bump :: ((a, a) -> Bool) -> (a, [a]) -> [a]
bump (a, a) -> Bool
r (a
a, [])  = [a
a]
        bump (a, a) -> Bool
r (a
a, a
b:[a]
x) | (a, a) -> Bool
r (a
a, a
b)  = a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
x
                        | (a, a) -> Bool
r (a
b, a
a)  = a
ba -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
x
                        | Bool
otherwise = a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:a
ba -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
x

length :: Num a => [t] -> a
length :: [t] -> a
length   = (a, (t, a) -> a) -> [t] -> a
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist (a
0, a -> a
forall a. Num a => a -> a
succ (a -> a) -> ((t, a) -> a) -> (t, a) -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (t, a) -> a
forall a b. (a, b) -> b
outr)
sum :: Num a => [a] -> a
sum :: [a] -> a
sum      = (a, (a, a) -> a) -> [a] -> a
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist (a
0, (a, a) -> a
forall a. Num a => (a, a) -> a
plus)
trans :: [[a]] -> [[a]]
trans :: [[a]] -> [[a]]
trans    = ([a] -> [[a]], ([a], [[a]]) -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b, (a, b) -> b) -> [a] -> b
cata1list ((a -> [a]) -> [a] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
list a -> [a]
forall a. a -> [a]
wrap, ((a, [a]) -> [a]) -> [(a, [a])] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
list (a, [a]) -> [a]
forall a. (a, [a]) -> [a]
cons ([(a, [a])] -> [[a]])
-> (([a], [[a]]) -> [(a, [a])]) -> ([a], [[a]]) -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a], [[a]]) -> [(a, [a])]
forall a b. ([a], [b]) -> [(a, b)]
zip)
list :: (a -> b) -> [a] -> [b]
list :: (a -> b) -> [a] -> [b]
list a -> b
f   = ([b], (a, [b]) -> [b]) -> [a] -> [b]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([], (b, [b]) -> [b]
forall a. (a, [a]) -> [a]
cons ((b, [b]) -> [b]) -> ((a, [b]) -> (b, [b])) -> (a, [b]) -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b, [b] -> [b]) -> (a, [b]) -> (b, [b])
forall a c b d. (a -> c, b -> d) -> (a, b) -> (c, d)
cross (a -> b
f, [b] -> [b]
forall a. a -> a
id))
filter :: (a -> Bool) -> [a] -> [a]
filter :: (a -> Bool) -> [a] -> [a]
filter a -> Bool
p = ([a], (a, [a]) -> [a]) -> [a] -> [a]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([], ((a, [a]) -> Bool)
-> ((a, [a]) -> [a], (a, [a]) -> [a]) -> (a, [a]) -> [a]
forall a b. (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond (a -> Bool
p (a -> Bool) -> ((a, [a]) -> a) -> (a, [a]) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, [a]) -> a
forall a b. (a, b) -> a
outl) ((a, [a]) -> [a]
forall a. (a, [a]) -> [a]
cons, (a, [a]) -> [a]
forall a b. (a, b) -> b
outr))

catalist :: (b, (a, b) -> b) -> [a] -> b
catalist :: (b, (a, b) -> b) -> [a] -> b
catalist (b
c, (a, b) -> b
f) []    = b
c
catalist (b
c, (a, b) -> b
f) (a
a:[a]
x) = (a, b) -> b
f (a
a, (b, (a, b) -> b) -> [a] -> b
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist (b
c, (a, b) -> b
f) [a]
x)

cata1list :: (a -> b, (a, b) -> b) -> [a] -> b
cata1list :: (a -> b, (a, b) -> b) -> [a] -> b
cata1list (a -> b
f, (a, b) -> b
g) [a
a]   = a -> b
f a
a
cata1list (a -> b
f, (a, b) -> b
g) (a
a:[a]
x) = (a, b) -> b
g (a
a, (a -> b, (a, b) -> b) -> [a] -> b
forall a b. (a -> b, (a, b) -> b) -> [a] -> b
cata1list (a -> b
f, (a, b) -> b
g) [a]
x)

cata2list :: ((a, a) -> b, (a, b) -> b) -> [a] -> b
cata2list :: ((a, a) -> b, (a, b) -> b) -> [a] -> b
cata2list ((a, a) -> b
f, (a, b) -> b
g) [a
a,a
b] = (a, a) -> b
f (a
a, a
b)
cata2list ((a, a) -> b
f, (a, b) -> b
g) (a
a:[a]
x) = (a, b) -> b
g (a
a, ((a, a) -> b, (a, b) -> b) -> [a] -> b
forall a b. ((a, a) -> b, (a, b) -> b) -> [a] -> b
cata2list ((a, a) -> b
f, (a, b) -> b
g) [a]
x)

loop :: ((a, b) -> a) -> (a, [b]) -> a
loop :: ((a, b) -> a) -> (a, [b]) -> a
loop (a, b) -> a
f (a
a, [])  = a
a
loop (a, b) -> a
f (a
a, b
b:[b]
x) = ((a, b) -> a) -> (a, [b]) -> a
forall a b. ((a, b) -> a) -> (a, [b]) -> a
loop (a, b) -> a
f ((a, b) -> a
f (a
a, b
b), [b]
x)

merge :: ((a, a) -> Bool) -> ([a], [a]) -> [a]
merge :: ((a, a) -> Bool) -> ([a], [a]) -> [a]
merge (a, a) -> Bool
_ ([], [a]
y)    = [a]
y
merge (a, a) -> Bool
_ ([a]
x, [])    = [a]
x
merge (a, a) -> Bool
r (a
a:[a]
x, a
b:[a]
y) | (a, a) -> Bool
r (a
a, a
b)  = a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: ((a, a) -> Bool) -> ([a], [a]) -> [a]
forall a. ((a, a) -> Bool) -> ([a], [a]) -> [a]
merge (a, a) -> Bool
r ([a]
x, a
ba -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
y)
                   | Bool
otherwise = a
b a -> [a] -> [a]
forall a. a -> [a] -> [a]
: ((a, a) -> Bool) -> ([a], [a]) -> [a]
forall a. ((a, a) -> Bool) -> ([a], [a]) -> [a]
merge (a, a) -> Bool
r (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
x, [a]
y)

zip :: ([a], [b]) -> [(a, b)]
zip :: ([a], [b]) -> [(a, b)]
zip ([a]
x, [])    = []
zip ([], [b]
y)    = []
zip (a
a:[a]
x, b
b:[b]
y) = (a
a, b
b) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: ([a], [b]) -> [(a, b)]
forall a b. ([a], [b]) -> [(a, b)]
zip ([a]
x, [b]
y)

unzip :: [(a, b)] -> ([a], [b])
unzip :: [(a, b)] -> ([a], [b])
unzip = ([(a, b)] -> [a], [(a, b)] -> [b]) -> [(a, b)] -> ([a], [b])
forall a b c. (a -> b, a -> c) -> a -> (b, c)
pair (((a, b) -> a) -> [(a, b)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
list (a, b) -> a
forall a b. (a, b) -> a
outl, ((a, b) -> b) -> [(a, b)] -> [b]
forall a b. (a -> b) -> [a] -> [b]
list (a, b) -> b
forall a b. (a, b) -> b
outr)

-- Word and line processing functions: ------------------------------
words :: String -> [String]
words :: String -> [String]
words = (String -> Bool) -> [String] -> [String]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (String -> Bool) -> String -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Bool
forall a. [a] -> Bool
null) ([String] -> [String])
-> (String -> [String]) -> String -> [String]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([String], (Char, [String]) -> [String]) -> String -> [String]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([[]], ((Char, [String]) -> Bool)
-> ((Char, [String]) -> [String], (Char, [String]) -> [String])
-> (Char, [String])
-> [String]
forall a b. (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond (Char, [String]) -> Bool
forall b. (Char, b) -> Bool
ok ((Char, [String]) -> [String]
forall a. (a, [[a]]) -> [[a]]
glue, (Char, [String]) -> [String]
forall a a. (a, [[a]]) -> [[a]]
new))
  where ok :: (Char, b) -> Bool
ok (Char
a, b
xs)     = (Char
a Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= Char
' ' Bool -> Bool -> Bool
&& Char
a Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= Char
'\n')
        glue :: (a, [[a]]) -> [[a]]
glue (a
a, [a]
x:[[a]]
xs) = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
x)[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
xs
        new :: (a, [[a]]) -> [[a]]
new (a
a, [[a]]
xs)    = [][a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
xs

lines :: String -> [String]
lines :: String -> [String]
lines = ([String], (Char, [String]) -> [String]) -> String -> [String]
forall b a. (b, (a, b) -> b) -> [a] -> b
catalist ([[]], ((Char, [String]) -> Bool)
-> ((Char, [String]) -> [String], (Char, [String]) -> [String])
-> (Char, [String])
-> [String]
forall a b. (a -> Bool) -> (a -> b, a -> b) -> a -> b
cond (Char, [String]) -> Bool
forall b. (Char, b) -> Bool
ok ((Char, [String]) -> [String]
forall a. (a, [[a]]) -> [[a]]
glue, (Char, [String]) -> [String]
forall a a. (a, [[a]]) -> [[a]]
new))
  where ok :: (Char, b) -> Bool
ok (Char
a, b
xs)     = (Char
a Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
/= Char
'\n')
        glue :: (a, [[a]]) -> [[a]]
glue (a
a, [a]
x:[[a]]
xs) = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
x)[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
xs
        new :: (a, [[a]]) -> [[a]]
new (a
a,[[a]]
xs)     = [][a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
xs

unwords :: [String] -> String
unwords :: [String] -> String
unwords = (String -> String, (String, String) -> String)
-> [String] -> String
forall a b. (a -> b, (a, b) -> b) -> [a] -> b
cata1list (String -> String
forall a. a -> a
id, (String, String) -> String
join)
  where join :: (String, String) -> String
join (String
x, String
y) = String
x String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
" " String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
y

unlines :: [String] -> String
unlines :: [String] -> String
unlines = (String -> String, (String, String) -> String)
-> [String] -> String
forall a b. (a -> b, (a, b) -> b) -> [a] -> b
cata1list (String -> String
forall a. a -> a
id, (String, String) -> String
join)
  where join :: (String, String) -> String
join (String
x, String
y) = String
x String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"\n" String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
y

-- Essentials and built-in primitives: -------------------------------
primPrint :: Show a => a -> IO ()
primPrint :: a -> IO ()
primPrint = a -> IO ()
forall a. Show a => a -> IO ()
print

strict :: (a -> b) -> a -> b
strict :: (a -> b) -> a -> b
strict = (a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
($!)

flip :: (a -> b -> c) -> b -> a -> c
flip :: (a -> b -> c) -> b -> a -> c
flip a -> b -> c
f b
a a
b = a -> b -> c
f a
b b
a

-- End of Algebra of Programming prelude ----------------------------