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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
# Data structures
Bruijn's standard library defines several common data structures.
Relevant blog post: [Data structures in pure lambda
calculus](https://text.marvinborner.de/2023-04-07-01.html).
## States
For storing states (i.e. enums), you can use the available libraries and
syntactic sugar.
### Booleans/bits [`std/Logic`](/std/Logic.bruijn.html)
- typical [Church
booleans](https://en.wikipedia.org/wiki/Church_encoding#Church_Booleans)
-- fast and reliable
- encoding: `true`{.bruijn}=`[[1]]`{.bruijn},
`false`{.bruijn}=`[[0]]`{.bruijn}
### Unary numbers [`std/Number/Unary`](/std/Number_Unary.bruijn.html)
- `u` suffix for syntactic sugar, e.g. `(+3u)`{.bruijn}
- encoding: `(+4u)`{.bruijn}=`[[(1 (1 (1 (1 0))))]]`{.bruijn}
- typical [Church
numerals](https://en.wikipedia.org/wiki/Church_encoding#Church_numerals),
simple but high space/time complexity
- only positive numbers
### Binary numbers [`std/Number/Binary`](/std/Number_Binary.bruijn.html)
- `b` suffix for syntactic sugar, e.g. `(+3b)`{.bruijn}
- encoding: `(+4b)`{.bruijn}=`[[[0 (0 (1 2))]]]`{.bruijn}
- encoding for chars/strings, e.g. `'0'`{.bruijn}=`(+48b)`{.bruijn}
- faster and more compact than unary
- only positive numbers (excluding two's complement)
### Balanced ternary [`std/Number/Ternary`](/std/Number_Ternary.bruijn.html)
- default syntactic sugar for numbers (optional suffix `t`),
e.g. `(+3)`{.bruijn}
- encoding: `(+4)`{.bruijn}=`[[[[(1 (1 3))]]]]`{.bruijn},
`(-4)`{.bruijn}=`[[[[(2 (2 3))]]]]`{.bruijn}
- faster and more compact than binary[^1]
- positive and negative numbers
## Boxes [`std/Box`](/std/Box.bruijn.html)
Boxes are good for storing single values as immutable object with an
empty/full state.
Example:
``` bruijn
a-box <>'a'
:test (set? a-box) (true)
:test (get 'b' a-box) ('a')
:test (get 'b' empty) ('b')
:test (store! a-box 'b') (<>'b')
```
## Pairs [`std/Pair`](/std/Pair.bruijn.html)
Pairs (tuples) can store any two terms. Pairs can be constructed using
the `…:…`{.bruijn} [mixfix](mixfix.md) function.
Example:
``` bruijn
one-two (+1) : (+2)
:test (^one-two) ((+1))
:test (~one-two) ((+2))
:test (inc <$> one-two) ((+2) : (+3))
:test (uncurry add one-two) ((+3))
```
## Lists [`std/List`](/std/List.bruijn.html)
Lists are a repeated composition (right-associative) of pairs with a
`empty`{.bruijn} ending symbol `[[1]]`{.bruijn}. They can store any
(heterogeneous) values and are recursively iterable. The call-by-need
reduction order of bruijn allows lazy evaluation (i.e. infinite lists).
Due to the right-associativeness, writing lists by hand is slightly
annoying. The usage of the `…:…`{.bruijn} [mixfix](mixfix.md) and
`{}‣`{.bruijn} [prefix](prefix.md) functions to denote pairs and the
final `empty`{.bruijn} symbol is encouraged.
Example:
``` bruijn
:test (length (take (+3) (repeat (+4)))) ((+3))
:test (take (+5) (iterate ++‣ (+0))) (((+0) : ((+1) : ((+2) : ((+3) : {}(+4))))))
:test ((foldr …+… (+0) ((+1) : ((+2) : {}(+3)))) =? (+6)) (true)
```
The internal structure of the list encoding means that when a list is
applied to a function, the function is called with the head and tail of
the list.
``` bruijn
:test ("abc" [[1]]) ('a')
:test ("abc" [[0]]) ("bc")
```
## Strings [`std/String`](/std/String.bruijn.html)
Strings are just a list of binary encoded bytes. You may use
[`std/List`](/std/List.bruijn.html) in combination with
[`std/Number/Binary`](/std/Binary.bruijn.html) to interact with them.
Example:
``` bruijn
:test (lines "abc\ndef") ("abc" : {}"def")
:test ("ab" =? "ab") (true)
```
[^1]: [Mogensen, Torben Æ. "An investigation of compact and efficient
number representations in the pure lambda calculus." Perspectives of
System Informatics: 4th International Andrei Ershov Memorial
Conference, PSI 2001 Akademgorodok, Novosibirsk, Russia, July 2--6,
2001 Revised Papers 4. Springer Berlin Heidelberg,
2001.](https://doi.org/10.1007/3-540-45575-2_20)
|
