changeset 1634:f4cb4eebf7ae

Some new List functions, based on code by Ron de Bruijn
author Adam Chlipala <adam@chlipala.net>
date Sun, 11 Dec 2011 15:02:55 -0500
parents deeeb036c8ed
children 8938f7b31573
files lib/ur/list.ur lib/ur/list.urs
diffstat 2 files changed, 39 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/lib/ur/list.ur	Mon Dec 05 10:43:06 2011 -0500
+++ b/lib/ur/list.ur	Sun Dec 11 15:02:55 2011 -0500
@@ -267,6 +267,18 @@
         foldlMi' 0
     end
 
+fun filterM [m] (_ : monad m) [a] (p : a -> m bool) =
+    let
+        fun filterM' (acc : list a) (xs : list a) : m (list a) =
+            case xs of
+                [] => return (rev acc)
+              | x :: xs =>
+                c <- p x;
+                filterM' (if c then x :: acc else acc) xs
+    in
+        filterM' []
+    end
+
 fun all [m] f =
     let
         fun all' ls =
@@ -393,3 +405,22 @@
 fun recToList [a ::: Type] [r ::: {Unit}] (fl : folder r)
   = @foldUR [a] [fn _ => list a] (fn [nm ::_] [rest ::_] [[nm] ~ rest] x xs =>
 				      x :: xs) [] fl
+
+fun take [a] (n : int) (xs : list a) : list a = 
+    if n <= 0 then
+        []
+    else
+        case xs of
+            [] => []
+          | x :: xs => x :: take (n-1) xs
+
+fun drop [a] (n : int) (xs : list a) : list a =
+    if n <= 0 then
+        xs
+    else
+        case xs of
+            [] => []
+          | x :: xs => drop (n-1) xs
+
+fun splitAt [a] (n : int) (xs : list a) : list a * list a =
+    (take n xs, drop n xs)
--- a/lib/ur/list.urs	Mon Dec 05 10:43:06 2011 -0500
+++ b/lib/ur/list.urs	Sun Dec 11 15:02:55 2011 -0500
@@ -46,6 +46,9 @@
 val foldlMi : m ::: (Type -> Type) -> monad m -> a ::: Type -> b ::: Type
              -> (int -> a -> b -> m b) -> b -> t a -> m b
 
+val filterM : m ::: (Type -> Type) -> monad m -> a ::: Type
+              -> (a -> m bool) -> t a -> m (t a)
+
 val foldlMap : a ::: Type -> b ::: Type -> c ::: Type
                -> (a -> b -> c * b) -> b -> t a -> t c * b
 
@@ -90,3 +93,8 @@
 (** Converting records to lists *)
 
 val recToList : a ::: Type -> r ::: {Unit} -> folder r -> $(mapU a r) -> t a
+
+(* Divide a list into two sections at a particular 0-based position, returning the second, first, or both parts, respectively. *)
+val drop : t ::: Type -> int -> list t -> list t
+val take : t ::: Type -> int -> list t -> list t
+val splitAt : t ::: Type -> int -> list t -> list t * list t