Tacinterp: more refactoring.

Introducing List.fold_right and List.fold_left in Monad.

1 files changed, 18 insertions, 2 deletions

diff --git a/lib/monad.mli b/lib/monad.mli
index 5c4f74e51d..39d4056384 100644
--- a/lib/monad.mli
+++ b/lib/monad.mli
@@ -32,14 +32,30 @@ module type S = sig
   (** List combinators *)
   module List : sig
 
-    (** [map f l] maps [f] on the elements of [l] in left to right
+    (** [List.map f l] maps [f] on the elements of [l] in left to right
         order. *)
     val map : ('a -> 'b t) -> 'a list -> 'b list t
 
-    (** [map f l] maps [f] on the elements of [l] in right to left
+    (** [List.map f l] maps [f] on the elements of [l] in right to left
         order. *)
     val map_right : ('a -> 'b t) -> 'a list -> 'b list t
 
+    (** Like the regular [List.fold_right]. The monadic effects are
+        threaded right to left.
+
+        Note: many monads behave poorly with right-to-left order. For
+        instance a failure monad would still have to traverse the
+        whole list in order to fail and failure needs to be propagated
+        through the rest of the list in binds which are now
+        spurious. It is also the worst case for substitution monads
+        (aka free monads), exposing the quadratic behaviour.*)
+    val fold_right : ('a -> 'b -> 'b t) -> 'a list -> 'b -> 'b t
+
+    (** Like the regular [List.fold_left]. The monadic effects are
+        threaded left to right. It is tail-recursive if the [(>>=)]
+        operator calls its second argument in a tail position. *)
+    val fold_left : ('a -> 'b -> 'a t) -> 'a -> 'b list -> 'a t
+
   end
 
 end