From 757022c288868cc5fb4212fe3cb5ebcaa794c0f9 Mon Sep 17 00:00:00 2001 From: Eduardo Julian Date: Tue, 28 Mar 2017 20:53:27 -0400 Subject: - Implemented finger-trees. - Implemented random-access sequences and priority-queues on top of finger-trees. --- stdlib/test/test/lux/data/coll/list.lux | 2 +- stdlib/test/test/lux/data/coll/priority-queue.lux | 56 ++++++++++ stdlib/test/test/lux/data/coll/seq.lux | 128 ++++++++++++++++++++++ stdlib/test/tests.lux | 4 +- 4 files changed, 188 insertions(+), 2 deletions(-) create mode 100644 stdlib/test/test/lux/data/coll/priority-queue.lux create mode 100644 stdlib/test/test/lux/data/coll/seq.lux (limited to 'stdlib/test') 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 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 + [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 sample non-member)) + (&;member? number;Eq (&;push non-member-priority non-member sample) + non-member)) + (and (&;member? number;Eq sample (&;peek sample)) + (not (&;member? number;Eq (&;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] + [number] + [bool] + [product]) + ["R" math/random] + pipe) + lux/test) + +(def: bounded-size + (R;Random Nat) + (|> R;nat + (:: R;Monad 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 number;Eq)]] + ($_ 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 + (&;prepend extra sample) + extra) + (&;member? number;Eq + (&;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 number;Eq) + (^open "&/") &;Functor]] + ($_ 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 number;Eq) + (^open "&/") &;Monad]] + ($_ 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] -- cgit v1.2.3