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
127
128
129
130
131
|
# 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')
```
Options ([`std/Option`](/std/Option.bruijn.html)) use the same data
structure and have additional definitions to resemble Haskell's
`Maybe`{.haskell}.
## 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/Number/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)
|
