<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="style.css" type="text/css">
<meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type">
<link rel="Start" href="index.html">
<link rel="Up" href="Reins.DoubleList.html">
<link title="Index of types" rel=Appendix href="index_types.html">
<link title="Index of exceptions" rel=Appendix href="index_exceptions.html">
<link title="Index of values" rel=Appendix href="index_values.html">
<link title="Index of modules" rel=Appendix href="index_modules.html">
<link title="Index of module types" rel=Appendix href="index_module_types.html">
<link title="Reins" rel="Chapter" href="Reins.html"><title>Reins.DoubleList.Make</title>
</head>
<body>
<div class="navbar"> <a href="Reins.DoubleList.html">Up</a>
</div>
<center><h1>Functor <a href="type_Reins.DoubleList.Make.html">Reins.DoubleList.Make</a></h1></center>
<br>
<pre><span class="keyword">module</span> Make: <div class="sig_block"><code class="code">functor (</code><code class="code">L</code><code class="code"> : </code><code class="type"><a href="Reins.Lists.ListSig.html">Reins.Lists.ListSig</a></code><code class="code">) -> </code><code class="code">sig</code> <a href="Reins.DoubleList.Make.html">..</a> <code class="code">end</code></div></pre><table border="0" cellpadding="3" width="100%">
<tr>
<td align="left" valign="top" width="1%%"><b>Parameters: </b></td>
<td>
<table class="paramstable">
<tr>
<td align="center" valign="top" width="15%">
<code>L</code></td>
<td align="center" valign="top">:</td>
<td><code class="type"><a href="Reins.Lists.ListSig.html">Reins.Lists.ListSig</a></code>
</table>
</td>
</tr>
</table>
<hr width="100%">
<pre><span id="TYPEt"><span class="keyword">type</span> <code class="type">'a</code> t</span> </pre>
<div class="info">
The type of doubly linked lists. This type can be thought
of as a cursor pointing into the middle of a <code class="code">L.t</code> list.
Elements to the right of <code class="code">t</code> can be reached with <code class="code">hd</code>, <code class="code">tl</code>,
<code class="code">pop</code>, and <code class="code">next</code>. Elements to the left of <code class="code">t</code> can be
reached with <code class="code">prev_hd</code>, <code class="code">prev_tl</code>, <code class="code">prev_pop</code>, and
<code class="code">prev</code>.<br>
</div>
<pre><span id="VALempty"><span class="keyword">val</span> empty</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
The empty list<br>
</div>
<pre><span id="VALis_empty"><span class="keyword">val</span> is_empty</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> bool</code></pre><div class="info">
Returns true if the list is empty. That is, there are no
elements to the left or right of <code class="code">t</code>. Runs in the same time
and stack space as <code class="code">L.is_empty</code>.<br>
</div>
<pre><span id="VALat_front"><span class="keyword">val</span> at_front</span> : <code class="type">'a cursor -> bool</code></pre><div class="info">
<code class="code">at_front t</code> Retruns true if there are no elements to the left
of <code class="code">t</code>. Runs in the same time and stack space as <code class="code">L.is_empty</code>.<br>
</div>
<pre><span id="VALat_back"><span class="keyword">val</span> at_back</span> : <code class="type">'a cursor -> bool</code></pre><div class="info">
<code class="code">at_front t</code> Retruns true if there are no elements to the
right of <code class="code">t</code>. Runs in the same time and stack space as
<code class="code">L.is_empty</code>.<br>
</div>
<pre><span id="VALlength"><span class="keyword">val</span> length</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">length t</code> Returns the length of the entire list. Runs in the
same time and stack space as <code class="code">L.length</code>.<br>
</div>
<pre><span id="VALnext_length"><span class="keyword">val</span> next_length</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">next_length t</code> Returns the number of elements to the right of
<code class="code">t</code>. Runs in the same time and stack space as <code class="code">L.length</code>.<br>
</div>
<pre><span id="VALprev_length"><span class="keyword">val</span> prev_length</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">prev_length t</code> Returns the number of elements in front of
<code class="code">t</code>. Runs in the same time and stack space as <code class="code">L.length</code>.<br>
</div>
<pre><span id="VALrev"><span class="keyword">val</span> rev</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">rev t</code> Reverse the list <code class="code">t</code>. All elements that were in front
of <code class="code">t</code> are now to the right of it and vice versa. Runs in
O(1) time and stack space.<br>
</div>
<pre><span id="VALhd"><span class="keyword">val</span> hd</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">hd t</code> Returns the element to the immediate right of <code class="code">t</code>.
Runs in the same time and stack space as <code class="code">L.hd</code>. If there are
no elements to the right of <code class="code">t</code>, it raises <code class="code">Failure "hd"</code>.<br>
</div>
<pre><span id="VALtl"><span class="keyword">val</span> tl</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">tl t</code> Return the list with the first element to the right of
<code class="code">t</code> removed. Runs in the same time and stack space as <code class="code">L.tl</code>.
If there are no elements to the right of <code class="code">t</code>, it raises
<code class="code">Failure "tl"</code>.<br>
</div>
<pre><span id="VALpop"><span class="keyword">val</span> pop</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a * 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">pop t</code> Equivalent to <code class="code">(hd t), (tl t)</code> but is slightly more
efficient. Runs in the same time and stack space as <code class="code">L.pop</code>.
If there are no elements to the right of <code class="code">t</code>, it raises
<code class="code">Failure "pop"</code>.<br>
</div>
<pre><span id="VALlast"><span class="keyword">val</span> last</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">last t</code> Returns the last element the right of <code class="code">t</code>. Runs in
the same time and stack space as <code class="code">L.last</code>. If there are no
elements to the right of <code class="code">t</code>, it raises <code class="code">Failure "last"</code>.<br>
</div>
<pre><span id="VALnext"><span class="keyword">val</span> next</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">next t</code> Advance <code class="code">t</code> to the next element in the list. The
element to the right of <code class="code">t</code> is now to the left of the result.
Runs in the same time and stack space as the maximum of <code class="code">L.hd</code>
and <code class="code">L.cons</code>. If there are no elements to the right of <code class="code">t</code>,
it raises <code class="code">Failure "next"</code>.<br>
</div>
<pre><span id="VALprev_hd"><span class="keyword">val</span> prev_hd</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">prev_hd t</code> Returns the element to the left of <code class="code">t</code>. Runs in
the same time and space as <code class="code">L.hd</code>. If there are no element to
the left of <code class="code">t</code>, it raises <code class="code">Failure "prev_hd"</code>.<br>
</div>
<pre><span id="VALprev_tl"><span class="keyword">val</span> prev_tl</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">prev_tl t</code> Return the list with the first element to the left
of <code class="code">t</code> removed. Runs in the same time and stack space as
<code class="code">L.tl</code>. If there are no elements to the left of <code class="code">t</code>, it
raises <code class="code">Failure "prev_tl"</code>.<br>
</div>
<pre><span id="VALprev_pop"><span class="keyword">val</span> prev_pop</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a * 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">prev_pop t</code> Equivalent to <code class="code">(prev_hd t), (prev_tl t)</code> but is
slightly more efficient. Runs in the same time and stack
space as <code class="code">L.pop</code>. If there are no elements to the left of <code class="code">t</code>,
it raises <code class="code">Failure "prev_pop"</code>.<br>
</div>
<pre><span id="VALprev"><span class="keyword">val</span> prev</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">prev t</code> Advance <code class="code">t</code> to the previous element in the list. The
element to the left of <code class="code">t</code> is now to the right of the result.
Runs in the same time and stack space as the maximum of <code class="code">L.hd</code>
and <code class="code">L.cons</code>. If there are no elements to the left of <code class="code">t</code>, it
raises <code class="code">Failure "prev"</code>.<br>
</div>
<pre><span id="VALcons"><span class="keyword">val</span> cons</span> : <code class="type">'a -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">cons x t</code> Adds <code class="code">x</code> as the first element to the right of <code class="code">t</code>.
Runs in the same time and stack space as <code class="code">L.cons</code>.<br>
</div>
<pre><span id="VALprev_cons"><span class="keyword">val</span> prev_cons</span> : <code class="type">'a -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">prev_cons x t</code> Adds <code class="code">x</code> as the first element to the left of <code class="code">t</code>.
Runs in the same time and stack space as <code class="code">L.cons</code>.<br>
</div>
<pre><span id="VALsnoc"><span class="keyword">val</span> snoc</span> : <code class="type">'a -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">snoc x t</code> Adds <code class="code">x</code> as the last element to the right of <code class="code">t</code>
(i.e., the last element in the entire list). The resulting
list otherwise has the same elements to the left of it and to
the right of it as <code class="code">t</code> (i.e., the position has not changed).
Runs in the same time and stack space as <code class="code">L.snoc</code>.<br>
</div>
<pre><span id="VALprev_snoc"><span class="keyword">val</span> prev_snoc</span> : <code class="type">'a -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">snoc x t</code> Adds <code class="code">x</code> as the last element to the left of t <code class="code">t</code>
(i.e., the first element in the entire list). The resulting
list otherwise has the same elements to the left of it and to
the right of it as <code class="code">t</code> (i.e., the position has not changed).
Runs in the same time and stack space as <code class="code">L.snoc</code>.<br>
</div>
<pre><span id="VALappend"><span class="keyword">val</span> append</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -><br> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">append t1 t2</code> Append the list <code class="code">t2</code> onto the back of <code class="code">t1</code>.
The resulting list has the same position as <code class="code">t1</code>. Runs in the
O(|t2| + LA) time where LA is the running time of <code class="code">L.append</code>.
It uses O(1 + LS) stack space where LS is the stack space
required by <code class="code">L.append</code>.<br>
</div>
<pre><span id="VALsplice"><span class="keyword">val</span> splice</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -><br> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">splice t1 t2</code> Splices the elements of <code class="code">t1</code> into <code class="code">t2</code>. The
resulting list has the shape:
<p>
prev_l2 @ prev_l1 @ next_l1 @ next_l2
<p>
Runs in the same time and stack space as <code class="code">L.append</code>.<br>
</div>
<pre><span id="VALflatten"><span class="keyword">val</span> flatten</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -><br> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">flatten l</code> Appends all of the elements of <code class="code">l</code> into a new list.
Currently ineffeciently implemented and has greater than O(n)
running time.<br>
</div>
<pre><span id="VALfrom_list"><span class="keyword">val</span> from_list</span> : <code class="type">'a list -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">from_list l</code> Convert the standard list <code class="code">l</code> into a <code class="code">DList.t</code>.
Runs in the same time and stack space as <code class="code">L.from_list</code>. The
resulting cursor points to the front of the list.<br>
</div>
<pre><span id="VALto_list"><span class="keyword">val</span> to_list</span> : <code class="type">'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a list</code></pre><div class="info">
<code class="code">to_list t</code> Convert the DList <code class="code">t</code> into a standard list. Runs
in O(|t|) time and O(1) stack space. The position of <code class="code">t</code> does
not affect the order of the resulting list.<br>
</div>
<pre><span id="VALiter"><span class="keyword">val</span> iter</span> : <code class="type">('a -> unit) -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code">iter f t</code> Iterates over each element in the list <code class="code">t</code> and
applies <code class="code">f</code> to that element. The elements to the right of <code class="code">t</code>
are visited first in order, following by the elements to the
left of <code class="code">t</code> in reverse order. Runs in the same time and stack
space as <code class="code">L.iter</code>.<br>
</div>
<pre><span id="VALfold"><span class="keyword">val</span> fold</span> : <code class="type">('a -> 'b -> 'a) -> 'a -> 'b <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">fold f acc t</code> Accumulates the result <code class="code">acc</code> by applying <code class="code">f acc
x</code> for each element <code class="code">x</code> in <code class="code">t</code>. The elements to the right of
<code class="code">t</code> are visited first in order, following by the elements to
the left of <code class="code">t</code> in reverse order. Runs in the same time and
stack space as <code class="code">L.fold</code>.<br>
</div>
<pre><span id="VALrev_map"><span class="keyword">val</span> rev_map</span> : <code class="type">('a -> 'b) -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'b <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">rev_map f t</code> Creates a new list by applying <code class="code">f</code> to each
element of <code class="code">t</code>. The resulting list is in reverse order of <code class="code">t</code>
and the cursor of the resulting list points to the same
location as <code class="code">t</code> whith the next and previous elements reversed.
e.g., if <code class="code">e == hd t</code>, then <code class="code">f(e) == prev_hd (rev_map f t)</code>
Runs in the same time and stack space as <code class="code">L.map</code>.<br>
</div>
<pre><span id="VALmap"><span class="keyword">val</span> map</span> : <code class="type">('a -> 'b) -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'b <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">map f t</code> Creates a new list by applying <code class="code">f</code> to each element
of <code class="code">t</code>. The resulting list is in the same order as <code class="code">t</code> and
the cursor points to the same location as <code class="code">t</code>. e.g., if <code class="code">e ==
hd t</code>, then <code class="code">f(e) == hd (map f t)</code>. Runs in the same time and
stack space as <code class="code">L.map</code>.<br>
</div>
<pre><span id="VALto_string"><span class="keyword">val</span> to_string</span> : <code class="type">('a -> string) -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> string</code></pre><div class="info">
<code class="code">to_string to_s t</code> Convert the list <code class="code">t</code> into a string using
<code class="code">to_s</code> to individually convert each element into a string.
Runs in O(|t|*st) where st is the running time of <code class="code">to_s</code> and
uses O(ss) stack space where ss is the amount of stack
required by <code class="code">to_s</code>.<br>
</div>
<pre><span id="VALcompare"><span class="keyword">val</span> compare</span> : <code class="type">('a -> 'a -> int) -><br> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">compare f t1 t2</code> Compares the lists <code class="code">t1</code> and <code class="code">t2</code> using <code class="code">f</code>
to compare individual elements. Returns 0 if <code class="code">t1</code> and <code class="code">t2</code>
are equal (under f). Returns <code class="code"><0</code> if <code class="code">t1</code> is less than <code class="code">t2</code>
and returns <code class="code">>0</code> otherwise. Runs in O(min(|t1|, |t2|)) time
and O(1) stack space.<br>
</div>
<pre><span id="VALgen"><span class="keyword">val</span> gen</span> : <code class="type">(?size:int -> Random.State.t -> 'a) -><br> ?size:int -> Random.State.t -> 'a <a href="Reins.DoubleList.Make.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">gen f ?size rs</code> Generates a random list whose length is bounded
by <code class="code">size</code>. Each element in the list is computed by calling <code class="code">f
?size rs</code>. Runs in time O(<code class="code">size</code> * ft) where ft is the running
time of <code class="code">f</code> and uses O(fs) stack space where fs is the stack space
of <code class="code">f</code>. The location of the cursor is not defined.<br>
</div>
<pre><span class="keyword">include</span> <a href="Reins.ListCursor.S.html">Reins.ListCursor.S</a></pre>
<br>
Note that the type <code class="code">cursor</code> is the same as <code class="code">t</code>. Therefore all
<code class="code">List_Cursor.S</code> operations can be applied directly to values of
type DList.t<br>
</body></html>
