WIP more sorting exploration

1 files changed, 56 insertions, 11 deletions

diff --git a/libs/sort.neb b/libs/sort.neb
index 66336e8..27779b1 100644
--- a/libs/sort.neb
+++ b/libs/sort.neb
@@ -1,6 +1,8 @@
 ; sort.neb
 ; an exploration of sorting algorithms in neb
 
+;(use "libs/sugar.neb")
+
 (func bubble (lst)
     (def orig lst)
     (def working (list))
@@ -62,11 +64,20 @@
 (func .insertion-nums (lst)
     (reduce .insert-num lst (list)))
 
-(func insertion (lst :[:string])
-    (insertion-strings lst))
+(func insertion (lst :{:string})
+    (.insertion-strings lst))
+
+(func insertion (lst :{:number})
+    (.insertion-nums lst))
+
+(func insertion (lst :nil) lst)
 
-(func insertion (lst :[:number])
-    (insertion-nums lst))
+(func nil? :bool (candidate :any)
+    (and
+        (list? candidate)
+        (empty? candidate)))
+
+(type :nil :[:any] nil?)
 
 (func insertion-iter (lst)
     (def ret (list))
@@ -75,24 +86,31 @@
         (print (->string ret)))
     ret)
 
-(func merge (lst)
+(func merge :[:string] (lst :[:string])
+    (.merge-cmp lst strcmp))
+
+(func merge :[:number] (lst :[:number])
+    (.merge-cmp lst <))
+
+(func .merge-cmp (lst cmp)
     (print (concat "sorting: " (->string lst)))
     (if (eq? 1 (length lst))
         lst
         (block
             (def half (floor (/ (length lst) 2)))
-            (def left (merge (slice lst 1 half)))
-            (def right (merge (slice lst (+ 1 half))))
-            (.merge left right))))
+            (def left (.merge-cmp (slice lst 1 half) cmp))
+            (def right (.merge-cmp (slice lst (+ 1 half)) cmp))
+            (.merge left right cmp))))
 
-(func .merge (lst1 lst2)
+(func .merge (lst1 lst2 cmp)
     (print (concat "lst1: " (->string lst1)))
     (print (concat "lst2: " (->string lst2)))
     (def res (list))
     (def w1 lst1)
     (def w2 lst2)
     (while (and (not (empty? w1)) (not (empty? w2)))
-        (if (< (first w1) (first w2))
+        ;(if (< (first w1) (first w2))
+        (if (cmp (first w1) (first w2))
             (block
                 (redef res (append res (first w1)))
                 (redef w1 (rest w1)))
@@ -143,7 +161,7 @@
                     (print (concat "consider: " (->string consider))))
                 (extend (append (quick before) pivot) (quick after))))))
 
-(func strcmp (left :string right :string)
+(func strcmp :bool (left :string right :string)
     (branch
         ((or
             (eq? 0 (length left))
@@ -154,3 +172,30 @@
         (#true
             (<= (ord (first left)) (ord (first right))))))
 
+(func strings? (candidate :any)
+    (and
+        (list? candidate)
+        (not (eq? 0 (length candidate)))
+        (apply and
+            (map string? candidate))))
+
+(type :strings :[:string] strings?)
+
+(func sorted? :bool (lst :strings)
+    (.sorted? lst strcmp))
+
+(func sorted? :bool (lst :[:number])
+    (.sorted? lst <=))
+
+;(func sorted? :bool (lst :nil) #true)
+
+(func .sorted? :bool (lst :[:any] cmp)
+    (def a (reverse (rest (reverse lst))))
+    (def b (rest lst))
+    (def acc (list))
+    (for-count (length a)
+        (append acc idx))
+    (empty? (drop-while acc 
+        (cmp 
+            (slice a _item_ 1)
+            (slice b _item_ 1)))))