diff options
| author | Marvin Borner | 2022-09-02 13:14:39 +0200 |
|---|---|---|
| committer | Marvin Borner | 2022-09-02 13:14:39 +0200 |
| commit | 336a1b4426713bd1c74e16f6a2af5c08d48f6f22 (patch) | |
| tree | ef197f6b8ac518b8305bc1c9dd945794e21f8a0b | |
| parent | cad52ec9b82015c352e39fbe6cf72234d097ca2b (diff) | |
Improved mst/last performance
| -rw-r--r-- | std/List.bruijn | 11 | ||||
| -rw-r--r-- | std/Number.bruijn | 33 |
2 files changed, 22 insertions, 22 deletions
diff --git a/std/List.bruijn b/std/List.bruijn index 02d55a7..f0cbc47 100644 --- a/std/List.bruijn +++ b/std/List.bruijn @@ -161,10 +161,13 @@ filter z [[[rec]]] :test (((+1) : ((+0) : ((+3) : empty))) <#> zero?) ((+0) : empty) # returns the last element of a list -last z [[rec]] - rec <>?0 case-end case-last - case-last <>?(~0) ^0 (1 ~0) - case-end empty +# - slow algorithm: +# last z [[rec]] +# rec <>?0 case-end case-last +# case-last <>?(~0) ^0 (1 ~0) +# case-end empty +# - taking the first element of the reversed list is actually way faster because laziness +last ^‣ ∘ <~>‣ _‣ last diff --git a/std/Number.bruijn b/std/Number.bruijn index 3049dad..ae4a3ac 100644 --- a/std/Number.bruijn +++ b/std/Number.bruijn @@ -106,16 +106,23 @@ lst [0 t⁰ [t⁻] [t⁺] [t⁰]] :test (lst (+1)) (t⁺) :test (lst (+42)) (t⁰) +# checks true if balanced ternary number is zero +zero? [0 true [false] [false] i] + +=?‣ zero? + +:test (=?(+0)) (true) +:test (=?(-1)) (false) +:test (=?(+1)) (false) +:test (=?(+42)) (false) + # extracts most significant trit from balanced ternary numbers -# TODO: Find a more elegant/fast way to do this (and resolve list import loop?) -# mst z [[[rec]]] (+0) -# rec =?0 case-end case-mst -# case-mst 2 0 /³0 -# case-end lst 1 -mst [fix (last (list! %0))] - last z [[<>?0 [false] (<>?(~0) ^0 (1 ~0))]] +# <~>/<>? 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 +mst [=?0 t⁰ ^(<~>(list! %0))] + <~>‣ z [[[[<>?0 1 (3 2 (2 1 ^0) ~0)]]]] f false <>?‣ [0 [[[false]]] true] - fix [((t⁻? 0) ⋁? (t⁺? 0) ⋁? (t⁰? 0)) 0 t⁰] :test (mst (-1)) (t⁻) :test (mst (+0)) (t⁰) @@ -142,16 +149,6 @@ positive? [t⁺? (mst 0)] :test (>?(+1)) (true) :test (>?(+42)) (true) -# checks true if balanced ternary number is zero -zero? [0 true [false] [false] i] - -=?‣ zero? - -:test (=?(+0)) (true) -:test (=?(-1)) (false) -:test (=?(+1)) (false) -:test (=?(+42)) (false) - # converts the normal balanced ternary representation into abstract # infinity can't be abstracted in finite time # → the abstract representation is used in eq?/add/sub/mul |