More efficient mst functions

2 files changed, 24 insertions, 25 deletions

diff --git a/std/Number/Binary.bruijn b/std/Number/Binary.bruijn
index 2d36c5f..2f0fbce 100644
--- a/std/Number/Binary.bruijn
+++ b/std/Number/Binary.bruijn
@@ -85,7 +85,7 @@ lst [0 b⁰ [b¹] [b⁰]] ⧗ Binary → Bit
 
 # extracts most significant bit from a binary number
 # not really useful for binary numbers, but part of interface
-mst [=?0 b⁰ ^(<~>(list! %0))] ⧗ Binary → Bit
+mst [=?0 b⁰ b¹] ⧗ Binary → Bit
 
 :test (mst (+0b)) (b⁰)
 :test (mst (+1b)) (b¹)
diff --git a/std/Number/Ternary.bruijn b/std/Number/Ternary.bruijn
index a92fa5e..84f4d4a 100644
--- a/std/Number/Ternary.bruijn
+++ b/std/Number/Ternary.bruijn
@@ -3,6 +3,7 @@
 # → refer to std/Math for more advanced functions
 # Heavily inspired by the works of T.Æ. Mogensen and Douglas W. Jones (see refs in README)
 
+:import std/Box B
 :import std/Combinator .
 :import std/Logic .
 :import std/Pair .
@@ -129,13 +130,11 @@ lst [0 t⁰ [t⁻] [t⁺] [t⁰]] ⧗ Number → Trit
 :test (lst (+42)) (t⁰)
 
 # extracts most significant trit from a balanced ternary number
-# <~>/<>? are hardcoded because list import would be recursive (TODO?)
-# while this looks incredibly inefficient it's actually fairly fast because laziness
-# TODO: find way of removing requirement of stripping first
-#       (or better solution in general)
-mst [=?0 t⁰ ^(<~>(list! %0))] ⧗ Number → Trit
-	<~>‣ z [[[[<>?0 1 (3 2 (2 1 ^0) ~0)]]]] f false
-		<>?‣ [0 [[[false]]] true]
+mst [B.get t⁰ (0 z a⁻ a⁺ a⁰)] ⧗ Number → Trit
+	z B.empty
+	a⁻ [B.store! 0 t⁻]
+	a⁺ [B.store! 0 t⁺]
+	a⁰ [0]
 
 :test (mst (-1)) (t⁻)
 :test (mst (+0)) (t⁰)
@@ -178,11 +177,11 @@ abstract! [0 z a⁻ a⁺ a⁰] ⧗ Number → AbstractNumber
 :test (→^(+3)) ([[[[0 [[[[1 [[[[3]]]]]]]]]]]])
 
 # converts the abstracted balanced ternary representation back to normal
-normal! ω [[0 z a⁻ a⁺ a⁰]] ⧗ AbstractNumber → Number
+normal! y [[0 z a⁻ a⁺ a⁰]] ⧗ AbstractNumber → Number
 	z (+0)
-	a⁻ [↑⁻([3 3 0] 0)]
-	a⁺ [↑⁺([3 3 0] 0)]
-	a⁰ [↑⁰([3 3 0] 0)]
+	a⁻ [↑⁻(2 0)]
+	a⁺ [↑⁺(2 0)]
+	a⁰ [↑⁰(2 0)]
 
 →_‣ normal!
 
@@ -231,11 +230,11 @@ inc [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number
 
 ++‣ inc
 
-:test ((++(-42)) =? (-41)) (true)
-:test ((++(-1)) =? (+0)) (true)
-:test ((++(+0)) =? (+1)) (true)
-:test ((++(++(++(++(++(+0)))))) =? (+5)) (true)
-:test ((++(+42)) =? (+43)) (true)
+:test (++(-42) =? (-41)) (true)
+:test (++(-1) =? (+0)) (true)
+:test (++(+0) =? (+1)) (true)
+:test (++(++(++(++(++(+0))))) =? (+5)) (true)
+:test (++(+42) =? (+43)) (true)
 
 # subs (+1) from a balanced ternary number (can introduce leading 0s)
 dec [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number
@@ -246,11 +245,11 @@ dec [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number
 
 --‣ dec
 
-:test ((--(-42)) =? (-43)) (true)
-:test ((--(+0)) =? (-1)) (true)
-:test ((--(--(--(--(--(+5)))))) =? (+0)) (true)
-:test ((--(+1)) =? (+0)) (true)
-:test ((--(+42)) =? (+41)) (true)
+:test (--(-42) =? (-43)) (true)
+:test (--(+0) =? (-1)) (true)
+:test (--(--(--(--(--(+5))))) =? (+0)) (true)
+:test (--(+1) =? (+0)) (true)
+:test (--(+42) =? (+41)) (true)
 
 # adds two balanced ternary numbers (can introduce leading 0s)
 # second argument gets abstracted (performance)
@@ -412,8 +411,8 @@ binary-search z [[[[rec]]]] ⧗ (Number → Boolean) → Number → Number → N
 ternary-search z [[[[rec]]]] ⧗ (Number → Number) → Number → Number → Number
 	rec (1 =? 0) case-end case-search
 		case-search go (1 + /³*(0 - 1)) (0 - /³*(0 - 1))
+			call [=?0 (6 5 ++2 --1) (>?0 (6 5 4 --1) (6 5 ++2 3))]
 			go [[call ((4 1) - (4 0))]]
-				call [=?0 (6 5 ++2 --1) (>?0 (6 5 4 --1) (6 5 ++2 3))]
 		case-end 0
 
 :test ((ternary-search [-((0 - (+3)) ⋅ (0 - (+3)))] (+0) (+5)) =? (+3)) (true)
@@ -443,7 +442,7 @@ mod ~‣ ∘∘ quot-rem ⧗ Number → Number
 
 # returns true if the number is even (remainder mod 2 == 0)
 # TODO: faster solution (using tupling?)
-even? z [[rec]]
+even? z [[rec]] ⧗ Number → Boolean
 	rec =?0 case-end case-rec
 		case-rec t⁰? (lst 0) (1 /³0) ¬(1 /³0)
 		case-end true
@@ -454,7 +453,7 @@ even? z [[rec]]
 :test (even? (+42)) (true)
 
 # returns true if the number is odd (remainder mod 2 == 1)
-odd? ¬‣ ∘ even?
+odd? ¬‣ ∘ even? ⧗ Number → Boolean
 
 :test (odd? (+0)) (false)
 :test (odd? (+1)) (true)