acgtk

Abstract Categorial Grammar development toolkit
Library acgtkLib.utilsLib
module Log : Logs.LOG

Logs is the log module for SharedForest

type address = (int * int) list

This type is the type of addresses of forests. It is a list of (position in the forest,position as a child).

This is the type of relative path from one forest to another one. The first argument is the number of steps to move up, then second argument is the address to reach from this point.

type relative_path = int * address

This is the type of relative path from one forest to another one. The first argument is the number of steps to move up, then second argument is the address to reach from this point.

val diff : address -> address -> relative_path

diff add add' returns the relative path to go from the forest (subtree) wich occurs at address add to the forest (subtree) wich occurs at address add'.

val path_to_string : relative_path -> string

path_to_string p returns a string describing the path p.

val address_to_string : address -> string

address_to_string add returns a string describing the address add.

type 'a stack = 'a list

The type of a stack.

A list context is a stack

type 'a list_context = 'a stack

A list context is a stack

type 'a focused_list = 'a list_context * 'a list

a focused list is a pair of a list context and of a list

type 'a forest = 'a tree focused_list

Recursive definition of a shared forest.

and 'a tree =
| Node of 'a * 'a child list
and 'a child =
| Forest of 'a forest
type 'a forest_zipper =
| Top of 'a tree focused_list * int
| Zip of 'a * 'a child focused_list * 'a tree focused_list * int * 'a forest_zipper * 'a forest_zipper option * address

Defintion of a "forest zipper"

type 'a focused_forest = 'a forest_zipper * 'a tree

Type definition for the focused forests

type 'a simple_tree =
| SimpleTree of 'a * 'a simple_tree list

Type definition for standard trees

type 'a zipper =
| ZTop
| Zipper of 'a * 'a simple_tree focused_list * 'a zipper

Type definition for standard tree zippers

type 'a focused_tree = 'a zipper * 'a simple_tree

Type definition for standard focused trees

type 'a resumption

An abstract type to give access to resumption when trees are built from a forest

val empty : 'a resumption

empty is the empty resumption

val fold_depth_first : (( 'a -> 'b ) * ( 'b -> 'b -> 'b )) -> 'a simple_tree -> 'b

fold_depth_first (f,g) t recursively computes (g a) b_1 .... b_n where a=f t_0 and b_i= f t_i and t is a tree of node t_0 and of children t_1...t_n

val init : 'a tree list -> 'a resumption

init forest builds the resumption with all the focused forest focusing on each of the tree of forest

val resumption : 'a resumption -> 'a simple_tree option * 'a resumption

resumption resume returns a pair (Some t,resume') where t is extracted from resume, the latter being updated with possible alternatives met in building t to produce resume'. It returns (None,[]) if no tree can be extracted

val is_empty : 'a resumption -> bool

is_empty resume returns true if resume does not propose any other value on which to resume, false otherwise