diff options
author | 2018-12-14 15:26:21 -0500 | |
---|---|---|
committer | 2018-12-14 15:26:21 -0500 | |
commit | 720e1cb2c84dfd274fcbfd7bf4974a1c110501cb (patch) | |
tree | 643890450a4a2231e7aa2971fa73f776943bdc33 | |
parent | 6d87f78102bba77bc090ca3fb105597d3ce3748f (diff) |
List.assocAddSorted
-rw-r--r-- | lib/ur/list.ur | 16 | ||||
-rw-r--r-- | lib/ur/list.urs | 3 |
2 files changed, 19 insertions, 0 deletions
diff --git a/lib/ur/list.ur b/lib/ur/list.ur index 0da9316e..10877420 100644 --- a/lib/ur/list.ur +++ b/lib/ur/list.ur @@ -479,6 +479,22 @@ fun assocAdd [a] [b] (_ : eq a) (x : a) (y : b) (ls : t (a * b)) = None => (x, y) :: ls | Some _ => ls +fun assocAddSorted [a] [b] (_ : eq a) (_ : ord a) (x : a) (y : b) (ls : t (a * b)) = + let + fun aas (ls : t (a * b)) (acc : t (a * b)) = + case ls of + [] => rev ((x, y) :: acc) + | (x', y') :: ls' => + if x' = x then + revAppend ((x, y) :: acc) ls' + else if x < x' then + revAppend ((x, y) :: acc) ls + else + aas ls' ((x', y') :: acc) + in + aas ls [] + end + fun recToList [a ::: Type] [r ::: {Unit}] (fl : folder r) = @foldUR [a] [fn _ => list a] (fn [nm ::_] [rest ::_] [[nm] ~ rest] x xs => x :: xs) [] fl diff --git a/lib/ur/list.urs b/lib/ur/list.urs index c5c279b7..c1d46022 100644 --- a/lib/ur/list.urs +++ b/lib/ur/list.urs @@ -109,6 +109,9 @@ val assoc : a ::: Type -> b ::: Type -> eq a -> a -> t (a * b) -> option b val assocAdd : a ::: Type -> b ::: Type -> eq a -> a -> b -> t (a * b) -> t (a * b) +val assocAddSorted : a ::: Type -> b ::: Type -> eq a -> ord a -> a -> b -> t (a * b) -> t (a * b) +(* Assume the list is already sorted in ascending order and maintain that ordering. *) + (** Converting records to lists *) val recToList : a ::: Type -> r ::: {Unit} -> folder r -> $(mapU a r) -> t a |