úÎwępJ      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIportable experimentalUwe Schmidt (uwe@fh-wedel.de) Safe-Inferred not portable experimentalUwe Schmidt (uwe@fh-wedel.de) Safe-Inferred0Set of strings implemented as lazy prefix tree.  type StringSet = StringMap () is not feasable because of / the strict fields in the StringMap definition      not portable experimentalUwe Schmidt (uwe@fh-wedel.de) Safe-Inferred*J*strict list of chars with unpacked fields =for internal use in prefix tree to optimize space efficiency O(1) Is the map empty? O(1)% Create a map with a single element. O(1)/ Extract the value of a node (if there is one)  TODO: INTERNAL O(1)K Extract the value of a node or return a default value if no value exists. KO(1)" Extract the successors of a node  O(min(n,L))9 Find the value associated with a key. The function will return the result in  the monad or fail in it if the key isn't in the map.  O(min(n,L))9 Find the value associated with a key. The function will return the result in  the monad or fail in it if the key isn't in the map.  O(min(n,L))! Is the key a member of the map?  O(min(n,L))I Find the value at a key. Calls error when the element can not be found.  O(min(n,L))K Insert a new key and value into the map. If the key is already present in D the map, the associated value will be replaced with the new value.  O(min(n,L))M Insert with a combining function. If the key is already present in the map,  the value of f new_value old_value will be inserted.  O(min(n,L))M Insert with a combining function. If the key is already present in the map,  the value of f key new_value old_value will be inserted. ! O(min(n,L))M Updates a value at a given key (if that key is in the trie) or deletes the 3 element if the result of the updating function is L$. If the key is not found, the trie  is returned unchanged. " O(min(n,L))M Updates a value at a given key (if that key is in the trie) or deletes the 3 element if the result of the updating function is L$. If the key is not found, the trie  is returned unchanged. # O(min(n,L))L Delete an element from the map. If no element exists for the key, the map  remains unchanged. $ O(max(L,R)): Find all values where the string is a prefix of the key. % O(max(L,R))O Find all values where the string is a prefix of the key and include the keys  in the result. &O(n+m)R Left-biased union of two maps. It prefers the first map when duplicate keys are  encountered, i.e. (& == ' M). 'O(n+m)" Union with a combining function. (O(n+m)5 Union with a combining function, including the key. ) (O(min(n,m))/ Difference between two tries (based on keys). * (O(min(n,m))P Difference with a combining function. If the combining function always returns  L*, this is equal to proper set difference. + O(min(n,m))P Difference with a combining function, including the key. If two equal keys are Z encountered, the combining function is applied to the key and both values. If it returns  L*, the element is discarded, if it returns N! a value, the element is updated  with the new value. O!cut off all branches from a tree t2 that are not part of set t1 the following laws must holds lookup' k' . cutPx' (singlePS k) $ t == lookup' k t for every k' with k prefix of k' lookup' k' . cutPx' (singlePS k) $ t == Nothing for every k' with k not being a prefix of k' ,O(n)4 Map a function over all values in the prefix tree. .O(n)R Updates a value or deletes the element if the result of the updating function is L. / Monadic map 0Monadic mapWithKey 1,space required by a prefix tree (logically) :Singletons are counted as 0, all other n-ary constructors B are counted as n+1 (1 for the constructor and 1 for every field) H cons nodes of char lists are counted 2, 1 for the cons, 1 for the char U for values only the ref to the value is counted, not the space for the value itself % key chars are assumed to be unboxed Pstatistics about the #0 of different nodes in an optimized prefix tree 3O(n) Fold over all key/value pairs in the map. 4O(n)" Fold over all values in the map. 5O(n) Convert into an ordinary map. 6O(n), Convert an ordinary map into a Prefix tree 7O(n)2 Returns all elements as list of key value pairs, 8O(n)" Creates a trie from a list of key/ value pairs. 9O(n) The number of elements. :O(n) Returns all values. ;O(n) Returns all values. <Greturns all key-value pairs in breadth first order (short words first) L this enables prefix search with upper bounds on the size of the result set  e.g. ' search ... >>> toListBF >>> take 1000 # will give the 1000 shortest words 8 found in the result set and will ignore all long words gtoList is derived from the following code found in the net when searching haskell breadth first search )Haskell Standard Libraray Implementation  br :: Tree a -> [a]  br t = map rootLabel $  concat $ 1 takeWhile (not . null) $ * iterate (concatMap subForest) [t] = O(max(L,R))O Find all values where the string is a prefix of the key and include the keys ; in the result. The result list contains short words first pQRSTUVWXYZ[\]J^_`abcdefghijklmnopqrstuvwxyz{|K !"#}~$%€&'(‚)*+ƒO„…,-†.‡/0ˆ‰12P34Š56789:;<‹Œ=Ž‘’4impuvz| !"#$%&'()*+„…,-./0123456789:;<=QQ RSTUVWXYZ[\]J_^"pmihgedcba`nojklnjkfkfklfnfnljnljnqrstuvwxyz{|K !"#}~$%€&'(‚)*+ƒO„…,-†.‡/0ˆ‰12P34Š56789:;<‹Œ=Ž‘’ not portable experimentalUwe Schmidt (uwe@fh-wedel.de) Safe-Inferred> O(max(L,R)): Find all values where the string is a prefix of the key. B O(max(L,R)): Find all values where the string is a prefix of the key. = Breadth first variant, short words first in the result list >?@ABCD“”•–— >?@ABCD“”•–— >?@ABCD“”•–— not portable experimentalUwe Schmidt (uwe@fh-wedel.de) Safe-Inferred2 !"#$%&'()*+,-./0123456789:;<=>?@ABCD29$%= #!"&'()*+,-/0.43;:87<6512>?@ABCD not portable experimentalUwe Schmidt (uwe@fh-wedel.de) Safe-InferredEO(1)% Create a map with a single element. F O(min(n,L))K Insert a new key and value into the map. If the key is already present in D the map, the associated value will be replaced with the new value. G O(min(n,L))M Insert with a combining function. If the key is already present in the map,  the value of f new_value old_value will be inserted. H O(min(n,L))M Insert with a combining function. If the key is already present in the map,  the value of f key new_value old_value will be inserted. IO(n)" Creates a trie from a list of key/ value pairs. EFGH˜I2!"#$%&'()*+,-./012345679:;<=>?@ABCDEFGHI29$%=EFGH#!"&'()*+,-/0.43;:I7<6512>?@ABCDEFGH˜I not portable experimentalUwe Schmidt (uwe@fh-wedel.de) Safe-Inferred2 !"#$%&'()*+,-./0123456789:;<=>?@ABCD29$%= #!"&'()*+,-/0.43;:87<6512>?@ABCD™      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKL&'(@MNOPQORSOPTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œ…ždata-stringmap-0.9.1Data.StringMap.TypesData.StringMap.StringSetData.StringMap.LazyData.StringMap.StrictData.StringMap.BaseData.StringMap.FuzzySearchData.StringMapKeySym StringSetPSnextPSelemPSemptyemptyPSelemPSelem0PSnextPSlastPSnullPSsinglePSprefixPSunionPSfoldPS foldWithKeyPSelemsPS fuzzyCharPS fuzzyCharsPS StringMapemptynull singletonvaluevalueWithDefaultlookupfindWithDefaultmember!insert insertWith insertWithKeyupdate updateWithKeydelete prefixFindprefixFindWithKeyunion unionWith unionWithKey differencedifferenceWithdifferenceWithKeymap mapWithKeymapMaybemapM mapWithKeyMspacekeyChars foldWithKeyfoldtoMapfromMaptoListfromListsizeelemskeystoListBFprefixFindWithKeyBFprefixFindCaseWithKeyprefixFindNoCaseWithKeyprefixFindNoCase lookupNoCaseprefixFindCaseWithKeyBFprefixFindNoCaseWithKeyBFlookupNoCaseBFKey1succbase Data.MaybeNothingGHC.BaseconstJustcutPx''statPrefixTreeVisitorPTVv_emptyv_valv_branchv_leafv_lastv_lsseqv_brseqv_lsselv_brselv_lsvalv_brvalConsNilLsValBrValBrSeLLsSeLBrSeqLsSeqsymsLastLeafBranchsymchildnextValvalue'treeEmpty.++.toKeyfromKeylength1valbranchlsseqbrseqsiseqnormdeepNorm normError lookupPx'lookup'insert'update'union'union''diff''cutPx' cutAllPx'map' mapMaybe'mapM''visitfold' rootLabel subForest$fBinaryStringMap$fNFDataStringMap$fReadStringMap$fFoldableStringMap$fFunctorStringMap $fShowKey1 noCaseKeysnoLowerCaseKeysnoCasePS noLowerCasePS noUmlautPS