-
Notifications
You must be signed in to change notification settings - Fork 7
/
_list.py
84 lines (82 loc) · 2.22 KB
/
_list.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
from ._bool import TRUE, FALSE, OR, NOT
from ._pair import CONS, CAR, CDR
from ._combinators import Y
from ._natural import DEC, INC, GTE, ISZERO, ZERO
LIST = CONS(TRUE)(TRUE)
PREPEND = lambda xs: lambda x: CONS(FALSE)(CONS(x)(xs))
EMPTY = lambda xs: CAR(xs)
HEAD = lambda xs: CAR(CDR(xs))
TAIL = lambda xs: CDR(CDR(xs))
APPEND = Y(
lambda f: lambda xs: lambda x: EMPTY(xs)
(lambda _: PREPEND(xs)(x))
(lambda _: CONS(FALSE)(CONS(HEAD(xs))(f(TAIL(xs))(x))))
(TRUE)
)
REVERSE = Y(
lambda f: lambda xs: EMPTY(xs)
(lambda _: LIST)
(lambda _: APPEND(f(TAIL(xs)))(HEAD(xs)))
(TRUE)
)
# MAP(a)(xs): apply `a` function to every element in `xs` list.
# Return list of results for every element.
MAP = Y(
lambda f: lambda a: lambda xs: EMPTY(xs)
(lambda _: LIST)
(lambda _: PREPEND(f(a)(TAIL(xs)))(a(HEAD(xs))))
(TRUE)
)
RANGE = Y(
lambda f: lambda a: lambda b: GTE(a)(b)
(lambda _: LIST)
(lambda _: PREPEND(f(INC(a))(b))(a))
(TRUE)
)
# REDUCE(r)(l)(v):
# 1. Apply pass head of `l` and `v` into `r` and save result into `v`.
# 2. Do it for every element into lest from left to right.
# 3. Return `v` (accumulated value)
REDUCE = FOLD = Y(
lambda f: lambda r: lambda l: lambda v: EMPTY(l)
(lambda _: v) # if list is empty, return accumulated value (v)
# pass accumulated value (v) and head into reducer (r)
# do reucing on tail of list (l) with a new accumulated value (v)
(lambda _: f(r)(TAIL(l))(r(HEAD(l))(v)))
(TRUE)
)
FILTER = lambda f: lambda l: (
REDUCE
(lambda x: lambda xs: f(x)(APPEND(xs)(x))(xs))
(l)
(LIST)
)
DROP = lambda n: lambda l: n(TAIL)(l)
TAKE = Y(lambda f: lambda n: lambda l: (
OR(EMPTY(l))(ISZERO(n))
(lambda _: LIST)
(lambda _: (
PREPEND(f(DEC(n))(TAIL(l)))
(HEAD(l))
))
(TRUE)
))
LENGTH = lambda l: REDUCE(lambda x: lambda n: INC(n))(l)(ZERO)
INDEX = Y(lambda f: lambda n: lambda l: (
ISZERO(n)
(lambda _: HEAD(l))
(lambda _: f(DEC(n))(TAIL(l)))
(TRUE)
))
ANY = Y(lambda f: lambda l: (
EMPTY(l)
(lambda _: FALSE)
(lambda _: HEAD(l)(TRUE)(f(TAIL(l))))
(TRUE)
))
ALL = Y(lambda f: lambda l: (
EMPTY(l)
(lambda _: TRUE)
(lambda _: NOT(HEAD(l))(FALSE)(f(TAIL(l))))
(TRUE)
))