Module Qunity.Binary_tree

type binary_tree =
  1. | Leaf
  2. | Node of binary_tree * binary_tree

A simple binary tree data structure, used for representing direct sum encoding structures.

type 'a valued_binary_tree =
  1. | ValuedLeaf of 'a
  2. | ValuedNode of 'a valued_binary_tree * 'a valued_binary_tree

A binary tree storing data in the leaves.

type tree_transformation =
  1. | TreeIdentity
  2. | TreeLeftRotation
  3. | TreeRightRotation
  4. | TreeCommute
  5. | TreeLeftApply of tree_transformation
  6. | TreeRightApply of tree_transformation
  7. | TreeBothApply of tree_transformation * tree_transformation
  8. | TreeConditionalCommute of bool list
  9. | TreeSequence of tree_transformation * tree_transformation

A transformation applied to a binary tree, in a form which can easily be converted into quantum operators acting on sum types.

val string_of_tree : binary_tree -> string

String representation of a binary tree.

val string_of_valued_tree : ('a -> string) -> 'a valued_binary_tree -> string

String representation of a valued binary tree.

val tree_size : binary_tree -> int

The number of leaves in the tree.

val tree_height : binary_tree -> int

The longest distance from the root of the tree to a leaf.

val tree_valued_to_normal : 'a valued_binary_tree -> binary_tree

Removes the values from a valued binary tree.

val tree_normal_to_valued : binary_tree -> unit valued_binary_tree

Converts a binary tree to a valued one by inserting unit values.

val assign_values_to_tree : binary_tree -> 'a list -> 'a valued_binary_tree

Converts a binary tree to a valued one by inserting values specified in the input list.

val tree_values : 'a valued_binary_tree -> 'a list

Obtains the list of values from a valued tree.

val tree_multiply : binary_tree -> binary_tree list -> binary_tree

To each leaf of tree0, attach a copy of the corresponding element of l_tree1. It is required that the length of l_tree1 is the same as the size of tree0.

val tree_get_path : 'a valued_binary_tree -> 'a -> bool list option

Given a value, assumed to occur exactly once in the given tree, finds the path from the root to the value and returns it as a bool list, where an entry of false corresponds to going to the left child, and an entry of true corresponds to going to the right child.

val valued_tree_get_subtree_from_path : 'a valued_binary_tree -> bool list -> 'a valued_binary_tree

Given a tree and a path, returns the subtree obtained by walking along the path.

val valued_tree_replace_at_path : 'a valued_binary_tree -> bool list -> 'a valued_binary_tree -> 'a valued_binary_tree

Replaces the subtree located at a given path with a new replacement tree.

val tree_path_apply : bool list -> tree_transformation -> tree_transformation

Creates a tree transformation that the given transformation to the subtree located at the given path.

val tree_transformation_inverse : tree_transformation -> tree_transformation

Given a tree transformation, finds its inverse. Left and right rotations are inverses of each other, sequences get reversed, and the other transformations are involutive.

val transform_valued_tree : tree_transformation -> 'a valued_binary_tree -> 'a valued_binary_tree

Applies a tree transformation to a valued binary tree, returning a new tree.

val transform_tree : tree_transformation -> binary_tree -> binary_tree

Applies a tree transformation to a binary tree, returning a new tree.

val bring_leaf_to_top_left : binary_tree -> tree_transformation

Creates a transformation that transforms a tree in such a way that it will have a leaf as its left child.

val bring_leaf_to_top_right : binary_tree -> tree_transformation

Creates a transformation that transforms a tree in such a way that it will have a leaf as its right child.

val transfer_right_to_left_subtree_single : binary_tree -> tree_transformation

Creates a transformation that transforms a tree in such a way that it will move a single leaf from its right subtree to its left subtree.

val transfer_right_to_left_subtree : binary_tree -> int -> tree_transformation

Creates a transformation that transforms a tree in such a way that it will move a given amount of leaves from its right subtree to its left subtree.

val transfer_left_to_right_subtree_single : binary_tree -> tree_transformation

Creates a transformation that transforms a tree in such a way that it will move a single leaf from its left subtree to its right subtree.

val transfer_left_to_right_subtree : binary_tree -> int -> tree_transformation

Creates a transformation that transforms a tree in such a way that it will move a given amount of leaves from its left subtree to its right subtree.

Creates a tree transformation that transforms tree0 in such a way that its shape matches that of tree1.

val bring_lower_path_to_depth_of_higher : binary_tree -> bool list -> bool list -> tree_transformation * bool list * bool list

Given a tree and two paths, creates a transformation that brings the nodes at these two paths to the same depth, and returns the new locations of these nodes along with the transformation.

val almost_swap_two_equal_length_paths : bool list -> bool list -> tree_transformation

Given two paths of equal length, creates a transformation that moves the node at the source path to almost the same path as the target path, except the first place where the two paths differ is kept.

val move_path : binary_tree -> bool list -> bool list -> tree_transformation

Creates a transformation that swaps the subtrees of the given tree located at two different paths.

val move_value : 'a valued_binary_tree -> 'a valued_binary_tree -> 'a -> tree_transformation

Given a source valued tree and a target valued tree, assumed to be of the same shape, as well as a value x, creates a tree transformation that moves the leaf containing x in source to the position where x occurs in target.

val move_values : 'a valued_binary_tree -> 'a valued_binary_tree -> 'a list -> tree_transformation

Given a source valued tree and a target valued tree, assumed to be of the same shape, as well as a list values, creates a tree transformation that, for each x in values, moves the leaf containing x in source to the position where x occurs in target.

val reshape_valued_tree : 'a valued_binary_tree -> 'a valued_binary_tree -> tree_transformation

Creates a tree transformation that transforms tree0 in such a way that becomes equal to tree1, having the same shape and the same values in the same positions.