From acc309665418f646857b8c246ef037d71fdea705 Mon Sep 17 00:00:00 2001
From: Enrico Tassi <enrico.tassi@inria.fr>
Date: Wed, 21 Oct 2009 09:09:47 +0000
Subject: [PATCH] new sharing-preserving map with accumulator

---
 helm/software/components/extlib/hExtlib.ml  | 13 +++++++++++++
 helm/software/components/extlib/hExtlib.mli |  2 ++
 2 files changed, 15 insertions(+)

diff --git a/helm/software/components/extlib/hExtlib.ml b/helm/software/components/extlib/hExtlib.ml
index cccb46767..237d4e77f 100644
--- a/helm/software/components/extlib/hExtlib.ml
+++ b/helm/software/components/extlib/hExtlib.ml
@@ -211,6 +211,19 @@ let sharing_map f l =
   if !unchanged then l else l1
 ;;
         
+let sharing_map_acc f acc l =
+  let unchanged = ref true in
+  let final_acc = ref acc in
+  let rec aux b acc = function
+    | [] as t -> unchanged := b; final_acc := acc; t
+    | he::tl ->
+        let acc, he1 = f acc he in
+        he1 :: aux (b && he1 == he) acc tl
+  in
+  let l1 = aux true acc l in
+  !final_acc, if !unchanged then l else l1
+;;
+
 let rec list_uniq ?(eq=(=)) = function 
   | [] -> []
   | h::[] -> [h]
diff --git a/helm/software/components/extlib/hExtlib.mli b/helm/software/components/extlib/hExtlib.mli
index f5e3741d4..34b4e3103 100644
--- a/helm/software/components/extlib/hExtlib.mli
+++ b/helm/software/components/extlib/hExtlib.mli
@@ -102,6 +102,8 @@ val list_mapi_acc:
 (* Finds the zero based index of the first element that satisfies a predicate*)
 val list_index: ('a -> bool) -> 'a list -> (int * 'a) option
 val sharing_map: ('a -> 'a) -> 'a list -> 'a list
+val sharing_map_acc: 
+     ('acc -> 'a -> 'acc * 'a) -> 'acc -> 'a list -> 'acc * 'a list
 (* Iters in parallel on two lists until the first list is empty.
    The second one can be shorter and is padded with a default value.
    This function cannot fail. *)
-- 
2.39.2