// Auto-Generated Level-1 Cat Library with Tests
// Generated by Cat interpreter 0.14.1
// on Sunday, June 03, 2007
// http://www.cat-language.com

// Executes a function.
// [$A] apply == $A
define apply  : ('A ('A -> 'B) -> 'B)
{ true swap [] if }

// Applies a unary function to the top two items on the stack.
// $a $a $B apply2 == $a $B $a $B
define apply2  : ('a 'a ('a -> 'b) -> 'b 'b)
{ under apply [apply] dip }

// Executes a function after temporarily removing the next item on the stack.
// $a [$B] dip == $B $a
define dip  : ('A 'b ('A -> 'C) -> 'C 'b)
{ swap quote compose apply }

// Executes a function after temporarily removing the next two items on the stack.
// $a $b [$C] dip2 == $C $a $b
define dip2  : ('A 'b 'c ('A -> 'D) -> 'D 'b 'c)
{ swap [dip] dip }

// Classical B combinator a.k.a. Bluebird
// [$A] [$B] [$C] b == [[$A] $B] $C
define b{ [k] [[s] k] s }

// Classical C combinator a.k.a. Cardinal
// [$A] [$B] [$C] c == [$B] [$A] $C
define c{ [[k] k] [[s] [b] b] s }

// D combinator a.k.a. Dove
// [$A] [$B] [$C] [$D] d == [[$A] $B] [$C] $D
define d{ [b] b }

// Classical I combinator, a.k.a. Identity
// [$A] i == $A
define i  : ('A ('A -> 'B) -> 'B)
{ [k] [k] s }

// Classical K combinator used to represent True, a.k.a. Kestrel
// [$A] [$B] k == $B
define k  : ('A 'b ('A -> 'C) -> 'C)
{ [pop] dip }

// KI combinator, used to represent False, a.k.a. Kite
// [$A] [$B] ki == $A
define ki  : ('A ('A -> 'B) 'c -> 'B)
{ [i] k }

// L combinator, a.ka. Lark
// [$A] [$B] l == [[$A] $A] $B
define l{ [m] [b] c }

// Self-applicative or recursive combinator, a.k.a. Mockingbird.
// [$A] m == [[$A] $A]
define m  : (f=(f -> 'A) -> 'A)
{ dup apply }

// O combinator, a.k.a. Owl
// [$A] [$B] o == [[$B] $B] $A
define o{ [i] s }

// R combinator, a.k.a. Robin
// [$A] [$B] [$C] r == [$C] [$A] $B
define r{ [t] [b] b }

// Classical S combinator, a.k.a. Starling
// [$A] [$B] [$C] s == [[$A] $B] [$A] $C
define s{ peek swap [curry] dip2 apply }

// T or reverse application combinator, a.k.a. Thrush.
// [$A] [$B] t == [$B] $A
define t{ [i] c }

// Turing's fixed point combinator.
// [$A] [$B] u == [[$B] [$A] [$A] $B] $A
define u{ [o] l }

// V combinator, a.k.a. Vireo
// [$A] [$B] [$C] v == [$B] [$C] $A
define v{ [t] [c] b }

// Classical W combinator, a.k.a. Warbler
// [$A] [$B] [$C] b == [[$A] $B] $C
define w{ [[r] [m] b] c }

// Classical fix-point Y combinator a.k.a. Sage Bird or Why Bird
// [$A] y == [[$A] y] $A
define y  : ('A f=('A f -> 'B) -> 'B)
{ dup quote [y] compose swap apply }

// Executes a boolean 'and' operation.
// $a $b and == $a [$b] [false] if
define and  : (bool bool -> bool)
{ quote [false] if }

// Executes a boolean 'nand' operation.
// $a $b and == $a [$b not] [true] if
define nand  : (bool bool -> bool)
{ and not }

// Executes a boolean 'nor' operation.
// $a $b nor == $a [false] [$b not] if
define nor  : (bool bool -> bool)
{ or not }

// Executes a boolean 'not' operation.
// true not == false; false not == true;
define not  : (bool -> bool)
{ [false] [true] if }

// Executes a boolean 'or' operation.
// $a $b or == $a [true] [$b] if
define or  : (bool bool -> bool)
{ [true] swap quote if }

// Compares top value to zero leaving the value on the stack.
// $a eqz == $a $a 0 eq
define eqz  : (int -> int bool)
{ dup 0 eq }

// Creates a function that tests an argument for equality with a specific value leaving the argument on the stack.
// $a eqf == [dup $a eq]
define eqf  : ('a -> ('a -> 'a bool))
{ [dupd eq] curry }

// Compares top items on the stack for inequality.
// $a $b neq == $a $a eq not
define neq  : ('a 'a -> bool)
{ eq not }

// Creates a function that tests an argument for inequality with a specific value leaving the argument on the stack.
// $a neqf == [dup $a neq]
define neqf  : ('a -> ('a -> 'a bool))
{ [dupd neq] curry }

// Checks top value for inequality with zero leaving the value on the stack.
// $a eqz == $a $a 0 neq
define neqz  : (int -> int bool)
{ dup 0 neq }

// Fixes a function's top argument to a constant value.
// $a [$B] curry == [$a $B]
define curry  : ('a ('B 'a -> 'C) -> ('B -> 'C))
{ [quote] dip compose }

// Fixes a function's top two arguments to constant values.
// $a $b [$C] curry2 == [$a $b $C]
define curry2  : ('a 'b ('C 'a 'b -> 'D) -> ('C -> 'D))
{ curry curry }

// Swaps then composes two functions.
// [$A] [$B] rcompose == [$B $A]
define rcompose  : (('A -> 'B) ('C-> 'A) -> ('C -> 'A))
{ swap compose }

// Fixes a function's top argument to a constant value.
// [$A] $b rcurry == [$B $a]
define rcurry  : (('A 'b -> 'C) 'b -> ('A -> 'C))
{ swap curry }

// Executes a loop a number of times passing the loop count.
// [$A] $b for == 0 [[$A] dip] [dup $b neq] while
define for  : ('A ('A int -> 'A) int -> 'A)
{ swap [dip inc] curry [dup] rcompose swap neqf 0 bury while pop }

// Executes a function a number of times  pushing a value from a list each time. Very similar to fold.
// () [$A] foreach == id; ($A $b) [$C] foreach == $b $C ($A) [$C] foreach
define for_each  : ('A list ('A 'b -> 'A) -> 'A)
{ [dip] curry [uncons swap] rcompose whilene }

// Executes a function a number of times.
// [$A] 0 repeat == id; $A [$B] $c repeat == $B $A [$B] $c dec repeat;
define repeat  : ('A ('A -> 'A) int -> 'A)
{ swap [dip dec] curry [neqz] while pop }

// Executes a reverse for loop which counts down from some value to one.
// [$A] 0 for == id; [$A] $b for == $b $A [$A] $b dec for
define rfor  : ('A ('A int -> 'A) int -> 'A)
{ swap [dip dec] curry [dup] rcompose whilenz }

// Repeatedly executes a function while the predicate returns false.
// [$A] [$B] whilen == [$A] [$B not] while
define whilen  : ('A ('A -> 'A) ('A -> 'A bool) -> 'A)
{ [not] compose while }

// Repeatedly executes a function while the list on the top of the stack is not empty.
// [$A] whilene == [$A] [empty not] while pop
define whilene  : ('A list ('A list -> 'A list) -> 'A)
{ [empty not] while pop }

// Repeatedly executes a function while the integer on the top of the stack is not zero.
// [$A] whilenz == [$A] [neqz] while pop
define whilenz  : ('A int ('A int -> 'A int) -> 'A)
{ [neqz] while pop }

// Concatenates two lists.
// ($A) ($B) cat == ($A $B)
define cat  : (list list -> list)
{ rev swap [cons] fold }

// Appends the second item on the stack to the list in the third position.
// ($A) $b $c cons == ($A $b) $c
define consd  : (list var 'a -> list 'a)
{ [cons] dip }

// Returns the number of items in a list.
// ($A $b) count == ($A) count inc; () count == 0
define count  : (list -> list count)
{ dup 0 [pop inc] fold }

// Returns how many of the first elements satisfy a predicate
// () [$A] count_while == 0; ($A $b) [$C] count_while == $b $C $A [$C] count_while [inc] [] if
define count_while  : (list ('a -> bool) -> list int)
{ [dup 0 swap] dip [[inc] dip] swap [uncons] rcompose while pop }

// Removes a number of items from the front of a list.
// ($A $b) 0 drop = ($A); ($A $b) $c drop == ($A $c dec drop)
define drop  : (list int -> list)
{ [[tail] dip dec] whilenz }

// Drops items from the front of a list while the predicate is satisfied.
// () [$A] drop_while == (); ($A $b) [$C] drop_while == $b $C [($A [$C] drop_while)] [($A)]
define drop_while  : (list ('a -> bool) -> list)
{ count_while drop }

// Creates a list containing elements of a source list  for which a predicate returns true.
// ($A $b) [$C] filter == $b $C if ($A [$C] filter $b) ($A [$C] filter)
define filter  : (list ('a -> bool) -> list)
{ [rev] dip [[cons] [pop] if] compose [dup] rcompose nil swap fold }

// Returns first item in a list.
// ($A $b) first == ($A $b) $b
define first  : (list -> list var)
{ dup uncons popd }

// Concatenates all children in a list of lists.
// () flatten == (); ($A ($b)) flatten == ($A flatten $b)
define flatten  : (list -> list)
{ rev nil [cat] fold }

// Applies a binary function to the first item in a list with an accumulated value. It removes the first item and repeats until the list is empty.
// () $a [$B] fold == $a; ($A $b) $c [$D] fold == $c $b $D ($A) [$D] fold
define fold  : (list 'a ('a 'a -> 'a) -> 'a)
{ swapd [dip] curry [uncons swap] rcompose whilene }

// Creates a new list  and appends an item to a list if the predicate is true. It then applies a transform to the last value and repeats.
// $a [$B] [$C] gen == $a $C [($a $a $B [$B] [$C] gen)] [()] if
define gen  : ('a ('a -> 'a) ('a -> bool) -> list)
{ nil swap [bury] dip [[dup consd] rcompose] dip [dup] rcompose while pop }

// Replace a list with the first item in it.
// ($A $b) head == $b
define head  : (list -> var)
{ uncons popd }

// Returns the last item in a list.
// ($A) last == ($A) count dec nth
define last  : (list -> list var)
{ count dec nth }

// Creates a new list by applying a transform function to each item in a list.
// $a [$B] map == $a [$B] rmap rev
define map  : (list ('a -> 'b) -> list)
{ rmap rev }

// Returns the middle item in a list.
// ($A) mid == ($A) count 2 div_int nth
define mid  : (list -> list var)
{ count 2 div_int nth }

// Moves the head of one list to the next.
// ($A) ($B $c) move_head == ($A $c) ($B)
define move_head  : (list list -> list list)
{ uncons swap consd }

// Creates a list of consecutive integers from 0 to some number minus one.
// 0 n == (); $a n = ($a dec n $a)
define n  : (int -> list)
{ nil swap [cons] swap for }

// Returns the nth item in a list.
// ($A $b) 0 nth == ($A $b) $b; ($A $b) 0 nth
define nth  : (list int -> list var)
{ dupd drop head }

// Creates a list containing two items.
// $a $b pair == ($a $b)
define pair  : ('a 'b -> list)
{ [unit] dip cons }

// Reverses a list.
// ($A $b) rev == ($b $A rev); () rev == ()
define rev  : (list -> list)
{ nil [cons] fold }

// Constructs a map of the reverse of a list.
// [$A] rmap == nil [cons] fold
define rmap  : (list ('a -> 'b) -> list)
{ nil swap [cons] compose fold }

// Creates a new list by replacing an item at a given index with a new value.
// ($A $b) $c 0 set_at == ($A $c); ($A $b) $c $d set_at == ($A $c $d dec set_at $b)
define set_at  : (list var int -> list)
{ swapd split_at [tail swons] dip cat }

// Returns true if a list contains one or zero items.
// ($A) small == ($A) count 1 lteq
define small  : (list -> list bool)
{ count 1 lteq_int }

// Splits a list in two according to a predicate function.
// ($A) [$B] split == ($A) [$B] (filter) ($A) [$B not] (filter)
define split  : (list ('a -> bool) -> list list)
{ dup2 [filter] dip2 [not] compose filter }

// Splits a list in two at a specific index.
// ($A) 0 split_at == ($A) (); ($A $b) $c split_at == ($A) $c dec split_at $b cons
define split_at  : (list int -> list list)
{ nil bury [move_head] swap repeat swap }

// Adds the item below a list to the front of it.
// $b ($A) swons == ($A $b)
define swons  : (var list -> list)
{ swap cons }

// Remove first item in a list.
// ($A $b) tail == ($A)
define tail  : (list -> list)
{ uncons pop }

// Creates a list from the first n items in another list.
// ($A $b) 0 take = (); ($A $b) $c take == ($A $c dec take $b)
define take  : (list int -> list)
{ nil bury [[move_head] dip dec] whilenz pop rev }

// Takes items from a list while the predicate is satisfied.
// () [$A] take_while == (); ($A $b) [$C] take_while == $b $C [($A [$C] take_while $b)] [()] if
define take_while  : (list ('a -> bool) -> list)
{ count_while take }

// Creates a list from the top three elements
// $a $b $c triple == ($a $b $c)
define triple  : ('a 'b 'c -> list)
{ [pair] dip cons }

// Removes first two items from a list and removes it.
// ($A $b $c) unpair == $b $c
define unpair  : (list -> var var)
{ uncons [head] dip }

// Creates a list containing one item.
// $a unit == ($a)
define unit  : ('a -> list)
{ nil swap cons }

// $a $b $c bury == $c $a $b
define bury  : ('a 'b 'c -> 'c 'a 'b)
{ swap swapd }

// $a $b $c dig == $b $c $a
define dig  : ('a 'b 'c -> 'b 'c 'a)
{ swapd swap }

// $a $b dup2 == $a $b $a $b
define dup2  : ('a 'b -> 'a 'b 'a 'b)
{ over over }

// $a $b dupd == $a $a $b
define dupd  : ('a 'b -> 'a 'a 'b)
{ [dup] dip }

// $a $b over == $a $b $a
define over  : ('a 'b -> 'a 'b 'a)
{ dupd swap }

// $a $b $c peek == $a $b $c $a
define peek  : ('a 'b 'c -> 'a 'b 'c 'a)
{ [dupd] dip dig }

// $a $b $c poke == $c $b
define poke  : ('a 'b 'c -> 'c 'b)
{ [popd] dip swap }

// $a $b pop2 == id
define pop2  : ('a 'b -> )
{ pop pop }

// $a $b $c pop3 == id
define pop3  : ('a 'b 'c -> )
{ pop pop pop }

// $a $b popd == $b
define popd  : ('a 'b -> 'b)
{ [pop] dip }

// $a $b $c $d swap2 == $c $d $a $b
define swap2  : ('a 'b 'c 'd -> 'c 'd 'a 'b)
{ [bury] dip bury }

// $a $b $c swapd == $b $a $c
define swapd  : ('a 'b 'c -> 'b 'a 'c)
{ [swap] dip }

// $a $b under == $b $a $b
define under  : ('a 'b -> 'b 'a 'b)
{ dup swapd }

// $a inc == {$a-1}
define dec  : (int -> int)
{ 1 sub_int }

// $a even == $a $a 2 mod_int 0 eq
define even  : (int -> int bool)
{ dup 2 mod_int 0 eq }

// $a inc == {$a+1}
define inc  : (int -> int)
{ 1 add_int }

// $a $b sub_int == {$a - $b}
define sub_int  : (int int -> int)
{ neg_int add_int }

// $a $b min_int == $a $b lt_int [$a] [$b] if
define min_int  : (int int -> int)
{ dup2 gt_int [popd] [pop] if }

// $a $b max_int == $a $b gt_int [$a] [$b] if
define max_int  : (int int -> int)
{ dup2 gt_int [pop] [popd] if }

// $a even == $a $a 2 mod 1 eq
define odd  : (int -> int bool)
{ dup 2 mod_int 1 eq }

// $a $b gt_int == {$a > $b}
define gt_int  : (int int -> bool)
{ lteq_int not }

// $a $b gteq_int == {$a >= $b}
define gteq_int  : (int int -> bool)
{ lt_int not }

// $a $b lteq_int == {$a <= $b}
define lteq_int  : (int int -> bool)
{ dup2 eq [lt_int] dip or }


// Tests

define run_tests
{
  [1 2 add_int 3 eq] test
  [[1] [inc] compose apply 2 eq] test
  [nil 1 cons uncons swap pop 1 eq] test
  [42 7 div_int 6 eq] test
  [2 dup add_int 4 eq] test
  [nil empty popd 1 unit empty popd not 1 2 pair empty popd not and and] test
  [1 1 eq] test
  [false [false] [true] if] test
  [true [1] [2] if 1 eq] test
  [3 5 lt_int] test
  [5 3 mod_int 2 eq] test
  [5 3 mul_int 15 eq] test
  [5 neg_int -5 eq] test
  [nil nil eq] test
  [3 5 pop 3 eq] test
  [true 1 quote 2 quote if 1 eq] test
  [1 2 swap pop 2 eq] test
  [true [true] [false] if] test
  [nil 2 cons 1 cons uncons pop uncons swap pop 2 eq] test
  [1 [2 mul_int] [dup 100 lt_int] while 128 eq] test
  [[1] apply 1 eq] test
  [1 3 [inc] apply2 pop 2 eq] test
  [1 3 [inc] dip pop 2 eq] test
  [1 3 5 [inc] dip2 pop pop 2 eq] test
  [true true and] test
  [true false nand] test
  [false false nor] test
  [false not] test
  [true false or] test
  [0 eqz popd] test
  [3 3 eqf apply popd] test
  [3 5 neq] test
  [3 5 neqf apply popd] test
  [3 neqz popd] test
  [1 2 [add_int] curry apply 3 eq] test
  [1 2 [add_int] curry2 apply 3 eq] test
  [1 [add_int] [2] rcompose apply 3 eq] test
  [1 [add_int] 2 rcurry apply 3 eq] test
  [nil [cons] 3 for 0 1 2 triple eq] test
  [8 1 2 pair [add_int] for_each 11 eq] test
  [1 [inc] 5 repeat 6 eq] test
  [nil [cons] 3 rfor 3 2 1 triple eq] test
  [1 [inc] [dup 3 gt_int] whilen 4 eq] test
  [0 1 2 3 triple [uncons swap [add_int] dip] whilene 6 eq] test
  [3 3 [[inc] dip dec] whilenz 6 eq] test
  [1 unit 2 unit cat nil 1 cons 2 cons eq] test
  [nil 1 2 consd pop head 1 eq] test
  [1 2 pair count popd 2 eq] test
  [1 2 3 triple [1 gt_int] count_while popd 2 eq] test
  [3 4 pair 1 drop head 3 eq] test
  [1 2 3 triple [2 gteq_int] drop_while 1 unit eq] test
  [1 2 3 triple [2 mod_int 0 eq] filter 2 unit eq] test
  [1 2 pair first popd 2 eq] test
  [nil 1 unit cons 2 unit cons flatten 1 2 pair eq] test
  [1 2 3 triple 0 [add_int] fold 6 eq] test
  [0 [inc] [2 lt_int] gen 0 1 pair eq] test
  [nil 1 cons 2 cons head 2 eq] test
  [1 2 3 triple last popd 1 eq] test
  [1 2 pair [3 mul_int] map head 6 eq] test
  [1 2 3 triple mid popd 2 eq] test
  [1 2 pair 3 4 pair move_head pop head 4 eq] test
  [3 n 0 1 2 triple eq] test
  [1 2 3 triple 2 nth popd 1 eq] test
  [1 2 pair head 2 eq] test
  [1 2 pair rev head 1 eq] test
  [1 2 pair [3 mul_int] rmap head 3 eq] test
  [1 2 pair 42 0 set_at head 42 eq] test
  [1 unit small popd] test
  [1 2 3 triple [2 mod_int 0 eq] split popd 1 3 pair eq] test
  [1 2 3 triple 1 split_at pop 1 2 pair eq] test
  [1 2 unit swons 2 1 pair eq] test
  [3 4 pair tail 3 unit eq] test
  [1 2 3 triple 2 take 2 3 pair eq] test
  [1 2 3 triple [2 gt_int] take_while 3 unit eq] test
  [1 2 3 triple 1 2 pair 3 cons eq] test
  [1 2 pair unpair pop 1 eq] test
  [1 unit nil 1 cons eq] test
  [1 2 3 bury pop pop 3 eq] test
  [1 2 3 dig popd popd 1 eq] test
  [1 2 dup2 pop popd popd 1 eq] test
  [1 2 dupd pop popd 1 eq] test
  [1 2 over popd popd 1 eq] test
  [1 2 3 peek popd popd popd 1 eq] test
  [1 2 3 poke pop 3 eq] test
  [1 2 3 pop2 1 eq] test
  [1 2 3 4 pop3 1 eq] test
  [1 2 popd 2 eq] test
  [1 2 3 4 swap2 pop3 3 eq] test
  [1 2 3 swapd pop2 2 eq] test
  [1 2 under pop2 2 eq] test
  [3 dec 2 eq] test
  [2 even popd] test
  [3 inc 4 eq] test
  [5 3 sub_int 2 eq] test
  [3 5 min_int 3 eq] test
  [3 5 max_int 5 eq] test
  [3 odd popd] test
  [5 3 gt_int] test
  [5 5 gteq_int] test
  [3 5 lteq_int] test
}