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 binary1
  • positive and negative numbers

Boxes std/Box#

Boxes are good for storing single values as immutable object with an empty/full state.

Example:

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) 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:

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#

Lists are a repeated composition (right-associative) of pairs with a empty ending symbol [[1]]. 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 …:… 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)

  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. ↩