Module IString

module IString: sig .. end

Immutable strings with fast comparison.

Summary of strings vs istrings:

Pro/Con (depending on your POV):

IStrings are immutable.

Pros:

IStrings are fast to compare. Equality can be tested in O(1), and a non-lexical comparison (suitable for Maps etc.) is usually O(1), except in rare pathological cases when it degrades to O(n).
IStrings are fast to hash. The hash is actually used internally so is stored with the string, and can be returned in O(1).
IStrings automatically share memory if they are equivelent, and to some extent if they have a common prefix.
Random access to elements in the string is O(1) on average.
Adding a character to the right of an istring is usually O(1), adding a string to the right is O(n) in the length of the right string (performance actually gets slightly better as the length of the left string increases)
Removing a character from the right of a string is O(1) to get both the character and the new string.

Cons:

IStrings are slower to create.
A single IString uses more memory than a single string of the same length.
Adding a character to the left of a string is slow. O(n) in the length of the right hand string.

type istring = internalised istring_

An immutable string, internalised istring.

type temp_istring = temp istring_

An immutable string, which may not yet have been internalised.

If you want maximum ease of use, ignore temp_istrings, and just use istrings. If you find that your program which builds a lot of strings is too slow, temp_istrings MAY help improve performance. See notes towards the end of this file.

type 'a istring_

The base type of istring and temp_istring. When you see this type as the parameter of a function, it means that the function can take either an internalised istring or a temporary istring.

type internalised

Phantom type used to mark an internalised istring.

type temp

Phantom type used to mark a temporary istring.

type t = istring

Type alias, so IString can easily be used as parameter for standard Map and Hash functors.

val empty : istring

The empty istring.

val snoc : 'a istring_ -> char -> istring

Add a character to the end of a string. Usually O(1) amortised, worst case O(n).

val is_empty : 'a istring_ -> bool

True iff the istring is empty. O(1).

val unsnoc : 'a istring_ -> istring * char

unsnoc s returns a pair consisting of s without the last character, and the last character.

val init : 'a istring_ -> istring

init s returns s without the last character.

val last : 'a istring_ -> char

last s returns the last character in s.

val head : 'a istring_ -> char

returns the first character in the string.

val tail : 'a istring_ -> istring

Return the string without the first character. This is slow, as it requires copying the whole string, it is not recommended that you traverse strings with head and tail. A more efficient way is to use get or a fold.

val length : 'a istring_ -> int

Return the length of the istring.

val temp_istring : 'a istring_ -> temp_istring

Turn any istring into a temporary istring. Because

...of something to do
with the dreaded monomorphism retriction?...

, recursive functions returning temp_istring sometimes end up only accepting temp_istring, when really you want any kind of istring. This function is used to fix that. (The implementation of temp_istring is actually the identity function!).

val equal : istring -> istring -> bool

Compare strings for equality. You can also use (==), which is equivelent to compare. However, using equal is recommended, as this prevents accidental use of (==) on temp_istring, which will give unexpected result.

val compare : istring -> istring -> int

Fast non-lexical comparison function, for maps etc. Should rarely need to compare strings letter by letter, although it may do for some pathological string pairs.

val lexical_compare : istring -> istring -> int

Lexical comparison. O(n) in length of string. (But O(1) if strings are equal.)

val hash : 'a istring_ -> int

Return value suitable for hashing. O(1).

val get : 'a istring_ -> int -> char

Get a character in an istring.

val rev : 'a istring_ -> istring

Reverse a istring. Constant stack and O(n) in the length of the string.

val append : 'a istring_ -> 'a istring_ -> istring

append a b returns an istring containing the contents of a followed by the contents of b. Runs in constant stack, and O(n) time in the length of b. (ie, if you are building a string by repeated appends, keep the long string on the left and append things to the right.)

val append_string : 'a istring_ -> string -> istring

As append but right hand parameter is a string.

val concat : ?sep:'a istring_ -> 'a istring_ list -> istring

Concatenate the istrings in the given list into a single istring. Constant stack space and approximately O(n) time in the length of the returned string.

val to_string : 'a istring_ -> string

Create a string from an istring.

val of_string : string -> istring

Create an istring from a string. O(n)

val of_char : char -> istring

Create an istring from a char. O(1)

val of_int : int -> istring

Create an istring from a int.

val of_float : float -> istring

Create an istring from a float.

val sub : 'a istring_ -> int -> int -> istring

sub s start len returns a substring of s starting a start and len characters long. O(len).

folds over istrings. Both run in O(n) time and O(1) stack.

val fold_left : ('a -> char -> 'a) -> 'a -> 'b istring_ -> 'a

val fold_right : (char -> 'a -> 'a) -> 'b istring_ -> 'a -> 'a

val internalise : 'a istring_ -> istring

Internalise an istring. This can be used to turn a temp_istring into an istring. On an istring, this is the identity function.

Temporary IStrings

The functions below are equivelent to the functions above, but are generally a little faster, and return temp_istring instead of istring.

Usually istrings are "internalised", so that they can be compared quickly. In the case that you are building a string in a number of steps, this may result in repeatedly internalising strings which are never compared.

For example, if you were to re-implement rev using snoc, the string would be internalised once for each character in the string. All but one of those strings would be thrown away and never compared. Internalising all those strings costs CPU time, and puts extra load on the garbage collector.

By using the functions below, that return temp_istring instead of istring, you are hinting that you don't yet need the string internalised. Actually, the string may still get internalised sometimes, but typically it will be O(log n) times, instead of O(n) times.

Although you can use == for lexical equality on istrings, you cannot do so for temp_istrings.

When you are done building the string, internalise will turn it into a "real" istring. Alternatively, many of the above functions will accept a temp_istring and return a istring.

val unsnoc' : 'a istring_ -> temp_istring * char

val snoc' : 'a istring_ -> char -> temp_istring

val rev' : 'a istring_ -> temp_istring

val append' : 'a istring_ -> 'a istring_ -> temp_istring

val append_string' : 'a istring_ -> string -> temp_istring

val concat' : ?sep:'a istring_ -> 'a istring_ list -> temp_istring

val of_string' : string -> temp_istring

val of_char' : char -> temp_istring

val of_int' : int -> temp_istring

val of_float' : float -> temp_istring

val toplevel_istring_printer : Format.formatter -> istring -> unit

A printer for the ocaml toplevel. Eg #install_printer Dynaml.IString.toplevel_istring_printer ;;

val toplevel_temp_istring_printer : Format.formatter -> temp_istring -> unit

val all_istrings : unit -> istring list

val all_istrings' : unit -> string list

val stats : unit -> int * int * int * int * int * int