<!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="previous" href="Reins.SList.html"> <link rel="next" href="Reins.Maps.html"> <link rel="Up" href="Reins.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.SkewBinaryList</title> </head> <body> <div class="navbar"><a href="Reins.SList.html">Previous</a> <a href="Reins.html">Up</a> <a href="Reins.Maps.html">Next</a> </div> <center><h1>Module <a href="type_Reins.SkewBinaryList.html">Reins.SkewBinaryList</a></h1></center> <br> <pre><span class="keyword">module</span> SkewBinaryList: <code class="code">sig</code> <a href="Reins.SkewBinaryList.html">..</a> <code class="code">end</code></pre><hr width="100%"> <br> Random access lists based on skew binary numbers <p> This module implements random access lists with O(1) <code class="code">hd</code> and <code class="code">tl</code> operations and O(log n) <code class="code">lookup</code> and <code class="code">update</code> operations.<br> <pre><span class="keyword">type</span> <a name="TYPEt"></a><code class="type">'a</code> t </pre> <div class="info"> The type of random access lists<br> </div> <pre><span class="keyword">val</span> <a name="VALempty"></a>empty : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> The empty list<br> </div> <pre><span class="keyword">val</span> <a name="VALis_empty"></a>is_empty : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> bool</code></pre><div class="info"> Returns tree if the list is emtpy.<br> </div> <pre><span class="keyword">val</span> <a name="VALlength"></a>length : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> int</code></pre><div class="info"> <code class="code">length t</code> returns the lenth of the list <code class="code">t</code>. Runs in O(log n) time and O(1) stack space where n is the number of elements in the list.<br> </div> <pre><span class="keyword">val</span> <a name="VALrev"></a>rev : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> <code class="code">rev t</code> Reverse the list <code class="code">t</code>. Runs in O(n) run and O(1) stack space where n is the number of elements in the list.<br> </div> <pre><span class="keyword">val</span> <a name="VALcons"></a>cons : <code class="type">'a -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> <code class="code">cons x t</code> Adds the element <code class="code">x</code> to the front of the list <code class="code">t</code>. Runs in O(1) time and stack space.<br> </div> <pre><span class="keyword">val</span> <a name="VALsnoc"></a>snoc : <code class="type">'a -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> <code class="code">snoc x t</code> Adds the element <code class="code">x</code> to the back of the list <code class="code">t</code>. Runs in O(n) time and O(1) stack space where n is the length of the list.<br> </div> <pre><span class="keyword">val</span> <a name="VALlast"></a>last : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a</code></pre><div class="info"> <code class="code">last t</code> Returns the element at the back of the list. If the list is empty, it raises <code class="code">Failure "last"</code>. Runs in O(1) stack and O(log n) time.<br> </div> <pre><span class="keyword">val</span> <a name="VALhd"></a>hd : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a</code></pre><div class="info"> <code class="code">hd t</code> Returns the element at the front of the list <code class="code">t</code>. Runs in O(1) time and stack space. Raises <code class="code">Failure "hd"</code> if the list is empty.<br> </div> <pre><span class="keyword">val</span> <a name="VALtl"></a>tl : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> <code class="code">tl t</code> Returns the list <code class="code">t</code> with the first element removed. Runs in O(1) time and stack space. Raises <code class="code">Failure "tl"</code> if the list is empty.<br> </div> <pre><span class="keyword">val</span> <a name="VALpop"></a>pop : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a * 'a <a href="Reins.SkewBinaryList.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 more efficient. Runs in amortized O(1) time and stack space. If the list is empty, it raises <code class="code">Failure "pop"</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALappend"></a>append : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -><br> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> <code class="code">append t1 t2</code> Appends the list <code class="code">t2</code> onto the back of list <code class="code">t1</code>. Runs in O(n) time and O(1) stack space where n is the number of elements in <code class="code">t1</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALflatten"></a>flatten : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> <code class="code">flatten t</code> Appends all of the elements of <code class="code">t</code> into a new list. Runs in O(n) time and O(1) stack space where n is the sum of each of the lists in <code class="code">t</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALfrom_list"></a>from_list : <code class="type">'a list -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> <code class="code">from_list l</code> Convert the standard list l into a SkewBinaryList. Runs in O(n) time and O(1) stack space where n is the number of elements in <code class="code">l</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALto_list"></a>to_list : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a list</code></pre><div class="info"> <code class="code">to_list t</code> Convert the SkewBinaryList <code class="code">t</code> into a standard list. Runs in O(n) time and O(1) stack space where n is the number of elements in <code class="code">t</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALiter"></a>iter : <code class="type">('a -> unit) -> 'a <a href="Reins.SkewBinaryList.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> in order and applies <code class="code">f</code> to that element. Runs in O(n*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 required by <code class="code">f</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALfold"></a>fold : <code class="type">('a -> 'b -> 'a) -> 'a -> 'b <a href="Reins.SkewBinaryList.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>. Runs in O(n*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 required by <code class="code">f</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALrev_map"></a>rev_map : <code class="type">('a -> 'b) -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'b <a href="Reins.SkewBinaryList.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>. Runs in O(n*ft) time where n is the number of elements in <code class="code">t</code> and ft is the running time of <code class="code">f</code>. It uses O(fs) stack space where fs is the stack space required by <code class="code">f</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALmap"></a>map : <code class="type">('a -> 'b) -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'b <a href="Reins.SkewBinaryList.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>. Runs in O(n*ft) time where n is the number of elements in <code class="code">t</code> and ft is the running time of <code class="code">f</code>. It uses O((fs * log n) stack space where fs is the stack space required by <code class="code">f</code>. This function is slightly more efficient than <a href="Reins.SkewBinaryList.html#VALrev_map"><code class="code">Reins.SkewBinaryList.rev_map</code></a> (yielding a different ordering) and significantly more efficient (by a constant factor) than <code class="code">SkewBinaryList.rev (SkewBinaryList.rev_map t)</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALto_string"></a>to_string : <code class="type">('a -> string) -> 'a <a href="Reins.SkewBinaryList.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(n*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 class="keyword">val</span> <a name="VALcompare"></a>compare : <code class="type">('a -> 'a -> int) -><br> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.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.<br> </div> <pre><span class="keyword">val</span> <a name="VALgen"></a>gen : <code class="type">(?size:int -> Random.State.t -> 'a) -><br> ?size:int -> Random.State.t -> 'a <a href="Reins.SkewBinaryList.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>.<br> </div> <pre><span class="keyword">val</span> <a name="VALlookup"></a>lookup : <code class="type">int -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a</code></pre><div class="info"> <code class="code">lookup i t</code> Returns the element at position <code class="code">i</code> (O-indexed) in the list <code class="code">t</code>. Raises <code class="code">Not_found</code> if the list contains fewer than <code class="code">i-1</code> elements. Runs in O(min(i,log n)) time and O(1) stack space where n is the number of elements in <code class="code">t</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALupdate"></a>update : <code class="type">int -> 'a -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info"> <code class="code">update i v t</code> Returns a new list where the element in position <code class="code">i</code> (0-indexed) has been replaced by <code class="code">v</code>. Raises <code class="code">Not_found</code> if the list contains fewer than <code class="code">i-1</code> elements. Runs in O(min(i,log n)) time and O(1) stack space where n is the number of elements in <code class="code">t</code>.<br> </div> </body></html>