From ea98cabbe4515bd5248f44214ad870858f1594aa Mon Sep 17 00:00:00 2001
From: Marvin Borner
Date: Tue, 7 Mar 2023 00:20:52 +0100
Subject: Useful additions

hehe
---
 std/Tree/Balanced.bruijn | 13 +++++++++++++
 1 file changed, 13 insertions(+)

(limited to 'std/Tree')

diff --git a/std/Tree/Balanced.bruijn b/std/Tree/Balanced.bruijn
index fe4a155..ab0a921 100644
--- a/std/Tree/Balanced.bruijn
+++ b/std/Tree/Balanced.bruijn
@@ -5,6 +5,7 @@
 
 :import std/Combinator .
 :import std/List L
+:import std/Logic .
 :import std/Number .
 :import std/Option .
 :import std/Pair .
@@ -82,13 +83,25 @@ insert z [[[rec]]] ⧗ Number → (Option BalancedTree) → (Option BalancedTree
 			lt some (node (2 1 //(!0)) ?(!0) \\(!0))
 			gt some (node //(!0) ?(!0) (2 1 \\(!0)))
 
+# returns true if a number is in a tree
+has? z [[[rec]]] ⧗ Number → (Option BalancedTree) → Boolean
+	rec none? 0 false (u 1 ?(!0))
+		u compare-case eq lt gt
+			eq true
+			lt 2 1 //(!0)
+			gt 2 1 \\(!0)
+
+:test (has? (+42) empty) (false)
+
 # number of elements in tree (slow)
 size z [[rec]] ⧗ (Option BalancedTree) → Number
 	rec none? 0 case-empty case-full
 		case-full (1 //(!0)) + (1 \\(!0)) + (+1)
 		case-empty (+0)
 
+# converts a tree to a list
 list! z [[map-or L.empty go 0]] ⧗ (Option BalancedTree) → (List Number)
 	go [L.append (L.append (2 //0) L.{}(?0)) (2 \\0)]
 
+# converts a list to a tree
 from-list L.foldr insert empty ⧗ (List Number) → (Option BalancedTree)
-- 
cgit v1.2.3