Expr.Fixed
module Pattern : sig ... end
include Common.Fixed.S with module Pattern := Pattern
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 Common.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 Common.Pretty.S1 with type 'a t := 'a t
val pp :
(Stdlib.Format.formatter -> 'a -> unit) ->
Stdlib.Format.formatter ->
'a t ->
unit
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.
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.
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
.