Up  Next

Module Aux

module Aux: sig .. end
Auxiliary functions that operate on standard library data structures and standard library-like definitions.
val pi : float
exception Timeout of string
type ('a, 'b) choice =
| Left of 'a
| Right of 'b 
module Strings: Set.S  with type elt = string
val add_strings : string list -> Strings.t -> Strings.t
val strings_of_list : string list -> Strings.t
module Ints: Set.S  with type elt = int
val add_ints : int list -> Ints.t -> Ints.t
val ints_of_list : int list -> Ints.t
module StrMap: Map.S  with type key = string
val strmap_of_assoc : (string * 'a) list -> 'a StrMap.t
val strmap_filter : (string -> 'a -> bool) -> 'a StrMap.t -> (string * 'a) list
module IntMap: Map.S  with type key = int
val intmap_of_assoc : (int * 'a) list -> 'a IntMap.t
val intmap_filter : (int -> 'a -> bool) -> 'a IntMap.t -> (int * 'a) list
module BasicOperators: sig .. end
val int_pow : int -> int -> int
val is_digit : char -> bool
val fst3 : 'a * 'b * 'c -> 'a
val snd3 : 'a * 'b * 'c -> 'b
val trd3 : 'a * 'b * 'c -> 'c
val map_fst : ('a -> 'b) -> 'a * 'c -> 'b * 'c
val map_snd : ('a -> 'b) -> 'c * 'a -> 'c * 'b

Helper functions on lists and other functions lacking from the standard library.


val random_elem : 'a list -> 'a
Random element of a list.
val concat_map : ('a -> 'b list) -> 'a list -> 'b list
Concatenate results of a function. Tail-recursive.
val map_prepend : 'a list -> ('b -> 'a) -> 'b list -> 'a list
Map a second list and prepend the result to the first list, by single traversal. Not tail-recursive.

Map a second list and prepend the result to the first list, in reverse order. Tail-recursive.

val map_rev_prepend : 'a list -> ('b -> 'a) -> 'b list -> 'a list
val map_some : ('a -> 'b option) -> 'a list -> 'b list
Map a list filtering out some elements.

Find the first non-None element. Raise Not_found if none exists.

val find_some : ('a -> 'b option) -> 'a list -> 'b
val map_reduce : ('a -> 'b * 'c) -> ('d -> 'c -> 'd) -> 'd -> 'a list -> ('b * 'd) list
Map elements into key-value pairs, and fold values with the same key. Uses List.fold_left, therefore reverses the order. The resulting keys are sorted in the Pervasives.compare order.
val collect : ('a * 'b) list -> ('a * 'b list) list
Collects elements by key (returns a list sorted by key). Same as map_reduce (fun x -> x) (fun y x->x::y) [].
val repeating_key_sorted : ('a * 'b) list -> bool
Checks for a repeating key in a sorted association list.
val concat_foldr : ('a -> 'b -> 'b list) -> 'a list -> 'b list -> 'b list
Another very useful function from the list monad family: concat_foldr f (a::l) init = concat_map (f a) (concat_foldr f l init)
val concat_foldl : ('a -> 'b -> 'b list) -> 'a list -> 'b list -> 'b list
concat_foldl f (a::l) init = concat_foldl f l (concat_map (f a) init)
val list_rev_split : ?acc1:'a list -> ?acc2:'b list -> ('a * 'b) list -> 'a list * 'b list
Tail-recursive List.split with accumulators; reverses the lists.
val list_remove : 'a -> 'a list -> 'a list
Remove all elements equal to the argument, using structural equality.
val list_diff : 'a list -> 'a list -> 'a list
Set difference: List.filter (fun e -> not (List.mem e b)) a.
val sorted_diff : 'a list -> 'a list -> 'a list
Set difference of lists of unique increasing elements (as returned by Aux.unique_sorted).
val list_inter : 'a list -> 'a list -> 'a list
Intersection: list_inter a b = List.filter (fun e -> List.mem e b) a.
val list_init : (int -> 'a) -> int -> 'a list
Create a list of given length initialized from the indices.
val sorted_inter : 'a list -> 'a list -> 'a list
Set intersection of lists of unique increasing elements (as returned by Aux.unique_sorted).
val sorted_merge : 'a list -> 'a list -> 'a list
Set union of lists of unique increasing elements (as returned by Aux.unique_sorted).
val merge : ?sorted:bool ->
       cmp:('a -> 'a -> int) ->
       merge:('a -> 'a -> 'a) -> 'a list -> 'a list -> 'a list
Merging of two lists, sorts arguments and produces a cmp-sorted list.
val sorted_multiset_union : ('a * int) list -> ('a * int) list -> ('a * int) list
val rev_assoc : ('a * 'b) list -> 'b -> 'a
Return first key with the given value from the key-value pairs, using structural equality.
val mem_rev_assoc : ('a * 'b) list -> 'b -> bool
Check if the value is associated with a key in the key-value pairs, using structural equality.
val rev_assoc_all : ('a * 'b) list -> 'b -> 'a list
Inverse image of an association: return all keys with a given value (using structural equality). Returns elements in reverse order.
val assoc_all : 'a -> ('a * 'b) list -> 'b list
Return all values of a key.
val replace_assoc : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list
Replace the value of a first occurrence of a key, or place it at the end of the assoc list. Not tail-recursive.
val pop_assoc : 'a -> ('a * 'b) list -> 'b * ('a * 'b) list
Find the value associated with the first occurrence of the key and remove them from the list. Uses structural equality. Tail-recursive.
val pop_assq : 'a -> ('a * 'b) list -> 'b * ('a * 'b) list
As Aux.pop_assoc, but uses physical equality. Tail-recursive.
val update_assoc : 'a -> 'b -> ('b -> 'b) -> ('a * 'b) list -> ('a * 'b) list
Update the value associated with the first occurrence of the key, if no key is present update the given default "zero" value. Tail-recursive.
val cons : 'a -> 'a list -> 'a list
cons e l = e::l.
val some : 'a -> 'a option
Constructors and unConstructors.
val unsome : 'a option -> 'a
val list_of_opt : 'a option -> 'a list
val map_try : ('a -> 'b) -> 'a list -> 'b list
Map f on the list collecting results whose computation does not raise Not_found. Therefore map_try call cannot raise Not_found.
val find_try : ('a -> 'b) -> 'a list -> 'b
Find the first element of the list on which the function does not raise Not_found and return its result. Raises Not_found if the function results in Not_found on all elements.
val fold_left_try : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
Fold f over the list collecting results whose computation does not raise Not_found. Therefore fold_left_try call cannot raise Not_found.
val array_foldi_left : (int -> 'a -> 'b -> 'a) -> 'a -> 'b array -> 'a
As Array.fold_left, but with the element position passed.
val power : ?timeout:(unit -> bool) -> 'a list -> 'b list -> ('a * 'b) list list
power dom img generates all functions with domain dom and image img, as graphs. Tail recursive.
val product : ?upto:int -> ?timeout:(unit -> bool) -> 'a list list -> 'a list list
Cartesian product of lists. Tail recursive.
val product_size : 'a list list -> int
Size of the cartesian product of lists; max_int if the size is bigger.
val pairs : 'a list -> ('a * 'a) list
A list of all pairs of elements that preserve the order of elements from the list.
val all_ntuples : ?timeout:(unit -> bool) -> 'a list -> int -> 'a list list
An nth cartesian power of the list. Tail recursive.
val all_subsets : ?max_size:int -> 'a list -> 'a list list
All subsets of a given set of size up to max_size.
val remove_one : 'a -> 'a list -> 'a list
Remove an occurrence of a value (uses structural equality).
val remove_last : 'a list -> 'a list
Remove the last element in a list; raise Not_found for [].
val insert_nth : int -> 'a -> 'a list -> 'a list
Insert as nth element of a list (counting from zero). Raise Not_found if the list has less than n elements (e.g. inserting 0th element to empty list is OK).
val find_index : 'a -> 'a list -> int
Find the index of the first occurrence of a value in a list, counting from zero.
val pop_find : ('a -> bool) -> 'a list -> 'a * 'a list
Find an element satisfying the predicate and separate it from the list.
val maximal : ('a -> 'a -> bool) -> 'a list -> 'a list
Return the list of all maximal elements, under the given less-or-equal comparison. (Maximal elements can be equivalent or incomparable.)
val maximal_o : ('a -> 'a -> bool) -> 'a list -> 'a
Return single maximal element (in case of "less" or "less-or-equal" comparison) .
val maximal_unique : ('a -> 'a -> bool) -> 'a list -> 'a list
Return the list of all maximal elements, under the given less-or-equal comparison. Return only a single element for an equivalence class, i.e. only incomparable elements.
val add_to_maximal : ('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list
Assuming that l2 already has only maximal elements, add_to_maximal cmp l1 l2 computes maximal cmp (l1 @ l2).
type 'a topol_sort_ops = {
   rem_edge :'a -> 'a -> unit; (*rem_edge a b removes a->b.*)
   iter_outgoing :('a -> unit) -> 'a -> unit;
   no_incoming :'a -> bool;
   node_to_string :'a -> string;
}
Operations for imperatively manipulating the graph for Aux.topol_sort.
val topol_sort : 'a topol_sort_ops -> 'a list -> 'a list
Topogical sort of l where cmp a b = true means that there is an arrow from a to b. Elements without incoming edges are first and elements without outgoing edges are last. Returns None / raises Not_found if a cycle is detected.

Implementation: http://en.wikipedia.org/wiki/Topological_sort#Algorithms

val unique_sorted : ?cmp:('a -> 'a -> int) -> 'a list -> 'a list
Return the list of structurally unique elements, in order sorted by Pervasives.compare. Not tail-recursive.
val unique_append : 'a list -> 'a list -> 'a list
unique_append l1 l2 appends elements not occurring in l2 to it, without repeating elements.
val unique : ('a -> 'a -> bool) -> 'a list -> 'a list
Return the list of unique elements, under the given comparison (the input does not need to be sorted). (Currently uses a straightforward n^2 algorithm. Currently not tail-recursive.)
val not_unique : 'a list -> bool
Check whether the list contains duplicates, using structural equality.
val take_n : int -> 'a list -> 'a list
Take n elements of the given list, or less it the list does not contain enough values.
val take_n_with_rest : int -> 'a list -> 'a list * 'a list
Take n elements of the given list, or less it the list does not contain enough values. Return the rest-list as the second argument.
val range : ?from:int -> int -> int list
Returns an int list from from (default 0) to k-1.
val array_from_assoc : (int * 'a) list -> 'a array
Make an array from an association from indices to values. The indices must cover the 0..length-1 range; raises Invalid_argument "Aux.array_from_assoc" otherwise.
val array_map_some : ('a -> 'b option) -> 'a array -> 'b array
Map an array filtering out some elements.
val array_mapi_some : (int -> 'a -> 'b option) -> 'a array -> 'b array
val array_map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
Map a function over two arrays index-wise. Raises Invalid_argument if the arrays are of different lengths.
val array_for_all2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
For all on two arrays.
val array_fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b array -> 'c array -> 'a
Fold-left on two arrays.
val array_fold_map2 : ('a -> 'b -> 'c -> 'a * 'd) -> 'a -> 'b array -> 'c array -> 'a * 'd array
Fold-left and map on two arrays.
val array_combine : 'a array -> 'b array -> ('a * 'b) array
Zip two arrays into an array of pairs. Raises Invalid_argument "Aux.array_map2" if the arrays are of different lengths.
val array_exists : ('a -> bool) -> 'a array -> bool
val array_existsi : (int -> 'a -> bool) -> 'a array -> bool
val array_mem : 'a -> 'a array -> bool
val array_map_of_list : ('a -> 'b) -> 'a list -> 'b array
Same as Array.of_list (List.map f l)
val array_argfind : ('a -> bool) -> 'a array -> int
val array_argfindi : (int -> 'a -> bool) -> 'a array -> int
val array_find_all : ('a -> bool) -> 'a array -> 'a list
Find all elements for which f holds.

Find all indices for which f holds.

val array_argfind_all : ('a -> bool) -> 'a array -> int list
val array_for_all : ('a -> bool) -> 'a array -> bool
Find if a predicate holds for all elements.
val array_for_alli : (int -> 'a -> bool) -> 'a array -> bool
Find if a position-dependent predicate holds for all elements.
val array_for_all2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
Find if a predicate holds for all elements of two arrays pointwise. Raises Invalid_argument "Aux.array_for_all2" if arrays are of different lengths.
val array_iter2 : ('a -> 'b -> unit) -> 'a array -> 'b array -> unit
Iterate an action over all elements of two arrays pointwise. Raises Invalid_argument "Aux.array_iter2" if arrays are of different lengths.
val array_replace : 'a array -> int -> 'a -> 'a array
Return a copy of array with the ith element replaced by elem.
val list_find_all_max : ('a -> 'a -> int) -> 'a list -> 'a list
Find all maximal elements in a list.

Find all maximal elements in an array.

val array_find_all_max : ('a -> 'a -> int) -> 'a array -> 'a list
Find indices of all maximal elements in an array.
val array_argfind_all_max : ('a -> 'a -> int) -> 'a array -> int list
val neg : ('a -> bool) -> 'a -> bool
neg f x = not (f x)
val is_right : ('a, 'b) choice -> bool
val partition_choice : ('a, 'b) choice list -> 'a list * 'b list
Partition a list of tagged elements into the Left and Right-tagged elements.
val partition_map : ('a -> ('b, 'c) choice) -> 'a list -> 'b list * 'c list
Map elements and partition them according to Aux.choice tags (see also Aux.partition_choice).
val map_choice : ('a -> 'b) -> ('c -> 'd) -> ('a, 'c) choice -> ('b, 'd) choice
val map_option : ('a -> 'b) -> 'a option -> 'b option
Map optional value, with a default result for the None case.
val omap : 'b -> ('a -> 'b) -> 'a option -> 'b
val transpose_lists : 'a list list -> 'a list list
Transpose a rectangular matrix represented by lists. Raises Invalid_argument "List.map2" when matrix is not rectangular.
val fold_n : ('a -> 'a) -> 'a -> int -> 'a
Iterate a function n times: f^n(x).
val not_conflicting_name : ?truncate:bool -> Strings.t -> string -> string
Returns a string prolonging s and not appearing in names. If truncate is true, remove numbers from the end of s.
val not_conflicting_names : ?truncate:bool -> string -> Strings.t -> 'a list -> string list
Returns n strings proloning s and not appearing in names.
val list_fprint : (Pervasives.out_channel -> 'a -> unit) ->
       Pervasives.out_channel -> 'a list -> unit
Printf helper functions.
val array_fprint : (Pervasives.out_channel -> 'a -> unit) ->
       Pervasives.out_channel -> 'a array -> unit
val fprint_sep_list : ?newline:int ->
       string ->
       (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a list -> unit
Print an unboxed separated list, with breaks after the separator.

Replacements for basic Str functions.
val is_uppercase : char -> bool
Character classes.
val is_lowercase : char -> bool
val is_digit : char -> bool
val is_letter : char -> bool
val is_alphanum : char -> bool
val is_space : char -> bool
val clean_name : string -> string
Changes a string s to use only alphanumeric characters and underscore and to start with a lowercase letter. *
val strip_charprop : (char -> bool) -> string -> string
Strip characters satisfying f from left and right of a string.
val strip_spaces : string -> string
Strip spaces from left and right of a string.
val split_charprop : ?keep_split_chars:bool -> (char -> bool) -> string -> string list
Split a string on characters satisfying f.
type split_result =
| Text of string
| Delim of string
Type for some split results.
val split_chars_after : char -> char list -> string -> split_result list
Look for characters from the list l after c, split on such pairs. *
val split_spaces : string -> string list
Split a string on spaces.
val split_newlines : string -> string list
Split a string on newlines (\n or \r).
val split_empty_lines : string -> string list
Split a string on empty lines (\n\n).
val normalize_spaces : string -> string
Replace all white space sequences by a simple space, strip on both ends.
val replace_charprop : (char -> bool) -> string -> string -> string
Replace characters satisfying f by repl.
val str_index : ?from:int -> string -> string -> int
Index of the first occurence of the first argument in the second one. Only positions after from count. If it does not occur, raise Not_found.
val str_contains : string -> string -> bool
Checks whether the first argument contains the second one.
val str_subst_once : string -> string -> string -> string
Substitute the first ocurrence of the first argument by the second one.
val str_subst_all : string -> string -> string -> string
Substitute all ocurrences of the first argument by the second one.
val str_subst_once_from_to : string -> string -> string -> string -> string
Substitute the first ocurrence of the interval between the first argument and the second one by the third one.
val str_subst_all_from_to : string -> string -> string -> string -> string
Substitute all ocurrences of the interval between the first argument and the second one by the third one. E.g. (str_subst_all_from_to "/*" "*/" "") removes C-style comments.

More data structures.


module type PRIOQUEUE = sig .. end
Priority queues with minimal elements on top. 
module SimplePrioQueue: PRIOQUEUE 
module LeftistPrioQueue: PRIOQUEUE