- Implemented finger-trees.

- Implemented random-access sequences and priority-queues on top of finger-trees.

4 files changed, 188 insertions, 2 deletions

diff --git a/stdlib/test/test/lux/data/coll/list.lux b/stdlib/test/test/lux/data/coll/list.lux
index e1705291a..fe381340d 100644
--- a/stdlib/test/test/lux/data/coll/list.lux
+++ b/stdlib/test/test/lux/data/coll/list.lux
@@ -55,7 +55,7 @@
                      (&;empty? (&;filter (bool;complement n.even?) sample)))
                 (&;any? (bool;complement n.even?) sample)))
 
-      (assert "Any element of the list can be considered it's member."
+      (assert "Any element of the list can be considered its member."
               (let [elem (default (undefined)
                            (&;nth idx sample))]
                 (&;member? number;Eq<Nat> sample elem)))
diff --git a/stdlib/test/test/lux/data/coll/priority-queue.lux b/stdlib/test/test/lux/data/coll/priority-queue.lux
new file mode 100644
index 000000000..5c53edfb1
--- /dev/null
+++ b/stdlib/test/test/lux/data/coll/priority-queue.lux
@@ -0,0 +1,56 @@
+(;module:
+  lux
+  (lux [io]
+       (control monad)
+       (data (coll ["&" priority-queue])
+             [number])
+       ["R" math/random]
+       pipe)
+  lux/test)
+
+(def: (gen-queue size)
+  (-> Nat (R;Random (&;Queue Nat)))
+  (do R;Monad<Random>
+    [inputs (R;list size R;nat)]
+    (case inputs
+      (#;Cons head tail)
+      (loop [head head
+             tail tail]
+        (do @
+          [priority R;nat]
+          (case tail
+            (#;Cons head' tail')
+            (do @
+              [=tail (recur head' tail')]
+              (wrap (&;push priority head =tail)))
+
+            _
+            (wrap (&;new priority head)))))
+
+      _
+      (undefined))))
+
+(test: "Queues"
+  [size (|> R;nat
+            (:: @ map (|>. (n.% +100) (n.max +1))))
+   sample (gen-queue size)
+   non-member-priority R;nat
+   non-member R;nat]
+  ($_ seq
+      (assert "I can query the size of a queue (and empty queues have size 0)."
+              (n.= size (&;size sample)))
+
+      (assert "Enqueueing and dequeing affects the size of queues."
+              (and (n.= (n.inc size)
+                        (&;size (&;push non-member-priority non-member sample)))
+                   (or (n.= +1 (&;size sample))
+                       (n.= (n.dec size)
+                            (&;size (&;pop sample))))))
+
+      (assert "I can query whether an element belongs to a queue."
+              (and (and (not (&;member? number;Eq<Nat> sample non-member))
+                        (&;member? number;Eq<Nat> (&;push non-member-priority non-member sample)
+                                   non-member))
+                   (and (&;member? number;Eq<Nat> sample (&;peek sample))
+                        (not (&;member? number;Eq<Nat> (&;pop sample) (&;peek sample))))))
+      ))
diff --git a/stdlib/test/test/lux/data/coll/seq.lux b/stdlib/test/test/lux/data/coll/seq.lux
new file mode 100644
index 000000000..e62f36854
--- /dev/null
+++ b/stdlib/test/test/lux/data/coll/seq.lux
@@ -0,0 +1,128 @@
+(;module:
+  lux
+  (lux [io]
+       (control monad)
+       (data (coll ["&" seq]
+                   ["F" tree/finger]
+                   ["L" list])
+             [text "Text/" Monoid<Text>]
+             [number]
+             [bool]
+             [product])
+       ["R" math/random]
+       pipe)
+  lux/test)
+
+(def: bounded-size
+  (R;Random Nat)
+  (|> R;nat
+      (:: R;Monad<Random> map (|>. (n.% +100) (n.+ +10) (n.max +1)))))
+
+(test: "Seqs: Part 1"
+  [size bounded-size
+   idx (:: @ map (n.% size) R;nat)
+   sample (|> (R;list size R;nat)
+              (:: @ map (|>. &;from-list (default (undefined)))))
+   extra R;nat
+   #let [(^open "&/") (&;Eq<Seq> number;Eq<Nat>)]]
+  ($_ seq
+      (assert "Can convert to/from list."
+              (|> sample
+                  &;to-list &;from-list (default (undefined))
+                  (&/= sample)))
+      
+      (assert "The size function should correctly portray the size of the seq."
+              (n.= size (&;size sample)))
+
+      (assert "Reversing a seq does not change it's size."
+              (n.= (&;size sample)
+                   (&;size (&;reverse sample))))
+      
+      (assert "Reversing a seq twice results in the original seq."
+              (&/= sample
+                   (&;reverse (&;reverse sample))))
+
+      (assert "If every element in a list satisfies a predicate, there can't be any that satisfy its complement."
+              (if (&;every? n.even? sample)
+                (not (&;any? (bool;complement n.even?) sample))
+                (&;any? (bool;complement n.even?) sample)))
+
+      (assert "Any element of the list can be considered its member."
+              (and (&;member? number;Eq<Nat>
+                              (&;prepend extra sample)
+                              extra)
+                   (&;member? number;Eq<Nat>
+                              (&;append extra sample)
+                              extra)))
+      
+      (assert "Can do random access to seq elements."
+              (and (|> (&;prepend extra sample)
+                       (&;nth +0)
+                       (case> (#;Some reference)
+                              (n.= reference extra)
+
+                              _
+                              false))
+                   (|> (&;append extra sample)
+                       (&;nth size)
+                       (case> (#;Some reference)
+                              (n.= reference extra)
+
+                              _
+                              false))))
+      ))
+
+(test: "Seqs: Part 2"
+  [size bounded-size
+   sample (|> (R;list size R;nat)
+              (:: @ map (|>. &;from-list (default (undefined)))))
+   #let [(^open "&/") (&;Eq<Seq> number;Eq<Nat>)
+         (^open "&/") &;Functor<Seq>]]
+  ($_ seq
+      (assert "Functor should go over every element of the seq."
+              (let [there (&/map n.inc sample)
+                    back-again (&/map n.dec there)]
+                (and (not (&/= sample there))
+                     (&/= sample back-again))))
+
+      (assert "Sorting a seq shouldn't change it's size."
+              (n.= (&;size sample)
+                   (&;size (&;sort n.< sample))))
+
+      (assert "Sorting a seq with one order should yield the reverse of sorting it with the opposite order."
+              (&/= (&;sort n.< sample)
+                   (&;reverse (&;sort n.> sample))))
+      ))
+
+(test: "Seqs: Part 3"
+  [size bounded-size
+   idx (:: @ map (n.% size) R;nat)
+   sample (|> (R;list size R;nat)
+              (:: @ map (|>. &;from-list (default (undefined)))))
+   other-size bounded-size
+   other-sample (|> (R;list other-size R;nat)
+                    (:: @ map (|>. &;from-list (default (undefined)))))
+   elem R;nat
+   #let [(^open "&/") (&;Eq<Seq> number;Eq<Nat>)
+         (^open "&/") &;Monad<Seq>]]
+  ($_ seq
+      (assert "Applicative allows you to create singleton seqs, and apply seqs of functions to seqs of values."
+              (and (&/= (&;seq elem) (&/wrap elem))
+                   (&/= (&/map n.inc sample)
+                        (&/apply (&/wrap n.inc) sample))))
+
+      (assert "Seq concatenation is a monad."
+              (&/= (F;branch sample other-sample)
+                   (&/join (&;seq sample other-sample))))
+
+      (assert "You can find any value that satisfies some criterium, if such values exist in the seq."
+              (case (&;find n.even? sample)
+                (#;Some found)
+                (and (n.even? found)
+                     (&;any? n.even? sample)
+                     (not (&;every? (bool;complement n.even?) sample)))
+
+                #;None
+                (and (not (&;any? n.even? sample))
+                     (&;every? (bool;complement n.even?) sample))))
+      ))
diff --git a/stdlib/test/tests.lux b/stdlib/test/tests.lux
index d92595424..c066e551e 100644
--- a/stdlib/test/tests.lux
+++ b/stdlib/test/tests.lux
@@ -48,7 +48,9 @@
                          [stack]
                          ## [vector]
                          (tree [rose]
-                               [zipper]))
+                               [zipper])
+                         ["_;" seq]
+                         ["_;" priority-queue])
                    (text [format])
                    )
              ["_;" math]