summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Adam Chlipala <adamc@csail.mit.edu>2016-02-26 10:15:13 -0500
committerGravatar Adam Chlipala <adamc@csail.mit.edu>2016-02-26 10:15:13 -0500
commit69e9c6064e7728458a9ba365726706612d10e3f8 (patch)
tree7290f54c790c43492e37b2bce759aee67bfc0ee7
parentc4e27c0873014af57224bccee09286f1adbbfa05 (diff)
parent026e50ceaad69147ae05386ea342861d18021cd5 (diff)
Merge pull request #18 from AlexanderAA/master
Find longest prefix of elements, which satisfy a predicate; Group a list
-rw-r--r--lib/ur/list.ur25
-rw-r--r--lib/ur/list.urs6
2 files changed, 31 insertions, 0 deletions
diff --git a/lib/ur/list.ur b/lib/ur/list.ur
index 11895884..eac5ab0c 100644
--- a/lib/ur/list.ur
+++ b/lib/ur/list.ur
@@ -434,6 +434,31 @@ fun drop [a] (n : int) (xs : list a) : list a =
fun splitAt [a] (n : int) (xs : list a) : list a * list a =
(take n xs, drop n xs)
+
+fun span [a] (f:(a -> bool)) (ls:list a) : list a * list a =
+ let
+ fun span' f acc ls =
+ case ls of
+ [] => (rev acc, [])
+ | x :: xs => if (f x) then span' f (x :: acc) xs else (rev acc, ls)
+ in
+ span' f [] ls
+ end
+
+fun groupBy [a] (f:(a -> a -> bool)) (ls:list a) : list (list a) =
+ let
+ fun groupBy' f ls =
+ case ls of
+ [] => [] :: []
+ | x :: xs =>
+ let
+ val (ys, zs) = span (f x) xs
+ in
+ (x :: ys) :: (groupBy' f zs)
+ end
+ in
+ groupBy' f ls
+ end
fun mapXiM [m ::: Type -> Type] (_ : monad m) [a] [ctx ::: {Unit}] (f : int -> a -> m (xml ctx [] [])) : t a -> m (xml ctx [] []) =
let
diff --git a/lib/ur/list.urs b/lib/ur/list.urs
index 55068935..ac874d7c 100644
--- a/lib/ur/list.urs
+++ b/lib/ur/list.urs
@@ -105,3 +105,9 @@ val recToList : a ::: Type -> r ::: {Unit} -> folder r -> $(mapU a r) -> t a
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
+
+(** Longest prefix of elements, which satisfy a predicate *)
+val span : a ::: Type -> (a -> bool) -> t a -> t a * t a
+
+(** Group a list *)
+val groupBy : a ::: Type -> (a -> a -> bool) -> t a -> t (t a)