|y     GHC experimentalbos@serpentine.comNone5A type that can be used as a key in a crit-bit tree. BWe use 9 bits to represent 8-bit bytes so that we can distinguish D between an interior byte that is zero (which must have the 9th bit 7 set) and a byte past the end of the input (which must not have  the 9th bit set). @Without this trick, the critical bit calculations would fail on  zero bytes within+ a string, and our tree would be unable to  handle arbitrary binary data. -Return the number of bytes used by this key. @For reasonable performance, implementations must be inlined and  O(1). :Return the byte at the given offset (counted in bytes) of @ this key, bitwise-ORed with 256. If the offset is past the end  of the key, return zero. @For reasonable performance, implementations must be inlined and  O(1). A crit-bit tree. Logically, the ( constructor is a property of the tree, = rather than a node (a non-empty tree will never contain any  % constructors). In practice, turning  from a  newtype into an ADT with an  constructor adds a A pattern-match and a memory indirection to every function, which  slows them all down. 6The byte at which the left and right subtrees differ. 5The bitmask representing the critical bit within the > differing byte. If the critical bit is e.g. 0x8, the bitmask / will have every bit below 0x8 set, hence 0x7. O(n)". Convert the map to a list of key/value pairs. The list ? returned will be sorted in lexicographically ascending order. ; toList (fromList [("b",3), ("a",5)]) == [("a",5),("b",3)]  toList empty == []  !"#$%&'()*+ !"#$%&'  !"$#%&'()*+GHC experimentalbos@serpentine.comNoneO(log n)8. Insert a new key and value in the map. If the key is C already present in the map, the associated value is replaced with  the supplied value.  is equivalent to  insertWith  ,. K insert "b" 7 (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",7)] T insert "x" 7 (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3), ("x",7)] ? insert "x" 5 empty == singleton "x" 5 O(log n)8. Delete a key and its value from the map. When the key ; is not a member of the map, the original map is returned. = delete "a" (fromList [("a",5), ("b",3)]) == singleton "b" 3 I delete "c" (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3)] 3 delete "a" empty == empty -@Determine which direction we should move down the tree based on E the critical bitmask at the current node and the corresponding byte $ in the key. Left is 0, right is 1. .AFigure out the byte offset at which the key we are interested in E differs from the leaf we reached when we initially walked the tree. &We return some auxiliary stuff that we'll bang on to help us figure 4 out which direction to go in to insert a new node. /Failure continuation Success continuation -0. The key from outside the tree. Key from the leaf we reached. /-0./-0.GHC experimentalbos@serpentine.comNoneO(1). Is the map empty?  null (empty) == True ! null (singleton 1 'a') == False O(1). The empty map.  empty == fromList []  size empty == 0 O(log n)". Is the key a member of the map?  2 member "a" (fromList [("a",5), ("b",3)]) == True 3 member "c" (fromList [("a",5), ("b",3)]) == False  See also  . O(log n)&. Is the key not a member of the map?  6 notMember "a" (fromList [("a",5), ("b",3)]) == False 5 notMember "c" (fromList [("a",5), ("b",3)]) == True  See also  . O(log n)(. Lookup the value at a key in the map. 4The function will return the corresponding value as (1 value),  or 2 if the key isn't in the map. An example of using lookup:  $ {-# LANGUAGE OverloadedStrings #-}  import Data.Text  import Prelude hiding (lookup)  import Data.CritBit.Map.Lazy  A employeeDept, deptCountry, countryCurrency :: CritBit Text Text : employeeDept = fromList [("John","Sales"), ("Bob","IT")] ; deptCountry = fromList [("IT","USA"), ("Sales","France")] D countryCurrency = fromList [("USA", "Dollar"), ("France", "Euro")]  ( employeeCurrency :: Text -> Maybe Text  employeeCurrency name = do $ dept <- lookup name employeeDept & country <- lookup dept deptCountry " lookup country countryCurrency   main = do F putStrLn $ "John's currency: " ++ (show (employeeCurrency "John")) F putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete")) The output of this program:  John's currency: Just "Euro"  Pete's currency: Nothing O(log n)6. Returns the value associated with the given key, or 7 the given default value if the key is not in the map. : findWithDefault 1 "x" (fromList [("a",5), ("b",3)]) == 1 : findWithDefault 1 "a" (fromList [("a",5), ("b",3)]) == 5 O(log n)3. Find smallest key greater than the given one and - return the corresponding (key, value) pair. = lookupGT "aa" (fromList [("a",3), ("b",5)]) == Just ("b",5) 8 lookupGT "b" (fromList [("a",3), ("b",5)]) == Nothing  O(n*log n) . Build a map from a list of key/value pairs. If B the list contains more than one value for the same key, the last  value for the key is retained.  fromList [] == empty E fromList [("a",5), ("b",3), ("a",2)] == fromList [("a",2), ("b",3)] O(1). A map with a single element. / singleton "a" 1 == fromList [("a", 1)] O(n)%. The number of elements in the map. 2 size empty == 0 2 size (singleton "a" 1) == 1 2 size (fromList [("a",1), ("c",2), ("b",3)]) == 3 O(n)-. Fold the values in the map using the given & left-associative function, such that   f z ==  f z . elems.  Examples:  ' elems = reverse . foldl (flip (:)) [] 2 foldl (+) 0 (fromList [("a",5), ("bbb",3)]) == 8 O(n). A strict version of . Each application of the ; function is evaluated before using the result in the next = application. This function is strict in the starting value. O(n)6. Fold the keys and values in the map using the given & left-associative function, such that   f z ==  (\z' (kx, x) -> f z' kx x) z .  toAscList.  Examples:  4 keys = reverse . foldlWithKey (\ks k x -> k:ks) [] ? let f result k a = result ++ "(" ++ show k ++ ":" ++ a ++ ")" K foldlWithKey f "Map: " (fromList [("a",5), ("b",3)]) == "Map: (b:3)(a:5)" O(n). A strict version of . Each application of ? the function is evaluated before using the result in the next = application. This function is strict in the starting value. O(n)-. Fold the values in the map using the given ' right-associative function, such that   f z ==  f z . elems.  Example:  elems map = foldr (:) [] map O(n). A strict version of . Each application of the ; function is evaluated before using the result in the next = application. This function is strict in the starting value. O(n)6. Fold the keys and values in the map using the given ' right-associative function, such that   f z ==  (3 f) z .  toAscList.  Examples:  2 keys map = foldrWithKey (\k x ks -> k:ks) [] map A let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")" K foldrWithKey f "Map: " (fromList [("a",5), ("b",3)]) == "Map: (a:5)(b:3)" O(n). A strict version of . Each application of ? the function is evaluated before using the result in the next = application. This function is strict in the starting value. O(n)1. Return all keys of the map in ascending order. 1 keys (fromList [("b",5), ("a",3)]) == ["a","b"]  keys empty == []  )Default value to return if lookup fails. 456  456GHC experimentalbos@serpentine.comNone  7      !"#$% &'()*+,-./0123456718918:1;<=>?@critbit-0.0.0.0Data.CritBit.Map.LazyData.CritBit.Types.InternalData.CritBit.CoreData.CritBit.TreePreludefoldlfoldr CritBitKey byteCountgetByteCritBittoListinsertdeletenullemptymember notMemberlookupfindWithDefaultlookupGTfromList singletonsizefoldl' foldlWithKey foldlWithKey'foldr' foldrWithKey foldrWithKey'keysunionLunionRunionEmptyibyte iotherBitscbRootNodeLeafInternalileftirightBitMask$fCritBitKeyText$fCritBitKeyByteString $fShowCritBit $fNFDataNodebaseGHC.Baseconst directionfollowPrefixes lookupWith calcDirection Data.MaybeJustNothing Data.Tupleuncurry byteComparefoldlWithKeyWithfoldrWithKeyWith