1 files changed, 86 insertions, 1 deletions

diff --git a/lib/ur/list.ur b/lib/ur/list.ur
index 95d6fbc8..1eb7626a 100644
--- a/lib/ur/list.ur
+++ b/lib/ur/list.ur
@@ -31,6 +31,16 @@ fun foldl [a] [b] (f : a -> b -> b) =
         foldl'
     end
 
+fun foldli [a] [b] (f : int -> a -> b -> b) =
+    let
+        fun foldli' i acc ls =
+            case ls of
+                [] => acc
+              | x :: ls => foldli' (i + 1) (f i x acc) ls
+    in
+        foldli' 0
+    end
+
 val rev = fn [a] =>
              let
                  fun rev' acc (ls : list a) =
@@ -101,6 +111,16 @@ fun mp [a] [b] f =
         mp' []
     end
 
+fun mapConcat [a] [b] f =
+    let
+        fun mapConcat' acc ls =
+            case ls of
+                [] => rev acc
+              | x :: ls => mapConcat' (revAppend (f x) acc) ls
+    in
+        mapConcat' []
+    end
+
 fun mapi [a] [b] f =
     let
         fun mp' n acc ls =
@@ -153,6 +173,26 @@ fun mapM [m ::: (Type -> Type)] (_ : monad m) [a] [b] f =
         mapM' []
     end
 
+fun mapConcatM [m] (_ : monad m) [a] [b] f =
+    let
+        fun mapConcatM' acc ls =
+            case ls of
+                [] => return (rev acc)
+              | x :: ls' => ls <- f x; mapConcatM' (revAppend ls acc) ls'
+    in
+        mapConcatM' []
+    end
+
+fun mapMi [m ::: (Type -> Type)] (_ : monad m) [a] [b] f =
+    let
+        fun mapM' i acc ls =
+            case ls of
+                [] => return (rev acc)
+              | x :: ls => x' <- f i x; mapM' (i + 1) (x' :: acc) ls
+    in
+        mapM' 0 []
+    end
+
 fun mapPartialM [m ::: (Type -> Type)] (_ : monad m) [a] [b] f =
     let
         fun mapPartialM' acc ls =
@@ -283,6 +323,20 @@ fun search [a] [b] f =
         search'
     end
 
+fun searchM [m] (_ : monad m) [a] [b] f =
+    let
+        fun search' ls =
+            case ls of
+                [] => return None
+              | x :: ls =>
+                o <- f x;
+                case o of
+                    None => search' ls
+                  | v => return v
+    in
+        search'
+    end
+
 fun foldlM [m] (_ : monad m) [a] [b] f =
     let
         fun foldlM' acc ls =
@@ -319,7 +373,7 @@ fun filterM [m] (_ : monad m) [a] (p : a -> m bool) =
         filterM' []
     end
 
-fun all [m] f =
+fun all [a] f =
     let
         fun all' ls =
             case ls of
@@ -329,6 +383,21 @@ fun all [m] f =
         all'
     end
 
+fun allM [m] (_ : monad m) [a] f =
+    let
+        fun all' ls =
+            case ls of
+                [] => return True
+              | x :: ls =>
+                b <- f x;
+                if b then
+                    all' ls
+                else
+                    return False
+    in
+        all'
+    end
+
 fun app [m] (_ : monad m) [a] f =
     let
         fun app' ls =
@@ -454,6 +523,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