From 7eec6f5c0d702323bd735e2184ff74f27ad37d17 Mon Sep 17 00:00:00 2001
From: Adam Chlipala <adam@chlipala.net>
Date: Sat, 25 Aug 2018 18:26:33 -0400
Subject: List.allM

---
 lib/ur/list.ur | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

(limited to 'lib/ur/list.ur')

diff --git a/lib/ur/list.ur b/lib/ur/list.ur
index 95d6fbc8..d28d2868 100644
--- a/lib/ur/list.ur
+++ b/lib/ur/list.ur
@@ -319,7 +319,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 +329,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 =
-- 
cgit v1.2.3


From 096fbda34b67cccd2026c44006bd9bc98d28c98c Mon Sep 17 00:00:00 2001
From: Adam Chlipala <adam@chlipala.net>
Date: Sun, 4 Nov 2018 09:39:07 -0500
Subject: List.mapMi

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

(limited to 'lib/ur/list.ur')

diff --git a/lib/ur/list.ur b/lib/ur/list.ur
index d28d2868..0da9316e 100644
--- a/lib/ur/list.ur
+++ b/lib/ur/list.ur
@@ -153,6 +153,16 @@ fun mapM [m ::: (Type -> Type)] (_ : monad m) [a] [b] f =
         mapM' []
     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 =
diff --git a/lib/ur/list.urs b/lib/ur/list.urs
index f4593dda..c5c279b7 100644
--- a/lib/ur/list.urs
+++ b/lib/ur/list.urs
@@ -31,6 +31,9 @@ val mapXi : a ::: Type -> ctx ::: {Unit} -> (int -> a -> xml ctx [] []) -> t a -
 val mapM : m ::: (Type -> Type) -> monad m -> a ::: Type -> b ::: Type
            -> (a -> m b) -> t a -> m (t b)
 
+val mapMi : m ::: (Type -> Type) -> monad m -> a ::: Type -> b ::: Type
+            -> (int -> a -> m b) -> t a -> m (t b)
+
 val mapPartialM : m ::: (Type -> Type) -> monad m -> a ::: Type -> b ::: Type -> (a -> m (option b)) -> t a -> m (t b)
                                                                         
 val mapXM : m ::: (Type -> Type) -> monad m -> a ::: Type -> ctx ::: {Unit}
-- 
cgit v1.2.3


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/ur/list.ur')

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


From b9ddbe0ce5c700fef313788fda5c7ecb82c84638 Mon Sep 17 00:00:00 2001
From: Adam Chlipala <adam@chlipala.net>
Date: Sun, 10 Feb 2019 18:01:46 -0500
Subject: List.searchM and ListPair.unzip

---
 lib/ur/list.ur      | 14 ++++++++++++++
 lib/ur/list.urs     |  2 ++
 lib/ur/listPair.ur  | 10 ++++++++++
 lib/ur/listPair.urs |  2 ++
 4 files changed, 28 insertions(+)

(limited to 'lib/ur/list.ur')

diff --git a/lib/ur/list.ur b/lib/ur/list.ur
index 10877420..b38097b7 100644
--- a/lib/ur/list.ur
+++ b/lib/ur/list.ur
@@ -293,6 +293,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 =
diff --git a/lib/ur/list.urs b/lib/ur/list.urs
index c1d46022..7e3cf205 100644
--- a/lib/ur/list.urs
+++ b/lib/ur/list.urs
@@ -67,6 +67,8 @@ val findM : m ::: (Type -> Type) -> monad m -> a ::: Type -> (a -> m bool) -> t
 
 val search : a ::: Type -> b ::: Type -> (a -> option b) -> t a -> option b
 
+val searchM : m ::: (Type -> Type) -> monad m -> a ::: Type -> b ::: Type -> (a -> m (option b)) -> t a -> m (option b)
+
 val all : a ::: Type -> (a -> bool) -> t a -> bool
 
 val allM : m ::: (Type -> Type) -> monad m -> a ::: Type -> (a -> m bool) -> t a -> m bool
diff --git a/lib/ur/listPair.ur b/lib/ur/listPair.ur
index c5e70708..52c73cd8 100644
--- a/lib/ur/listPair.ur
+++ b/lib/ur/listPair.ur
@@ -58,3 +58,13 @@ fun mapM [m] (_ : monad m) [a] [b] [c] (f : a -> b -> m c) =
     in
         mapM'
     end
+
+fun unzip [a] [b] (ls : list (a * b)) : list a * list b =
+    let
+        fun unzip' ls ls1 ls2 =
+            case ls of
+                [] => (List.rev ls1, List.rev ls2)
+              | (x1, x2) :: ls => unzip' ls (x1 :: ls1) (x2 :: ls2)
+    in
+        unzip' ls [] []
+    end
diff --git a/lib/ur/listPair.urs b/lib/ur/listPair.urs
index 9efff405..91d8807d 100644
--- a/lib/ur/listPair.urs
+++ b/lib/ur/listPair.urs
@@ -11,3 +11,5 @@ val mp : a ::: Type -> b ::: Type -> c ::: Type
 
 val mapM : m ::: (Type -> Type) -> monad m -> a ::: Type -> b ::: Type -> c ::: Type
          -> (a -> b -> m c) -> list a -> list b -> m (list c)
+
+val unzip : a ::: Type -> b ::: Type -> list (a * b) -> list a * list b
-- 
cgit v1.2.3


From 62dfceb86ba7dfbabb0fabaf89c9cbc8d08afc32 Mon Sep 17 00:00:00 2001
From: Adam Chlipala <adam@chlipala.net>
Date: Tue, 12 Feb 2019 11:05:48 -0500
Subject: List.mapConcat and mapConcatM

---
 lib/ur/list.ur  | 20 ++++++++++++++++++++
 lib/ur/list.urs |  4 ++++
 2 files changed, 24 insertions(+)

(limited to 'lib/ur/list.ur')

diff --git a/lib/ur/list.ur b/lib/ur/list.ur
index b38097b7..848bbd5f 100644
--- a/lib/ur/list.ur
+++ b/lib/ur/list.ur
@@ -101,6 +101,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 +163,16 @@ 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 =
diff --git a/lib/ur/list.urs b/lib/ur/list.urs
index 7e3cf205..6df2d5d9 100644
--- a/lib/ur/list.urs
+++ b/lib/ur/list.urs
@@ -20,6 +20,10 @@ val append : a ::: Type -> t a -> t a -> t a
 
 val mp : a ::: Type -> b ::: Type -> (a -> b) -> t a -> t b
 
+val mapConcat : a ::: Type -> b ::: Type -> (a -> t b) -> t a -> t b
+
+val mapConcatM : m ::: (Type -> Type) -> monad m -> a ::: Type -> b ::: Type -> (a -> m (t b)) -> t a -> m (t b)
+
 val mapPartial : a ::: Type -> b ::: Type -> (a -> option b) -> t a -> t b
 
 val mapi : a ::: Type -> b ::: Type -> (int -> a -> b) -> t a -> t b
-- 
cgit v1.2.3


From f2882c39c1acb5abc16f49524acb08d6c0b7b1d5 Mon Sep 17 00:00:00 2001
From: Adam Chlipala <adam@chlipala.net>
Date: Fri, 7 Feb 2020 13:53:50 -0500
Subject: List.foldli

---
 lib/ur/list.ur  | 10 ++++++++++
 lib/ur/list.urs |  2 ++
 2 files changed, 12 insertions(+)

(limited to 'lib/ur/list.ur')

diff --git a/lib/ur/list.ur b/lib/ur/list.ur
index 848bbd5f..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) =
diff --git a/lib/ur/list.urs b/lib/ur/list.urs
index 6df2d5d9..f81f38a4 100644
--- a/lib/ur/list.urs
+++ b/lib/ur/list.urs
@@ -7,6 +7,8 @@ val foldl : a ::: Type -> b ::: Type -> (a -> b -> b) -> b -> t a -> b
 val foldlAbort : a ::: Type -> b ::: Type -> (a -> b -> option b) -> b -> t a -> option b
 val foldlMapAbort : a ::: Type -> b ::: Type -> c ::: Type
                     -> (a -> b -> option (c * b)) -> b -> t a -> option (t c * b)
+val foldli : a ::: Type -> b ::: Type
+             -> (int -> a -> b -> b) -> b -> t a -> b
 
 val foldr : a ::: Type -> b ::: Type -> (a -> b -> b) -> b -> t a -> b
 
-- 
cgit v1.2.3