# Ticket #4887: mapops-benchmark.dpatch

File mapops-benchmark.dpatch, 36.6 KB (added by , 6 years ago) |
---|

Line | |
---|---|

1 | 2 patches for repository /Users/tibell/src/containers/master: |

2 | |

3 | Fri Jan 7 18:12:08 CET 2011 Ross Paterson <ross@soi.city.ac.uk> |

4 | * add a Location interface for element-wise operations |

5 | |

6 | This is a variant of a suggestion by apfelmus: |

7 | |

8 | http://www.haskell.org/pipermail/libraries/2010-September/014510.html |

9 | |

10 | To avoid proliferation of variants of element-wise operations, the idea |

11 | is to split these operations into two phases mediated by a new Location |

12 | type, so that users can do whatever they like between these phases. |

13 | |

14 | Wed Jan 12 22:45:11 CET 2011 Johan Tibell <johan.tibell@gmail.com> |

15 | * Modified benchmark to use MapOps |

16 | |

17 | This allows us to test the performance of e.g. insertWith', when defined |

18 | in terms of 'search'. |

19 | |

20 | New patches: |

21 | |

22 | [add a Location interface for element-wise operations |

23 | Ross Paterson <ross@soi.city.ac.uk>**20110107171208 |

24 | Ignore-this: eae16f6e0219241daf0b1d6dbc9662a1 |

25 | |

26 | This is a variant of a suggestion by apfelmus: |

27 | |

28 | http://www.haskell.org/pipermail/libraries/2010-September/014510.html |

29 | |

30 | To avoid proliferation of variants of element-wise operations, the idea |

31 | is to split these operations into two phases mediated by a new Location |

32 | type, so that users can do whatever they like between these phases. |

33 | ] { |

34 | hunk ./Data/Map.hs 65 |

35 | -- * Operators |

36 | , (!), (\\) |

37 | |

38 | + -- * Locations |

39 | + , Location |

40 | + -- ** Components |

41 | + , key |

42 | + , before |

43 | + , after |

44 | + -- ** Locations in maps |

45 | + , search |

46 | + , index |

47 | + , minLocation |

48 | + , maxLocation |

49 | + -- ** Building maps |

50 | + , assign |

51 | + , clear |

52 | + |

53 | -- * Query |

54 | , null |

55 | , size |

56 | hunk ./Data/Map.hs 305 |

57 | |

58 | #endif |

59 | |

60 | +{-------------------------------------------------------------------- |

61 | + Map locations |

62 | +--------------------------------------------------------------------} |

63 | + |

64 | +-- | A location represents a map with a \"hole\" at a particular key |

65 | +-- position. |

66 | +-- |

67 | +-- Locations are used for element-wise operations on maps (insertion, |

68 | +-- deletion and update) in a two-stage process: |

69 | +-- |

70 | +-- (1) A 'Location' (and the value at that position, if any) is obtained |

71 | +-- from a 'Map' by searching or indexing. |

72 | +-- |

73 | +-- (2) A new 'Map' is made from a 'Location' by either filling the hole |

74 | +-- with a value ('assign') or erasing it ('clear'). |

75 | + |

76 | +data Location k a |

77 | + = Empty !k !(Path k a) |

78 | + | Full {-# UNPACK #-} !Size !k !(Path k a) !(Map k a) !(Map k a) |

79 | + |

80 | +data Path k a |

81 | + = Root |

82 | + | LeftBin {-# UNPACK #-} !Size !k a !(Path k a) !(Map k a) |

83 | + | RightBin {-# UNPACK #-} !Size !k a !(Map k a) !(Path k a) |

84 | + |

85 | +-- | /O(log n)/. Search the map for the given key, returning the |

86 | +-- corresponding value (if any) and an updatable location for that key. |

87 | +-- |

88 | +-- Properties: |

89 | +-- |

90 | +-- @ |

91 | +-- case 'search' k m of |

92 | +-- (Nothing, loc) -> 'key' loc == k && 'clear' loc == m |

93 | +-- (Just v, loc) -> 'key' loc == k && 'assign' v loc == m |

94 | +-- @ |

95 | +-- |

96 | +-- @'lookup' k m == 'fst' ('search' k m)@ |

97 | + |

98 | +search :: Ord k => k -> Map k a -> (Maybe a, Location k a) |

99 | +search k = k `seq` go Root |

100 | + where |

101 | + go path Tip = (Nothing, Empty k path) |

102 | + go path (Bin sx kx x l r) = case compare k kx of |

103 | + LT -> go (LeftBin sx kx x path r) l |

104 | + GT -> go (RightBin sx kx x l path) r |

105 | + EQ -> (Just x, Full sx kx path l r) |

106 | + |

107 | +-- | /O(log n)/. Return the value and an updatable location for the |

108 | +-- /i/th key in the map. Calls 'error' if /i/ is out of range. |

109 | +-- |

110 | +-- Properties: |

111 | +-- |

112 | +-- @ |

113 | +-- 0 \<= i && i \< 'size' m ==> |

114 | +-- let (v, loc) = 'index' i m in |

115 | +-- 'size' ('before' loc) == i && 'assign' v loc == m |

116 | +-- @ |

117 | +-- |

118 | +-- @'elemAt' i m == let (v, loc) = 'index' i m in ('key' loc, v)@ |

119 | + |

120 | +index :: Int -> Map k a -> (a, Location k a) |

121 | +index = go Root |

122 | + where |

123 | + STRICT_2_OF_3(go) |

124 | + go _path _i Tip = error "Map.index: out of range" |

125 | + go path i (Bin sx kx x l r) = case compare i size_l of |

126 | + LT -> go (LeftBin sx kx x path r) i l |

127 | + GT -> go (RightBin sx kx x l path) (i-size_l-1) r |

128 | + EQ -> (x, Full sx kx path l r) |

129 | + where size_l = size l |

130 | + |

131 | +-- | /O(log n)/. Return the value and an updatable location for the |

132 | +-- least key in the map, which must be non-empty. |

133 | +-- |

134 | +-- Properties: |

135 | +-- |

136 | +-- @ |

137 | +-- 'size' m > 0 ==> |

138 | +-- let (v, loc) = 'minLocation' i m in |

139 | +-- 'size' (`before` loc) == 0 && 'assign' v loc == m |

140 | +-- @ |

141 | +-- |

142 | +-- @'findMin' m == let (v, loc) = 'minLocation' i m in ('key' loc, v)@ |

143 | + |

144 | +minLocation :: Map k a -> (a, Location k a) |

145 | +minLocation = go Root |

146 | + where |

147 | + go _path Tip = error "Map.least: empty map" |

148 | + go path (Bin sx kx x Tip r) = (x, Full sx kx path Tip r) |

149 | + go path (Bin sx kx x l r) = go (LeftBin sx kx x path r) l |

150 | + |

151 | +-- | /O(log n)/. Return the value and an updatable location for the |

152 | +-- greatest key in the map, which must be non-empty. |

153 | +-- |

154 | +-- Properties: |

155 | +-- |

156 | +-- @ |

157 | +-- 'size' m > 0 ==> |

158 | +-- let (v, loc) = 'maxLocation' i m in |

159 | +-- 'size' (`after` loc) == 0 && 'assign' v loc == m |

160 | +-- @ |

161 | +-- |

162 | +-- @'findMax' m == let (v, loc) = 'maxLocation' i m in ('key' loc, v)@ |

163 | + |

164 | +maxLocation :: Map k a -> (a, Location k a) |

165 | +maxLocation = go Root |

166 | + where |

167 | + go _path Tip = error "Map.greatest: empty map" |

168 | + go path (Bin sx kx x l Tip) = (x, Full sx kx path l Tip) |

169 | + go path (Bin sx kx x l r) = go (RightBin sx kx x l path) r |

170 | + |

171 | +-- | /O(1)/. The key marking the position of the \"hole\" in the map. |

172 | +key :: Location k a -> k |

173 | +key (Empty k _path) = k |

174 | +key (Full _sx kx _path _l _r) = kx |

175 | + |

176 | +-- | /O(log n)/. @'before' loc@ is the submap with keys less than @'key' loc@. |

177 | +before :: Ord k => Location k a -> Map k a |

178 | +before (Empty _k path) = buildBefore Tip path |

179 | +before (Full _sx _kx path l _r) = buildBefore l path |

180 | + |

181 | +buildBefore :: Ord k => Map k a -> Path k a -> Map k a |

182 | +buildBefore t Root = t |

183 | +buildBefore t (LeftBin _sx _kx _x path _r) = buildBefore t path |

184 | +buildBefore t (RightBin _sx kx x l path) = buildBefore (join kx x l t) path |

185 | + |

186 | +-- | /O(log n)/. @'after' loc@ is the submap with keys greater than @'key' loc@. |

187 | +after :: Ord k => Location k a -> Map k a |

188 | +after (Empty _k path) = buildAfter Tip path |

189 | +after (Full _sx _kx path l _r) = buildAfter l path |

190 | + |

191 | +buildAfter :: Ord k => Map k a -> Path k a -> Map k a |

192 | +buildAfter t Root = t |

193 | +buildAfter t (LeftBin _sx kx x path r) = buildAfter (join kx x t r) path |

194 | +buildAfter t (RightBin _sx _kx _x _l path) = buildAfter t path |

195 | + |

196 | +-- | /O(log n)/. Return a map obtained by placing the given value |

197 | +-- at the location (replacing an existing value, if any). |

198 | +-- |

199 | +-- @'assign' v loc == 'before' loc `union` 'singleton' ('key' loc) v `union` 'after' loc@ |

200 | + |

201 | +assign :: a -> Location k a -> Map k a |

202 | +assign x (Empty k path) = rebuildGT (singleton k x) path |

203 | +assign x (Full sx kx path l r) = rebuildEQ (Bin sx kx x l r) path |

204 | + |

205 | +-- | /O(log n)/. Return a map obtained by erasing the location. |

206 | +-- |

207 | +-- @'clear' loc == 'before' loc `union` 'after' loc@ |

208 | + |

209 | +clear :: Location k a -> Map k a |

210 | +clear (Empty _k path) = rebuildEQ Tip path |

211 | +clear (Full _sx _kx path l r) = rebuildLT (glue l r) path |

212 | + |

213 | +-- Rebuild the tree the same size as it was, so no rebalancing is needed. |

214 | +rebuildEQ :: Map k a -> Path k a -> Map k a |

215 | +rebuildEQ t Root = t |

216 | +rebuildEQ l (LeftBin sx kx x path r) = rebuildEQ (Bin sx kx x l r) path |

217 | +rebuildEQ r (RightBin sx kx x l path) = rebuildEQ (Bin sx kx x l r) path |

218 | + |

219 | +-- Rebuild the tree one entry smaller than it was, rebalancing as we go. |

220 | +rebuildLT :: Map k a -> Path k a -> Map k a |

221 | +rebuildLT t Root = t |

222 | +rebuildLT l (LeftBin _sx kx x path r) = rebuildLT (balanceR kx x l r) path |

223 | +rebuildLT r (RightBin _sx kx x l path) = rebuildLT (balanceL kx x l r) path |

224 | + |

225 | +-- Rebuild the tree one entry larger than it was, rebalancing as we go. |

226 | +rebuildGT :: Map k a -> Path k a -> Map k a |

227 | +rebuildGT t Root = t |

228 | +rebuildGT l (LeftBin _sx kx x path r) = rebuildGT (balanceL kx x l r) path |

229 | +rebuildGT r (RightBin _sx kx x l path) = rebuildGT (balanceR kx x l r) path |

230 | + |

231 | {-------------------------------------------------------------------- |

232 | Query |

233 | --------------------------------------------------------------------} |

234 | } |

235 | [Modified benchmark to use MapOps |

236 | Johan Tibell <johan.tibell@gmail.com>**20110112214511 |

237 | Ignore-this: fdce9f67a45fd07e340fee299d3d1f6d |

238 | |

239 | This allows us to test the performance of e.g. insertWith', when defined |

240 | in terms of 'search'. |

241 | ] { |

242 | hunk ./benchmarks/Map.hs 14 |

243 | import Data.Maybe (fromMaybe) |

244 | import Prelude hiding (lookup) |

245 | |

246 | +import qualified MapOps as MO |

247 | + |

248 | instance (NFData k, NFData a) => NFData (M.Map k a) where |

249 | rnf M.Tip = () |

250 | rnf (M.Bin _ k a l r) = rnf k `seq` rnf a `seq` rnf l `seq` rnf r |

251 | hunk ./benchmarks/Map.hs 82 |

252 | lookupIndex xs m = foldl' (\n k -> fromMaybe n (M.lookupIndex k m)) 0 xs |

253 | |

254 | ins :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int |

255 | -ins xs m = foldl' (\m (k, v) -> M.insert k v m) m xs |

256 | +ins xs m = foldl' (\m (k, v) -> MO.insert k v m) m xs |

257 | |

258 | insWith :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int |

259 | hunk ./benchmarks/Map.hs 85 |

260 | -insWith xs m = foldl' (\m (k, v) -> M.insertWith (+) k v m) m xs |

261 | +insWith xs m = foldl' (\m (k, v) -> MO.insertWith (+) k v m) m xs |

262 | |

263 | insWithKey :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int |

264 | hunk ./benchmarks/Map.hs 88 |

265 | -insWithKey xs m = foldl' (\m (k, v) -> M.insertWithKey add3 k v m) m xs |

266 | +insWithKey xs m = foldl' (\m (k, v) -> MO.insertWithKey add3 k v m) m xs |

267 | |

268 | insWith' :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int |

269 | hunk ./benchmarks/Map.hs 91 |

270 | -insWith' xs m = foldl' (\m (k, v) -> M.insertWith' (+) k v m) m xs |

271 | +insWith' xs m = foldl' (\m (k, v) -> MO.insertWith' (+) k v m) m xs |

272 | |

273 | insWithKey' :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int |

274 | hunk ./benchmarks/Map.hs 94 |

275 | -insWithKey' xs m = foldl' (\m (k, v) -> M.insertWithKey' add3 k v m) m xs |

276 | +insWithKey' xs m = foldl' (\m (k, v) -> MO.insertWithKey' add3 k v m) m xs |

277 | |

278 | data PairS a b = PS !a !b |

279 | |

280 | hunk ./benchmarks/Map.hs 101 |

281 | insLookupWithKey :: [(Int, Int)] -> M.Map Int Int -> (Int, M.Map Int Int) |

282 | insLookupWithKey xs m = let !(PS a b) = foldl' f (PS 0 m) xs in (a, b) |

283 | where |

284 | - f (PS n m) (k, v) = let !(n', m') = M.insertLookupWithKey add3 k v m |

285 | + f (PS n m) (k, v) = let !(n', m') = MO.insertLookupWithKey add3 k v m |

286 | in PS (fromMaybe 0 n' + n) m' |

287 | |

288 | insLookupWithKey' :: [(Int, Int)] -> M.Map Int Int -> (Int, M.Map Int Int) |

289 | hunk ./benchmarks/Map.hs 107 |

290 | insLookupWithKey' xs m = let !(PS a b) = foldl' f (PS 0 m) xs in (a, b) |

291 | where |

292 | - f (PS n m) (k, v) = let !(n', m') = M.insertLookupWithKey' add3 k v m |

293 | + f (PS n m) (k, v) = let !(n', m') = MO.insertLookupWithKey' add3 k v m |

294 | in PS (fromMaybe 0 n' + n) m' |

295 | |

296 | del :: [Int] -> M.Map Int Int -> M.Map Int Int |

297 | hunk ./benchmarks/Map.hs 111 |

298 | -del xs m = foldl' (\m k -> M.delete k m) m xs |

299 | +del xs m = foldl' (\m k -> MO.delete k m) m xs |

300 | |

301 | upd :: [Int] -> M.Map Int Int -> M.Map Int Int |

302 | hunk ./benchmarks/Map.hs 114 |

303 | -upd xs m = foldl' (\m k -> M.update Just k m) m xs |

304 | +upd xs m = foldl' (\m k -> MO.update Just k m) m xs |

305 | |

306 | upd' :: [Int] -> M.Map Int Int -> M.Map Int Int |

307 | hunk ./benchmarks/Map.hs 117 |

308 | -upd' xs m = foldl' (\m k -> snd $ M.updateLookupWithKey (\_ a -> Just a) k m) m xs |

309 | +upd' xs m = foldl' (\m k -> snd $ MO.updateLookupWithKey (\_ a -> Just a) k m) m xs |

310 | |

311 | alt :: [Int] -> M.Map Int Int -> M.Map Int Int |

312 | hunk ./benchmarks/Map.hs 120 |

313 | -alt xs m = foldl' (\m k -> M.alter id k m) m xs |

314 | +alt xs m = foldl' (\m k -> MO.alter id k m) m xs |

315 | |

316 | maybeDel :: Int -> Maybe Int |

317 | maybeDel n | n `mod` 3 == 0 = Nothing |

318 | addfile ./benchmarks/MapOps.hs |

319 | hunk ./benchmarks/MapOps.hs 1 |

320 | +-- Element-wise operations from Data.Map re-defined using Locations. |

321 | + |

322 | +module MapOps where |

323 | + |

324 | +import Data.Map (Map, empty, null, |

325 | + Location, key, before, after, assign, clear, |

326 | + search, index, minLocation, maxLocation) |

327 | + |

328 | +import Prelude hiding (null) |

329 | + |

330 | +-- ** Insertion |

331 | + |

332 | +insert :: Ord k => k -> a -> Map k a -> Map k a |

333 | +insert k v m = assign v (snd (search k m)) |

334 | + |

335 | +insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a |

336 | +insertWith f k v m = case search k m of |

337 | + (Nothing, loc) -> assign v loc |

338 | + (Just oldv, loc) -> assign (f v oldv) loc |

339 | + |

340 | +insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a |

341 | +insertWith' f k v m = case search k m of |

342 | + (Nothing, loc) -> assign v loc |

343 | + (Just oldv, loc) -> flip assign loc $! f v oldv |

344 | + |

345 | +insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a |

346 | +insertWithKey f k v m = case search k m of |

347 | + (Nothing, loc) -> assign v loc |

348 | + (Just oldv, loc) -> assign (f (key loc) v oldv) loc |

349 | + |

350 | +insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a |

351 | +insertWithKey' f k v m = case search k m of |

352 | + (Nothing, loc) -> assign v loc |

353 | + (Just oldv, loc) -> flip assign loc $! f (key loc) v oldv |

354 | + |

355 | +insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a) |

356 | +insertLookupWithKey f k v m = case search k m of |

357 | + (Nothing, loc) -> (Nothing, assign v loc) |

358 | + (Just oldv, loc) -> (Just oldv, assign (f (key loc) v oldv) loc) |

359 | + |

360 | +insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a) |

361 | +insertLookupWithKey' f k v m = case search k m of |

362 | + (Nothing, loc) -> (Nothing, assign v loc) |

363 | + (Just oldv, loc) -> v' `seq` (Just oldv, assign v' loc) |

364 | + where v' = f (key loc) v oldv |

365 | + |

366 | +-- ** Delete/Update |

367 | + |

368 | +delete :: Ord k => k -> Map k a -> Map k a |

369 | +delete k m = clear (snd (search k m)) |

370 | + |

371 | +adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a |

372 | +adjust f k m = case search k m of |

373 | + (Nothing, _) -> m |

374 | + (Just v, loc) -> assign (f v) loc |

375 | + |

376 | +adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a |

377 | +adjustWithKey f k m = case search k m of |

378 | + (Nothing, _) -> m |

379 | + (Just v, loc) -> assign (f (key loc) v) loc |

380 | + |

381 | +update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a |

382 | +update f k m = case search k m of |

383 | + (Nothing, _) -> m |

384 | + (Just v, loc) -> maybeAssign (f v) loc |

385 | + |

386 | +updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a |

387 | +updateWithKey f k m = case search k m of |

388 | + (Nothing, _) -> m |

389 | + (Just v, loc) -> maybeAssign (f (key loc) v) loc |

390 | + |

391 | +updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a) |

392 | +updateLookupWithKey f k m = case search k m of |

393 | + (Nothing, _) -> (Nothing, m) |

394 | + (Just v, loc) -> (Just v, maybeAssign (f (key loc) v) loc) |

395 | + |

396 | +alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a |

397 | +alter f k m = case search k m of |

398 | + (v, loc) -> maybeAssign (f v) loc |

399 | + |

400 | +-- * Filter |

401 | + |

402 | +split :: Ord k => k -> Map k a -> (Map k a, Map k a) |

403 | +split k m = case search k m of |

404 | + (_, loc) -> (before loc, after loc) |

405 | + |

406 | +splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a) |

407 | +splitLookup k m = case search k m of |

408 | + (res, loc) -> (before loc, res, after loc) |

409 | + |

410 | +-- * Indexed |

411 | + |

412 | +updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a |

413 | +updateAt f i m = case index i m of |

414 | + (v, loc) -> maybeAssign (f (key loc) v) loc |

415 | + |

416 | +deleteAt :: Int -> Map k a -> Map k a |

417 | +deleteAt i m = clear (snd (index i m)) |

418 | + |

419 | +-- * Min/Max |

420 | + |

421 | +deleteMin :: Map k a -> Map k a |

422 | +deleteMin m |

423 | + | null m = empty |

424 | + | otherwise = clear (snd (minLocation m)) |

425 | + |

426 | +deleteMax :: Map k a -> Map k a |

427 | +deleteMax m |

428 | + | null m = empty |

429 | + | otherwise = clear (snd (maxLocation m)) |

430 | + |

431 | +deleteFindMin :: Map k a -> ((k, a), Map k a) |

432 | +deleteFindMin m |

433 | + | null m = (error "Map.deleteFindMin: empty map", m) |

434 | + | otherwise = case minLocation m of |

435 | + (x, loc) -> ((key loc, x), clear loc) |

436 | + |

437 | +deleteFindMax :: Map k a -> ((k, a), Map k a) |

438 | +deleteFindMax m |

439 | + | null m = (error "Map.deleteFindMax: empty map", m) |

440 | + | otherwise = case maxLocation m of |

441 | + (x, loc) -> ((key loc, x), clear loc) |

442 | + |

443 | +updateMin :: (a -> Maybe a) -> Map k a -> Map k a |

444 | +updateMin f m |

445 | + | null m = m |

446 | + | otherwise = case minLocation m of |

447 | + (x, loc) -> maybeAssign (f x) loc |

448 | + |

449 | +updateMax :: (a -> Maybe a) -> Map k a -> Map k a |

450 | +updateMax f m |

451 | + | null m = m |

452 | + | otherwise = case maxLocation m of |

453 | + (x, loc) -> maybeAssign (f x) loc |

454 | + |

455 | +updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a |

456 | +updateMinWithKey f m |

457 | + | null m = m |

458 | + | otherwise = case minLocation m of |

459 | + (x, loc) -> maybeAssign (f (key loc) x) loc |

460 | + |

461 | +updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a |

462 | +updateMaxWithKey f m |

463 | + | null m = m |

464 | + | otherwise = case maxLocation m of |

465 | + (x, loc) -> maybeAssign (f (key loc) x) loc |

466 | + |

467 | +minView :: Map k a -> Maybe (a, Map k a) |

468 | +minView m |

469 | + | null m = Nothing |

470 | + | otherwise = case minLocation m of |

471 | + (x, loc) -> Just (x, clear loc) |

472 | + |

473 | +maxView :: Map k a -> Maybe (a, Map k a) |

474 | +maxView m |

475 | + | null m = Nothing |

476 | + | otherwise = case maxLocation m of |

477 | + (x, loc) -> Just (x, clear loc) |

478 | + |

479 | +minViewWithKey :: Map k a -> Maybe ((k, a), Map k a) |

480 | +minViewWithKey m |

481 | + | null m = Nothing |

482 | + | otherwise = case minLocation m of |

483 | + (x, loc) -> Just ((key loc, x), clear loc) |

484 | + |

485 | +maxViewWithKey :: Map k a -> Maybe ((k, a), Map k a) |

486 | +maxViewWithKey m |

487 | + | null m = Nothing |

488 | + | otherwise = case maxLocation m of |

489 | + (x, loc) -> Just ((key loc, x), clear loc) |

490 | + |

491 | +-- utility |

492 | + |

493 | +maybeAssign :: Maybe a -> Location k a -> Map k a |

494 | +maybeAssign = maybe clear assign |

495 | } |

496 | |

497 | Context: |

498 | |

499 | [Fixed space leak in lookupIndex |

500 | Johan Tibell <johan.tibell@gmail.com>**20110109113222 |

501 | Ignore-this: 4fcd3af4b613a1cdfd306bb9708a5eaa |

502 | ] |

503 | [Rollback "hoist constant parameter" |

504 | Johan Tibell <johan.tibell@gmail.com>**20110109112457 |

505 | Ignore-this: ecb77a93588ca5743273cf777ce73826 |

506 | |

507 | SAT-ing the key causes an extra closure to be allocated. |

508 | |

509 | rolling back: |

510 | |

511 | Fri Jan 7 16:50:12 CET 2011 Ross Paterson <ross@soi.city.ac.uk> |

512 | * hoist constant parameter |

513 | |

514 | M ./Data/Map.hs -8 +7 |

515 | ] |

516 | [hoist constant parameter |

517 | Ross Paterson <ross@soi.city.ac.uk>**20110107155012 |

518 | Ignore-this: 1061fdf82eb91cad409ccea022610856 |

519 | ] |

520 | [fix typos in comments |

521 | Ross Paterson <ross@soi.city.ac.uk>**20101215172553 |

522 | Ignore-this: f66f871ce348a41bc1598bc2b5e40943 |

523 | ] |

524 | [whitespace changes and a little re-ordering to make the export lists match |

525 | Ross Paterson <ross@soi.city.ac.uk>**20101215170649 |

526 | Ignore-this: 3bf7b6d824ea1c25ed92bbe3ca826efe |

527 | ] |

528 | [whitespace changes and a little re-ordering to make the export lists match |

529 | Ross Paterson <ross@soi.city.ac.uk>**20101215162127 |

530 | Ignore-this: 7f11aef6c6c8330bb93b6571589e18af |

531 | ] |

532 | [change Int to Key (type synonym) in 3 places for consistency |

533 | Ross Paterson <ross@soi.city.ac.uk>**20101215150459 |

534 | Ignore-this: 6da6f8629bb0718e2394a85ce0944d7f |

535 | ] |

536 | [use Applicative form in Arbitrary instances |

537 | Ross Paterson <ross@soi.city.ac.uk>**20101213040129 |

538 | Ignore-this: 335e6eac24563baef481fdc689f369dc |

539 | (these are ifdef'ed out by default) |

540 | ] |

541 | [fix comment for unfoldl |

542 | Ross Paterson <ross@soi.city.ac.uk>**20101213040022 |

543 | Ignore-this: c4bac18538933b981ed2875595f98196 |

544 | ] |

545 | [make local binding monomorphic without using scoped type variables |

546 | Ross Paterson <ross@soi.city.ac.uk>**20101213035831 |

547 | Ignore-this: 52b7f5ed7cb7c6ef0eda6caa39e4713f |

548 | ] |

549 | [Always inline foldrWithKey' and foldlWithKey' from Data.Map |

550 | Johan Tibell <johan.tibell@gmail.com>**20101201110527 |

551 | Ignore-this: a84198febd304659ff029c3424855be3 |

552 | |

553 | Inlining makes it possible to replace an indirect call to an unknown |

554 | function with a call to a known function at the call site. |

555 | ] |

556 | [Tweak insertWith' and insertWithKey' to better match the non-' versions |

557 | Ian Lynagh <igloo@earth.li>**20101128175028 |

558 | Ignore-this: 41b50b13b1a94ae56bad8d381c696d04 |

559 | They now are not marked inlinable, force the key, and are exported. |

560 | ] |

561 | [Explain INLINEs in IntMap and IntSet. |

562 | Milan Straka <fox@ucw.cz>**20101104224507 |

563 | Ignore-this: 322a22056e9aa5d4e5a9f2caa6542017 |

564 | ] |

565 | [Fix warnings. |

566 | Milan Straka <fox@ucw.cz>**20101104223950 |

567 | Ignore-this: 19460b7cab4554fef3b637ebb36addd1 |

568 | |

569 | Just trivial renames of shadows variables. |

570 | ] |

571 | [Explain the nomatch clause in IntSet.hs |

572 | Milan Straka <fox@ucw.cz>**20101104221451 |

573 | Ignore-this: 2f90d0037027e77cffff30cf21729845 |

574 | ] |

575 | [Rename STRICTxy to STRICT_x_OF_y. |

576 | Milan Straka <fox@ucw.cz>**20101104220917 |

577 | Ignore-this: fb12cee5518d1a8844ee44273330fa57 |

578 | |

579 | Also explain why bang patterns are not used. |

580 | ] |

581 | [Settle performance issues in Map and Set. |

582 | Milan Straka <fox@ucw.cz>**20101031082146 |

583 | Ignore-this: 9a4c70d5f9a5884c7ff8f714ae4ff1e4 |

584 | |

585 | Explain the INLINE/INLINABLE in the Map and Set sources. |

586 | |

587 | Use 'go' only for functions that can be INLINE. |

588 | ] |

589 | [Settle performance issues in IntMap and IntSet. |

590 | Milan Straka <fox@ucw.cz>**20101029231653 |

591 | Ignore-this: c1234a5113da14178a2394976e91b786 |

592 | |

593 | The worker-wrapper transformation is removed from |

594 | all functions but lookup and member. This is the |

595 | only place where it causes benefits -- a 10% to |

596 | 15% speedup. It increases memory allocation |

597 | slightly (0-5%), but the effect on GHC is really |

598 | minor. |

599 | |

600 | Also INLINE/INLINABLE hints are not really needed, |

601 | GHC figures it all by itself. The explicit INLINE |

602 | were left on internal functions that are crutial |

603 | to INLINE because of performance. |

604 | ] |

605 | [Make foldlStrict semantics to match foldl'. |

606 | Milan Straka <fox@ucw.cz>**20101022100939 |

607 | Ignore-this: 3790a5a47e4ff7b55c005a8c95e5890f |

608 | ] |

609 | [Remove INLINABLE in IntMap and IntSet.hs. |

610 | Milan Straka <fox@ucw.cz>**20101022091744 |

611 | Ignore-this: 4f532887bf54444989cc66d6546f1c89 |

612 | |

613 | It makes no sense, as the calls are already specialized |

614 | for Int keys. Benchmarks actually show small slowdown. |

615 | ] |

616 | [Do not pass f explicitely for fold. |

617 | Milan Straka <fox@ucw.cz>**20101019202043 |

618 | Ignore-this: bb0a5e758ebfebbdf8160be4317898e9 |

619 | |

620 | Benchmarks shows this is a huge win (100% for (:) being |

621 | the function, 1000% for (+) being the function). |

622 | ] |

623 | [Mark fold explicitely as INLINE. |

624 | Milan Straka <fox@ucw.cz>**20101016222150 |

625 | Ignore-this: b72855a0af39e57b1862908717fc14fc |

626 | |

627 | The INLINABLE does not work well in this case. Benchmarks |

628 | show memory savings (due to unboxing) and nearly no GHC binary |

629 | size increase. |

630 | ] |

631 | [Changing INLINE pragmas. |

632 | Milan Straka <fox@ucw.cz>**20101016215959 |

633 | Ignore-this: 933327354749d18e4617280fde55cce0 |

634 | |

635 | The internal functions that need to be inlined are marked INLINE |

636 | (bit fiddling in IntMap/IntSet, empty, singleton, bin). |

637 | |

638 | Aslo if INLINABLE is available, use it for all exported functions. |

639 | The functions like insert that were INLINE because of specialization |

640 | issues are now INLINE only in the case of INLINABLE absence. |

641 | ] |

642 | [Whitespace changes only. |

643 | Milan Straka <fox@ucw.cz>**20101016202831 |

644 | Ignore-this: 8850e09fb49937b54da6585d01aade9a |

645 | ] |

646 | [Correct a typo in macro name. |

647 | Milan Straka <fox@ucw.cz>**20101016202641 |

648 | Ignore-this: 356621b0ca954f73d543fc33d43383b2 |

649 | ] |

650 | [Change the worker/wrapper to explicitly pass arguments. |

651 | Milan Straka <fox@ucw.cz>**20101016195757 |

652 | Ignore-this: 7f4a2180a263ee15cbb73c60b2d8cc46 |

653 | |

654 | As the benchmarking showed, it is not a good idea to create |

655 | closures in the worker/wrapper transformation, as the captured |

656 | arguments of the enclosing function have to be allocated on the |

657 | heap. It is better to explicitly pass the arguments on the stack. |

658 | This saves memory and add no time penalty if the arguments are |

659 | the first arguments of recursive function (GHC refrains from |

660 | needless copying). |

661 | |

662 | The worker is often strict in some arguments. I did not want |

663 | to use BangPatterns, so I used macros to indicate strictness. |

664 | If majority thinks BangPatters are fine, I will gladly change it. |

665 | ] |

666 | [Add foldlWithKey' and foldrWithKey' to Data.Map |

667 | Johan Tibell <johan.tibell@gmail.com>**20101103132836 |

668 | Ignore-this: d2ac0f0a50842ec5a007b9ad11ce63d0 |

669 | ] |

670 | [Add strict versions of insertWith and insertWithKey to IntMap |

671 | Johan Tibell <johan.tibell@gmail.com>**20101030135122 |

672 | Ignore-this: 5472c9be565e75672140d243ef0211f2 |

673 | ] |

674 | [Fix warnings in Data.Map and Data.Set. |

675 | Milan Straka <fox@ucw.cz>**20100924154946 |

676 | Ignore-this: cb2c0a8ecf0a57acc5941ba841aa7c40 |

677 | |

678 | Only trivial changes. |

679 | ] |

680 | [Finish the started worker/wrapper transformation. |

681 | Milan Straka <fox@ucw.cz>**20100924153353 |

682 | Ignore-this: baeb24573242beb56c3bbe7ca67f5ff7 |

683 | |

684 | Some methods (insert, lookup) were not modified as the rest |

685 | (like insertWith, delete, ...). Also the `seq` were missing |

686 | sometimes. |

687 | ] |

688 | [Merge all the OPTIONS and LANGUAGE module pragmas. |

689 | Milan Straka <fox@ucw.cz>**20100924152642 |

690 | Ignore-this: 86067abf13f0501f29c13ec7c877533c |

691 | ] |

692 | [Remove most INLINE from Map, Set, IntMap and IntSet. |

693 | Milan Straka <fox@ucw.cz>**20100924152008 |

694 | Ignore-this: c88c4ede21c06bfda20af131c232a720 |

695 | |

696 | Because of a code bloat the INLINEs cause, remove most of |

697 | them. The only INLINEs left are the following: |

698 | - only in Set and Map, because in IntMap and IntSet the specialization |

699 | does not help |

700 | - only on functions which need Ord |

701 | - only on 'small' functions, namely member, notMember, lookup*, |

702 | insert*, delete*, adjust*, alter*, update* |

703 | |

704 | All other functions of Map, Set, IntMap and IntSet are marked INLINABLE, |

705 | even if they are recursive. |

706 | |

707 | The INLINEs left are only a short-term solution. In the long run the |

708 | auto-specialization of INLINABLE methods seems a good way (maybe |

709 | SPECIALIZABLE). |

710 | ] |

711 | [Comment tests and benchmarks on foldlWithKey' which |

712 | Milan Straka <fox@ucw.cz>**20100924110705 |

713 | Ignore-this: 71b988389e6ae9a78ea3b0e20156ca2f |

714 | was commented recently by Ian Lynagh. |

715 | ] |

716 | [Worker/wrapper transformation for Data.IntSet. |

717 | Milan Straka <fox@ucw.cz>**20100923125604 |

718 | Ignore-this: b0228582818f7bfb690d0853022a7809 |

719 | ] |

720 | [Compile only the benchmark source, not the Data/*.hs. |

721 | Milan Straka <fox@ucw.cz>**20100921115821 |

722 | Ignore-this: f94d9e3ffe126cd057d23490c973a4e9 |

723 | ] |

724 | [Add criterion-based benchmark for IntSet.hs. |

725 | Milan Straka <fox@ucw.cz>**20100921103225 |

726 | Ignore-this: 3d31a820830c7382748626bc9a1ba54 |

727 | |

728 | The benchmark is nearly identical copy of Set.hs benchmark. |

729 | ] |

730 | [Add a testsuite for Data.IntSet. |

731 | Milan Straka <fox@ucw.cz>**20100921102802 |

732 | Ignore-this: e55484ee185e71915452bdf2a7b2a2b3 |

733 | ] |

734 | [Further improve Data.Set balance function. |

735 | Milan Straka <fox@ucw.cz>**20100921091828 |

736 | Ignore-this: f23be37859224e9bbe919a3c0a71fdc6 |

737 | |

738 | As suggested by Kazu Yamamoto, we split balance to balanceL and |

739 | balanceR, which handle only one-sided inbalance, but need fewer |

740 | tests than balance. |

741 | |

742 | As nearly all functions modifying the structure use balance, this |

743 | results in speedup of many functions. On my 32-bit GHC 6.12.1, |

744 | 11% speedup for insert, 12% speedup for delete. |

745 | ] |

746 | [Further improve Data.Map balance function. |

747 | Milan Straka <fox@ucw.cz>**20100921091547 |

748 | Ignore-this: 8abfd027142a5183b2b5282e96ccb414 |

749 | |

750 | As suggested by Kazu Yamamoto, we split balance to balanceL and |

751 | balanceR, which handle only one-sided inbalance, but need fewer |

752 | tests than balance. |

753 | |

754 | As nearly all functions modifying the structure use balance, this |

755 | results in speedup of many functions. On my 32-bit GHC 6.12.1, |

756 | 20% speedup for insert, 7% speedup for delete, 5% speedup for update. |

757 | ] |

758 | [Changing delta to 3 in Data.Set. |

759 | Milan Straka <fox@ucw.cz>**20100921090507 |

760 | Ignore-this: a47d0c542ed9cee99ad6b17c52c977a1 |

761 | |

762 | Only possible values are 3 and 4. The value 3 has much faster inserts, |

763 | value 4 slightly faster deletes, so choosing 3. |

764 | |

765 | Also changed the inequalities to rebalance only when one subtree |

766 | is _strictly_ larger than delta * the other one, to mimic the behaviour |

767 | from the proof (both from the Adams' and from the one to come). |

768 | ] |

769 | [Changing delta to 3 in Data.Map. |

770 | Milan Straka <fox@ucw.cz>**20100921090358 |

771 | Ignore-this: 85f733f836b65b2b1038383ddb92e8e1 |

772 | |

773 | Only possible values are 3 and 4. The value 3 has much faster inserts, |

774 | value 4 slightly faster deletes, so choosing 3. |

775 | |

776 | Also changed the inequalities to rebalance only when one subtree |

777 | is _strictly_ larger than delta * the other one, to mimic the behaviour |

778 | from the proof (both from the Adams' and from the one to come). |

779 | ] |

780 | [Correct Data.Set Arbitrary instance never to return unbalanced trees. |

781 | Milan Straka <fox@ucw.cz>**20100914150442 |

782 | Ignore-this: b5c70fa98a56f225b8eb5faf420677b0 |

783 | |

784 | The previous instance sometimes returned unbalanced trees, |

785 | which broke the tests. |

786 | |

787 | Also the new instance mimics Data.Map instance more closely in the shape |

788 | of the generated trees. |

789 | ] |

790 | [Correct Data.Map Arbitrary instance never to return unbalanced trees. |

791 | Milan Straka <fox@ucw.cz>**20100914145841 |

792 | Ignore-this: 114bbcc63acdb16b77140ea56aeb0a95 |

793 | |

794 | The previous instance sometimes returned unbalanced trees, |

795 | which broke the tests. |

796 | ] |

797 | [Improve Data.Set benchmark. |

798 | Milan Straka <fox@ucw.cz>**20100914142010 |

799 | Ignore-this: 9b878ae3aa5a43ef083abfd7f9b22513 |

800 | |

801 | Add union, difference and intersection to Data.Set benchmark. |

802 | ] |

803 | [Improve benchmark infrastructure and Data.Map benchmark. |

804 | Milan Straka <fox@ucw.cz>**20100914141707 |

805 | Ignore-this: 67e8dafcb4abcb9c726b9b29c7c320fd |

806 | |

807 | Renamed Benchmarks.hs to Map.hs, as it only benchmarks Data.Map. |

808 | Improve the Makefile to work with multiple benchmarks. |

809 | Add union, difference and intersection to Data.Map benchmark. |

810 | ] |

811 | [Improve the performance of Data.Set balance function. |

812 | Milan Straka <fox@ucw.cz>**20100914140417 |

813 | Ignore-this: 577c511c219695b8d483af546c7387e8 |

814 | |

815 | The balance function is now one monolithic function, which allows |

816 | to perform all pattern-matches only once. |

817 | |

818 | Nearly all functions modifying Data.Map use balance. |

819 | The improvements are 12% for insert, 14% for delete (GHC 6.12.1). |

820 | ] |

821 | [Improve the performance of Data.Map balance function. |

822 | Milan Straka <fox@ucw.cz>**20100914140217 |

823 | Ignore-this: 951181e035fcac90674dff3300350a1 |

824 | |

825 | The balance function is now one monolithic function, which allows |

826 | to perform all pattern-matches only once. |

827 | |

828 | Nearly all functions modifying Data.Map use balance. |

829 | The improvements are 7-11% for various insert*, delete*, alter, |

830 | update or intersection functions (GHC 6.12.1). |

831 | ] |

832 | [Improve performance of Data.Set union and difference operations. |

833 | Milan Straka <fox@ucw.cz>**20100914135725 |

834 | Ignore-this: 6dc4a186ea060b9cdb9e783db71ca280 |

835 | |

836 | Use datatype storing evaluated bound instead of high-order functions. |

837 | The improvements are over 25% for both union and difference (GHC 6.12.1). |

838 | ] |

839 | [Improve performance of Data.Map union* and difference* operations. |

840 | Milan Straka <fox@ucw.cz>**20100914134614 |

841 | Ignore-this: 35b23a40ef33e9fa14eb81fdee4b152d |

842 | |

843 | Use datatype storing evaluated bound instead of high-order functions. |

844 | The improvements are 22% for union and 20% for difference (GHC 6.12.1). |

845 | ] |

846 | [Make the Set store the elements evaluated (bang added). |

847 | Milan Straka <fox@ucw.cz>**20100913165132 |

848 | Ignore-this: b3f230db5bf30d93d3fddf2c81c5f3b4 |

849 | ] |

850 | [Improved performance of Data.Set |

851 | Johan Tibell <johan.tibell@gmail.com>**20100831124352 |

852 | Ignore-this: 38a304a0408d29a2956aa9a1fc0ce755 |

853 | |

854 | Performance improvements are due to manually applying the |

855 | worker/wrapper transformation and strictifying the keys. |

856 | |

857 | Average speed-up is 32% on a 2GHz Core 2 Duo on OS X 10.5.8 |

858 | ] |

859 | [Added benchmarks for Data.Set |

860 | Johan Tibell <johan.tibell@gmail.com>**20100831124225 |

861 | Ignore-this: fcacf88761034b8c534d936f0b336cc0 |

862 | ] |

863 | [Added a test suite for Data.Set |

864 | Johan Tibell <johan.tibell@gmail.com>**20100831124030 |

865 | Ignore-this: f430dc302c0fcb8b5d62db2272a1d6f7 |

866 | |

867 | Expression coverage: 74% |

868 | ] |

869 | [Remove use of lambdas with irrefutable patterns |

870 | simonpj@microsoft.com**20100923120838 |

871 | Ignore-this: c36e90a0258c0d5262684c585c321419 |

872 | ] |

873 | [Revert the recent contentious changes |

874 | Ian Lynagh <igloo@earth.li>**20100915135103 |

875 | Ignore-this: fe4f71ff1ade51c11421dc9974aa0fda |

876 | These will probably be tidied up and reinstated later, but this gets |

877 | the package back to a releasable state. |

878 | ] |

879 | [fix warnings |

880 | Simon Marlow <marlowsd@gmail.com>**20100831114555 |

881 | Ignore-this: 53df71bc054a779b8ad2dad89c09e02d |

882 | ] |

883 | [Missing MagicHash for IntSet |

884 | Don Stewart <dons@galois.com>**20100831093446 |

885 | Ignore-this: d075f760adb9a2aa0ee04676e38a07cc |

886 | ] |

887 | [Performance improvements for Data.IntMap (worker/wrapper and inlining) |

888 | Don Stewart <dons@galois.com>**20100831093316 |

889 | Ignore-this: 206036448558d270f0eb85ef4cd55368 |

890 | ] |

891 | [Add criterion-based benchmarking for IntMap |

892 | Don Stewart <dons@galois.com>**20100831093240 |

893 | Ignore-this: d7d85b9afb513532cc30f5b51a3f825e |

894 | ] |

895 | [Add comprehensive testsuite for IntMap |

896 | Don Stewart <dons@galois.com>**20100831093202 |

897 | Ignore-this: d455fedbc615e5b63ac488e605550557 |

898 | ] |

899 | [-O2 -fregs-graph is a uniform 10% improvements for IntMap |

900 | Don Stewart <dons@galois.com>**20100831092956 |

901 | Ignore-this: 2372cf4be945fe7939d0af94e32c567f |

902 | ] |

903 | [Missed base case for updateAt worker. Spotted by Jan-Willem Maessen |

904 | Don Stewart <dons@galois.com>**20100829163329 |

905 | Ignore-this: b8daf1c55c163c16f50c3b54cca2dba1 |

906 | ] |

907 | [Major bump (new functions, clarified strictness properties, vastly better performance) |

908 | Don Stewart <dons@galois.com>**20100829122628 |

909 | Ignore-this: 9bfbc58ecaa24a86be37b8c4cb043457 |

910 | ] |

911 | [Add two new functions: foldlWithKey' and insertLookupWithKey' |

912 | Don Stewart <dons@galois.com>**20100829122147 |

913 | Ignore-this: a2f112653ba38737fe1b38609e06c314 |

914 | |

915 | These two functions use strict accumulators, compared to their existing |

916 | counterparts (which are lazy left folds, that appear not to be useful). |

917 | Performance is significantly better. |

918 | |

919 | ] |

920 | [Performance improvements to Data.Map |

921 | Don Stewart <dons@galois.com>**20100829120245 |

922 | Ignore-this: b4830cddfa6d62e4883f4e0f58ac4e57 |

923 | |

924 | Applied several standard transformations to improve the performance of |

925 | code: |

926 | |

927 | * Worker/wrapper of all recursive functions with constant arguments |

928 | * Inlining of all (non-recursive) wrappers |

929 | * Consistent use of strict keys |

930 | |

931 | Average performance improvements across common API (with GHC 6.12.3): |

932 | |

933 | * Linux / x86_64 / 2.6Ghz i7 : 48% |

934 | * Mac OSX 10.5 / x86 / 2 Ghz Xeon : 36% |

935 | |

936 | Graphs and raw data: http://is.gd/eJHIE |

937 | |

938 | This patch is (mostly) orthogonal to the algorithmic changes suggested |

939 | by Milan Straka in his HW 2010 paper: |

940 | |

941 | http://research.microsoft.com/~simonpj/papers/containers/containers.pdf |

942 | |

943 | Those changes could be added separately, for some additional improvments. |

944 | |

945 | Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan Tibell |

946 | and Don Stewart. |

947 | |

948 | ] |

949 | [Add a criterion-based benchmark suite for Data.Map |

950 | Don Stewart <dons@galois.com>**20100829114611 |

951 | Ignore-this: ec61668f5bcb78bd15b72e2728c01c19 |

952 | |

953 | This adds a criterion-based micro-benchmarking suite for Data.Map. It |

954 | can be used to measure performance improvements for individual top-level |

955 | functions. |

956 | |

957 | Examples here: http://is.gd/eJHIE |

958 | |

959 | ] |

960 | [Add a comprehensive testsuite for Data.Map |

961 | Don Stewart <dons@galois.com>**20100829113545 |

962 | Ignore-this: 891e7fe6bac3523868714ac1ff51c0a3 |

963 | |

964 | This patch adds a joint quickcheck2 / hunit testsuite, with coverage of |

965 | 91% of top level functions (remaining features are mostly in instances). |

966 | |

967 | The coverage data is here: |

968 | |

969 | http://code.haskell.org/~dons/tests/containers/hpc_index.html |

970 | |

971 | No bugs were found. It includes unit tests for known past bugs |

972 | (balancing). |

973 | |

974 | ] |

975 | [Oops, get the #ifdef symbol correct. |

976 | Malcolm.Wallace@me.com**20100902081938] |

977 | [Protect a gratuitous GHC-ism with #ifdefs. |

978 | Malcolm.Wallace@me.com**20100902081217] |

979 | [Set Data.Map's delta to 4; fixes #4242 |

980 | Ian Lynagh <igloo@earth.li>**20100815131954] |

981 | [Add a test for #4242 |

982 | Ian Lynagh <igloo@earth.li>**20100815131856] |

983 | [Add a local type signature |

984 | simonpj@microsoft.com**20100730124447 |

985 | Ignore-this: b581d3f2c80a7a860456d589960f12f2 |

986 | ] |

987 | [Add type signature in local where clause |

988 | simonpj@microsoft.com**20100727151709 |

989 | Ignore-this: 5929c4156500b25b280eb414b508c508 |

990 | ] |

991 | [Fix Data.Sequence's breakr, and add a test for it; fixes trac #4157 |

992 | Ian Lynagh <igloo@earth.li>**20100704140627] |

993 | [Fix proposal #4109: Make Data.Map.insertWith's strictness consistent |

994 | Ian Lynagh <igloo@earth.li>**20100615133055] |

995 | [Tweak layout to work with the alternative layout rule |

996 | Ian Lynagh <igloo@earth.li>**20091129154519] |

997 | [Disable building Data.Sequence (and dependents) for nhc98. |

998 | Malcolm.Wallace@cs.york.ac.uk**20091124025653 |

999 | There is some subtlety of polymorphically recursive datatypes and |

1000 | type-class defaulting that nhc98's type system barfs over. |

1001 | ] |

1002 | [Fix another instance of non-ghc breakage. |

1003 | Malcolm.Wallace@cs.york.ac.uk**20091123092637] |

1004 | [Add #ifdef around ghc-only (<$) as member of Functor class. |

1005 | Malcolm.Wallace@cs.york.ac.uk**20091123085155] |

1006 | [Fix broken code in non-GHC branch of an ifdef. |

1007 | Malcolm.Wallace@cs.york.ac.uk**20091123084824] |

1008 | [doc bugfix: correct description of index argument |

1009 | Ross Paterson <ross@soi.city.ac.uk>**20091028105532 |

1010 | Ignore-this: 9790e7bf422c4cb528722c03cfa4fed9 |

1011 | |

1012 | As noted by iaefai on the libraries list. |

1013 | |

1014 | Please merge to STABLE. |

1015 | ] |

1016 | [Bump version to 0.3.0.0 |

1017 | Ian Lynagh <igloo@earth.li>**20090920141847] |

1018 | [update base dependency |

1019 | Ross Paterson <ross@soi.city.ac.uk>**20090916073125 |

1020 | Ignore-this: ad382ffc6c6a18c15364e6c072f19edb |

1021 | |

1022 | The package uses mkNoRepType and Data.Functor, which were not in the |

1023 | stable branch of base-4. |

1024 | ] |

1025 | [add fast version of <$ for Seq |

1026 | Ross Paterson <ross@soi.city.ac.uk>**20090916072812 |

1027 | Ignore-this: 5a39a7d31d39760ed589790b1118d240 |

1028 | ] |

1029 | [new methods for Data.Sequence (proposal #3271) |

1030 | Ross Paterson <ross@soi.city.ac.uk>**20090915173324 |

1031 | Ignore-this: cf17bedd709a6ab3448fd718dcdf62e7 |

1032 | |

1033 | Adds a lot of new methods to Data.Sequence, mostly paralleling those |

1034 | in Data.List. Several of these are significantly faster than versions |

1035 | implemented with the previous public interface. In particular, replicate |

1036 | takes O(log n) time and space instead of O(n). |

1037 | (by Louis Wasserman) |

1038 | ] |

1039 | [Fix "Cabal check" warnings |

1040 | Ian Lynagh <igloo@earth.li>**20090811215900] |

1041 | [TAG 2009-06-25 |

1042 | Ian Lynagh <igloo@earth.li>**20090625160202] |

1043 | Patch bundle hash: |

1044 | ffad03dd8b00f2031ce09dcbb2dfd71d97cad94f |