Data structures#
Bruijn's standard library defines several common data structures.
Relevant blog post: Data structures in pure lambda calculus.
States#
For storing states (i.e. enums), you can use the available libraries and syntactic sugar.
Booleans/bits std/Logic
#
 typical Church booleans  fast and reliable
 encoding:
true
=[[1]]
,false
=[[0]]
Unary numbers std/Number/Unary
#
u
suffix for syntactic sugar, e.g.(+3u)
 encoding:
(+4u)
=[[(1 (1 (1 (1 0))))]]
 typical Church numerals, simple but high space/time complexity
 only positive numbers
Binary numbers std/Number/Binary
#
b
suffix for syntactic sugar, e.g.(+3b)
 encoding:
(+4b)
=[[[0 (0 (1 2))]]]
 encoding for chars/strings, e.g.
'0'
=(+48b)
 faster and more compact than unary
 only positive numbers (excluding two's complement)
Balanced ternary std/Number/Ternary
#
 default syntactic sugar for numbers (optional suffix
t
), e.g.(+3)
 encoding:
(+4)
=[[[[(1 (1 3))]]]]
,(4)
=[[[[(2 (2 3))]]]]
 faster and more compact than binary^{1}
 positive and negative numbers
Boxes std/Box
#
Boxes are good for storing single values as immutable object with an empty/full state.
Example:
abox <>'a'
:test (set? abox) (true)
:test (get 'b' abox) ('a')
:test (get 'b' empty) ('b')
:test (store! abox 'b') (<>'b')
Options (std/Option
) use the same data
structure and have additional definitions to resemble Haskell's
Maybe
.
Pairs std/Pair
#
Pairs (tuples) can store any two terms. Pairs can be constructed using
the …:…
mixfix function.
Example:
onetwo (+1) : (+2)
:test (^onetwo) ((+1))
:test (~onetwo) ((+2))
:test (inc <$> onetwo) ((+2) : (+3))
:test (uncurry add onetwo) ((+3))
Lists std/List
#
Lists are a repeated composition (rightassociative) of pairs with a
empty
ending symbol [[1]]
. They can store any
(heterogeneous) values and are recursively iterable. The callbyneed
reduction order of bruijn allows lazy evaluation (i.e. infinite lists).
Due to the rightassociativeness, writing lists by hand is slightly
annoying. The usage of the …:…
mixfix and
{}‣
prefix functions to denote pairs and the
final empty
symbol is encouraged.
Example:
: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.
:test ("abc" [[1]]) ('a')
:test ("abc" [[0]]) ("bc")
Strings std/String
#
Strings are just a list of binary encoded bytes. You may use
std/List
in combination with
std/Number/Binary
to interact with
them.
Example:
:test (lines "abc\ndef") ("abc" : {}"def")
:test ("ab" =? "ab") (true)

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 26, 2001 Revised Papers 4. Springer Berlin Heidelberg, 2001. ↩