From 720e1cb2c84dfd274fcbfd7bf4974a1c110501cb Mon Sep 17 00:00:00 2001
From: Adam Chlipala <adam@chlipala.net>
Date: Fri, 14 Dec 2018 15:26:21 -0500
Subject: List.assocAddSorted

---
 lib/ur/list.ur  | 16 ++++++++++++++++
 lib/ur/list.urs |  3 +++
 2 files changed, 19 insertions(+)

(limited to 'lib')

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
-- 
cgit v1.2.3