diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/monad.ml | 50 |
1 files changed, 23 insertions, 27 deletions
diff --git a/lib/monad.ml b/lib/monad.ml index d4641194ee..78cf929d2c 100644 --- a/lib/monad.ml +++ b/lib/monad.ml @@ -25,11 +25,33 @@ module type Def = sig end module type ListS = sig + type 'a t + + (** [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 + + (** [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 module type S = sig @@ -37,33 +59,7 @@ module type S = sig include Def (** List combinators *) - module List : sig - - (** [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 - - (** [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 + module List : ListS with type 'a t := 'a t end |