1 files changed, 111 insertions, 0 deletions
diff --git a/docs/wiki_src/coding/data-structures.md b/docs/wiki_src/coding/data-structures.md
new file mode 100644
index 0000000..384ac29
--- /dev/null
+++ b/docs/wiki_src/coding/data-structures.md
@@ -0,0 +1,111 @@
+# 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))]]]]`,
+    `(-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.
+
+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).
+
+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)
+```
+
+## 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 combinatoin 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)