Module Generic_fun_multiplate

module Generic_fun_multiplate: sig .. end

Library for boilerplate-less traversals, generalising Generic_fun_uniplate to mutually recursive types.

The library is inspired by the Haskell multiplate library by Russell O'Connor.

type 'f plate = {

plate : 'a. 'a Ty.T.ty -> 'a -> ('a, 'f) App.T.app;

}

A plate is a type-indexed function that may transform values of any type while carrying some effect in an applicative functor or a monad.

type id_plate = {

id_plate : 'a. 'a Ty.T.ty -> 'a -> 'a;

}

Specialisation of plate to the identity functor.

type 'b const_plate = {

const_plate : 'a. 'a Ty.T.ty -> 'a -> 'b;

}

Specialisation of plate to a constant functor.

val pure_plate : 'f Applicative.T.applicative -> 'f plate

A plate that lift all values into the applicative functor. For all f, t and x, (pure_plate f).plate t x == f.pure x

val pure_id_plate : id_plate

Specialisation of pure_plate to the identity functor. For all t and x, pure_id_plate.plate t x == x

val pure_const_plate : 't Monoid.T.monoid -> 't const_plate

Specialisation of pure_plate to the constant functor. For all m, t and x, pure_const_plate.plate t x == m.mempty

val compose : 'f Functor.T.functorial ->
       'g plate ->
       'f plate ->
       ('g, 'f) App.comp plate

val compose_monad : 'f Monad.T.monad ->
       'f plate ->
       'f plate -> 'f plate

val compose_right_id : 'f plate ->
       id_plate -> 'f plate

val compose_left_id : 'f Functor.T.functorial ->
       id_plate ->
       'f plate -> 'f plate

val append_plate : 'r Monoid.T.monoid ->
       'r const_plate ->
       'r const_plate ->
       'r const_plate

val traverse : 'f Applicative.T.applicative ->
       'f plate ->
       'a Product.T.product -> 'a -> ('a, 'f) App.T.app

Traversing a product type with effects

val map : id_plate ->
       'a Product.T.product -> 'a -> 'a

Mapping a function on each component of a product. map is the specialisation of traverse with the identity functor.

type 'a scrapped =

|

Scrapped : 'b Product.t * 'b * ('b -> 'a0) -> 'a0 scrapped

(*

'a scrapped is meant to deconstruct the root of a tree into a tuple of subtrees (the children) and a function that replace those children.

*)

val scrap : 'a Ty.T.ty -> 'a -> 'a scrapped

scrap is a generic function that deconstruct a value in a tuple children with a function to rebuild the value given the children.

val children : 'a Ty.T.ty -> 'a -> Ty.Dynamic.dyn list

val children_d : Ty.Dynamic.dyn -> Ty.Dynamic.dyn list

children is a generic function that computes a list of dynamic values which are the immediate children of the given value.

val family : 'a Ty.T.ty -> 'a -> Ty.Dynamic.dyn list

val family_d : Ty.Dynamic.dyn -> Ty.Dynamic.dyn list

family is a generic function that computes a list of dynamic values which are the descendent of a given value, that is: the value itself and the descendents of its immediate children

val traverse_children_p : 'f Applicative.T.applicative ->
       'f plate -> 'f plate

val traverse_children : 'f Applicative.T.applicative ->
       'f plate ->
       'a Ty.T.ty -> 'a -> ('a, 'f) App.T.app

Replace each child using the plate. (left to right traversal of children). Note that fmap_children corresponds to multiplate and mapChildrenM in the Haskell library.

val map_children_p : id_plate -> id_plate

val map_children : id_plate -> 'a Ty.T.ty -> 'a -> 'a

Specialisation of fmap_children with the identity functor. Replace each child using the pure plate.

val traverse_family_p : 'f Monad.T.monad ->
       'f plate -> 'f plate

val traverse_family : 'f Monad.T.monad ->
       'f plate ->
       'a Ty.T.ty -> 'a -> ('a, 'f) App.T.app

Bottom up (Depth-first, post-order) traversal of a value of a recursive type.

Given a plate whose fields transform each type, fmap_family_p returns a plate whose fields transform the family of the input. The traversal proceeds bottom up, first transforming the families of the children, before finally transforming the value itself.

val map_family_p : id_plate -> id_plate

val map_family : id_plate -> 'a Ty.T.ty -> 'a -> 'a

Specialisation of fmap_family with the identity monad.

val para_p : ('r list -> 'r) const_plate ->
       'r const_plate

val para_d : (Ty.Dynamic.dyn -> 'r list -> 'r) ->
       Ty.Dynamic.dyn -> 'r

val para : (Ty.Dynamic.dyn -> 'r list -> 'r) ->
       'a Ty.T.ty -> 'a -> 'r

val fold_children_p : 't Monoid.T.monoid ->
       't const_plate ->
       't const_plate

val fold_children_d : 't Monoid.T.monoid ->
       (Ty.Dynamic.dyn -> 't) -> Ty.Dynamic.dyn -> 't

val fold_children : 't Monoid.T.monoid ->
       (Ty.Dynamic.dyn -> 't) -> 'a Ty.T.ty -> 'a -> 't

Use the plate on each child to get an element of the monoid, and use the monoid to reduce them to a single value. (left to right traversal of children). Corresponds to mChildren in the Haskell library.

val pre_fold_p : 't Monoid.T.monoid ->
       't const_plate ->
       't const_plate

val pre_fold_d : 't Monoid.T.monoid ->
       (Ty.Dynamic.dyn -> 't) -> Ty.Dynamic.dyn -> 't

val pre_fold : 't Monoid.T.monoid ->
       (Ty.Dynamic.dyn -> 't) -> 'a Ty.T.ty -> 'a -> 't

Folds a family in pre-order.

Given a plate whose fields all return a Monoid o, preorderFold produces a plate that returns the mconcat of the family of the input.

The input itself produces the leftmost element of the concatenation, then this is followed by the family of the first child, then it is followed by the family of the second child, and so forth.

val post_fold_p : 't Monoid.T.monoid ->
       't const_plate ->
       't const_plate

val post_fold_d : 't Monoid.T.monoid ->
       (Ty.Dynamic.dyn -> 't) -> Ty.Dynamic.dyn -> 't

val post_fold : 't Monoid.T.monoid ->
       (Ty.Dynamic.dyn -> 't) -> 'a Ty.T.ty -> 'a -> 't

folds a family in post-order

Given a plate whose fields all return a Monoid o, preorderFold produces a plate that returns the mconcat of the family of the input.

The concatenation sequence begins with the family of the first child, then it is followed by the family of the second child, and so forth until finally the input itself produces the rightmost element of the concatenation.

Open recursion

We may generalise Ast_mapper and Ast_iterator to any types

type 'f openrec = {

run : 'f openrec -> 'f plate;

}

val default : 'a Applicative.T.applicative ->
       'a openrec

the default open-recursive transformation applies its openrec argument to all the children of a value.

default a = { run = fun r -> traverse_children_p a (r.run r) }