From 6ae44d09faa0ae353c0818705503cad42127d102 Mon Sep 17 00:00:00 2001 From: Marvin Borner Date: Sun, 3 Mar 2024 15:03:41 +0100 Subject: Even more samples wtf --- samples/rosetta/99_bottles_of_beer.bruijn | 15 ++-- samples/rosetta/a+b.bruijn | 6 ++ samples/rosetta/balanced_ternary.bruijn | 100 +++++++++++++++++++++ samples/rosetta/binary_search.bruijn | 20 +++++ samples/rosetta/comments.bruijn | 1 + samples/rosetta/fibonacci_sequence.bruijn | 20 +++++ samples/rosetta/fizzbuzz.bruijn | 11 +++ samples/rosetta/hamming_numbers.bruijn | 28 ++++++ samples/rosetta/loops_infinite.bruijn | 4 + samples/rosetta/palindrome_detection.bruijn | 6 ++ samples/rosetta/test_a_function.bruijn | 6 ++ .../rosetta/variadic_fixed-point_combinator.bruijn | 22 +++++ samples/rosetta/y_combinator.bruijn | 15 ++++ 13 files changed, 246 insertions(+), 8 deletions(-) create mode 100644 samples/rosetta/a+b.bruijn create mode 100644 samples/rosetta/balanced_ternary.bruijn create mode 100644 samples/rosetta/binary_search.bruijn create mode 100644 samples/rosetta/comments.bruijn create mode 100644 samples/rosetta/fibonacci_sequence.bruijn create mode 100644 samples/rosetta/fizzbuzz.bruijn create mode 100644 samples/rosetta/hamming_numbers.bruijn create mode 100644 samples/rosetta/loops_infinite.bruijn create mode 100644 samples/rosetta/palindrome_detection.bruijn create mode 100644 samples/rosetta/test_a_function.bruijn create mode 100644 samples/rosetta/variadic_fixed-point_combinator.bruijn create mode 100644 samples/rosetta/y_combinator.bruijn (limited to 'samples/rosetta') 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 (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))]]] + +: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 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