package containers

  1. Overview
  2. Docs
package containers
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module CCKTreeSource

Lazy Tree Structure

This structure can be used to represent trees and directed graphs (as infinite trees) in a lazy fashion. Like CCKList, it is a structural type.

Sourcetype 'a sequence = ('a -> unit) -> unit
Sourcetype 'a gen = unit -> 'a option
Sourcetype 'a klist = unit -> [ `Nil | `Cons of 'a * 'a klist ]
Sourcetype 'a printer = Format.formatter -> 'a -> unit

Basics

Sourcetype +'a t = unit -> [ `Nil | `Node of 'a * 'a t list ]
Sourceval empty : 'a t
Sourceval is_empty : _ t -> bool
Sourceval singleton : 'a -> 'a t

Tree with only one label.

Sourceval node : 'a -> 'a t list -> 'a t

Build a node from a label and a list of children.

Sourceval node1 : 'a -> 'a t -> 'a t

Node with one child.

Sourceval node2 : 'a -> 'a t -> 'a t -> 'a t

Node with two children.

Sourceval fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

Fold on values in no specified order. May not terminate if the tree is infinite.

Sourceval iter : ('a -> unit) -> 'a t -> unit
Sourceval size : _ t -> int

Number of elements.

Sourceval height : _ t -> int

Length of the longest path to empty leaves.

Sourceval map : ('a -> 'b) -> 'a t -> 'b t
Sourceval (>|=) : 'a t -> ('a -> 'b) -> 'b t
Sourceval cut_depth : int -> 'a t -> 'a t

Cut the tree at the given depth, so it becomes finite.

Graph Traversals

Sourceclass type 'a pset = object ... end

Abstract Set structure

Sourceval set_of_cmp : cmp:('a -> 'a -> int) -> unit -> 'a pset

Build a set structure given a total ordering.

Sourceval dfs : pset:'a pset -> 'a t -> [ `Enter of 'a | `Exit of 'a ] klist

Depth-first traversal of the tree.

Sourceval bfs : pset:'a pset -> 'a t -> 'a klist

Breadth-first traversal of the tree.

Sourceval force : 'a t -> [ `Nil | `Node of 'a * 'b list ] as 'b

force t evaluates t completely and returns a regular tree structure.

  • since 0.13
Sourceval find : pset:'a pset -> ('a -> 'b option) -> 'a t -> 'b option

Look for an element that maps to Some _.

Pretty-printing

Example (tree of calls for naive Fibonacci function):

  let mk_fib n =
    let rec fib' l r i =
      if i=n then r else fib' r (l+r) (i+1)
    in fib' 1 1 1;;

  let rec fib n = match n with
    | 0 | 1 -> CCKTree.singleton (`Cst n)
    | _ -> CCKTree.node2 (`Plus (mk_fib n)) (fib (n-1)) (fib (n-2));;

  let pp_node fmt = function
    | `Cst n -> Format.fprintf fmt "%d" n
    | `Plus n -> Format.fprintf fmt "%d" n;;

  Format.printf "%a@." (CCKTree.pp pp_node) (fib 8);;
Sourceval pp : 'a printer -> 'a t printer

A pretty-printer using S-expressions and boxes to render the tree. Empty nodes are not rendered; sharing is ignored.

  • since 0.9

Pretty printing in the DOT (graphviz) format

Sourcemodule Dot : sig ... end
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct