13 files changed, 246 insertions, 8 deletions
diff --git a/samples/rosetta/99_bottles_of_beer.bruijn b/samples/rosetta/99_bottles_of_beer.bruijn
index 7ff3371..afaffdd 100644
--- a/samples/rosetta/99_bottles_of_beer.bruijn
+++ b/samples/rosetta/99_bottles_of_beer.bruijn
@@ -2,11 +2,10 @@
 :import std/Number .
 :import std/String .
 
-main y [[rec]] (+99)
-	rec =?0 case-end case-rec
-		case-rec n ++ t1 ++ n ++ t2 ++ t3 ++ n ++ t1 ++ "\n" ++ (1 --0)
-			n number→string 0
-			t1 " bottles of beer on the wall\n"
-			t2 " bottles of beer\n"
-			t3 "Take one down, pass it around\n"
-		case-end empty
+main [y [[=?0 case-end case-rec]] (+99)]
+	case-rec n ++ t1 ++ n ++ t2 ++ t3 ++ n ++ t1 ++ "\n" ++ (1 --0)
+		n number→string 0
+		t1 " bottles of beer on the wall\n"
+		t2 " bottles of beer\n"
+		t3 "Take one down, pass it around\n"
+	case-end empty
diff --git a/samples/rosetta/a+b.bruijn b/samples/rosetta/a+b.bruijn
new file mode 100644
index 0000000..e6be660
--- /dev/null
+++ b/samples/rosetta/a+b.bruijn
@@ -0,0 +1,6 @@
+:import std/Combinator .
+:import std/String .
+:import std/Number .
+:import std/Char C
+
+main (split-by (C.eq? ' ')) → &(add ⋔ string→number)
diff --git a/samples/rosetta/balanced_ternary.bruijn b/samples/rosetta/balanced_ternary.bruijn
new file mode 100644
index 0000000..5f7aa99
--- /dev/null
+++ b/samples/rosetta/balanced_ternary.bruijn
@@ -0,0 +1,100 @@
+:import std/Combinator .
+:import std/Logic .
+:import std/Pair .
+
+# negative trit indicating coefficient of (-1)
+t⁻ [[[2]]]
+
+# positive trit indicating coefficient of (+1)
+t⁺ [[[1]]]
+
+# zero trit indicating coefficient of 0
+t⁰ [[[0]]]
+
+# shifts a negative trit into a balanced ternary number
+↑⁻‣ [[[[[2 (4 3 2 1 0)]]]]]
+
+# shifts a positive trit into a balanced ternary number
+↑⁺‣ [[[[[1 (4 3 2 1 0)]]]]]
+
+# shifts a zero trit into a balanced ternary number
+↑⁰‣ [[[[[0 (4 3 2 1 0)]]]]]
+
+# shifts a specified trit into a balanced ternary number
+…↑… [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]]
+
+# negates a balanced ternary number
+-‣ [[[[[4 3 1 2 0]]]]]
+
+# increments a balanced ternary number (can introduce leading 0s)
+++‣ [~(0 z a⁻ a⁺ a⁰)]
+	z (+0) : (+1)
+	a⁻ &[[↑⁻1 : ↑⁰1]]
+	a⁺ &[[↑⁺1 : ↑⁻0]]
+	a⁰ &[[↑⁰1 : ↑⁺1]]
+
+# decrements a balanced ternary number (can introduce leading 0s)
+--‣ [~(0 z a⁻ a⁺ a⁰)]
+	z (+0) : (-1)
+	a⁻ &[[↑⁻1 : ↑⁺0]]
+	a⁺ &[[↑⁺1 : ↑⁰1]]
+	a⁰ &[[↑⁰1 : ↑⁻1]]
+
+# converts the normal balanced ternary representation into abstract form
+→^‣ [0 z a⁻ a⁺ a⁰]
+	z (+0)
+	a⁻ [[[[[2 4]]]]]
+	a⁺ [[[[[1 4]]]]]
+	a⁰ [[[[[0 4]]]]]
+
+# converts the abstracted balanced ternary representation back to normal
+→_‣ y [[0 z a⁻ a⁺ a⁰]]
+	z (+0)
+	a⁻ [↑⁻(2 0)]
+	a⁺ [↑⁺(2 0)]
+	a⁰ [↑⁰(2 0)]
+
+# adds two balanced ternary numbers (can introduce leading 0s)
+…+… [[[c (0 z a⁻ a⁺ a⁰)] 1 →^0]]
+	b⁻ [1 ↑⁺(3 0 t⁻) ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁰)]
+	b⁰ [1 ↑ (3 0 t⁰)]
+	b⁺ [1 ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁺) ↑⁺(3 0 t⁰)]
+	a⁻ [[[1 (b⁻ 1) b⁻' b⁰ b⁻]]]
+		b⁻' [1 ↑⁰(3 0 t⁻) ↑⁻(3 0 t⁰) ↑⁺(3 0 t⁻)]
+	a⁺ [[[1 (b⁺ 1) b⁰ b⁺' b⁺]]]
+		b⁺' [1 ↑⁺(3 0 t⁰) ↑⁰(3 0 t⁺) ↑⁻(3 0 t⁺)]
+	a⁰ [[[1 (b⁰ 1) b⁻ b⁺ b⁰]]]
+	z [[0 --(→_1) ++(→_1) →_1]]
+	c [[1 0 t⁰]]
+
+# subtracts two balanced ternary numbers (can introduce leading 0s)
+…-… [[1 + -0]]
+
+# multiplicates two balanced ternary numbers (can introduce leading 0s)
+…⋅… [[1 z a⁻ a⁺ a⁰]]
+	z (+0)
+	a⁻ [↑⁰0 - 1]
+	a⁺ [↑⁰0 + 1]
+	a⁰ [↑⁰0]
+
+# true if balanced ternary number is zero
+=?‣ [0 true [false] [false] i]
+
+# true if two balanced ternary numbers are equal
+# → ignores leading 0s!
+…=?… [[[0 z a⁻ a⁺ a⁰] 1 →^0]]
+	z [=?(→_0)]
+	a⁻ [[0 false [2 0] [false] [false]]]
+	a⁺ [[0 false [false] [2 0] [false]]]
+	a⁰ [[0 (1 0) [false] [false] [2 0]]]
+
+main [[0]]
+
+# --- tests/examples ---
+
+:test ((-42) + (-1) =? (-43)) (true)
+:test ((+1) + (+2) =? (+3)) (true)
+:test ((-42) - (-1) =? (-41)) (true)
+:test ((+1) - (+2) =? (-1)) (true)
+:test ((-1) ⋅ (+42) =? (-42)) (true)
+:test ((+3) ⋅ (+11) =? (+33)) (true)
diff --git a/samples/rosetta/binary_search.bruijn b/samples/rosetta/binary_search.bruijn
new file mode 100644
index 0000000..87f01ba
--- /dev/null
+++ b/samples/rosetta/binary_search.bruijn
@@ -0,0 +1,20 @@
+:import std/Combinator .
+:import std/Math .
+:import std/List .
+:import std/Option .
+
+binary-search [y [[[[[2 <? 3 none go]]]]] (+0) --(∀0) 0]
+	go [compare-case eq lt gt (2 !! 0) 1] /²(3 + 2)
+		eq some 0
+		lt 5 4 --0 2 1
+		gt 5 ++0 3 2 1
+
+# example using sorted list of x^3, x=[-50,50]
+find [[map-or "not found" [0 : (1 !! 0)] (binary-search 0 1)] lst]
+	lst take (+100) ((\pow (+3)) <$> (iterate ++‣ (-50)))
+
+:test (find (+100)) ("not found")
+:test ((head (find (+125))) =? (+55)) ([[1]])
+:test ((head (find (+117649))) =? (+99)) ([[1]])
+
+main [[0]]
diff --git a/samples/rosetta/comments.bruijn b/samples/rosetta/comments.bruijn
new file mode 100644
index 0000000..7dd15c1
--- /dev/null
+++ b/samples/rosetta/comments.bruijn
@@ -0,0 +1 @@
+# This is a comment
diff --git a/samples/rosetta/fibonacci_sequence.bruijn b/samples/rosetta/fibonacci_sequence.bruijn
new file mode 100644
index 0000000..d2e4752
--- /dev/null
+++ b/samples/rosetta/fibonacci_sequence.bruijn
@@ -0,0 +1,20 @@
+:import std/Combinator .
+:import std/Math .
+:import std/List .
+
+# unary/Church fibonacci (moderately fast but very high space complexity)
+fib-unary [0 [[[2 0 [2 (1 0)]]]] k i]
+
+:test (fib-unary (+6u)) ((+8u))
+
+# ternary fibonacci using infinite list iteration (very fast)
+fib-list \index fibs
+	fibs head <$> (iterate &[[0 : (1 + 0)]] ((+0) : (+1)))
+
+:test (fib-list (+6)) ((+8))
+
+# recursive fib (very slow)
+fib-rec y [[0 <? (+1) (+0) (0 <? (+2) (+1) rec)]]
+	rec (1 --0) + (1 --(--0))
+
+:test (fib-rec (+6)) ((+8))
diff --git a/samples/rosetta/fizzbuzz.bruijn b/samples/rosetta/fizzbuzz.bruijn
new file mode 100644
index 0000000..7f61704
--- /dev/null
+++ b/samples/rosetta/fizzbuzz.bruijn
@@ -0,0 +1,11 @@
+:import std/Combinator .
+:import std/String .
+:import std/Number .
+
+main [y [[0 =? (+101) case-end case-rec]] (+1)]
+	case-rec str ++ "\n" ++ (1 ++0)
+		str fizzbuzz "FizzBuzz" (fizz "Fizz" (buzz "Buzz" (number→string 0)))
+			fizz =?(0 % (+3))
+			buzz =?(0 % (+5))
+			fizzbuzz fizz buzz fizz
+	case-end empty
diff --git a/samples/rosetta/hamming_numbers.bruijn b/samples/rosetta/hamming_numbers.bruijn
new file mode 100644
index 0000000..426223d
--- /dev/null
+++ b/samples/rosetta/hamming_numbers.bruijn
@@ -0,0 +1,28 @@
+:import std/Combinator .
+:import std/Number .
+:import std/List .
+
+merge y [[[∅?1 0 (1 [[2 [[go]]]])]]]
+	go 3 <? 1 (3 : (6 2 4)) (1 : (6 5 0))
+
+# classic version while avoiding duplicate generation
+hammings-classic (+1) : (foldr u empty ((+2) : ((+3) : {}(+5))))
+	u [[y [merge 1 ((mul 2) <$> ((+1) : 0))]]]
+
+:test ((hammings-classic !! (+42)) =? (+162)) ([[1]])
+
+# enumeration by a chain of folded merges (faster)
+hammings-folded ([(0 ∘ a) ∘ (0 ∘ b)] (foldr merge1 empty)) $ c
+	merge1 [[1 [[1 : (merge 0 2)]]]]
+	a iterate (map (mul (+5)))
+	b iterate (map (mul (+3)))
+	c iterate (mul (+2)) (+1)
+
+:test ((hammings-folded !! (+42)) =? (+162)) ([[1]])
+
+# --- output ---
+
+main [first-twenty : (n1691 : {}n1000000)]
+	first-twenty take (+20) hammings-folded
+	n1691 hammings-folded !! (+1690)
+	n1000000 hammings-folded !! (+999999)
diff --git a/samples/rosetta/loops_infinite.bruijn b/samples/rosetta/loops_infinite.bruijn
new file mode 100644
index 0000000..badcec1
--- /dev/null
+++ b/samples/rosetta/loops_infinite.bruijn
@@ -0,0 +1,4 @@
+:import std/String .
+
+main [spam spam]
+	spam ["SPAM\n" ++ (0 0)]
diff --git a/samples/rosetta/palindrome_detection.bruijn b/samples/rosetta/palindrome_detection.bruijn
new file mode 100644
index 0000000..f4c05b2
--- /dev/null
+++ b/samples/rosetta/palindrome_detection.bruijn
@@ -0,0 +1,6 @@
+:import std/String .
+
+main [<~>0 =? 0]
+
+:test (main "tacocat") ([[1]])
+:test (main "bruijn") ([[0]])
diff --git a/samples/rosetta/test_a_function.bruijn b/samples/rosetta/test_a_function.bruijn
new file mode 100644
index 0000000..dc76eeb
--- /dev/null
+++ b/samples/rosetta/test_a_function.bruijn
@@ -0,0 +1,6 @@
+:import std/String .
+
+main [<~>0 =? 0]
+
+:test (main "tacocat") ([[1]])
+:test (main "bruijn") ([[1]])
diff --git a/samples/rosetta/variadic_fixed-point_combinator.bruijn b/samples/rosetta/variadic_fixed-point_combinator.bruijn
new file mode 100644
index 0000000..cf50875
--- /dev/null
+++ b/samples/rosetta/variadic_fixed-point_combinator.bruijn
@@ -0,0 +1,22 @@
+:import std/Number .
+:import std/List .
+
+y* [[[0 1] <$> 0] ([[1 <! ([[1 2 0]] <$> 0)]] <$> 0)]
+
+# --- example usage ---
+# mutual recurrence relation of odd?/even?
+
+# even x = if x == 0 then true else odd? (x-1)
+g [[[=?0 [[1]] (1 --0)]]]
+
+# odd x = if x == 0 then false else even? (x-1)
+h [[[=?0 [[0]] (2 --0)]]]
+
+even? ^(y* (g : {}h))
+
+odd? _(y* (g : {}h))
+
+:test (even? (+5)) ([[0]])
+:test (odd? (+5)) ([[1]])
+
+main [[0]]
diff --git a/samples/rosetta/y_combinator.bruijn b/samples/rosetta/y_combinator.bruijn
new file mode 100644
index 0000000..95a985b
--- /dev/null
+++ b/samples/rosetta/y_combinator.bruijn
@@ -0,0 +1,15 @@
+:import std/Number .
+
+# sage bird combinator
+y [[1 (0 0)] [1 (0 0)]]
+
+# factorial using y
+factorial y [[=?0 (+1) (0 ⋅ (1 --0))]]
+
+:test ((factorial (+6)) =? (+720)) ([[1]])
+
+# (very slow) fibonacci using y
+fibonacci y [[0 <? (+1) (+0) (0 <? (+2) (+1) rec)]]
+	rec (1 --0) + (1 --(--0))
+
+:test ((fibonacci (+6)) =? (+8)) ([[1]])