7e79b5fdc582 — Chris Cannam 5 years ago
Docs
6 files changed, 105 insertions(+), 64 deletions(-)

M README
A => persistent-array.sig
M persistent-array.sml
A => persistent-queue.sig
M persistent-queue.sml
M trie.mlb
M README +59 -20
@@ 1,16 1,19 @@ 
 
-Persistent tries in Standard ML
-===============================
+Trie and persistent trie-based containers in Standard ML
+========================================================
+
+This is a trie library in Standard ML.
 
-This is an immutable trie library in Standard ML.
+The library contains implementations the following container
+data structures:
 
-The library contains two types of container implementation: a Trie (in
-both "set" and "map" kinds), and a Persistent Hash Map implemented
-using tries internally.
+   1. Trie and Trie Map
+   2. Persistent Hash Map (implemented using bitmap tries)
+   3. Persistent Array and Queue (implemented using bitmap tries)
 
 
-1. TRIES
---------
+1. TRIE AND TRIE MAP
+--------------------
 
 A trie is an ordered container. It stores a set of entries of a common
 entry type, which is some sort of sequence (vector, list, string etc),

          
@@ 101,32 104,33 @@ And there are specialisations for string
  * StringTrieMap, StringTrie - aliases for StringMTrieMap, StringMTrie
 
 
-2. PERSISTENT HASH MAPS
------------------------
+2. PERSISTENT HASH MAP
+----------------------
 
-This library also contains an implementation of a persistent hash map
+This library contains an implementation of a persistent hash map
 structure. That is, a hash map in which every insertion or removal
 returns a separate hash map, without modifying the one passed in, but
 internally sharing any unmodified parts with it.
 
 Like a classic hash table, the persistent hash map is unordered (keys
-can be enumerated but not in sort order, and do not need to be
-comparable) and requires that a hash function be provided for the key
-type.
+can be enumerated but not in any guaranteed order, and do not need to
+be comparable) and requires that a hash function be provided for the
+key type.
 
 The implementation is a hash-array-mapped trie (HAMT) somewhat like
-that popularised by the Clojure language.
+that popularised by the Clojure language. Hashes are 32-bit words and
+collisions are handled using simple list chaining.
 
 The main signature is:
 
  * PERSISTENT_HASH_MAP (persistent-hash-map.sig) - signature of a
-   polymorphic-value hash map container with arbitrary key type
+   polymorphic-value hash map container with a fixed key type
 
 And this is implemented by
 
  * PersistentHashMapFn (persistent-hash-map-fn.sml) - a functor that
    takes a hash key type and hash function and implements a
-   PERSISTENT_HASH_MAP with that key type.
+   PERSISTENT_HASH_MAP with that key type
 
 There is a specialisation for string keys:
 

          
@@ 134,8 138,43 @@ There is a specialisation for string key
    string keys
 
 
-BUILD & TEST
-------------
+3. PERSISTENT ARRAY AND QUEUE
+-----------------------------
+
+This library contains implementations of persistent array and queue
+containers. These are immutable containers (like the standard vector)
+that also support update, append, and pop-from-end operations. The
+queue additionally supports prepend and pop-from-start, but in return
+its plain iteration (foldl) is not as fast as the array. For both
+containers, all of the update, append, prepend, and pop operations
+take time independent of the container size.
+
+The implementation uses an array-mapped-trie somewhat like that
+popularised by the Clojure language. Both containers are limited in
+size to 2^32 elements (by the implementation) or the maximum size of
+Int.int (by the API), whichever is smaller. For the queue the
+limitation is on current queue length, not on total number of
+push/pops.
+
+The main signatures are:
+
+ * PERSISTENT_ARRAY (persistent-array.sig) - signature of a
+   polymorphic-value persistent array container
+
+ * PERSISTENT_QUEUE (persistent-queue.sig) - signature of a
+   polymorphic-value persistent queue container
+
+And these are implemented by
+
+ * PersistentArray (persistent-array.sml) - a polymorphic-value
+   persistent array container
+
+ * PersistentQueue (persistent-queue.sml) - a polymorphic-value
+   persistent queue container
+
+
+TO BUILD & TEST
+---------------
 
 Basic unit tests are provided. With the MLton compiler, run
 

          
@@ 147,6 186,6 @@ To use in other projects, include trie.m
 AUTHOR
 ------
 
-Copyright 2015-2018 Chris Cannam.
+Copyright 2015-2019 Chris Cannam.
 MIT/X11 licence. See the file COPYING for details.
 

          
A => persistent-array.sig +33 -0
@@ 0,0 1,33 @@ 
+
+signature PERSISTENT_ARRAY = sig
+
+    type 'a array (* nb not an eqtype *)
+
+    val maxLen : int
+
+    val fromList : 'a list -> 'a array 
+    val tabulate : int * (int -> 'a) -> 'a array
+    val length : 'a array -> int
+
+    val sub : 'a array * int -> 'a
+    val update : 'a array * int * 'a -> 'a array
+
+    val appi : (int * 'a -> unit) -> 'a array -> unit
+    val app : ('a -> unit) -> 'a array -> unit
+
+    val mapi : (int * 'a -> 'b) -> 'a array -> 'b array
+    val map : ('a -> 'b) -> 'a array -> 'b array
+
+    val foldli : (int * 'a * 'b -> 'b) -> 'b -> 'a array -> 'b
+    val foldl : ('a * 'b -> 'b) -> 'b -> 'a array -> 'b
+
+    val empty : 'a array
+    val isEmpty : 'a array -> bool
+
+    val append : 'a array * 'a -> 'a array
+    val popEnd : 'a array -> 'a array * 'a
+
+    val toList : 'a array -> 'a list
+
+    (* !!! + collate etc *)
+end

          
M persistent-array.sml +0 -33
@@ 1,36 1,3 @@ 
-
-signature PERSISTENT_ARRAY = sig
-
-    type 'a array (* nb not an eqtype *)
-
-    val maxLen : int
-
-    val fromList : 'a list -> 'a array 
-    val tabulate : int * (int -> 'a) -> 'a array
-    val length : 'a array -> int
-
-    val sub : 'a array * int -> 'a
-    val update : 'a array * int * 'a -> 'a array
-
-    val appi : (int * 'a -> unit) -> 'a array -> unit
-    val app : ('a -> unit) -> 'a array -> unit
-
-    val mapi : (int * 'a -> 'b) -> 'a array -> 'b array
-    val map : ('a -> 'b) -> 'a array -> 'b array
-
-    val foldli : (int * 'a * 'b -> 'b) -> 'b -> 'a array -> 'b
-    val foldl : ('a * 'b -> 'b) -> 'b -> 'a array -> 'b
-
-    val empty : 'a array
-    val isEmpty : 'a array -> bool
-
-    val append : 'a array * 'a -> 'a array
-    val popEnd : 'a array -> 'a array * 'a
-
-    val toList : 'a array -> 'a list
-
-    (* !!! + collate etc *)
-end
 
 structure PersistentArray :> PERSISTENT_ARRAY = struct
 

          
A => persistent-queue.sig +11 -0
@@ 0,0 1,11 @@ 
+
+signature PERSISTENT_QUEUE = sig
+
+    include PERSISTENT_ARRAY
+
+    type 'a queue = 'a array
+
+    val prepend : 'a array * 'a -> 'a array
+    val popStart : 'a array -> 'a array * 'a
+                                            
+end

          
M persistent-queue.sml +0 -11
@@ 1,14 1,3 @@ 
-
-signature PERSISTENT_QUEUE = sig
-
-    include PERSISTENT_ARRAY
-
-    type 'a queue = 'a array
-
-    val prepend : 'a array * 'a -> 'a array
-    val popStart : 'a array -> 'a array * 'a
-                                            
-end
 
 structure PersistentQueue :> PERSISTENT_QUEUE = struct
 

          
M trie.mlb +2 -0
@@ 22,5 22,7 @@ vector-tries.sml
 string-trie-map.sml
 string-trie.sml
 string-hash-map.sml
+persistent-array.sig
 persistent-array.sml
+persistent-queue.sig
 persistent-queue.sml