diff options
author | Adam Chlipala <adamc@csail.mit.edu> | 2016-02-26 10:15:13 -0500 |
---|---|---|
committer | Adam Chlipala <adamc@csail.mit.edu> | 2016-02-26 10:15:13 -0500 |
commit | 69e9c6064e7728458a9ba365726706612d10e3f8 (patch) | |
tree | 7290f54c790c43492e37b2bce759aee67bfc0ee7 /lib/ur/list.ur | |
parent | c4e27c0873014af57224bccee09286f1adbbfa05 (diff) | |
parent | 026e50ceaad69147ae05386ea342861d18021cd5 (diff) |
Merge pull request #18 from AlexanderAA/master
Find longest prefix of elements, which satisfy a predicate; Group a list
Diffstat (limited to 'lib/ur/list.ur')
-rw-r--r-- | lib/ur/list.ur | 25 |
1 files changed, 25 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 |