diff options
| author |  letouzey <letouzey@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2009-01-22 18:56:39 +0000 |
|---|---|---|
| committer | letouzey <letouzey@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2009-01-22 18:56:39 +0000 |
| commit | 847f28cb238c734cac9fb08aff00347d2eec7bb0 (patch) | |
| tree | 2dad1d8469bf6a2fef93c57e982c6c146e3493e4 /lib/util.ml | |
| parent | a4e01117965de462e14bb56d106859a7ef8f3e65 (diff) | |
Util.split_at : for quadratic to linear complexity
This function is probably used only on small lists, but it's not a
reason to let it be quadratic... I'm wondering how many other inefficient
functions like this one may exist in the source of Coq.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@11847 85f007b7-540e-0410-9357-904b9bb8a0f7
Diffstat (limited to 'lib/util.ml')
| -rw-r--r-- | lib/util.ml | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/lib/util.ml b/lib/util.ml index 93032140c..c685ee226 100644 --- a/lib/util.ml +++ b/lib/util.ml @@ -774,7 +774,7 @@ let list_split_at p = let rec split_at_loop x y = match y with | [] -> ([],[]) - | (a::l) -> if (p a) then (x,y) else (split_at_loop (x@[a]) l) + | (a::l) -> if (p a) then (List.rev x,y) else split_at_loop (a::x) l in split_at_loop [] |