Module S2.First

type 'a t = {
  1. pattern : 'a t Pattern.t;
  2. meta : 'a;
}
val map : ('a -> 'b) -> 'a t -> 'b t
val fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
include Ppx_compare_lib.Comparable.S1 with type 'a t := 'a t
val compare : 'a Base__Ppx_compare_lib.compare -> 'a t Base__Ppx_compare_lib.compare
include Ppx_hash_lib.Hashable.S1 with type 'a t := 'a t
val hash_fold_t : 'a Base__Ppx_hash_lib.hash_fold -> 'a t Base__Ppx_hash_lib.hash_fold
include Sexplib0.Sexpable.S1 with type 'a t := 'a t
val t_of_sexp : (Sexplib0__.Sexp.t -> 'a) -> Sexplib0__.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib0__.Sexp.t) -> 'a t -> Sexplib0__.Sexp.t
include Foldable.S with type 'a t := 'a t
val fold_left : f:('b -> 'a -> 'b) -> init:'b -> 'a t -> 'b

Left associative fold of a data structure; this is the same as the function derived from [@@deriving fold] but with labelled arguments

val fold_right : f:('a -> 'b -> 'b) -> init:'b -> 'a t -> 'b

Right associative fold of a data structure

val any : pred:('a -> bool) -> ?init:bool -> 'a t -> bool

Test whether any element of the data structure satisfies the supplied predicate. The optional argument init specifies the starting value and defaults to false.

val all : pred:('a -> bool) -> ?init:bool -> 'a t -> bool

Test whether all elements of the the data structure satify the supplied predicate. The optional argument init specifies the starting value and defaults to true.

include Pretty.S1 with type 'a t := 'a t
val pp : (Stdlib.Format.formatter -> 'a -> unit) -> Stdlib.Format.formatter -> 'a t -> unit
val fold_pattern : f:(('a * 'r Pattern.t) -> 'r) -> 'a t -> 'r

fold_pattern traverses the data structure from the bottom up replacing the original meta data of type 'a with some result type 'r and combines the result values on the way back up. For example, given a pattern with the following type:

type 'a pattern = Leaf of string | Branch of 'a * 'a

we can use fold_pattern to calculate the maximum depth of data structure obtained by fixing the pattern type:

let max_depth t =
  let f = function
      | meta , Leaf _ -> 1
      | meta , Branch(left_depth,right_depth) ->
          1 + (max left_depth right_depth)
  in
  fold_pattern ~f t

Note that the function 'f' supplied to fold_pattern accepts a tuple rather than our type 'a t since the type of the pattern has been transformed to 'r t Pattern.t and is no longer 'compatible' with the original type of meta data 'a. That is, a tuple ('a * 'b t Pattern.t) has two type variables where as 'a t has one.

val rewrite_bottom_up : f:('a t -> 'a t) -> 'a t -> 'a t

rewrite_bottom_up specializes fold_pattern so that the result type 'r is equal to the type of our fixed-point data structure i.e. 'r = 'a t. This also means that the function f can be written with our fixed-point type 'a t as its argument.

val unfold_pattern : f:('r -> 'a * 'r Pattern.t) -> 'r -> 'a t

unfold builds a fixed-point data structure from the top down. Starting with a user-supplied seed of type 'r, unfold recursively applies the function f yielding a tuple of meta-data and pattern with elements of type 'r to which f is further applied.

The unfold terminates when a pattern element which does not carry an 'r is reached.

As with fold_pattern the function f returns a tuple of meta-data and pattern rather than our record type since, in general, 'r =/= 'a t.

val rewrite_top_down : f:('a t -> 'a t) -> 'a t -> 'a t

rewrite_top_down specializes unfold by requiring that r = 'a t. As a consequence the function f accepts our record type 'a t as its argument.