Module Prelude.Rose

N-ary (Rose) trees.

type 'a t =
  1. | Node of 'a * 'a t list

The type of Rose trees.

val tree : 'a -> 'a t list -> 'a t

(tree v ts) is the tree carrying value v with children ts.

val unit : 'a -> 'a t

(unit v) is the unit tree carrying value v and no children.

val unfold : ('a -> 'b * 'a list) -> 'a -> 'b t

(unfold f seed) builds a t by recusively expanding (f seed).

The recursion is terminated when (snd << f) = [].

This example builds a tree isomorphic to the directory structure rooted at dir:

 let f d =
  Filename.(basename d, default [||] Sys.readdir d |> Array.to_list |> map (concat d)) in
unfold f dir
val random : (unit -> 'a) -> unit -> 'a t

(random r ()) is a random rose tree; each element is given by (r ()).

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

(fold f init) folds f across a t with init as the initial accumulator.

Example:

  • size = (fold (fun n _ -> succ n) 0)
val size : 'a t -> int

size returns the number of nodes in a t.

val map : ('a -> 'b) -> 'a t -> 'b t

(map f) maps f across all the values in a t.

val flatten : 'a t -> 'a list

flatten does a pre-order traversal of a t and returns the values in a list.

val draw : ('a -> string) -> 'a t -> string list

(draw f t) "returns a neat two dimentional drawing of t; shamelessly ripped of from Haskell 'containers' package."

Each element of the list is a line of output; the list is suitable to pass to (iter print_endline).

  • author Sergei Lebedev