Module Generic_fun_uniplate

module Generic_fun_uniplate: sig .. end

Library for boilerplate-less tree-traversals.

It is inspired by the Haskell uniplate by Neil Mitchell.

The function names, implementation and many comments are taken from Traversal implementation by Sebastian Fischer, and are the same as in the Generic_fun_multiplate generalisation.

val scrap : 'a Ty.T.ty -> 'a -> 'a list * ('a list -> 'a)

Scrap a returns the list of children of type a of a value of type a and a function to replace the children. That function should be given a list of the same size as the children list.

x == let (children, replace) = scrap a b x in replace children

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

The list of children of type a of a value of type a

val replace_children : 'a Ty.T.ty -> 'a -> 'a list -> 'a

Replacing the children of a value with new children. The list should contain exactly the number of required children.

(Alternative specification: additional children are ignored, and if not enough are given, only the first ones are changed)

val map_children : 'a Ty.T.ty -> ('a -> 'a) -> 'a -> 'a

Replace the children of a value using the given function.

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

A family is a list of descendents. A descendent of a value is either the value itself or a descendent of one of its children. family builds a pre-order family where the value is listed before its descendents

val post_family : 'a Ty.T.ty -> 'a -> 'a list

Generic_fun_uniplate.post_family lists the descendents in post-order: the leaves are first and the root is last

val map_family : 'a Ty.T.ty -> ('a -> 'a) -> 'a -> 'a

Bottom up (Depth-first, post-order) traversal of a value of a recursive type. The given function is applied to each member of the family.

val reduce_family : 'a Ty.T.ty -> ('a -> 'a option) -> 'a -> 'a

given a function that may optionally transform a value, reduce_family returns a function that exhaustively transforms the family of the input. The traversal proceeds bottom-up, first transforming the families of the children. If a transformation succeeds then the result is re-reduce_family-ed.

A post-condition is that the input function returns None on all family members of the output.

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

Paramorphism. this is a bottom-up

applicative and monadic variants

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

applicative variant of Generic_fun_uniplate.map_children

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

monadic variant of Generic_fun_uniplate.map_family

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

monadic variant of Generic_fun_uniplate.reduce_family