prelude.txt

; Identity
ident = \x.x
const = \c.(\x.c)

I = ident
C = const

; Boolean
true = \x y.x
false = \x y.y

not = \x.(x false true)
and = \x y.(x y false)
or  = \x y.(x true y)
if  = \p l r.(p l r)

! = not
& = and
| = or
? = if

; Numbers
succ = \n.\f x.((n f) (f x))
pred = \n.\f x.(n (\g h.(h (g f))) (\u.x) (\u.u))

++ = succ
-- = pred

add  = \m n.(n succ m)
sub  = \m n.(n pred m)
mul  = \m n.(n (add m) 0)
pow  = \m n.(n (mul m) 1)

+  = add
-  = sub
*  = mul
** = pow

zero? = \f.(f (\t.false) true)
leq?  = \m n.(zero? (sub m n))
eq?   = \m n.(and (leq? m n) (leq? n m))
neq?  = \m n.(not (eq? m n))
gtr?  = \m n.(not (leq? m n))
geq?  = \m n.(zero? (sub n m))
lss?  = \m n.(not (geq? m n))

== = eq?
!= = neq?
<> = neq?
<  = lss?
>  = gtr?
<= = leq?
>= = geq?

; Y-combinator
Y = \f.(\g.(f (g g)) \g.(f (g g)))

; Pairs
pair  = \x y.\p.(p x y)
left  = \p.(p true)
right = \p.(p false)

; Lists
nil  = false
cons = pair
head = left
tail = \L.(L (\h t.\_.t) nil)
nil? = \L.(L (\h t.\_.false) true)
isnil? = nil?

fold = \f.(Y (\r.\a L.(L (\h t.\_.(r (f a h) t)) a)))
rfold = \f a.(Y (\r.\L.(L (\h t.\_.(f (r t) h)) a)))
foldr = rfold

len = (fold \a h.(succ a) 0)
reverse = (fold \a h.(cons h a) nil)
concat = \L1 L2.(rfold (\a h.(cons h a)) L2 L1)
append = \L v.(concat L (cons v nil))

map = \f.(rfold (\a h.(cons (f h) a)) nil)
filter = \f.(rfold (\a h.((f h) (cons h a) a)) nil)

skip = \n.(n tail)
skipWhile = \f.(Y (\r.\L.(L (\h t.\_.((f h) (r t) L)) nil)))
take = (Y (\r.\n.\L.(L (\h t.\_.((zero? n) nil (cons h (r (pred n) t)))) nil)))
takeWhile = \f.(Y (\r.\L.(L (\h t.\_.((f h) (cons h (r t)) nil)) nil)))

all = \f.(fold \a h.(and a (f h)) true)
any = \f.(fold \a h.(or a (f h)) false)

elementAt = \n.\L.(head (skip n L))
insertAt = \n v.\L.(concat (take n L) (cons v (skip n L)))
removeAt = \n.\L.(concat (take n L) (skip (succ n) L))
replaceAt = \n v.\L.(concat (take n L) (cons v (skip (succ n) L)))

; Note: returns len(L) if not found
indexOf = \f.(Y (\r.\n.\L.(L (\h t.\_.((f h) n (r (succ n) t))) n)) 0)

; Tuples

; Get ith field of n-length tuple (0 <= i < n, n > 0)
; E.g.: ((field 1 4) {5 4 3 2}) returns 4
field = \i n.\T.(T ((i const) (pred (sub n i) const)))