{"action":"created","comment":{"url":"https://api.github.com/repos/haskell/containers/pulls/comments/365549042","pull_request_review_id":341228641,"id":365549042,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDM2NTU0OTA0Mg==","diff_hunk":"@@ -537,2248 +856,860 @@ fromListConstr = mkConstr intMapDataType \"fromList\" [] Prefix\n \n intMapDataType :: DataType\n intMapDataType = mkDataType \"Data.IntMap.Internal.IntMap\" [fromListConstr]\n-\n #endif\n \n-{--------------------------------------------------------------------\n-  Query\n---------------------------------------------------------------------}\n+instance NFData a => NFData (IntMap a) where\n+    rnf (IntMap m) = rnf m\n+\n+instance NFData a => NFData (IntMap_ t a) where\n+    rnf Empty = ()\n+    rnf (NonEmpty _ v root) = rnf v `seq` rnf root\n+\n+instance NFData a => NFData (Node t a) where\n+    rnf Tip = ()\n+    rnf (Bin _ v l r) = rnf v `seq` rnf l `seq` rnf r\n+\n+-- | /O(min(n,W))/. Find the value at a key.\n+-- Calls 'error' when the element can not be found.\n+--\n+-- > fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map\n+-- > fromList [(5,'a'), (3,'b')] ! 5 == 'a'\n+(!) :: IntMap a -> Key -> a\n+(!) m k = findWithDefault (error $ \"IntMap.!: key \" ++ show k ++ \" is not an element of the map\") k m\n+\n+\n+-- | /O(min(n,W))/. Find the value at a key.\n+-- Returns 'Nothing' when the element can not be found.\n+--\n+-- > fromList [(5,'a'), (3,'b')] !? 1 == Nothing\n+-- > fromList [(5,'a'), (3,'b')] !? 5 == Just 'a'\n+--\n+-- @since 0.5.11\n+(!?) :: IntMap a -> Key -> Maybe a\n+(!?) m k = lookup k m\n+\n+-- | Same as 'difference'.\n+(\\\\) :: IntMap a -> IntMap b -> IntMap a\n+(\\\\) = difference\n+\n -- | /O(1)/. Is the map empty?\n --\n--- > Data.IntMap.null (empty)           == True\n+-- > Data.IntMap.null empty             == True\n -- > Data.IntMap.null (singleton 1 'a') == False\n-\n null :: IntMap a -> Bool\n-null Nil = True\n-null _   = False\n-{-# INLINE null #-}\n+null (IntMap Empty) = True\n+null _ = False\n \n -- | /O(n)/. Number of elements in the map.\n --\n -- > size empty                                   == 0\n -- > size (singleton 1 'a')                       == 1\n -- > size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3\n size :: IntMap a -> Int\n-size = go 0\n+size (IntMap Empty) = 0\n+size (IntMap (NonEmpty _ _ node)) = sizeNode 0 node\n   where\n-    go !acc (Bin _ _ l r) = go (go acc l) r\n-    go acc (Tip _ _) = 1 + acc\n-    go acc Nil = acc\n+    -- A binary tree will always have exactly one more leaf than it has internal nodes. Counting\n+    -- the leaves is also more efficient since we don't have to add a bunch of zeros. From a\n+    -- different perspective, where the tree is seen as a shuffled PATRICIA tree, the data was\n+    -- \"originally\" stored in the leaves, so counting those locations gives the size of the map.\n+    sizeNode :: Int -> Node t a -> Int\n+    sizeNode !acc Tip = acc + 1\n+    sizeNode !acc (Bin _ _ l r) = sizeNode (sizeNode acc l) r\n+\n+-- | /O(min(n,W)/. Lookup the value at a key in the map, returning the result\n+-- to the provided continuations. See also 'lookup'.\n+--\n+-- When 'lookupChurch' is given three arguments (the continuations and key), it\n+-- is inlined to the call site. You should therefore use 'lookupChurch' only to\n+-- define custom lookup functions.\n+{-# INLINE lookupChurch #-}\n+lookupChurch :: r -> (a -> r) -> Key -> IntMap a -> r\n+lookupChurch nothing just !k = start\n+  where\n+    start (IntMap Empty) = nothing\n+    start (IntMap (NonEmpty min minV node)) = case compareMinBound k min of\n+        OutOfBound -> nothing\n+        Matched -> just minV\n+        InBound -> goL (xor k min) node\n+\n+    goL !_ Tip = nothing\n+    goL !xorCache (Bin max maxV l r) = case compareMaxBound k max of\n+        InBound | xorCache < xorCacheMax -> goL xorCache    l\n+                | otherwise              -> goR xorCacheMax r\n+        OutOfBound -> nothing\n+        Matched -> just maxV\n+      where xorCacheMax = xor k max\n+\n+    goR !_ Tip = nothing\n+    goR !xorCache (Bin min minV l r) = case compareMinBound k min of\n+        InBound | xorCache < xorCacheMin -> goR xorCache    r\n+                | otherwise              -> goL xorCacheMin l\n+        OutOfBound -> nothing\n+        Matched -> just minV\n+      where xorCacheMin = xor k min\n \n -- | /O(min(n,W))/. Is the key a member of the map?\n --\n -- > member 5 (fromList [(5,'a'), (3,'b')]) == True\n -- > member 1 (fromList [(5,'a'), (3,'b')]) == False\n-\n--- See Note: Local 'go' functions and capturing]\n+{-# NOINLINE[1] member #-}\n member :: Key -> IntMap a -> Bool\n-member !k = go\n-  where\n-    go (Bin p m l r) | nomatch k p m = False\n-                     | zero k m  = go l\n-                     | otherwise = go r\n-    go (Tip kx _) = k == kx\n-    go Nil = False\n+member !k = lookupChurch False (const True) k\n \n -- | /O(min(n,W))/. Is the key not a member of the map?\n --\n -- > notMember 5 (fromList [(5,'a'), (3,'b')]) == False\n -- > notMember 1 (fromList [(5,'a'), (3,'b')]) == True\n-\n+{-# NOINLINE[1] notMember #-}\n notMember :: Key -> IntMap a -> Bool\n-notMember k m = not $ member k m\n+notMember !k = lookupChurch True (const False) k\n \n -- | /O(min(n,W))/. Lookup the value at a key in the map. See also 'Data.Map.lookup'.\n-\n--- See Note: Local 'go' functions and capturing]\n+{-# NOINLINE[1] lookup #-}\n lookup :: Key -> IntMap a -> Maybe a\n-lookup !k = go\n-  where\n-    go (Bin p m l r) | nomatch k p m = Nothing\n-                     | zero k m  = go l\n-                     | otherwise = go r\n-    go (Tip kx x) | k == kx   = Just x\n-                  | otherwise = Nothing\n-    go Nil = Nothing\n+lookup !k = lookupChurch Nothing Just k\n \n-\n--- See Note: Local 'go' functions and capturing]\n-find :: Key -> IntMap a -> a\n-find !k = go\n-  where\n-    go (Bin p m l r) | nomatch k p m = not_found\n-                     | zero k m  = go l\n-                     | otherwise = go r\n-    go (Tip kx x) | k == kx   = x\n-                  | otherwise = not_found\n-    go Nil = not_found\n-\n-    not_found = error (\"IntMap.!: key \" ++ show k ++ \" is not an element of the map\")\n-\n--- | /O(min(n,W))/. The expression @('findWithDefault' def k map)@\n+-- | /O(min(n,W))/. The expression @'findWithDefault' def k map@\n -- returns the value at key @k@ or returns @def@ when the key is not an\n -- element of the map.\n --\n -- > findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'\n -- > findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'\n-\n--- See Note: Local 'go' functions and capturing]\n+{-# NOINLINE[1] findWithDefault #-}\n findWithDefault :: a -> Key -> IntMap a -> a\n-findWithDefault def !k = go\n-  where\n-    go (Bin p m l r) | nomatch k p m = def\n-                     | zero k m  = go l\n-                     | otherwise = go r\n-    go (Tip kx x) | k == kx   = x\n-                  | otherwise = def\n-    go Nil = def\n+findWithDefault def !k = lookupChurch def id k\n \n -- | /O(log n)/. Find largest key smaller than the given one and return the\n -- corresponding (key, value) pair.\n --\n -- > lookupLT 3 (fromList [(3,'a'), (5,'b')]) == Nothing\n -- > lookupLT 4 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')\n-\n--- See Note: Local 'go' functions and capturing.\n lookupLT :: Key -> IntMap a -> Maybe (Key, a)\n-lookupLT !k t = case t of\n-    Bin _ m l r | m < 0 -> if k >= 0 then go r l else go Nil r\n-    _ -> go Nil t\n+lookupLT !k = start\n   where\n-    go def (Bin p m l r)\n-      | nomatch k p m = if k < p then unsafeFindMax def else unsafeFindMax r\n-      | zero k m  = go def l\n-      | otherwise = go l r\n-    go def (Tip ky y)\n-      | k <= ky   = unsafeFindMax def\n-      | otherwise = Just (ky, y)\n-    go def Nil = unsafeFindMax def\n+    start (IntMap Empty) = Nothing\n+    start (IntMap (NonEmpty min minV node))\n+        | boundKey min >= k = Nothing\n+        | otherwise = Just (goL (xor k min) min minV node)\n+\n+    goL !_ min minV Tip = (boundKey min, minV)\n+    goL !xorCache min minV (Bin max maxV l r)\n+        | boundKey max < k = (boundKey max, maxV)\n+        | xorCache < xorCacheMax = goL xorCache min minV l\n+        | otherwise = goR xorCacheMax r min minV l\n+      where\n+        xorCacheMax = xor k max\n \n--- | /O(log n)/. Find smallest key greater than the given one and return the\n--- corresponding (key, value) pair.\n---\n--- > lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')\n--- > lookupGT 5 (fromList [(3,'a'), (5,'b')]) == Nothing\n+    goR !_ Tip fMin fMinV fallback = getMax fMin fMinV fallback\n+    goR !xorCache (Bin min minV l r) fMin fMinV fallback\n+        | boundKey min >= k = getMax fMin fMinV fallback\n+        | xorCache < xorCacheMin = goR xorCache r min minV l\n+        | otherwise = goL xorCacheMin min minV l\n+      where\n+        xorCacheMin = xor k min\n \n--- See Note: Local 'go' functions and capturing.\n-lookupGT :: Key -> IntMap a -> Maybe (Key, a)\n-lookupGT !k t = case t of\n-    Bin _ m l r | m < 0 -> if k >= 0 then go Nil l else go l r\n-    _ -> go Nil t\n-  where\n-    go def (Bin p m l r)\n-      | nomatch k p m = if k < p then unsafeFindMin l else unsafeFindMin def\n-      | zero k m  = go r l\n-      | otherwise = go def r\n-    go def (Tip ky y)\n-      | k >= ky   = unsafeFindMin def\n-      | otherwise = Just (ky, y)\n-    go def Nil = unsafeFindMin def\n+    getMax min minV Tip = (boundKey min, minV)\n+    getMax _   _   (Bin max maxV _ _) = (boundKey max, maxV)\n \n -- | /O(log n)/. Find largest key smaller or equal to the given one and return\n -- the corresponding (key, value) pair.\n --\n -- > lookupLE 2 (fromList [(3,'a'), (5,'b')]) == Nothing\n -- > lookupLE 4 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')\n -- > lookupLE 5 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')\n-\n--- See Note: Local 'go' functions and capturing.\n lookupLE :: Key -> IntMap a -> Maybe (Key, a)\n-lookupLE !k t = case t of\n-    Bin _ m l r | m < 0 -> if k >= 0 then go r l else go Nil r\n-    _ -> go Nil t\n+lookupLE !k = start\n+  where\n+    start (IntMap Empty) = Nothing\n+    start (IntMap (NonEmpty min minV node))\n+        | boundKey min > k = Nothing\n+        | otherwise = Just (goL (xor k min) min minV node)\n+\n+    goL !_ min minV Tip = (boundKey min, minV)\n+    goL !xorCache min minV (Bin max maxV l r)\n+        | boundKey max <= k = (boundKey max, maxV)\n+        | xorCache < xorCacheMax = goL xorCache min minV l\n+        | otherwise = goR xorCacheMax r min minV l\n+      where\n+        xorCacheMax = xor k max\n+\n+    goR !_ Tip fMin fMinV fallback = getMax fMin fMinV fallback\n+    goR !xorCache (Bin min minV l r) fMin fMinV fallback\n+        | boundKey min > k = getMax fMin fMinV fallback\n+        | xorCache < xorCacheMin = goR xorCache r min minV l\n+        | otherwise = goL xorCacheMin min minV l\n+      where\n+        xorCacheMin = xor k min\n+\n+    getMax min minV Tip = (boundKey min, minV)\n+    getMax _   _   (Bin max maxV _ _) = (boundKey max, maxV)\n+\n+-- | /O(log n)/. Find smallest key greater than the given one and return the\n+-- corresponding (key, value) pair.\n+--\n+-- > lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')\n+-- > lookupGT 5 (fromList [(3,'a'), (5,'b')]) == Nothing\n+lookupGT :: Key -> IntMap a -> Maybe (Key, a)\n+lookupGT !k = start\n   where\n-    go def (Bin p m l r)\n-      | nomatch k p m = if k < p then unsafeFindMax def else unsafeFindMax r\n-      | zero k m  = go def l\n-      | otherwise = go l r\n-    go def (Tip ky y)\n-      | k < ky    = unsafeFindMax def\n-      | otherwise = Just (ky, y)\n-    go def Nil = unsafeFindMax def\n+    start (IntMap Empty) = Nothing\n+    start (IntMap (NonEmpty min minV Tip))\n+        | boundKey min <= k = Nothing\n+        | otherwise = Just (boundKey min, minV)\n+    start (IntMap (NonEmpty min minV (Bin max maxV l r)))\n+        | boundKey max <= k = Nothing\n+        | otherwise = Just (goR (xor k max) max maxV (Bin min minV l r))\n+\n+    goL !_ Tip fMax fMaxV fallback = getMin fMax fMaxV fallback\n+    goL !xorCache (Bin max maxV l r) fMax fMaxV fallback\n+        | boundKey max <= k = getMin fMax fMaxV fallback\n+        | xorCache < xorCacheMax = goL xorCache l max maxV r\n+        | otherwise = goR xorCacheMax max maxV r\n+      where\n+        xorCacheMax = xor k max\n+\n+    goR !_ max maxV Tip = (boundKey max, maxV)\n+    goR !xorCache max maxV (Bin min minV l r)\n+        | boundKey min > k = (boundKey min, minV)\n+        | xorCache < xorCacheMin = goR xorCache max maxV r\n+        | otherwise = goL xorCacheMin l max maxV r\n+      where\n+        xorCacheMin = xor k min\n+\n+    getMin max maxV Tip = (boundKey max, maxV)\n+    getMin _   _   (Bin min minV _ _) = (boundKey min, minV)\n \n -- | /O(log n)/. Find smallest key greater or equal to the given one and return\n -- the corresponding (key, value) pair.\n --\n -- > lookupGE 3 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')\n -- > lookupGE 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')\n -- > lookupGE 6 (fromList [(3,'a'), (5,'b')]) == Nothing\n-\n--- See Note: Local 'go' functions and capturing.\n lookupGE :: Key -> IntMap a -> Maybe (Key, a)\n-lookupGE !k t = case t of\n-    Bin _ m l r | m < 0 -> if k >= 0 then go Nil l else go l r\n-    _ -> go Nil t\n-  where\n-    go def (Bin p m l r)\n-      | nomatch k p m = if k < p then unsafeFindMin l else unsafeFindMin def\n-      | zero k m  = go r l\n-      | otherwise = go def r\n-    go def (Tip ky y)\n-      | k > ky    = unsafeFindMin def\n-      | otherwise = Just (ky, y)\n-    go def Nil = unsafeFindMin def\n-\n-\n--- Helper function for lookupGE and lookupGT. It assumes that if a Bin node is\n--- given, it has m > 0.\n-unsafeFindMin :: IntMap a -> Maybe (Key, a)\n-unsafeFindMin Nil = Nothing\n-unsafeFindMin (Tip ky y) = Just (ky, y)\n-unsafeFindMin (Bin _ _ l _) = unsafeFindMin l\n-\n--- Helper function for lookupLE and lookupLT. It assumes that if a Bin node is\n--- given, it has m > 0.\n-unsafeFindMax :: IntMap a -> Maybe (Key, a)\n-unsafeFindMax Nil = Nothing\n-unsafeFindMax (Tip ky y) = Just (ky, y)\n-unsafeFindMax (Bin _ _ _ r) = unsafeFindMax r\n-\n-{--------------------------------------------------------------------\n-  Disjoint\n---------------------------------------------------------------------}\n--- | /O(n+m)/. Check whether the key sets of two maps are disjoint\n--- (i.e. their 'intersection' is empty).\n---\n--- > disjoint (fromList [(2,'a')]) (fromList [(1,()), (3,())])   == True\n--- > disjoint (fromList [(2,'a')]) (fromList [(1,'a'), (2,'b')]) == False\n--- > disjoint (fromList [])        (fromList [])                 == True\n---\n--- > disjoint a b == null (intersection a b)\n---\n--- @since 0.6.2.1\n-disjoint :: IntMap a -> IntMap b -> Bool\n-disjoint Nil _ = True\n-disjoint _ Nil = True\n-disjoint (Tip kx _) ys = notMember kx ys\n-disjoint xs (Tip ky _) = notMember ky xs\n-disjoint t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)\n-  | shorter m1 m2 = disjoint1\n-  | shorter m2 m1 = disjoint2\n-  | p1 == p2      = disjoint l1 l2 && disjoint r1 r2\n-  | otherwise     = True\n+lookupGE !k = start\n   where\n-    disjoint1 | nomatch p2 p1 m1 = True\n-              | zero p2 m1       = disjoint l1 t2\n-              | otherwise        = disjoint r1 t2\n-    disjoint2 | nomatch p1 p2 m2 = True\n-              | zero p1 m2       = disjoint t1 l2\n-              | otherwise        = disjoint t1 r2\n-\n-{--------------------------------------------------------------------\n-  Construction\n---------------------------------------------------------------------}\n+    start (IntMap Empty) = Nothing\n+    start (IntMap (NonEmpty min minV Tip))\n+        | boundKey min < k = Nothing\n+        | otherwise = Just (boundKey min, minV)\n+    start (IntMap (NonEmpty min minV (Bin max maxV l r)))\n+        | boundKey max < k = Nothing\n+        | otherwise = Just (goR (xor k max) max maxV (Bin min minV l r))\n+\n+    goL !_ Tip fMax fMaxV fallback = getMin fMax fMaxV fallback\n+    goL !xorCache (Bin max maxV l r) fMax fMaxV fallback\n+        | boundKey max < k = getMin fMax fMaxV fallback\n+        | xorCache < xorCacheMax = goL xorCache l max maxV r\n+        | otherwise = goR xorCacheMax max maxV r\n+      where\n+        xorCacheMax = xor k max\n+\n+    goR !_ max maxV Tip = (boundKey max, maxV)\n+    goR !xorCache max maxV (Bin min minV l r)\n+        | boundKey min >= k = (boundKey min, minV)\n+        | xorCache < xorCacheMin = goR xorCache max maxV r\n+        | otherwise = goL xorCacheMin l max maxV r\n+      where\n+        xorCacheMin = xor k min\n+\n+    getMin max maxV Tip = (boundKey max, maxV)\n+    getMin _   _   (Bin min minV _ _) = (boundKey min, minV)\n+\n -- | /O(1)/. The empty map.\n --\n -- > empty      == fromList []\n -- > size empty == 0\n-\n empty :: IntMap a\n-empty\n-  = Nil\n-{-# INLINE empty #-}\n-\n--- | /O(1)/. A map of one element.\n---\n--- > singleton 1 'a'        == fromList [(1, 'a')]\n--- > size (singleton 1 'a') == 1\n-\n-singleton :: Key -> a -> IntMap a\n-singleton k x\n-  = Tip k x\n-{-# INLINE singleton #-}\n-\n-{--------------------------------------------------------------------\n-  Insert\n---------------------------------------------------------------------}\n--- | /O(min(n,W))/. Insert a new key\\/value pair in the map.\n--- If the key is already present in the map, the associated value is\n--- replaced with the supplied value, i.e. 'insert' is equivalent to\n--- @'insertWith' 'const'@.\n---\n--- > insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]\n--- > insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]\n--- > insert 5 'x' empty                         == singleton 5 'x'\n-\n-insert :: Key -> a -> IntMap a -> IntMap a\n-insert !k x t@(Bin p m l r)\n-  | nomatch k p m = link k (Tip k x) p t\n-  | zero k m      = Bin p m (insert k x l) r\n-  | otherwise     = Bin p m l (insert k x r)\n-insert k x t@(Tip ky _)\n-  | k==ky         = Tip k x\n-  | otherwise     = link k (Tip k x) ky t\n-insert k x Nil = Tip k x\n-\n--- right-biased insertion, used by 'union'\n--- | /O(min(n,W))/. Insert with a combining function.\n--- @'insertWith' f key value mp@\n--- will insert the pair (key, value) into @mp@ if key does\n--- not exist in the map. If the key does exist, the function will\n--- insert @f new_value old_value@.\n---\n--- > insertWith (++) 5 \"xxx\" (fromList [(5,\"a\"), (3,\"b\")]) == fromList [(3, \"b\"), (5, \"xxxa\")]\n--- > insertWith (++) 7 \"xxx\" (fromList [(5,\"a\"), (3,\"b\")]) == fromList [(3, \"b\"), (5, \"a\"), (7, \"xxx\")]\n--- > insertWith (++) 5 \"xxx\" empty                         == singleton 5 \"xxx\"\n-\n-insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a\n-insertWith f k x t\n-  = insertWithKey (\\_ x' y' -> f x' y') k x t\n-\n--- | /O(min(n,W))/. Insert with a combining function.\n--- @'insertWithKey' f key value mp@\n--- will insert the pair (key, value) into @mp@ if key does\n--- not exist in the map. If the key does exist, the function will\n--- insert @f key new_value old_value@.\n---\n--- > let f key new_value old_value = (show key) ++ \":\" ++ new_value ++ \"|\" ++ old_value\n--- > insertWithKey f 5 \"xxx\" (fromList [(5,\"a\"), (3,\"b\")]) == fromList [(3, \"b\"), (5, \"5:xxx|a\")]\n--- > insertWithKey f 7 \"xxx\" (fromList [(5,\"a\"), (3,\"b\")]) == fromList [(3, \"b\"), (5, \"a\"), (7, \"xxx\")]\n--- > insertWithKey f 5 \"xxx\" empty                         == singleton 5 \"xxx\"\n-\n-insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a\n-insertWithKey f !k x t@(Bin p m l r)\n-  | nomatch k p m = link k (Tip k x) p t\n-  | zero k m      = Bin p m (insertWithKey f k x l) r\n-  | otherwise     = Bin p m l (insertWithKey f k x r)\n-insertWithKey f k x t@(Tip ky y)\n-  | k == ky       = Tip k (f k x y)\n-  | otherwise     = link k (Tip k x) ky t\n-insertWithKey _ k x Nil = Tip k x\n-\n--- | /O(min(n,W))/. The expression (@'insertLookupWithKey' f k x map@)\n--- is a pair where the first element is equal to (@'lookup' k map@)\n--- and the second element equal to (@'insertWithKey' f k x map@).\n---\n--- > let f key new_value old_value = (show key) ++ \":\" ++ new_value ++ \"|\" ++ old_value\n--- > insertLookupWithKey f 5 \"xxx\" (fromList [(5,\"a\"), (3,\"b\")]) == (Just \"a\", fromList [(3, \"b\"), (5, \"5:xxx|a\")])\n--- > insertLookupWithKey f 7 \"xxx\" (fromList [(5,\"a\"), (3,\"b\")]) == (Nothing,  fromList [(3, \"b\"), (5, \"a\"), (7, \"xxx\")])\n--- > insertLookupWithKey f 5 \"xxx\" empty                         == (Nothing,  singleton 5 \"xxx\")\n---\n--- This is how to define @insertLookup@ using @insertLookupWithKey@:\n---\n--- > let insertLookup kx x t = insertLookupWithKey (\\_ a _ -> a) kx x t\n--- > insertLookup 5 \"x\" (fromList [(5,\"a\"), (3,\"b\")]) == (Just \"a\", fromList [(3, \"b\"), (5, \"x\")])\n--- > insertLookup 7 \"x\" (fromList [(5,\"a\"), (3,\"b\")]) == (Nothing,  fromList [(3, \"b\"), (5, \"a\"), (7, \"x\")])\n-\n-insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)\n-insertLookupWithKey f !k x t@(Bin p m l r)\n-  | nomatch k p m = (Nothing,link k (Tip k x) p t)\n-  | zero k m      = let (found,l') = insertLookupWithKey f k x l\n-                    in (found,Bin p m l' r)\n-  | otherwise     = let (found,r') = insertLookupWithKey f k x r\n-                    in (found,Bin p m l r')\n-insertLookupWithKey f k x t@(Tip ky y)\n-  | k == ky       = (Just y,Tip k (f k x y))\n-  | otherwise     = (Nothing,link k (Tip k x) ky t)\n-insertLookupWithKey _ k x Nil = (Nothing,Tip k x)\n-\n-\n-{--------------------------------------------------------------------\n-  Deletion\n---------------------------------------------------------------------}\n--- | /O(min(n,W))/. Delete a key and its value from the map. When the key is not\n--- a member of the map, the original map is returned.\n---\n--- > delete 5 (fromList [(5,\"a\"), (3,\"b\")]) == singleton 3 \"b\"\n--- > delete 7 (fromList [(5,\"a\"), (3,\"b\")]) == fromList [(3, \"b\"), (5, \"a\")]\n--- > delete 5 empty                         == empty\n+empty = IntMap Empty\n+\n+-- | /O(min(n,W))/. Insert with a combining function, generic over strictness.\n+-- Before inserting a value into the map, @'insertWithEval' eval@ will strictly\n+-- depend on the resut of calling @eval@ on the value to be inserted. Passing\n+-- an evaluation function that does no evaluation will result in lazy\n+-- insertion, while passing a function that actually evaluates its argument\n+-- will result in strict insertion.\n+--\n+-- When 'insertWithEval' is given one argument (the evaluation function), it is\n+-- inlined at the call site. 'insertWithEval' is intended for defining\n+-- @insert@-style functions.\n+{-# INLINE insertWithEval #-}\n+insertWithEval :: (a -> ()) -> (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a\n+insertWithEval eval = start\n+  where\n+    start _       !k v (IntMap Empty) = eval v `seq` IntMap (NonEmpty (Bound k) v Tip)\n+    start combine !k v (IntMap (NonEmpty min minV root)) = case compareMinBound k min of\n+        InBound -> IntMap (NonEmpty min minV (goL combine k v (xor k min) min root))\n+        OutOfBound -> eval v `seq` IntMap (NonEmpty (Bound k) v (insertMinL (xor k min) min minV root))\n+        Matched -> let v' = combine v minV\n+                    in eval v' `seq` IntMap (NonEmpty (Bound k) v' root)\n+\n+    -- | Insert a key/value pair into a left node when the key is known to be larger\n+    -- than the minimum bound of the subtree.\n+    goL _       !k v !_        !_    Tip = eval v `seq` Bin (Bound k) v Tip Tip\n+    goL combine !k v !xorCache !min (Bin max maxV l r) = case compareMaxBound k max of\n+        -- In the simple case, we recurse into whichever branch is applicable.\n+        InBound | xorCache < xorCacheMax -> Bin max maxV (goL combine k v xorCache min l) r\n+                | otherwise              -> Bin max maxV l (goR combine k v xorCacheMax max r)\n+\n+        -- If the key is the new maximum, then we have two cases to consider. If\n+        -- the split point between 'min' and 'k' is earlier than the split between\n+        -- 'min' and 'max', then we can just immediately create a new node. Otherwise,\n+        -- we need to push 'max' down into the right branch until it arrives at the\n+        -- correct location.\n+        --\n+        -- We do the this check by simulating a navigation where 'max' is the key,\n+        -- 'min' is the minimum, and 'k' is the maximum. If 'max' belongs on the\n+        -- left side, then the entire old subtree belongs on the left side. If\n+        -- 'max' belongs on the right side, then we have to push it down.\n+        OutOfBound | xor (boundKey max) min < xorCacheMax -> eval v `seq` Bin (Bound k) v (Bin max maxV l r) Tip\n+                   | otherwise -> eval v `seq` Bin (Bound k) v l (insertMaxR xorCacheMax max maxV r)\n+\n+        Matched -> let v' = combine v maxV\n+                    in eval v' `seq` Bin max v' l r\n+      where xorCacheMax = xor k max\n+\n+    goR _       !k v !_        !_    Tip = eval v `seq` Bin (Bound k) v Tip Tip\n+    goR combine !k v !xorCache !max (Bin min minV l r) = case compareMinBound k min of\n+        InBound | xorCache < xorCacheMin -> Bin min minV l (goR combine k v xorCache max r)\n+                | otherwise -> Bin min minV (goL combine k v xorCacheMin min l) r\n+        OutOfBound | xor (boundKey min) max < xorCacheMin -> eval v `seq` Bin (Bound k) v Tip (Bin min minV l r)\n+                   | otherwise -> eval v `seq` Bin (Bound k) v (insertMinL xorCacheMin min minV l) r\n+        Matched -> let v' = combine v minV\n+                    in eval v' `seq` Bin min v' l r\n+      where xorCacheMin = xor k min\n+\n+-- Small functions that really ought to be defined in Data.IntMap.Lazy but have\n+-- to be here for the sake of type class implementations\n+{-# NOINLINE[1] insertLazy #-}\n+insertLazy :: Key -> a -> IntMap a -> IntMap a\n+insertLazy = insertWithEval (const ()) const\n+fromListLazy :: [(Key, a)] -> IntMap a","path":"containers/src/Data/IntMap/Internal.hs","position":1790,"original_position":1790,"commit_id":"535e44cbdcdb18b3f6855ed60cb5b82e197ef027","original_commit_id":"535e44cbdcdb18b3f6855ed60cb5b82e197ef027","user":{"login":"sjakobi","id":3664523,"node_id":"MDQ6VXNlcjM2NjQ1MjM=","avatar_url":"https://avatars1.githubusercontent.com/u/3664523?v=4","gravatar_id":"","url":"https://api.github.com/users/sjakobi","html_url":"https://github.com/sjakobi","followers_url":"https://api.github.com/users/sjakobi/followers","following_url":"https://api.github.com/users/sjakobi/following{/other_user}","gists_url":"https://api.github.com/users/sjakobi/gists{/gist_id}","starred_url":"https://api.github.com/users/sjakobi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sjakobi/subscriptions","organizations_url":"https://api.github.com/users/sjakobi/orgs","repos_url":"https://api.github.com/users/sjakobi/repos","events_url":"https://api.github.com/users/sjakobi/events{/privacy}","received_events_url":"https://api.github.com/users/sjakobi/received_events","type":"User","site_admin":false},"body":"Please add the usual empty lines between definitions.","created_at":"2020-01-12T00:13:33Z","updated_at":"2020-01-12T00:39:26Z","html_url":"https://github.com/haskell/containers/pull/340#discussion_r365549042","pull_request_url":"https://api.github.com/repos/haskell/containers/pulls/340","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/haskell/containers/pulls/comments/365549042"},"html":{"href":"https://github.com/haskell/containers/pull/340#discussion_r365549042"},"pull_request":{"href":"https://api.github.com/repos/haskell/containers/pulls/340"}}},"pull_request":{"url":"https://api.github.com/repos/haskell/containers/pulls/340","id":84981922,"node_id":"MDExOlB1bGxSZXF1ZXN0ODQ5ODE5MjI=","html_url":"https://github.com/haskell/containers/pull/340","diff_url":"https://github.com/haskell/containers/pull/340.diff","patch_url":"https://github.com/haskell/containers/pull/340.patch","issue_url":"https://api.github.com/repos/haskell/containers/issues/340","number":340,"state":"open","locked":false,"title":"Rewrite Data.IntMap to be faster and use less memory","user":{"login":"gereeter","id":2328242,"node_id":"MDQ6VXNlcjIzMjgyNDI=","avatar_url":"https://avatars1.githubusercontent.com/u/2328242?v=4","gravatar_id":"","url":"https://api.github.com/users/gereeter","html_url":"https://github.com/gereeter","followers_url":"https://api.github.com/users/gereeter/followers","following_url":"https://api.github.com/users/gereeter/following{/other_user}","gists_url":"https://api.github.com/users/gereeter/gists{/gist_id}","starred_url":"https://api.github.com/users/gereeter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gereeter/subscriptions","organizations_url":"https://api.github.com/users/gereeter/orgs","repos_url":"https://api.github.com/users/gereeter/repos","events_url":"https://api.github.com/users/gereeter/events{/privacy}","received_events_url":"https://api.github.com/users/gereeter/received_events","type":"User","site_admin":false},"body":"I still sort of think of this as a work in progress, but I've been sitting for over 2 years now on this code, and all the tests pass with significant improvements on many benchmarks. The general approach is detailed at [gereeter/bounded-intmap](https://github.com/gereeter/bounded-intmap) - the README is a bit outdated and I really should incorporate it into comments, but it is the best reference for how the structure works. As for compatibility, I think I'm missing some instances, some Safe Haskell stuff, and anything required to get things working on compilers that aren't the latest GHC.\n\nIf this is a large enough change, I wouldn't mind sending mail to the libraries mailing list, but it should be entirely backwards compatible.\n\ncc @ekmett - This is a (heavily modified) version of an idea you came up with.\n## Memory usage\n\nThe old implementation had `6n-5` words of overhead (i.e. discounting storage of the keys and the pointers to values). The new implementation has only `3n-1` words of overhead.\n## Large runtime regressions\n- ~~`fromAscList` and `fromDistinctAscList` are currently just aliases for `fromList`~~\n- I have no clue about `foldlWithKey'`\n- `keysSet`, `fromSet`, `restrictKeys`, and `withoutKeys` are currently implemented naively and are probably much slower\n## Benchmarks\n\n```\nBenchmark                     Runtime change  Original runtime\nlookup                         -19.25%        4.38e-04\ninsert                         -22.57%        9.17e-04\n\"insertWith empty\"             -10.20%        8.85e-04\n\"insertWith update\"             -7.32%        1.96e-03\n\"insertWith' empty\"             -9.92%        8.84e-04\n\"insertWith' update\"           -11.00%        1.67e-03\n\"insertWithKey empty\"          -10.23%        8.76e-04\n\"insertWithKey update\"          +6.64%        1.96e-03\n\"insertWithKey' empty\"         -10.47%        8.84e-04\n\"insertWithKey' update\"        -11.29%        1.68e-03\n\"insertLookupWithKey empty\"    -46.46%        1.74e-03\n\"insertLookupWithKey update\"   -41.50%        3.94e-03\nmap                            -17.13%        1.81e-04\nmapWithKey                     -24.97%        2.19e-04\nfoldlWithKey                   -19.19%        1.50e-03\nfoldlWithKey'                 +112.26%        4.29e-05\nfoldrWithKey                   -79.82%        1.02e-07\ndelete                          +9.36%        3.42e-04\nupdate                         -12.59%        1.50e-03\nupdateLookupWithKey             +1.39%        2.44e-03\nalter                           +5.04%        1.53e-03\nmapMaybe                       -15.58%        2.25e-04\nmapMaybeWithKey                -15.88%        2.24e-04\nfromList                       -15.42%        8.96e-04\nfromAscList                    -81.50%        6.83e-04\nfromDistinctAscList            -43.34%        2.24e-04\n```\n### Merges\n\n```\nBenchmark               Runtime change  Original runtime\nunion-disj_nn             +8.53%        2.08e-07\nunion-disj_nn             +9.74%        2.09e-07\nunion-disj_ns            +11.66%        1.85e-07\nunion-disj_ns             +7.15%        1.85e-07\nunion-disj_sn             +7.00%        1.94e-07\nunion-disj_sn             +5.67%        1.94e-07\nunion-disj_nt             +7.22%        1.55e-07\nunion-disj_nt             +5.51%        1.55e-07\nunion-disj_tn             +5.88%        1.61e-07\nunion-disj_tn             +5.91%        1.61e-07\nunion-common_nn          -15.58%        1.12e-02\nunion-common_nn          -15.30%        1.10e-02\nunion-common_ns          -11.65%        4.69e-03\nunion-common_ns          -11.57%        4.67e-03\nunion-common_sn          -10.49%        4.67e-03\nunion-common_sn          -10.23%        4.67e-03\nunion-common_nt          -26.05%        9.11e-05\nunion-common_nt          -28.51%        9.43e-05\nunion-common_tn          -21.01%        8.89e-05\nunion-common_tn          -19.67%        8.80e-05\nunion-mix_nn             +12.20%        2.06e-02\nunion-mix_nn             +11.70%        2.06e-02\nunion-mix_ns              +5.05%        5.10e-03\nunion-mix_ns              +5.84%        5.10e-03\nunion-mix_sn              +6.15%        5.11e-03\nunion-mix_sn              +7.16%        5.08e-03\nunion-mix_nt              -4.19%        8.05e-05\nunion-mix_nt              -4.29%        8.03e-05\nunion-mix_tn              -6.17%        8.58e-05\nunion-mix_tn              -6.81%        8.61e-05\nunion-block_nn           +38.23%        1.03e-04\nunion-block_nn           +39.21%        1.03e-04\nunion-block_ns           +30.53%        6.79e-06\nunion-block_ns           +31.57%        6.78e-06\nunion-block_sn           +29.41%        6.92e-06\nunion-block_sn           +30.39%        6.88e-06\ndifference-disj_nn       -78.96%        1.72e-07\ndifference-disj_nn       -78.95%        1.72e-07\ndifference-disj_ns       -73.77%        1.60e-07\ndifference-disj_ns       -77.32%        1.60e-07\ndifference-disj_sn       -82.64%        1.91e-07\ndifference-disj_sn       -82.02%        1.91e-07\ndifference-disj_nt       -74.05%        1.40e-07\ndifference-disj_nt       -74.09%        1.40e-07\ndifference-disj_tn       -77.35%        1.47e-07\ndifference-disj_tn       -77.28%        1.47e-07\ndifference-common_nn      +4.10%        7.50e-03\ndifference-common_nn      +4.25%        7.50e-03\ndifference-common_ns      -0.97%        4.27e-03\ndifference-common_ns      -1.31%        4.28e-03\ndifference-common_sn     -30.13%        8.64e-04\ndifference-common_sn     -34.10%        8.55e-04\ndifference-common_nt     -20.80%        1.00e-04\ndifference-common_nt     -18.82%        1.01e-04\ndifference-common_tn     -37.75%        5.91e-05\ndifference-common_tn     -32.56%        5.92e-05\ndifference-mix_nn        -18.42%        1.78e-02\ndifference-mix_nn        -18.95%        1.78e-02\ndifference-mix_ns        -21.13%        4.36e-03\ndifference-mix_ns        -21.18%        4.35e-03\ndifference-mix_sn        +19.57%        1.49e-03\ndifference-mix_sn        +19.49%        1.49e-03\ndifference-mix_nt        -29.75%        8.57e-05\ndifference-mix_nt        -29.13%        8.52e-05\ndifference-mix_tn        -27.97%        5.37e-05\ndifference-mix_tn        -29.38%        5.45e-05\ndifference-block_nn      -69.85%        7.37e-05\ndifference-block_nn      -70.66%        7.57e-05\ndifference-block_ns      -64.67%        6.55e-06\ndifference-block_ns      -64.53%        6.54e-06\ndifference-block_sn      -40.12%        5.43e-06\ndifference-block_sn      -40.19%        5.44e-06\nintersection-disj_nn     -70.09%        1.24e-07\nintersection-disj_nn     -69.98%        1.24e-07\nintersection-disj_ns     -67.57%        1.12e-07\nintersection-disj_ns     -66.18%        1.12e-07\nintersection-disj_sn     -66.65%        1.12e-07\nintersection-disj_sn     -66.92%        1.12e-07\nintersection-disj_nt     -60.91%        9.38e-08\nintersection-disj_nt     -61.18%        9.38e-08\nintersection-disj_tn     -60.17%        9.28e-08\nintersection-disj_tn     -60.32%        9.27e-08\nintersection-common_nn    +6.06%        7.08e-03\nintersection-common_nn    +5.82%        7.07e-03\nintersection-common_ns   -25.00%        1.04e-03\nintersection-common_ns   -25.84%        1.05e-03\nintersection-common_sn   -20.87%        1.07e-03\nintersection-common_sn   -15.66%        1.05e-03\nintersection-common_nt   -31.67%        5.48e-05\nintersection-common_nt   -31.14%        5.45e-05\nintersection-common_tn   -28.09%        5.97e-05\nintersection-common_tn   -28.55%        5.98e-05\nintersection-mix_nn       +0.71%        3.01e-03\nintersection-mix_nn       -6.14%        3.14e-03\nintersection-mix_ns      -29.39%        6.40e-04\nintersection-mix_ns      -30.65%        6.39e-04\nintersection-mix_sn      -23.04%        6.64e-04\nintersection-mix_sn      -22.10%        6.58e-04\nintersection-mix_nt      -17.51%        3.90e-05\nintersection-mix_nt      -19.35%        3.91e-05\nintersection-mix_tn      -21.05%        4.63e-05\nintersection-mix_tn      -17.28%        4.59e-05\nintersection-block_nn    -62.01%        4.88e-05\nintersection-block_nn    -62.37%        4.88e-05\nintersection-block_ns    -45.10%        3.52e-06\nintersection-block_ns    -45.39%        3.54e-06\nintersection-block_sn    -27.86%        3.43e-06\nintersection-block_sn    -27.83%        3.43e-06\n```\n","created_at":"2016-09-13T03:57:06Z","updated_at":"2020-01-12T00:39:25Z","closed_at":null,"merged_at":null,"merge_commit_sha":"f2866fedcb81a460f1c199aa87d272199c8e7efe","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[{"id":787842281,"node_id":"MDU6TGFiZWw3ODc4NDIyODE=","url":"https://api.github.com/repos/haskell/containers/labels/performance","name":"performance","color":"5319e7","default":false,"description":null}],"milestone":null,"commits_url":"https://api.github.com/repos/haskell/containers/pulls/340/commits","review_comments_url":"https://api.github.com/repos/haskell/containers/pulls/340/comments","review_comment_url":"https://api.github.com/repos/haskell/containers/pulls/comments{/number}","comments_url":"https://api.github.com/repos/haskell/containers/issues/340/comments","statuses_url":"https://api.github.com/repos/haskell/containers/statuses/535e44cbdcdb18b3f6855ed60cb5b82e197ef027","head":{"label":"gereeter:direct-bounded-intmap","ref":"direct-bounded-intmap","sha":"535e44cbdcdb18b3f6855ed60cb5b82e197ef027","user":{"login":"gereeter","id":2328242,"node_id":"MDQ6VXNlcjIzMjgyNDI=","avatar_url":"https://avatars1.githubusercontent.com/u/2328242?v=4","gravatar_id":"","url":"https://api.github.com/users/gereeter","html_url":"https://github.com/gereeter","followers_url":"https://api.github.com/users/gereeter/followers","following_url":"https://api.github.com/users/gereeter/following{/other_user}","gists_url":"https://api.github.com/users/gereeter/gists{/gist_id}","starred_url":"https://api.github.com/users/gereeter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gereeter/subscriptions","organizations_url":"https://api.github.com/users/gereeter/orgs","repos_url":"https://api.github.com/users/gereeter/repos","events_url":"https://api.github.com/users/gereeter/events{/privacy}","received_events_url":"https://api.github.com/users/gereeter/received_events","type":"User","site_admin":false},"repo":{"id":12346414,"node_id":"MDEwOlJlcG9zaXRvcnkxMjM0NjQxNA==","name":"containers","full_name":"gereeter/containers","private":false,"owner":{"login":"gereeter","id":2328242,"node_id":"MDQ6VXNlcjIzMjgyNDI=","avatar_url":"https://avatars1.githubusercontent.com/u/2328242?v=4","gravatar_id":"","url":"https://api.github.com/users/gereeter","html_url":"https://github.com/gereeter","followers_url":"https://api.github.com/users/gereeter/followers","following_url":"https://api.github.com/users/gereeter/following{/other_user}","gists_url":"https://api.github.com/users/gereeter/gists{/gist_id}","starred_url":"https://api.github.com/users/gereeter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gereeter/subscriptions","organizations_url":"https://api.github.com/users/gereeter/orgs","repos_url":"https://api.github.com/users/gereeter/repos","events_url":"https://api.github.com/users/gereeter/events{/privacy}","received_events_url":"https://api.github.com/users/gereeter/received_events","type":"User","site_admin":false},"html_url":"https://github.com/gereeter/containers","description":null,"fork":true,"url":"https://api.github.com/repos/gereeter/containers","forks_url":"https://api.github.com/repos/gereeter/containers/forks","keys_url":"https://api.github.com/repos/gereeter/containers/keys{/key_id}","collaborators_url":"https://api.github.com/repos/gereeter/containers/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/gereeter/containers/teams","hooks_url":"https://api.github.com/repos/gereeter/containers/hooks","issue_events_url":"https://api.github.com/repos/gereeter/containers/issues/events{/number}","events_url":"https://api.github.com/repos/gereeter/containers/events","assignees_url":"https://api.github.com/repos/gereeter/containers/assignees{/user}","branches_url":"https://api.github.com/repos/gereeter/containers/branches{/branch}","tags_url":"https://api.github.com/repos/gereeter/containers/tags","blobs_url":"https://api.github.com/repos/gereeter/containers/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/gereeter/containers/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/gereeter/containers/git/refs{/sha}","trees_url":"https://api.github.com/repos/gereeter/containers/git/trees{/sha}","statuses_url":"https://api.github.com/repos/gereeter/containers/statuses/{sha}","languages_url":"https://api.github.com/repos/gereeter/containers/languages","stargazers_url":"https://api.github.com/repos/gereeter/containers/stargazers","contributors_url":"https://api.github.com/repos/gereeter/containers/contributors","subscribers_url":"https://api.github.com/repos/gereeter/containers/subscribers","subscription_url":"https://api.github.com/repos/gereeter/containers/subscription","commits_url":"https://api.github.com/repos/gereeter/containers/commits{/sha}","git_commits_url":"https://api.github.com/repos/gereeter/containers/git/commits{/sha}","comments_url":"https://api.github.com/repos/gereeter/containers/comments{/number}","issue_comment_url":"https://api.github.com/repos/gereeter/containers/issues/comments{/number}","contents_url":"https://api.github.com/repos/gereeter/containers/contents/{+path}","compare_url":"https://api.github.com/repos/gereeter/containers/compare/{base}...{head}","merges_url":"https://api.github.com/repos/gereeter/containers/merges","archive_url":"https://api.github.com/repos/gereeter/containers/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/gereeter/containers/downloads","issues_url":"https://api.github.com/repos/gereeter/containers/issues{/number}","pulls_url":"https://api.github.com/repos/gereeter/containers/pulls{/number}","milestones_url":"https://api.github.com/repos/gereeter/containers/milestones{/number}","notifications_url":"https://api.github.com/repos/gereeter/containers/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/gereeter/containers/labels{/name}","releases_url":"https://api.github.com/repos/gereeter/containers/releases{/id}","deployments_url":"https://api.github.com/repos/gereeter/containers/deployments","created_at":"2013-08-24T16:46:36Z","updated_at":"2016-08-02T03:16:54Z","pushed_at":"2020-01-11T22:24:58Z","git_url":"git://github.com/gereeter/containers.git","ssh_url":"git@github.com:gereeter/containers.git","clone_url":"https://github.com/gereeter/containers.git","svn_url":"https://github.com/gereeter/containers","homepage":"","size":8932,"stargazers_count":0,"watchers_count":0,"language":"Haskell","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"disabled":false,"open_issues_count":0,"license":{"key":"other","name":"Other","spdx_id":"NOASSERTION","url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"haskell:master","ref":"master","sha":"f7e27e6eb3717a1f11727b47d84fa42904ca6b1a","user":{"login":"haskell","id":450574,"node_id":"MDEyOk9yZ2FuaXphdGlvbjQ1MDU3NA==","avatar_url":"https://avatars1.githubusercontent.com/u/450574?v=4","gravatar_id":"","url":"https://api.github.com/users/haskell","html_url":"https://github.com/haskell","followers_url":"https://api.github.com/users/haskell/followers","following_url":"https://api.github.com/users/haskell/following{/other_user}","gists_url":"https://api.github.com/users/haskell/gists{/gist_id}","starred_url":"https://api.github.com/users/haskell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haskell/subscriptions","organizations_url":"https://api.github.com/users/haskell/orgs","repos_url":"https://api.github.com/users/haskell/repos","events_url":"https://api.github.com/users/haskell/events{/privacy}","received_events_url":"https://api.github.com/users/haskell/received_events","type":"Organization","site_admin":false},"repo":{"id":1924888,"node_id":"MDEwOlJlcG9zaXRvcnkxOTI0ODg4","name":"containers","full_name":"haskell/containers","private":false,"owner":{"login":"haskell","id":450574,"node_id":"MDEyOk9yZ2FuaXphdGlvbjQ1MDU3NA==","avatar_url":"https://avatars1.githubusercontent.com/u/450574?v=4","gravatar_id":"","url":"https://api.github.com/users/haskell","html_url":"https://github.com/haskell","followers_url":"https://api.github.com/users/haskell/followers","following_url":"https://api.github.com/users/haskell/following{/other_user}","gists_url":"https://api.github.com/users/haskell/gists{/gist_id}","starred_url":"https://api.github.com/users/haskell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haskell/subscriptions","organizations_url":"https://api.github.com/users/haskell/orgs","repos_url":"https://api.github.com/users/haskell/repos","events_url":"https://api.github.com/users/haskell/events{/privacy}","received_events_url":"https://api.github.com/users/haskell/received_events","type":"Organization","site_admin":false},"html_url":"https://github.com/haskell/containers","description":"Assorted concrete container types","fork":false,"url":"https://api.github.com/repos/haskell/containers","forks_url":"https://api.github.com/repos/haskell/containers/forks","keys_url":"https://api.github.com/repos/haskell/containers/keys{/key_id}","collaborators_url":"https://api.github.com/repos/haskell/containers/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/haskell/containers/teams","hooks_url":"https://api.github.com/repos/haskell/containers/hooks","issue_events_url":"https://api.github.com/repos/haskell/containers/issues/events{/number}","events_url":"https://api.github.com/repos/haskell/containers/events","assignees_url":"https://api.github.com/repos/haskell/containers/assignees{/user}","branches_url":"https://api.github.com/repos/haskell/containers/branches{/branch}","tags_url":"https://api.github.com/repos/haskell/containers/tags","blobs_url":"https://api.github.com/repos/haskell/containers/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/haskell/containers/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/haskell/containers/git/refs{/sha}","trees_url":"https://api.github.com/repos/haskell/containers/git/trees{/sha}","statuses_url":"https://api.github.com/repos/haskell/containers/statuses/{sha}","languages_url":"https://api.github.com/repos/haskell/containers/languages","stargazers_url":"https://api.github.com/repos/haskell/containers/stargazers","contributors_url":"https://api.github.com/repos/haskell/containers/contributors","subscribers_url":"https://api.github.com/repos/haskell/containers/subscribers","subscription_url":"https://api.github.com/repos/haskell/containers/subscription","commits_url":"https://api.github.com/repos/haskell/containers/commits{/sha}","git_commits_url":"https://api.github.com/repos/haskell/containers/git/commits{/sha}","comments_url":"https://api.github.com/repos/haskell/containers/comments{/number}","issue_comment_url":"https://api.github.com/repos/haskell/containers/issues/comments{/number}","contents_url":"https://api.github.com/repos/haskell/containers/contents/{+path}","compare_url":"https://api.github.com/repos/haskell/containers/compare/{base}...{head}","merges_url":"https://api.github.com/repos/haskell/containers/merges","archive_url":"https://api.github.com/repos/haskell/containers/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/haskell/containers/downloads","issues_url":"https://api.github.com/repos/haskell/containers/issues{/number}","pulls_url":"https://api.github.com/repos/haskell/containers/pulls{/number}","milestones_url":"https://api.github.com/repos/haskell/containers/milestones{/number}","notifications_url":"https://api.github.com/repos/haskell/containers/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/haskell/containers/labels{/name}","releases_url":"https://api.github.com/repos/haskell/containers/releases{/id}","deployments_url":"https://api.github.com/repos/haskell/containers/deployments","created_at":"2011-06-20T17:48:10Z","updated_at":"2020-01-10T15:22:05Z","pushed_at":"2020-01-11T22:25:01Z","git_url":"git://github.com/haskell/containers.git","ssh_url":"git@github.com:haskell/containers.git","clone_url":"https://github.com/haskell/containers.git","svn_url":"https://github.com/haskell/containers","homepage":"https://hackage.haskell.org/package/containers","size":8628,"stargazers_count":243,"watchers_count":243,"language":"Haskell","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":132,"mirror_url":null,"archived":false,"disabled":false,"open_issues_count":165,"license":{"key":"other","name":"Other","spdx_id":"NOASSERTION","url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":132,"open_issues":165,"watchers":243,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/haskell/containers/pulls/340"},"html":{"href":"https://github.com/haskell/containers/pull/340"},"issue":{"href":"https://api.github.com/repos/haskell/containers/issues/340"},"comments":{"href":"https://api.github.com/repos/haskell/containers/issues/340/comments"},"review_comments":{"href":"https://api.github.com/repos/haskell/containers/pulls/340/comments"},"review_comment":{"href":"https://api.github.com/repos/haskell/containers/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/haskell/containers/pulls/340/commits"},"statuses":{"href":"https://api.github.com/repos/haskell/containers/statuses/535e44cbdcdb18b3f6855ed60cb5b82e197ef027"}},"author_association":"NONE"}}
{"actor":{"display_login":"sjakobi"}}