Safe-Inferred  A map from a keys to b% elements where keys instantiate the  ! type class. Key/element pairs are kept in " objects 0 which takes care of potential hash collisions. "Value in a HashMap. !+Class for types which provide hash values. #(Find element associated to a value key. $'Assumption: element is a member of the ". %Convert map into a & form if possible. 'Insert element into a value. (%Delete element from a value. Return ) if the resultant  value is empty. * Empty map. +Lookup element in the map. ,+Assumption: element is present in the map. -)Insert a new element. The function doesn't check 0 if the element was already present in the map. .+Assumption: element is present in the map.  /01"2&!34#$%'(*+,-.56 /01!3*+,-. /01"&2!34#$%'(*+,-.56None7Given a vector of length n, strictly ascending with respect to a given H comparison function, find an index at which the given element could be ' inserted while preserving sortedness.  The 8 result indicates, that the 9 element has been found,  while the :' result means otherwise. Value of the :  result is in the [0,n] range. ;AGiven a vector sorted with respect to some underlying comparison * function, find last element which is not < with respect to the  comparison function. = Combine two given hash values. = has zero as a left  identity. 7;=7;=7;= Safe-Inferred>@A set of nodes. To every node a unique identifier is assigned.  Invariants:  freeIDs \intersection occupiedIDs = \ emptySet,  freeIDs \sum occupiedIDs =  {0, 1, ..., |freeIDs \sum occupiedIDs| - 1}, #where occupiedIDs = elemSet idMap. TODO: Is it possible to merge ? with @ to reduce  the memory footprint? A3Map from nodes to IDs with hash values interpreted ; as keys and (node, ID) pairs interpreted as map elements. ?Set of free IDs. BMap from IDs to nodes. @7Number of ingoing paths (different paths from the root 3 to the given node) for each node ID in the graph. 8 The number of ingoing paths can be also interpreted as = a number of occurences of the node in a tree representation  of the graph. C Empty graph. D%Size of the graph (number of nodes). EList of graph nodes. F Node with the given identifier. G5Retrieve identifier of a node assuming that the node 4 is present in the graph. If the assumption is not 6 safisfied, the returned identifier may be incorrect. H=Add new graph node (assuming that it is not already a member  of the graph). I9Remove node from the graph (assuming that it is a member  of the graph). J'Increment the number of ingoing paths. K1Decrement the number of ingoing paths and return  the resulting number. L>Insert node into the graph. If the node was already a member : of the graph, just increase the number of ingoing paths. G NOTE: Number of ingoing paths will not be changed for any descendants E of the node, so the operation alone will not ensure that properties  of the graph are preserved. MBDelete node from the graph. If the node was present in the graph C at multiple positions, just decrease the number of ingoing paths. = Function crashes if the node is not a member of the graph. F NOTE: The function does not delete descendant nodes which may become D inaccesible nor does it change the number of ingoing paths for any  descendant of the node. >NA?B@OCDEFGHIJKLMP >NA?B@CDEFLM>NA?B@OCDEFGHIJKLMP Safe-InferredQ0Internal representation of an alphabet element. RNode identifier. QRQRQR Safe-InferredS:Abstraction over transition maps from alphabet symbols to  node identifiers. TEmpty transition map. ULookup sybol in the map. VFind index of the symbol. W@Select a (symbol, ID) pair by index of its position in the map. X&Insert element to the transition map. Y&Construct transition map from a list. Z&Translate transition map into a list. STUVWXYZSTUVWXYZSTUVWXYZNone[A vector of distinct key/,value pairs strictly ascending with respect  to key values. [\]^[][\]^ None_A vector of distinct key/,value pairs strictly ascending with respect  to key values. _`ab_a_`ab Nonec:Hash of a transition map is a sum of element-wise hashes.  Hash for a given element  (Sym, ID) is equal to combine Sym ID. cdefghcdefcdefgh Nonei>Two nodes (states) belong to the same equivalence class (and, B consequently, they must be represented as one node in the graph) > iff they are equal with respect to their values and outgoing  edges. Since j nodes are distinguished from k nodes, two values  equal with respect to l! function are always kept in one j  node in the graph. It doesn't change the fact that to all k = nodes one value is assigned through the epsilon transition. Invariant: the m! identifier always points to the j node.  Edges in the edgeMap, on the other hand, point to k nodes. mEpsilon transition. n!Transition map (outgoing edges). oTransition function. pList of symbol/#edge pairs outgoing from the node. qList of children identifiers. r-Substitue edge determined by a given symbol. ijskmnopqrtu ijskmnopqrikjmnsopqrtu None0A directed acyclic word graph with phantom type a representing  type of alphabet elements. vwxyvwxvwxy None z>Two nodes (states) belong to the same equivalence class (and, B consequently, they must be represented as one node in the graph) > iff they are equal with respect to their values and outgoing  edges. Since { nodes are distinguished from | nodes, two values  equal with respect to l! function are always kept in one {  node in the graph. It doesn't change the fact that to all | = nodes one value is assigned through the epsilon transition. Invariant: the }! identifier always points to the { node.  Edges in the edgeMap, on the other hand, point to | nodes. }Epsilon transition. ~!Transition map (outgoing edges). *Labels corresponding to individual edges. Transition function. Transition function. List of symbol/#edge pairs outgoing from the node. List of children identifiers. -Substitue edge determined by a given symbol. Make static node from a dynamic node. z{|}~Assign new IDs Dynamic node Static node z{|}~z|{}~None'Return node with the given identifier. Leaf node with no children and ) value. (Invariant: the identifier points to the Branch node.  Empty DAWG. #Number of states in the automaton. "Number of edges in the automaton. ,Insert the (key, value) pair into the DAWG. ;Insert with a function, combining new value and old value.  ; f key value d will insert the pair (key, value) into d if E key does not exist in the DAWG. If the key does exist, the function 4 will insert the pair (key, f new_value old_value). Delete the key from the DAWG. $Find value associated with the key. Return all key/0value pairs in the DAWG in ascending key order. 0Return all keys of the DAWG in ascending order. FReturn all elements of the DAWG in the ascending order of their keys. 5Construct DAWG from the list of (word, value) pairs. 4Construct DAWG from the list of (word, value) pairs 7 with a combining function. The combining function is  applied strictly. ;Make DAWG from the list of words. Annotate each word with  the () value.      None;Weight of a node corresponds to the number of final states A reachable from the node. Weight of an edge is a sum of weights 8 of preceding nodes outgoing from the same parent node.  DAWG a b c8 constitutes an automaton with alphabet symbols of type a,  transition labels of type b and node values of type Maybe c.  All nodes are stored in a ' with positions of nodes corresponding  to their Rs.  Empty DAWG. #Number of states in the automaton. "Number of edges in the automaton.  Node with the given identifier. $Value in leaf node with a given ID. $Find value associated with the key. Return all key/0value pairs in the DAWG in ascending key order. 0Return all keys of the DAWG in ascending order. FReturn all elements of the DAWG in the ascending order of their keys.  Construct ' from the list of (word, value) pairs.  First a ( is created and then it is frozen using  the  function. 4Construct DAWG from the list of (word, value) pairs 7 with a combining function. The combining function is  applied strictly. First a  is created and then  it is frozen using the  function. ;Make DAWG from the list of words. Annotate each word with  the () value. First a " is created and then it is frozen  using the  function. JCompute node weights and store corresponding values in transition labels. .Construct immutable version of the automaton. Inverse of the map. 9Position in a set of all dictionary entries with respect  to the lexicographic order. 1Perfect hashing function for dictionary entries.  A synonym for the  function. :Find dictionary entry given its index with respect to the  lexicographic order. Inverse of the  function and a synonym for the  function.   !"#$%&'()*+,-./01#234 5678,9:;<=,9>?;<@ABCDEF2GHIJKLMBNOPNQ!RQQST Q Q S T U U V W X Y Z [;\] ^ _ ` a b  c d e  f g h Y Z [ ^ _ i ` j a b  k c dHlmnopqrstuvwxHyz{|}~hdawg-0.9Data.DAWG.DynamicData.DAWG.StaticData.DAWG.HashMapData.DAWG.UtilData.DAWG.GraphData.DAWG.TypesData.DAWG.TransData.DAWG.Trans.VectorData.DAWG.Trans.MapData.DAWG.Trans.HashedData.DAWG.Dynamic.NodeData.DAWG.Dynamic.InternalData.DAWG.Static.NodeDAWGempty numStatesnumEdgesinsert insertWithdeletelookupassocskeyselemsfromList fromListWithfromLangWeightweighfreezeindexhashbyIndexunHashHashMapHashValuefind findUnsafe trySingleSingleembed ejectUnsafebase Data.MaybeNothing lookupUnsafe insertUnsafe deleteUnsafesizehashMapMultifromJust$fBinaryHashMap $fBinaryValue binarySearch Data.EitherLeftghc-prim GHC.TypesEQRight findLastLEGTcombineGraphfreeIDsingoMapidMapnodeMapnodesnodeBy nodeID'UnsafenewNoderemNodeincIngodecIngoID $fBinaryGraphSymTranstoListunTrans $fTransTransHashedtrans $fTransHashed$fBinaryHashedNodeLeafBranch GHC.Classes==epstransMaponSymedgeschildrenvalue $fBinaryNode $fHashNodegraphroot $fBinaryDAWG labelVectonSym'fromDyn insertLeafinsertMGraphMmkState insertNode deleteNode insertWithMdeleteMlookupM assocsAccvector-0.10.0.1 Data.VectorVector leafValueinverseunDAWGlookup'Iassocs'Iindex'I byIndex'I