# Ticket #996: test.txt

File test.txt, 78.4 KB (added by pauljohnson, 9 years ago) |
---|

Line | |
---|---|

1 | |

2 | New patches: |

3 | |

4 | [Ranged sets added |

5 | Paul Johnson <paul@cogito.org.uk>**20061107192229] { |

6 | adddir ./Data/Ranged |

7 | addfile ./Data/Ranged.hs |

8 | hunk ./Data/Ranged.hs 1 |

9 | +----------------------------------------------------------------------------- |

10 | +-- | |

11 | +-- Module : Data.Ranged |

12 | +-- Copyright : (c) Paul Johnson 2006 |

13 | +-- License : BSD-style |

14 | +-- Maintainer : paul@cogito.org.uk |

15 | +-- Stability : experimental |

16 | +-- Portability : portable |

17 | +-- |

18 | +-- Ranged sets represent a set of ordered values as a list of ranges. Each |

19 | +-- range has an upper and lower boundary, and each boundary divides values |

20 | +-- into those above and below: no value can ever sit on a boundary. |

21 | + |

22 | + |

23 | +-- | Re-exports 'Data.Ranged.Boundaries', 'Data.Ranged.Ranges' and |

24 | +-- 'Data.Ranged.RangedSet' for convenience. |

25 | + |

26 | +module Data.Ranged ( |

27 | + module Data.Ranged.Boundaries, |

28 | + module Data.Ranged.Ranges, |

29 | + module Data.Ranged.RangedSet |

30 | +) where |

31 | + |

32 | +import Data.Ranged.Boundaries |

33 | +import Data.Ranged.Ranges |

34 | +import Data.Ranged.RangedSet |

35 | addfile ./Data/Ranged/Boundaries.hs |

36 | hunk ./Data/Ranged/Boundaries.hs 1 |

37 | +{-# OPTIONS_GHC -fglasgow-exts #-} |

38 | +module Data.Ranged.Boundaries ( |

39 | + DiscreteOrdered, |

40 | + adjacent, |

41 | + enumAdjacent, |

42 | + boundedAdjacent, |

43 | + Boundary (..), |

44 | + above, |

45 | + (/>/) |

46 | +) where |

47 | + |

48 | +import Test.QuickCheck |

49 | + |

50 | +infix 4 />/ |

51 | + |

52 | +{- | |

53 | +Distinguish between dense and sparse ordered types. A dense type is |

54 | +one in which any two values @v1 < v2@ have a third value @v3@ such that |

55 | +@v1 < v3 < v2@. |

56 | + |

57 | +In theory the floating types are dense, although in practice they can only have |

58 | +finitely many values. This class treats them as dense. |

59 | + |

60 | +Tuples up to 4 members are declared as instances. Larger tuples may be added |

61 | +if necessary. |

62 | + |

63 | +This approach was suggested by Ben Rudiak-Gould on comp.lang.functional. |

64 | +-} |

65 | +class Ord a => DiscreteOrdered a where |

66 | + -- | Two values @x@ and @y@ are adjacent if @x < y@ and there does not |

67 | + -- exist a third value between them. Always @False@ for dense types. |

68 | + adjacent :: a -> a -> Bool |

69 | + |

70 | +instance DiscreteOrdered Bool where adjacent = boundedAdjacent |

71 | +instance DiscreteOrdered Ordering where adjacent = boundedAdjacent |

72 | +instance DiscreteOrdered Char where adjacent = boundedAdjacent |

73 | +instance DiscreteOrdered Int where adjacent = boundedAdjacent |

74 | +instance DiscreteOrdered Integer where adjacent = enumAdjacent |

75 | +instance DiscreteOrdered Rational where adjacent _ _ = False |

76 | +instance DiscreteOrdered Float where adjacent _ _ = False |

77 | +instance DiscreteOrdered Double where adjacent _ _ = False |

78 | +instance Ord a => DiscreteOrdered [a] where adjacent _ _ = False |

79 | +instance (Ord a, DiscreteOrdered b) => DiscreteOrdered (a, b) |

80 | + where adjacent (x1, x2) (y1, y2) = (x1 == y1) && adjacent x2 y2 |

81 | +instance (Ord a, Ord b, DiscreteOrdered c) => DiscreteOrdered (a, b, c) |

82 | + where |

83 | + adjacent (x1, x2, x3) (y1, y2, y3) = |

84 | + (x1 == y1) && (x2 == y2) && adjacent x3 y3 |

85 | +instance (Ord a, Ord b, Ord c, DiscreteOrdered d) => |

86 | + DiscreteOrdered (a, b, c, d) |

87 | + where |

88 | + adjacent (x1, x2, x3, x4) (y1, y2, y3, y4) = |

89 | + (x1 == y1) && (x2 == y2) && (x3 == y3) && adjacent x4 y4 |

90 | + |

91 | +-- | Check adjacency for sparse enumerated types (i.e. where there |

92 | +-- is no value between @x@ and @succ x@). Use as the definition of |

93 | +-- "adjacent" for most enumerated types. |

94 | +enumAdjacent :: (Ord a, Enum a) => a -> a -> Bool |

95 | +enumAdjacent x y = (succ x == y) |

96 | + |

97 | +-- | Check adjacency, allowing for case where x = maxBound. Use as the |

98 | +-- definition of "adjacent" for bounded enumerated types such as Int and Char. |

99 | +boundedAdjacent :: (Ord a, Enum a) => a -> a -> Bool |

100 | +boundedAdjacent x y = if x < y then succ x == y else False |

101 | + |

102 | + |

103 | +{- | |

104 | +A Boundary is a division of an ordered type into values above |

105 | +and below the boundary. No value can sit on a boundary. |

106 | + |

107 | +Known bug: for Bounded types |

108 | + |

109 | +* @BoundaryAbove maxBound < BoundaryAboveAll@ |

110 | + |

111 | +* @BoundaryBelow minBound > BoundaryBelowAll@ |

112 | + |

113 | +This is incorrect because there are no possible values in between the left |

114 | +and right sides of these inequalities. |

115 | +-} |

116 | + |

117 | +data Boundary a = |

118 | + -- | The argument is the highest value below the boundary. |

119 | + BoundaryAbove a | |

120 | + -- | The argument is the lowest value above the boundary. |

121 | + BoundaryBelow a | |

122 | + -- | The boundary above all values. |

123 | + BoundaryAboveAll | |

124 | + -- | The boundary below all values. |

125 | + BoundaryBelowAll |

126 | + deriving (Eq, Show) |

127 | + |

128 | +-- | True if the value is above the boundary, false otherwise. |

129 | +above :: Ord v => Boundary v -> v -> Bool |

130 | +above (BoundaryAbove b) v = v > b |

131 | +above (BoundaryBelow b) v = v >= b |

132 | +above BoundaryAboveAll _ = False |

133 | +above BoundaryBelowAll _ = True |

134 | + |

135 | +-- | Same as 'above', but with the arguments reversed for more intuitive infix |

136 | +-- usage. |

137 | +(/>/) :: Ord v => v -> Boundary v -> Bool |

138 | +(/>/) = flip above |

139 | + |

140 | +instance (DiscreteOrdered a) => Ord (Boundary a) where |

141 | + -- Comparison alogrithm based on brute force and ignorance: |

142 | + -- enumerate all combinations. |

143 | + |

144 | + compare boundary1 boundary2 = |

145 | + case boundary1 of |

146 | + BoundaryAbove b1 -> |

147 | + case boundary2 of |

148 | + BoundaryAbove b2 -> compare b1 b2 |

149 | + BoundaryBelow b2 -> |

150 | + if b1 < b2 |

151 | + then |

152 | + if adjacent b1 b2 then EQ else LT |

153 | + else GT |

154 | + BoundaryAboveAll -> LT |

155 | + BoundaryBelowAll -> GT |

156 | + BoundaryBelow b1 -> |

157 | + case boundary2 of |

158 | + BoundaryAbove b2 -> |

159 | + if b1 > b2 |

160 | + then |

161 | + if adjacent b2 b1 then EQ else GT |

162 | + else LT |

163 | + BoundaryBelow b2 -> compare b1 b2 |

164 | + BoundaryAboveAll -> LT |

165 | + BoundaryBelowAll -> GT |

166 | + BoundaryAboveAll -> |

167 | + case boundary2 of |

168 | + BoundaryAboveAll -> EQ |

169 | + otherwise -> GT |

170 | + BoundaryBelowAll -> |

171 | + case boundary2 of |

172 | + BoundaryBelowAll -> EQ |

173 | + otherwise -> LT |

174 | + |

175 | + |

176 | +-- QuickCheck Generator |

177 | + |

178 | +instance Arbitrary a => Arbitrary (Boundary a) where |

179 | + arbitrary = frequency [ |

180 | + (1, return BoundaryAboveAll), |

181 | + (1, return BoundaryBelowAll), |

182 | + (18, do |

183 | + v <- arbitrary |

184 | + oneof [return $ BoundaryAbove v, return $ BoundaryBelow v] |

185 | + )] |

186 | + coarbitrary BoundaryBelowAll = variant 0 |

187 | + coarbitrary BoundaryAboveAll = variant 1 |

188 | + coarbitrary (BoundaryBelow v) = variant 2 . coarbitrary v |

189 | + coarbitrary (BoundaryAbove v) = variant 3 . coarbitrary v |

190 | + |

191 | addfile ./Data/Ranged/RangedSet.hs |

192 | hunk ./Data/Ranged/RangedSet.hs 1 |

193 | - |

194 | +{-# OPTIONS_GHC -fglasgow-exts #-} |

195 | + |

196 | +module Data.Ranged.RangedSet ( |

197 | + -- ** Ranged Set Type |

198 | + RSet, |

199 | + rSetRanges, |

200 | + rSetRanges1, |

201 | + -- ** Ranged Set construction functions and their Preconditions |

202 | + rangedSet, |

203 | + unsafeRangedSet, |

204 | + validRangeList, |

205 | + normaliseRangeList, |

206 | + -- ** Predicates |

207 | + rSetIsEmpty, |

208 | + (-?-), rSetHas, |

209 | + (-<=-), rSetSubset, |

210 | + (-<-), rSetSubsetStrict, |

211 | + -- ** Set Operations |

212 | + (-\/-), rSetUnion, |

213 | + (-/\-), rSetIntersection, |

214 | + (-!-), rSetDifference, |

215 | + rSetNegation, |

216 | + -- ** Useful Sets |

217 | + rSetEmpty, |

218 | + rSetFull, |

219 | + rSetUnfold |

220 | + |

221 | + -- ** QuickCheck Properties |

222 | + |

223 | + -- *** Construction |

224 | + -- $ConstructionProperties |

225 | + |

226 | + -- *** Basic Operations |

227 | + -- $BasicOperationProperties |

228 | + |

229 | + -- *** Some Identities and Inequalities |

230 | + -- $SomeIdentitiesAndInequalities |

231 | +) where |

232 | + |

233 | +import Data.Ranged.Boundaries |

234 | +import Data.Ranged.Ranges |

235 | + |

236 | +import Data.List |

237 | +import Test.QuickCheck |

238 | + |

239 | +infixl 7 -/\- |

240 | +infixl 6 -\/-, -!- |

241 | +infixl 5 -<=-, -<-, -?- |

242 | + |

243 | +-- | An RSet (for Ranged Set) is a list of ranges. The ranges must be sorted |

244 | +-- and not overlap. |

245 | + |

246 | +newtype DiscreteOrdered v => RSet v = RSet {rSetRanges :: [Range v]} |

247 | + deriving Show |

248 | + |

249 | +-- | RSet is an instance of @Eq@, but is likely to diverge on infinite sets. |

250 | +instance DiscreteOrdered v => Eq (RSet v) where |

251 | + (==) rs1 rs2 = |

252 | + rSetRanges1 rs1 == rSetRanges1 rs2 |

253 | + |

254 | + |

255 | +-- | A strict version of rSetRanges. Empty ranges are filtered out, and |

256 | +-- touching ranges are merged. However it may diverge on the unions, |

257 | +-- intersections and differences of certain infinite sets. |

258 | +rSetRanges1 :: DiscreteOrdered v => RSet v -> [Range v] |

259 | +rSetRanges1 rs = normalise1 $ filter (not.rangeIsEmpty) $ rSetRanges rs |

260 | + where |

261 | + normalise1 (r1:r2:rs) = |

262 | + if rangeUpper r1 >= rangeLower r2 |

263 | + then normalise1 (Range (rangeLower r1) (rangeUpper r2) : rs) |

264 | + else r1 : normalise1 (r2 : rs) |

265 | + normalise1 rs = rs |

266 | + |

267 | +-- | Determine if the ranges in the list are both in order and non-overlapping. |

268 | +-- If so then they are suitable input for the unsafeRangedSet function. |

269 | +validRangeList :: DiscreteOrdered v => [Range v] -> Bool |

270 | + |

271 | +validRangeList [] = True |

272 | +validRangeList [Range lower upper] = lower <= upper |

273 | +validRangeList ranges = and $ zipWith okAdjacent ranges (tail ranges) |

274 | + where |

275 | + okAdjacent (Range lower1 upper1) (Range lower2 upper2) = |

276 | + lower1 <= upper1 && upper1 <= lower2 && lower2 <= upper2 |

277 | + |

278 | + |

279 | +-- | Rearrange and merge the ranges in the list so that they are in order and |

280 | +-- non-overlapping. |

281 | +normaliseRangeList :: DiscreteOrdered v => [Range v] -> [Range v] |

282 | + |

283 | +normaliseRangeList ranges = normalise $ sort $ filter nonEmpty ranges |

284 | + where |

285 | + nonEmpty (Range lower upper) = lower < upper |

286 | + |

287 | + |

288 | +-- Private routine: normalise a range list that is known to be already sorted. |

289 | +-- This precondition is not checked. |

290 | +normalise :: DiscreteOrdered v => [Range v] -> [Range v] |

291 | +normalise (r1:r2:rs) = |

292 | + if overlap r1 r2 |

293 | + then normalise $ |

294 | + Range (rangeLower r1) |

295 | + (max (rangeUpper r1) (rangeUpper r2)) |

296 | + : rs |

297 | + else r1 : (normalise $ r2 : rs) |

298 | + where |

299 | + overlap (Range _ upper1) (Range lower2 _) = upper1 >= lower2 |

300 | + |

301 | +normalise rs = rs |

302 | + |

303 | +-- | Create a new Ranged Set from a list of ranges. The list may contain |

304 | +-- ranges that overlap or are not in ascending order. |

305 | +rangedSet :: DiscreteOrdered v => [Range v] -> RSet v |

306 | +rangedSet = RSet . normaliseRangeList |

307 | + |

308 | +-- | Create a new Ranged Set from a list of ranges. @validRangeList ranges@ |

309 | +-- must return @True@. This precondition is not checked. |

310 | +unsafeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v |

311 | +unsafeRangedSet = RSet |

312 | + |

313 | + |

314 | +-- | True if the set has no members. Warning: if the argument is the result |

315 | +-- of operations on infinite sets then this can only ever return False. |

316 | +rSetIsEmpty :: DiscreteOrdered v => RSet v -> Bool |

317 | +rSetIsEmpty rs = null $ filter (not.rangeIsEmpty) $ rSetRanges rs |

318 | + |

319 | + |

320 | +-- | True if the value is within the ranged set. Infix precedence is left 5. |

321 | +rSetHas, (-?-) :: DiscreteOrdered v => RSet v -> v -> Bool |

322 | +rSetHas (RSet ls) value = rSetHas1 ls |

323 | + where |

324 | + rSetHas1 [] = False |

325 | + rSetHas1 (r:rs) |

326 | + | value />/ rangeLower r = rangeHas r value || rSetHas1 rs |

327 | + | otherwise = False |

328 | + |

329 | +(-?-) = rSetHas |

330 | + |

331 | +-- | True if the first argument is a subset of the second argument, or is |

332 | +-- equal. Warning: if both arguments are infinite then this can never |

333 | +-- return True. Infix precedence is left 5. |

334 | +rSetSubset, (-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool |

335 | +rSetSubset rs1 rs2 = rSetIsEmpty (rs1 -!- rs2) |

336 | +(-<=-) = rSetSubset |

337 | + |

338 | + |

339 | +-- | True if the first argument is a strict subset of the second argument. |

340 | +-- Warning: if both arguments are infinite then this can never return True. |

341 | +-- Infix precedence is left 5. |

342 | +rSetSubsetStrict, (-<-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool |

343 | +rSetSubsetStrict rs1 rs2 = |

344 | + rSetIsEmpty (rs1 -!- rs2) |

345 | + && not (rSetIsEmpty (rs2 -!- rs1)) |

346 | + |

347 | +(-<-) = rSetSubsetStrict |

348 | + |

349 | +-- | Set union for ranged sets. Infix precedence is left 6. |

350 | +rSetUnion, (-\/-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v |

351 | +-- Implementation note: rSetUnion merges the two lists into a single |

352 | +-- sorted list and then calls normalise to combine overlapping ranges. |

353 | +rSetUnion (RSet ls1) (RSet ls2) = RSet $ normalise $ merge ls1 ls2 |

354 | + where |

355 | + merge ls1 [] = ls1 |

356 | + merge [] ls2 = ls2 |

357 | + merge ls1@(h1:t1) ls2@(h2:t2) = |

358 | + if h1 < h2 |

359 | + then h1 : merge t1 ls2 |

360 | + else h2 : merge ls1 t2 |

361 | + |

362 | +(-\/-) = rSetUnion |

363 | + |

364 | +-- | Set intersection for ranged sets. Infix precedence is left 7. |

365 | +rSetIntersection, (-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v |

366 | +rSetIntersection (RSet ls1) (RSet ls2) = |

367 | + RSet $ filter (not . rangeIsEmpty) $ merge ls1 ls2 |

368 | + where |

369 | + merge ls1@(h1:t1) ls2@(h2:t2) = |

370 | + rangeIntersection h1 h2 |

371 | + : if rangeUpper h1 < rangeUpper h2 |

372 | + then merge t1 ls2 |

373 | + else merge ls1 t2 |

374 | + merge _ _ = [] |

375 | + |

376 | +(-/\-) = rSetIntersection |

377 | + |

378 | + |

379 | +-- | Set difference. Infix precedence is left 6. |

380 | +rSetDifference, (-!-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v |

381 | +rSetDifference rs1 rs2 = rs1 -/\- (rSetNegation rs2) |

382 | +(-!-) = rSetDifference |

383 | + |

384 | + |

385 | +-- | Set negation. |

386 | +rSetNegation :: DiscreteOrdered a => RSet a -> RSet a |

387 | +rSetNegation set = RSet $ ranges $ setBounds1 |

388 | + where |

389 | + ranges (b1:b2:bs) = Range b1 b2 : ranges bs |

390 | + ranges [BoundaryAboveAll] = [] |

391 | + ranges [b] = [Range b BoundaryAboveAll] |

392 | + ranges _ = [] |

393 | + setBounds1 = case setBounds of |

394 | + (BoundaryBelowAll : bs) -> bs |

395 | + _ -> BoundaryBelowAll : setBounds |

396 | + setBounds = bounds $ rSetRanges set |

397 | + bounds (r:rs) = rangeLower r : rangeUpper r : bounds rs |

398 | + bounds _ = [] |

399 | + |

400 | + |

401 | +-- | The empty set. |

402 | +rSetEmpty :: DiscreteOrdered a => RSet a |

403 | +rSetEmpty = RSet [] |

404 | + |

405 | +-- | The set that contains everything. |

406 | +rSetFull :: DiscreteOrdered a => RSet a |

407 | +rSetFull = RSet [Range BoundaryBelowAll BoundaryAboveAll] |

408 | + |

409 | + |

410 | +-- | Construct a range set. |

411 | +rSetUnfold :: DiscreteOrdered a => |

412 | + Boundary a |

413 | + -- ^ A first lower boundary. |

414 | + -> (Boundary a -> Boundary a) |

415 | + -- ^ A function from a lower boundary to an upper boundary, which must |

416 | + -- return a result greater than the argument (not checked). |

417 | + -> (Boundary a -> Maybe (Boundary a)) |

418 | + -- ^ A function from a lower boundary to @Maybe@ the successor lower boundary, |

419 | + -- which must return a result greater than the argument (not checked). |

420 | + -> RSet a |

421 | +rSetUnfold bound upperFunc succFunc = RSet $ normalise $ ranges bound |

422 | + where |

423 | + ranges b = |

424 | + Range b (upperFunc bound) |

425 | + : case succFunc b of |

426 | + Just b2 -> ranges b2 |

427 | + Nothing -> [] |

428 | + |

429 | + |

430 | +-- QuickCheck Generators |

431 | + |

432 | +instance (Arbitrary v, DiscreteOrdered v, Show v) => |

433 | + Arbitrary (RSet v) |

434 | + where |

435 | + arbitrary = do |

436 | + ls <- arbitrary |

437 | + return $ rangedSet $ rangeList $ sort ls |

438 | + where |

439 | + -- Arbitrary lists of ranges don't give many interesting sets after |

440 | + -- normalisation. So instead generate a sorted list of boundaries |

441 | + -- and pair them off. Odd boundaries are dropped. |

442 | + rangeList (b1:b2:bs) = Range b1 b2 : rangeList bs |

443 | + rangeList _ = [] |

444 | + |

445 | + coarbitrary (RSet ls) = variant 0 . coarbitrary ls |

446 | + |

447 | +-- ================================================================== |

448 | +-- QuickCheck Properties |

449 | +-- ================================================================== |

450 | + |

451 | +-- Note for maintenance: Haddock does not include QuickCheck properties, |

452 | +-- so they have to be copied into documentation blocks manually. This |

453 | +-- process must be repeated for new or modified properties. |

454 | + |

455 | + |

456 | +--------------------------------------------------------------------- |

457 | +-- Construction properties |

458 | +--------------------------------------------------------------------- |

459 | + |

460 | +{- $ConstructionProperties |

461 | + |

462 | +A normalised range list is valid for unsafeRangedSet |

463 | + |

464 | +> prop_validNormalised ls = validRangeList $ normaliseRangeList ls |

465 | +> where types = ls :: [Range Double] |

466 | + |

467 | +Iff a value is in a range list then it is in a ranged set |

468 | +constructed from that list. |

469 | + |

470 | +> prop_has (ls :: [Range Double], v :: Double) = |

471 | +> (ls `rangeListHas` v) == rangedSet ls -?- v |

472 | + |

473 | +-} |

474 | + |

475 | +-- A normalised range list is valid for unsafeRangedSet |

476 | +prop_validNormalised ls = validRangeList $ normaliseRangeList ls |

477 | + where types = ls :: [Range Double] |

478 | + |

479 | +-- Iff a value is in a range list then it is in a ranged set |

480 | +-- constructed from that list. |

481 | +prop_has (ls :: [Range Double], v :: Double) = |

482 | + (ls `rangeListHas` v) == rangedSet ls -?- v |

483 | + |

484 | +--------------------------------------------------------------------- |

485 | +-- Basic operation properties |

486 | +--------------------------------------------------------------------- |

487 | + |

488 | +{- $BasicOperationProperties |

489 | +Iff a value is in either of two ranged sets then it is in the union of |

490 | +those two sets. |

491 | + |

492 | +> prop_union (rs1, rs2 :: RSet Double, v :: Double) = |

493 | +> (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v) |

494 | + |

495 | +Iff a value is in both of two ranged sets then it is in the intersection |

496 | +of those two sets. |

497 | + |

498 | +> prop_intersection (rs1, rs2 :: RSet Double, v :: Double) = |

499 | +> (rs1 -?- v && rs2 -?- v) == |

500 | +> ((rs1 `rSetIntersection` rs2) -?- v) |

501 | + |

502 | + |

503 | +Iff a value is in ranged set 1 and not in ranged set 2 then it is in the |

504 | +difference of the two. |

505 | + |

506 | +> prop_difference (rs1, rs2 :: RSet Double, v :: Double) = |

507 | +> (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v) |

508 | + |

509 | + |

510 | +Iff a value is not in a ranged set then it is in its negation. |

511 | + |

512 | +> prop_negation (rs :: RSet Double, v :: Double) = |

513 | +> rs -?- v == not (rSetNegation rs -?- v) |

514 | + |

515 | + |

516 | +A set that contains a value is not empty |

517 | + |

518 | +> prop_not_empty (rs :: RSet Double, v :: Double) = |

519 | +> (rs -?- v) ==> not (rSetIsEmpty rs) |

520 | +-} |

521 | + |

522 | +-- Iff a value is in either of two ranged sets then it is in the union of |

523 | +-- those two sets. |

524 | +prop_union (rs1, rs2 :: RSet Double, v :: Double) = |

525 | + (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v) |

526 | + |

527 | +-- Iff a value is in both of two ranged sets then it is in the intersection |

528 | +-- of those two sets. |

529 | +prop_intersection (rs1, rs2 :: RSet Double, v :: Double) = |

530 | + (rs1 -?- v && rs2 -?- v) == |

531 | + ((rs1 `rSetIntersection` rs2) -?- v) |

532 | + |

533 | + |

534 | +-- Iff a value is in ranged set 1 and not in ranged set 2 then it is in the |

535 | +-- difference of the two. |

536 | +prop_difference (rs1, rs2 :: RSet Double, v :: Double) = |

537 | + (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v) |

538 | + |

539 | + |

540 | +-- Iff a value is not in a ranged set then it is in its negation. |

541 | +prop_negation (rs :: RSet Double, v :: Double) = |

542 | + rs -?- v == not (rSetNegation rs -?- v) |

543 | + |

544 | + |

545 | +-- A set that contains a value is not empty |

546 | +prop_not_empty (rs :: RSet Double, v :: Double) = |

547 | + (rs -?- v) ==> not (rSetIsEmpty rs) |

548 | + |

549 | +--------------------------------------------------------------------- |

550 | +-- Some identities and inequalities of sets |

551 | +--------------------------------------------------------------------- |

552 | + |

553 | +{- $SomeIdentitiesAndInequalities |

554 | +The intersection of a set with its negation is empty. |

555 | + |

556 | +> prop_empty_intersection rs = |

557 | +> rSetIsEmpty (rs -/\- rSetNegation rs) |

558 | +> where types = rs :: RSet Double |

559 | + |

560 | + |

561 | +The union of a set with its negation is full. |

562 | + |

563 | +> prop_full_union (rs :: RSet Double, v :: Double) = |

564 | +> (rs -\/- rSetNegation rs) -?- v |

565 | + |

566 | + |

567 | +The union of two sets is the non-strict superset of both. |

568 | + |

569 | +> prop_union_superset (rs1, rs2 :: RSet Double) = |

570 | +> rs1 -<=- u && rs2 -<=- u |

571 | +> where |

572 | +> u = rs1 -\/- rs2 |

573 | + |

574 | +The intersection of two sets is the non-strict subset of both. |

575 | + |

576 | +> prop_intersection_subset (rs1, rs2 :: RSet Double) = |

577 | +> i -<=- rs1 && i -<=- rs2 |

578 | +> where |

579 | +> i = rs1 -/\- rs2 |

580 | + |

581 | +The difference of two sets intersected with the subtractand is empty. |

582 | + |

583 | +> prop_diff_intersect (rs1, rs2 :: RSet Double) = |

584 | +> rSetIsEmpty ((rs1 -!- rs2) -/\- rs2) |

585 | + |

586 | +A set is the non-strict subset of itself. |

587 | + |

588 | +> prop_subset rs = |

589 | +> rs -<=- rs |

590 | +> where types = rs :: RSet Double |

591 | + |

592 | +A set is not the strict subset of itself. |

593 | + |

594 | +> prop_strict_subset rs = |

595 | +> not (rs -<- rs) |

596 | +> where types = rs :: RSet Double |

597 | + |

598 | + |

599 | +If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a strict |

600 | +superset of rs2. |

601 | + |

602 | +> prop_union_strict_superset (rs1, rs2 :: RSet Double) = |

603 | +> (not $ rSetIsEmpty (rs1 -!- rs2)) |

604 | +> ==> (rs2 -<- (rs1 -\/- rs2)) |

605 | + |

606 | +Intersection commutes |

607 | + |

608 | +> prop_intersection_commutes (rs1, rs2 :: RSet Double) = |

609 | +> (rs1 -/\- rs2) == (rs2 -/\- rs1) |

610 | + |

611 | +Union commutes |

612 | + |

613 | +> prop_union_commutes (rs1, rs2 :: RSet Double) = |

614 | +> (rs1 -\/- rs2) == (rs2 -\/- rs1) |

615 | + |

616 | +Intersection associates |

617 | + |

618 | +> prop_intersection_associates (rs1, rs2, rs3 :: RSet Double) = |

619 | +> ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3)) |

620 | + |

621 | +Union associates |

622 | + |

623 | +> prop_union_associates (rs1, rs2, rs3 :: RSet Double) = |

624 | +> ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3)) |

625 | + |

626 | +-} |

627 | + |

628 | +-- The intersection of a set with its negation is empty. |

629 | +prop_empty_intersection rs = |

630 | + rSetIsEmpty (rs -/\- rSetNegation rs) |

631 | + where types = rs :: RSet Double |

632 | + |

633 | + |

634 | +-- The union of a set with its negation is full. |

635 | +prop_full_union (rs :: RSet Double, v :: Double) = |

636 | + (rs -\/- rSetNegation rs) -?- v |

637 | + |

638 | + |

639 | +-- The union of two sets is the non-strict superset of both. |

640 | +prop_union_superset (rs1, rs2 :: RSet Double) = |

641 | + rs1 -<=- u && rs2 -<=- u |

642 | + where |

643 | + u = rs1 -\/- rs2 |

644 | + |

645 | +-- The intersection of two sets is the non-strict subset of both. |

646 | +prop_intersection_subset (rs1, rs2 :: RSet Double) = |

647 | + i -<=- rs1 && i -<=- rs2 |

648 | + where |

649 | + i = rs1 -/\- rs2 |

650 | + |

651 | +-- The difference of two sets intersected with the subtractand is empty. |

652 | +prop_diff_intersect (rs1, rs2 :: RSet Double) = |

653 | + rSetIsEmpty ((rs1 -!- rs2) -/\- rs2) |

654 | + |

655 | + |

656 | +-- A set is the non-strict subset of itself. |

657 | +prop_subset rs = |

658 | + rs -<=- rs |

659 | + where types = rs :: RSet Double |

660 | + |

661 | +-- A set is not the strict subset of itself. |

662 | +prop_strict_subset rs = |

663 | + not (rs -<- rs) |

664 | + where types = rs :: RSet Double |

665 | + |

666 | + |

667 | +-- If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a strict |

668 | +-- superset of rs2. |

669 | +prop_union_strict_superset (rs1, rs2 :: RSet Double) = |

670 | + (not $ rSetIsEmpty (rs1 -!- rs2)) |

671 | + ==> (rs2 -<- (rs1 -\/- rs2)) |

672 | + |

673 | +-- Intersection commutes |

674 | +prop_intersection_commutes (rs1, rs2 :: RSet Double) = |

675 | + (rs1 -/\- rs2) == (rs2 -/\- rs1) |

676 | + |

677 | +-- Union commutes |

678 | +prop_union_commutes (rs1, rs2 :: RSet Double) = |

679 | + (rs1 -\/- rs2) == (rs2 -\/- rs1) |

680 | + |

681 | +-- Intersection associates |

682 | +prop_intersection_associates (rs1, rs2, rs3 :: RSet Double) = |

683 | + ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3)) |

684 | + |

685 | +-- Union associates |

686 | +prop_union_associates (rs1, rs2, rs3 :: RSet Double) = |

687 | + ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3)) |

688 | + |

689 | + |

690 | + |

691 | + |

692 | addfile ./Data/Ranged/Ranges.hs |

693 | hunk ./Data/Ranged/Ranges.hs 1 |

694 | +{-# OPTIONS_GHC -fglasgow-exts #-} |

695 | + |

696 | +-- | A range has an upper and lower boundary. |

697 | +module Data.Ranged.Ranges ( |

698 | + -- ** Construction |

699 | + Range (..), |

700 | + emptyRange, |

701 | + fullRange, |

702 | + -- ** Predicates |

703 | + rangeIsEmpty, |

704 | + rangeOverlap, |

705 | + rangeEncloses, |

706 | + -- ** Membership |

707 | + rangeHas, |

708 | + rangeListHas, |

709 | + -- ** Set Operations |

710 | + rangeIntersection, |

711 | + rangeUnion, |

712 | + rangeDifference |

713 | + -- ** QuickCheck Properties |

714 | + -- $properties |

715 | +) where |

716 | + |

717 | +import Data.Ranged.Boundaries |

718 | +import Data.Maybe |

719 | +import Test.QuickCheck |

720 | + |

721 | +-- | A Range has upper and lower boundaries. |

722 | +data Ord v => Range v = Range {rangeLower, rangeUpper :: Boundary v} |

723 | + |

724 | +instance (DiscreteOrdered a) => Eq (Range a) where |

725 | + r1 == r2 = (rangeIsEmpty r1 && rangeIsEmpty r2) || |

726 | + (rangeLower r1 == rangeLower r2 && |

727 | + rangeUpper r1 == rangeUpper r2) |

728 | + |

729 | + |

730 | +instance (DiscreteOrdered a) => Ord (Range a) where |

731 | + compare r1 r2 |

732 | + | r1 == r2 = EQ |

733 | + | rangeIsEmpty r1 = LT |

734 | + | rangeIsEmpty r2 = GT |

735 | + | otherwise = compare (rangeLower r1, rangeUpper r1) |

736 | + (rangeLower r2, rangeUpper r2) |

737 | + |

738 | +instance (Show a, DiscreteOrdered a) => Show (Range a) where |

739 | + show r |

740 | + | rangeIsEmpty r = "Empty" |

741 | + | otherwise = lowerBound ++ "x" ++ upperBound |

742 | + where |

743 | + lowerBound = case rangeLower r of |

744 | + BoundaryBelowAll -> "" |

745 | + BoundaryBelow v -> show v ++ " <= " |

746 | + BoundaryAbove v -> show v ++ " < " |

747 | + BoundaryAboveAll -> error "show Range: lower bound is BoundaryAboveAll" |

748 | + upperBound = case rangeUpper r of |

749 | + BoundaryBelowAll -> error "show Range: upper bound is BoundaryBelowAll" |

750 | + BoundaryBelow v -> " < " ++ show v |

751 | + BoundaryAbove v -> " <=" ++ show v |

752 | + BoundaryAboveAll -> "" |

753 | + |

754 | + |

755 | +-- | True if the value is within the range. |

756 | +rangeHas :: Ord v => Range v -> v -> Bool |

757 | + |

758 | +rangeHas (Range b1 b2) v = |

759 | + (v />/ b1) && not (v />/ b2) |

760 | + |

761 | + |

762 | +-- | True if the value is within one of the ranges. |

763 | +rangeListHas :: Ord v => |

764 | + [Range v] -> v -> Bool |

765 | +rangeListHas ls v = or $ map (\r -> rangeHas r v) ls |

766 | + |

767 | +-- The empty range |

768 | +emptyRange :: DiscreteOrdered v => Range v |

769 | +emptyRange = Range BoundaryAboveAll BoundaryBelowAll |

770 | + |

771 | +-- The full range. All values are within it. |

772 | +fullRange :: DiscreteOrdered v => Range v |

773 | +fullRange = Range BoundaryBelowAll BoundaryAboveAll |

774 | + |

775 | +-- | A range is empty unless its upper boundary is greater than its lower |

776 | +-- boundary. |

777 | +rangeIsEmpty :: DiscreteOrdered v => Range v -> Bool |

778 | +rangeIsEmpty (Range lower upper) = upper <= lower |

779 | + |

780 | + |

781 | +-- | Two ranges overlap if their intersection is non-empty. |

782 | +rangeOverlap :: DiscreteOrdered v => Range v -> Range v -> Bool |

783 | +rangeOverlap r1 r2 = |

784 | + not (rangeIsEmpty r1) |

785 | + && not (rangeIsEmpty r2) |

786 | + && not (rangeUpper r1 <= rangeLower r2 || rangeUpper r2 <= rangeLower r1) |

787 | + |

788 | +-- | The first range encloses the second if every value in the second range is |

789 | +-- also within the first range. If the second range is empty then this is |

790 | +-- always true. |

791 | + |

792 | +rangeEncloses :: DiscreteOrdered v => Range v -> Range v -> Bool |

793 | +rangeEncloses r1 r2 = |

794 | + (rangeLower r1 <= rangeLower r2 && rangeUpper r2 <= rangeUpper r1) |

795 | + || rangeIsEmpty r2 |

796 | + |

797 | + |

798 | +-- | Intersection of two ranges, if any. |

799 | +rangeIntersection :: DiscreteOrdered v => Range v -> Range v -> Range v |

800 | + |

801 | +rangeIntersection (Range lower1 upper1) (Range lower2 upper2) = |

802 | + Range (max lower1 lower2) (min upper1 upper2) |

803 | + |

804 | + |

805 | +-- | Union of two ranges. Returns one or two results. |

806 | +-- |

807 | +-- If there are two results then they are guaranteed to have a non-empty |

808 | +-- gap in between, but may not be in ascending order. |

809 | +rangeUnion :: DiscreteOrdered v => Range v -> Range v -> [Range v] |

810 | + |

811 | +rangeUnion r1@(Range lower1 upper1) r2@(Range lower2 upper2) = |

812 | + if touching |

813 | + then [Range lower upper] |

814 | + else [r1, r2] |

815 | + where |

816 | + touching = (max lower1 lower2) <= (min upper1 upper2) |

817 | + lower = min lower1 lower2 |

818 | + upper = max upper1 upper2 |

819 | + |

820 | +-- | @range1@ minus @range2@. Zero, one or two results. |

821 | +rangeDifference :: DiscreteOrdered v => Range v -> Range v -> [Range v] |

822 | + |

823 | +rangeDifference r1@(Range lower1 upper1) r2@(Range lower2 upper2) = |

824 | + -- There are six possibilities |

825 | + -- 1: r2 completely less than r1 |

826 | + -- 2: r2 overlaps bottom of r1 |

827 | + -- 3: r2 encloses r1 |

828 | + -- 4: r1 encloses r2 |

829 | + -- 5: r2 overlaps top of r1 |

830 | + -- 6: r2 completely greater than r1 |

831 | + if intersects |

832 | + then -- Cases 2,3,4,5 |

833 | + filter (not . rangeIsEmpty) [Range lower1 lower2, Range upper2 upper1] |

834 | + else -- Cases 1, 6 |

835 | + [r1] |

836 | + where |

837 | + intersects = (max lower1 lower2) < (min upper1 upper2) |

838 | + |

839 | +-- QuickCheck generators |

840 | + |

841 | +instance (Arbitrary v, DiscreteOrdered v, Show v) => |

842 | + Arbitrary (Range v) where |

843 | + |

844 | + arbitrary = frequency [ |

845 | + (18, do |

846 | + (b1 :: Boundary v) <- arbitrary |

847 | + (b2 :: Boundary v) <- arbitrary |

848 | + if b1 < b2 |

849 | + then return $ Range b1 b2 |

850 | + else return $ Range b2 b1 |

851 | + ), |

852 | + (1, return emptyRange), |

853 | + (1, return fullRange) |

854 | + ] |

855 | + |

856 | + coarbitrary (Range lower upper) = |

857 | + variant 0 . coarbitrary lower . coarbitrary upper |

858 | + |

859 | + |

860 | + |

861 | +-- QuickCheck Properties |

862 | + |

863 | +{- $properties |

864 | +Range union |

865 | + |

866 | +> prop_union (r1, r2 :: Range Double, n :: Double) = |

867 | +> (r1 `rangeHas` n || r2 `rangeHas` n) |

868 | +> == (r1 `rangeUnion` r2) `rangeListHas` n |

869 | + |

870 | +Range intersection |

871 | + |

872 | +> prop_intersection (r1, r2 :: Range Double, n :: Double) = |

873 | +> (r1 `rangeHas` n && r2 `rangeHas` n) |

874 | +> == (r1 `rangeIntersection` r2) `rangeHas` n |

875 | + |

876 | +Range difference |

877 | + |

878 | +> prop_difference (r1, r2 :: Range Double, n :: Double) = |

879 | +> (r1 `rangeHas` n && not (r2 `rangeHas` n)) |

880 | +> == (r1 `rangeDifference` r2) `rangeListHas` n |

881 | + |

882 | +-} |

883 | + |

884 | +-- Range union |

885 | +prop_union (r1, r2 :: Range Double, n :: Double) = |

886 | + (r1 `rangeHas` n || r2 `rangeHas` n) |

887 | + == (r1 `rangeUnion` r2) `rangeListHas` n |

888 | + |

889 | +-- Range intersection |

890 | +prop_intersection (r1, r2 :: Range Double, n :: Double) = |

891 | + (r1 `rangeHas` n && r2 `rangeHas` n) |

892 | + == (r1 `rangeIntersection` r2) `rangeHas` n |

893 | + |

894 | +-- Range difference |

895 | +prop_difference (r1, r2 :: Range Double, n :: Double) = |

896 | + (r1 `rangeHas` n && not (r2 `rangeHas` n)) |

897 | + == (r1 `rangeDifference` r2) `rangeListHas` n |

898 | } |

899 | |

900 | [Submission to base library |

901 | Paul Johnson <paul@cogito.org.uk>**20061109203014 |

902 | |

903 | Ranged sets with QuickCheck properties. All tests passed 100 times. |

904 | ] { |

905 | hunk ./Data/Ranged/Boundaries.hs 2 |

906 | +----------------------------------------------------------------------------- |

907 | +-- | |

908 | +-- Module : Data.Ranged.Boundaries |

909 | +-- Copyright : (c) Paul Johnson 2006 |

910 | +-- License : BSD-style |

911 | +-- Maintainer : paul@cogito.org.uk |

912 | +-- Stability : experimental |

913 | +-- Portability : portable |

914 | +-- |

915 | +----------------------------------------------------------------------------- |

916 | + |

917 | + |

918 | + |

919 | hunk ./Data/Ranged/Boundaries.hs 90 |

920 | -This is incorrect because there are no possible values in between the left |

921 | -and right sides of these inequalities. |

922 | +This is incorrect because there are no possible values in |

923 | +between the left and right sides of these inequalities. |

924 | hunk ./Data/Ranged/Boundaries.hs 103 |

925 | - deriving (Eq, Show) |

926 | + deriving (Show) |

927 | hunk ./Data/Ranged/Boundaries.hs 117 |

928 | +instance (DiscreteOrdered a) => Eq (Boundary a) where |

929 | + b1 == b2 = compare b1 b2 == EQ |

930 | + |

931 | hunk ./Data/Ranged/Boundaries.hs 155 |

932 | - |

933 | hunk ./Data/Ranged/Boundaries.hs 169 |

934 | - |

935 | + |

936 | hunk ./Data/Ranged/RangedSet.hs 7 |

937 | - rSetRanges1, |

938 | hunk ./Data/Ranged/RangedSet.hs 8 |

939 | - rangedSet, |

940 | + makeRangedSet, |

941 | hunk ./Data/Ranged/RangedSet.hs 14 |

942 | - (-?-), rSetHas, |

943 | - (-<=-), rSetSubset, |

944 | - (-<-), rSetSubsetStrict, |

945 | + (-?-), rSetHas, |

946 | + (-<=-), rSetIsSubset, |

947 | + (-<-), rSetIsSubsetStrict, |

948 | hunk ./Data/Ranged/RangedSet.hs 20 |

949 | - (-!-), rSetDifference, |

950 | + (-!-), rSetDifference, |

951 | hunk ./Data/Ranged/RangedSet.hs 53 |

952 | - deriving Show |

953 | + deriving (Eq, Show) |

954 | hunk ./Data/Ranged/RangedSet.hs 55 |

955 | --- | RSet is an instance of @Eq@, but is likely to diverge on infinite sets. |

956 | -instance DiscreteOrdered v => Eq (RSet v) where |

957 | - (==) rs1 rs2 = |

958 | - rSetRanges1 rs1 == rSetRanges1 rs2 |

959 | - |

960 | - |

961 | --- | A strict version of rSetRanges. Empty ranges are filtered out, and |

962 | --- touching ranges are merged. However it may diverge on the unions, |

963 | --- intersections and differences of certain infinite sets. |

964 | -rSetRanges1 :: DiscreteOrdered v => RSet v -> [Range v] |

965 | -rSetRanges1 rs = normalise1 $ filter (not.rangeIsEmpty) $ rSetRanges rs |

966 | - where |

967 | - normalise1 (r1:r2:rs) = |

968 | - if rangeUpper r1 >= rangeLower r2 |

969 | - then normalise1 (Range (rangeLower r1) (rangeUpper r2) : rs) |

970 | - else r1 : normalise1 (r2 : rs) |

971 | - normalise1 rs = rs |

972 | hunk ./Data/Ranged/RangedSet.hs 72 |

973 | -normaliseRangeList ranges = normalise $ sort $ filter nonEmpty ranges |

974 | - where |

975 | - nonEmpty (Range lower upper) = lower < upper |

976 | +normaliseRangeList ranges = |

977 | + normalise $ sort $ filter (not . rangeIsEmpty) ranges |

978 | hunk ./Data/Ranged/RangedSet.hs 91 |

979 | + |

980 | hunk ./Data/Ranged/RangedSet.hs 94 |

981 | -rangedSet :: DiscreteOrdered v => [Range v] -> RSet v |

982 | -rangedSet = RSet . normaliseRangeList |

983 | +makeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v |

984 | +makeRangedSet = RSet . normaliseRangeList |

985 | + |

986 | hunk ./Data/Ranged/RangedSet.hs 104 |

987 | --- | True if the set has no members. Warning: if the argument is the result |

988 | --- of operations on infinite sets then this can only ever return False. |

989 | +-- | True if the set has no members. |

990 | hunk ./Data/Ranged/RangedSet.hs 106 |

991 | -rSetIsEmpty rs = null $ filter (not.rangeIsEmpty) $ rSetRanges rs |

992 | +rSetIsEmpty = null . rSetRanges |

993 | + |

994 | + |

995 | +-- | True if the negation of the set has no members. |

996 | +rSetIsFull :: DiscreteOrdered v => RSet v -> Bool |

997 | +rSetIsFull = rSetIsEmpty . rSetNegation |

998 | hunk ./Data/Ranged/RangedSet.hs 126 |

999 | --- equal. Warning: if both arguments are infinite then this can never |

1000 | --- return True. Infix precedence is left 5. |

1001 | -rSetSubset, (-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool |

1002 | -rSetSubset rs1 rs2 = rSetIsEmpty (rs1 -!- rs2) |

1003 | -(-<=-) = rSetSubset |

1004 | +-- equal. |

1005 | +-- |

1006 | +-- Infix precedence is left 5. |

1007 | +rSetIsSubset, (-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool |

1008 | +rSetIsSubset rs1 rs2 = rSetIsEmpty (rs1 -!- rs2) |

1009 | +(-<=-) = rSetIsSubset |

1010 | hunk ./Data/Ranged/RangedSet.hs 135 |

1011 | --- Warning: if both arguments are infinite then this can never return True. |

1012 | +-- |

1013 | hunk ./Data/Ranged/RangedSet.hs 137 |

1014 | -rSetSubsetStrict, (-<-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool |

1015 | -rSetSubsetStrict rs1 rs2 = |

1016 | +rSetIsSubsetStrict, (-<-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool |

1017 | +rSetIsSubsetStrict rs1 rs2 = |

1018 | hunk ./Data/Ranged/RangedSet.hs 142 |

1019 | -(-<-) = rSetSubsetStrict |

1020 | +(-<-) = rSetIsSubsetStrict |

1021 | hunk ./Data/Ranged/RangedSet.hs 213 |

1022 | - -- ^ A function from a lower boundary to @Maybe@ the successor lower boundary, |

1023 | - -- which must return a result greater than the argument (not checked). |

1024 | + -- ^ A function from a lower boundary to @Maybe@ the successor lower |

1025 | + -- boundary, which must return a result greater than the argument |

1026 | + -- (not checked). |

1027 | hunk ./Data/Ranged/RangedSet.hs 231 |

1028 | - arbitrary = do |

1029 | - ls <- arbitrary |

1030 | - return $ rangedSet $ rangeList $ sort ls |

1031 | + arbitrary = frequency [ |

1032 | + (1, return rSetEmpty), |

1033 | + (1, return rSetFull), |

1034 | + (18, do |

1035 | + ls <- arbitrary |

1036 | + return $ makeRangedSet $ rangeList $ sort ls |

1037 | + )] |

1038 | hunk ./Data/Ranged/RangedSet.hs 277 |

1039 | - where types = ls :: [Range Double] |

1040 | + where types = ls :: [Range Integer] |

1041 | hunk ./Data/Ranged/RangedSet.hs 281 |

1042 | -prop_has (ls :: [Range Double], v :: Double) = |

1043 | - (ls `rangeListHas` v) == rangedSet ls -?- v |

1044 | +prop_has (ls :: [Range Integer], v :: Integer) = |

1045 | + (ls `rangeListHas` v) == makeRangedSet ls -?- v |

1046 | hunk ./Data/Ranged/RangedSet.hs 292 |

1047 | -> prop_union (rs1, rs2 :: RSet Double, v :: Double) = |

1048 | +> prop_union (rs1, rs2 :: RSet Integer, v :: Integer) = |

1049 | hunk ./Data/Ranged/RangedSet.hs 298 |

1050 | -> prop_intersection (rs1, rs2 :: RSet Double, v :: Double) = |

1051 | +> prop_intersection (rs1, rs2 :: RSet Integer, v :: Integer) = |

1052 | hunk ./Data/Ranged/RangedSet.hs 306 |

1053 | -> prop_difference (rs1, rs2 :: RSet Double, v :: Double) = |

1054 | +> prop_difference (rs1, rs2 :: RSet Integer, v :: Integer) = |

1055 | hunk ./Data/Ranged/RangedSet.hs 312 |

1056 | -> prop_negation (rs :: RSet Double, v :: Double) = |

1057 | +> prop_negation (rs :: RSet Integer, v :: Integer) = |

1058 | hunk ./Data/Ranged/RangedSet.hs 318 |

1059 | -> prop_not_empty (rs :: RSet Double, v :: Double) = |

1060 | +> prop_not_empty (rs :: RSet Integer, v :: Integer) = |

1061 | hunk ./Data/Ranged/RangedSet.hs 324 |

1062 | -prop_union (rs1, rs2 :: RSet Double, v :: Double) = |

1063 | +prop_union (rs1, rs2 :: RSet Integer, v :: Integer) = |

1064 | hunk ./Data/Ranged/RangedSet.hs 329 |

1065 | -prop_intersection (rs1, rs2 :: RSet Double, v :: Double) = |

1066 | +prop_intersection (rs1, rs2 :: RSet Integer, v :: Integer) = |

1067 | hunk ./Data/Ranged/RangedSet.hs 336 |

1068 | -prop_difference (rs1, rs2 :: RSet Double, v :: Double) = |

1069 | +prop_difference (rs1, rs2 :: RSet Integer, v :: Integer) = |

1070 | hunk ./Data/Ranged/RangedSet.hs 341 |

1071 | -prop_negation (rs :: RSet Double, v :: Double) = |

1072 | +prop_negation (rs :: RSet Integer, v :: Integer) = |

1073 | hunk ./Data/Ranged/RangedSet.hs 346 |

1074 | -prop_not_empty (rs :: RSet Double, v :: Double) = |

1075 | +prop_not_empty (rs :: RSet Integer, v :: Integer) = |

1076 | hunk ./Data/Ranged/RangedSet.hs 354 |

1077 | + |

1078 | +The empty set has no members. |

1079 | + |

1080 | +> prop_empty (v :: Integer) = not (rSetEmpty -?- v) |

1081 | + |

1082 | + |

1083 | +The full set has every member. |

1084 | + |

1085 | +> prop_full (v :: Integer) = rSetFull -?- v |

1086 | + |

1087 | + |

1088 | hunk ./Data/Ranged/RangedSet.hs 367 |

1089 | -> prop_empty_intersection rs = |

1090 | +> prop_empty_intersection (rs :: RSet Integer) = |

1091 | hunk ./Data/Ranged/RangedSet.hs 369 |

1092 | -> where types = rs :: RSet Double |

1093 | hunk ./Data/Ranged/RangedSet.hs 373 |

1094 | -> prop_full_union (rs :: RSet Double, v :: Double) = |

1095 | -> (rs -\/- rSetNegation rs) -?- v |

1096 | +> prop_full_union (rs :: RSet Integer, v :: Integer) = |

1097 | +> rSetIsFull (rs -\/- rSetNegation rs) |

1098 | hunk ./Data/Ranged/RangedSet.hs 379 |

1099 | -> prop_union_superset (rs1, rs2 :: RSet Double) = |

1100 | +> prop_union_superset (rs1, rs2 :: RSet Integer) = |

1101 | hunk ./Data/Ranged/RangedSet.hs 386 |

1102 | -> prop_intersection_subset (rs1, rs2 :: RSet Double) = |

1103 | +> prop_intersection_subset (rs1, rs2 :: RSet Integer) = |

1104 | hunk ./Data/Ranged/RangedSet.hs 393 |

1105 | -> prop_diff_intersect (rs1, rs2 :: RSet Double) = |

1106 | +> prop_diff_intersect (rs1, rs2 :: RSet Integer) = |

1107 | hunk ./Data/Ranged/RangedSet.hs 400 |

1108 | -> where types = rs :: RSet Double |

1109 | +> where types = rs :: RSet Integer |

1110 | hunk ./Data/Ranged/RangedSet.hs 406 |

1111 | -> where types = rs :: RSet Double |

1112 | +> where types = rs :: RSet Integer |

1113 | hunk ./Data/Ranged/RangedSet.hs 412 |

1114 | -> prop_union_strict_superset (rs1, rs2 :: RSet Double) = |

1115 | +> prop_union_strict_superset (rs1, rs2 :: RSet Integer) = |

1116 | hunk ./Data/Ranged/RangedSet.hs 418 |

1117 | -> prop_intersection_commutes (rs1, rs2 :: RSet Double) = |

1118 | +> prop_intersection_commutes (rs1, rs2 :: RSet Integer) = |

1119 | hunk ./Data/Ranged/RangedSet.hs 423 |

1120 | -> prop_union_commutes (rs1, rs2 :: RSet Double) = |

1121 | +> prop_union_commutes (rs1, rs2 :: RSet Integer) = |

1122 | hunk ./Data/Ranged/RangedSet.hs 428 |

1123 | -> prop_intersection_associates (rs1, rs2, rs3 :: RSet Double) = |

1124 | +> prop_intersection_associates (rs1, rs2, rs3 :: RSet Integer) = |

1125 | hunk ./Data/Ranged/RangedSet.hs 433 |

1126 | -> prop_union_associates (rs1, rs2, rs3 :: RSet Double) = |

1127 | +> prop_union_associates (rs1, rs2, rs3 :: RSet Integer) = |

1128 | hunk ./Data/Ranged/RangedSet.hs 436 |

1129 | +De Morgan's Law for Intersection |

1130 | + |

1131 | +> prop_de_morgan_intersection (rs1, rs2 :: RSet Integer) = |

1132 | +> rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2) |

1133 | + |

1134 | +De Morgan's Law for Union |

1135 | + |

1136 | +> prop_de_morgan_union (rs1, rs2 :: RSet Integer) = |

1137 | +> rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2) |

1138 | + |

1139 | hunk ./Data/Ranged/RangedSet.hs 448 |

1140 | +-- The empty set has no members. |

1141 | +prop_empty (v :: Integer) = not (rSetEmpty -?- v) |

1142 | + |

1143 | + |

1144 | +-- The full set has every member. |

1145 | +prop_full (v :: Integer) = rSetFull -?- v |

1146 | + |

1147 | + |

1148 | hunk ./Data/Ranged/RangedSet.hs 457 |

1149 | -prop_empty_intersection rs = |

1150 | +prop_empty_intersection (rs :: RSet Integer) = |

1151 | hunk ./Data/Ranged/RangedSet.hs 459 |

1152 | - where types = rs :: RSet Double |

1153 | hunk ./Data/Ranged/RangedSet.hs 462 |

1154 | -prop_full_union (rs :: RSet Double, v :: Double) = |

1155 | - (rs -\/- rSetNegation rs) -?- v |

1156 | +prop_full_union (rs :: RSet Integer, v :: Integer) = |

1157 | + rSetIsFull (rs -\/- rSetNegation rs) |

1158 | hunk ./Data/Ranged/RangedSet.hs 467 |

1159 | -prop_union_superset (rs1, rs2 :: RSet Double) = |

1160 | +prop_union_superset (rs1, rs2 :: RSet Integer) = |

1161 | hunk ./Data/Ranged/RangedSet.hs 473 |

1162 | -prop_intersection_subset (rs1, rs2 :: RSet Double) = |

1163 | +prop_intersection_subset (rs1, rs2 :: RSet Integer) = |

1164 | hunk ./Data/Ranged/RangedSet.hs 479 |

1165 | -prop_diff_intersect (rs1, rs2 :: RSet Double) = |

1166 | +prop_diff_intersect (rs1, rs2 :: RSet Integer) = |

1167 | hunk ./Data/Ranged/RangedSet.hs 486 |

1168 | - where types = rs :: RSet Double |

1169 | + where types = rs :: RSet Integer |

1170 | hunk ./Data/Ranged/RangedSet.hs 491 |

1171 | - where types = rs :: RSet Double |

1172 | + where types = rs :: RSet Integer |

1173 | hunk ./Data/Ranged/RangedSet.hs 496 |

1174 | -prop_union_strict_superset (rs1, rs2 :: RSet Double) = |

1175 | +prop_union_strict_superset (rs1, rs2 :: RSet Integer) = |

1176 | hunk ./Data/Ranged/RangedSet.hs 501 |

1177 | -prop_intersection_commutes (rs1, rs2 :: RSet Double) = |

1178 | +prop_intersection_commutes (rs1, rs2 :: RSet Integer) = |

1179 | hunk ./Data/Ranged/RangedSet.hs 505 |

1180 | -prop_union_commutes (rs1, rs2 :: RSet Double) = |

1181 | +prop_union_commutes (rs1, rs2 :: RSet Integer) = |

1182 | hunk ./Data/Ranged/RangedSet.hs 509 |

1183 | -prop_intersection_associates (rs1, rs2, rs3 :: RSet Double) = |

1184 | +prop_intersection_associates (rs1, rs2, rs3 :: RSet Integer) = |

1185 | hunk ./Data/Ranged/RangedSet.hs 513 |

1186 | -prop_union_associates (rs1, rs2, rs3 :: RSet Double) = |

1187 | +prop_union_associates (rs1, rs2, rs3 :: RSet Integer) = |

1188 | hunk ./Data/Ranged/RangedSet.hs 516 |

1189 | +-- De Morgan's Law for Intersection |

1190 | +prop_de_morgan_intersection (rs1, rs2 :: RSet Integer) = |

1191 | + rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2) |

1192 | hunk ./Data/Ranged/RangedSet.hs 520 |

1193 | +-- De Morgan's Law for Union |

1194 | +prop_de_morgan_union (rs1, rs2 :: RSet Integer) = |

1195 | + rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2) |

1196 | hunk ./Data/Ranged/RangedSet.hs 524 |

1197 | - |

1198 | hunk ./Data/Ranged/Ranges.hs 1 |

1199 | -{-# OPTIONS_GHC -fglasgow-exts #-} |

1200 | +{-# OPTIONS_GHC -cpp -fglasgow-exts #-} |

1201 | +----------------------------------------------------------------------------- |

1202 | +-- | |

1203 | +-- Module : Data.Ranged.Ranges |

1204 | +-- Copyright : (c) Paul Johnson 2006 |

1205 | +-- License : BSD-style |

1206 | +-- Maintainer : paul@cogito.org.uk |

1207 | +-- Stability : experimental |

1208 | +-- Portability : portable |

1209 | +-- |

1210 | +----------------------------------------------------------------------------- |

1211 | + |

1212 | hunk ./Data/Ranged/Ranges.hs 31 |

1213 | - -- ** QuickCheck Properties |

1214 | + -- ** QuickCheck properties |

1215 | hunk ./Data/Ranged/Ranges.hs 69 |

1216 | - BoundaryAbove v -> " <=" ++ show v |

1217 | + BoundaryAbove v -> " <= " ++ show v |

1218 | hunk ./Data/Ranged/Ranges.hs 93 |

1219 | + |

1220 | hunk ./Data/Ranged/Ranges.hs 106 |

1221 | - |

1222 | + |

1223 | + |

1224 | hunk ./Data/Ranged/Ranges.hs 111 |

1225 | - |

1226 | hunk ./Data/Ranged/Ranges.hs 138 |

1227 | - |

1228 | --- | @range1@ minus @range2@. Zero, one or two results. |

1229 | + |

1230 | + |

1231 | +-- | @range1@ minus @range2@. Returns zero, one or two results. Multiple |

1232 | +-- results are guaranteed to have non-empty gaps in between, but may not be in |

1233 | +-- ascending order. |

1234 | hunk ./Data/Ranged/Ranges.hs 160 |

1235 | - |

1236 | + |

1237 | + |

1238 | hunk ./Data/Ranged/Ranges.hs 222 |

1239 | + |

1240 | hunk ./Data/Ranged.hs 13 |

1241 | +----------------------------------------------------------------------------- |

1242 | } |

1243 | |

1244 | Context: |

1245 | |

1246 | [redefine writeFile and appendFile using withFile |

1247 | Ross Paterson <ross@soi.city.ac.uk>**20061107140359] |

1248 | [add withFile and withBinaryFile (#966) |

1249 | Ross Paterson <ross@soi.city.ac.uk>**20061107134510] |

1250 | [remove conflicting import for nhc98 |

1251 | Malcolm.Wallace@cs.york.ac.uk**20061108111215] |

1252 | [Add intercalate to Data.List (ticket #971) |

1253 | Josef Svenningsson <josef.svenningsson@gmail.com>**20061102122052] |

1254 | [non-GHC: fix canonicalizeFilePath |

1255 | Ross Paterson <ross@soi.city.ac.uk>**20061107133902 |

1256 | |

1257 | I've also removed the #ifdef __GLASGOW_HASKELL__ from the proper |

1258 | Windows versions of a few functions. These will need testing with |

1259 | Hugs on Windows. |

1260 | ] |

1261 | [enable canonicalizePath for non-GHC platforms |

1262 | Simon Marlow <simonmar@microsoft.com>**20061107121141] |

1263 | [Update documentation for hWaitForInput |

1264 | Simon Marlow <simonmar@microsoft.com>**20061107111430 |

1265 | See #972 |

1266 | Merge to 6.6 branch. |

1267 | ] |

1268 | [Use unchecked shifts to implement Data.Bits.rotate |

1269 | Samuel Bronson <naesten@gmail.com>**20061012125553 |

1270 | This should get rid of those cases, maybe lower the size enough that the inliner will like it? |

1271 | ] |

1272 | [fix Haddock module headers |

1273 | Ross Paterson <ross@soi.city.ac.uk>**20061106124140] |

1274 | [fix example in docs |

1275 | Ross Paterson <ross@soi.city.ac.uk>**20061106115628] |

1276 | [Add intercalate and split to Data.List |

1277 | Josef Svenningsson <josef.svenningsson@gmail.com>*-20061024172357] |

1278 | [Data.Generics.Basics is GHC-only |

1279 | Ross Paterson <ross@soi.city.ac.uk>**20061102111736] |

1280 | [#ifdef around non-portable Data.Generics.Basics |

1281 | Malcolm.Wallace@cs.york.ac.uk**20061102103445] |

1282 | [Add deriving Data to Complex |

1283 | simonpj@microsoft**20061101102059] |

1284 | [minor clarification of RandomGen doc |

1285 | Ross Paterson <ross@soi.city.ac.uk>**20061030230842] |

1286 | [rearrange docs a bit |

1287 | Ross Paterson <ross@soi.city.ac.uk>**20061030161223] |

1288 | [Add intercalate and split to Data.List |

1289 | Josef Svenningsson <josef.svenningsson@gmail.com>**20061024172357] |

1290 | [Export pseq from Control.Parallel, and use it in Control.Parallel.Strategies |

1291 | Simon Marlow <simonmar@microsoft.com>**20061027150141] |

1292 | [`par` should be infixr 0 |

1293 | Simon Marlow <simonmar@microsoft.com>**20061027130800 |

1294 | Alas, I didn't spot this due to lack of testing, and the symptom is |

1295 | that an expression like x `par` y `seq z will have exactly the wrong |

1296 | parallelism properties. The workaround is to add parantheses. |

1297 | |

1298 | I think we could push this to the 6.6 branch. |

1299 | ] |

1300 | [fix example in comment |

1301 | Ross Paterson <ross@soi.city.ac.uk>**20061023163925] |

1302 | [Use the new Any type for dynamics (GHC only) |

1303 | simonpj@microsoft**20061019160408] |

1304 | [add Data.Sequence to nhc98 build |

1305 | Malcolm.Wallace@cs.york.ac.uk**20061012135200] |

1306 | [Remove Data.FiniteMap, add Control.Applicative, Data.Traversable, and |

1307 | Malcolm.Wallace@cs.york.ac.uk**20061012095605 |

1308 | Data.Foldable to the nhc98 build. |

1309 | ] |

1310 | [STM invariants |

1311 | tharris@microsoft.com**20061007123253] |

1312 | [Inline shift in GHC's Bits instances for {Int,Word}{,8,16,32,64} |

1313 | Samuel Bronson <naesten@gmail.com>**20061009020906] |

1314 | [Don't create GHC.Prim when bootstrapping; we can't, and we don't need it |

1315 | Ian Lynagh <igloo@earth.li>**20061004165355] |

1316 | [Data.ByteString: fix lazyness of take, drop & splitAt |

1317 | Don Stewart <dons@cse.unsw.edu.au>**20061005011703 |

1318 | |

1319 | ByteString.Lazy's take, drop and splitAt were too strict when demanding |

1320 | a byte string. Spotted by Einar Karttunen. Thanks to him and to Bertram |

1321 | Felgenhauer for explaining the problem and the fix. |

1322 | |

1323 | ] |

1324 | [Fix syntax error that prevents building Haddock documentation on Windows |

1325 | brianlsmith@gmail.com**20060917013530] |

1326 | [Hugs only: unbreak typeRepKey |

1327 | Ross Paterson <ross@soi.city.ac.uk>**20060929102743] |

1328 | [make hGetBufNonBlocking do something on Windows w/ -threaded |

1329 | Simon Marlow <simonmar@microsoft.com>**20060927145811 |

1330 | hGetBufNonBlocking will behave the same as hGetBuf on Windows now, which |

1331 | is better than just crashing (which it did previously). |

1332 | ] |

1333 | [add typeRepKey :: TypeRep -> IO Int |

1334 | Simon Marlow <simonmar@microsoft.com>**20060927100342 |

1335 | See feature request #880 |

1336 | ] |

1337 | [fix header comment |

1338 | Ross Paterson <ross@soi.city.ac.uk>**20060926135843] |

1339 | [Add strict versions of insertWith and insertWithKey (Data.Map) |

1340 | jeanphilippe.bernardy@gmail.com**20060910162443] |

1341 | [doc tweaks, including more precise equations for evaluate |

1342 | Ross Paterson <ross@soi.city.ac.uk>**20060910115259] |

1343 | [Sync Data.ByteString with stable branch |

1344 | Don Stewart <dons@cse.unsw.edu.au>**20060909050111 |

1345 | |

1346 | This patch: |

1347 | * hides the LPS constructor (its in .Base if you need it) |

1348 | * adds functions to convert between strict and lazy bytestrings |

1349 | * and adds readInteger |

1350 | |

1351 | ] |

1352 | [Typeable1 instances for STM and TVar |

1353 | Ross Paterson <ross@soi.city.ac.uk>**20060904231425] |

1354 | [remove obsolete Hugs stuff |

1355 | Ross Paterson <ross@soi.city.ac.uk>**20060904223944] |

1356 | [Cleaner isInfixOf suggestion from Ross Paterson |

1357 | John Goerzen <jgoerzen@complete.org>**20060901143654] |

1358 | [New function isInfixOf that searches a list for a given sublist |

1359 | John Goerzen <jgoerzen@complete.org>**20060831151556 |

1360 | |

1361 | Example: |

1362 | |

1363 | isInfixOf "Haskell" "I really like Haskell." -> True |

1364 | isInfixOf "Ial" "I really like Haskell." -> False |

1365 | |

1366 | This function was first implemented in MissingH as MissingH.List.contains |

1367 | ] |

1368 | [Better doc on Data.Map.lookup: explain what the monad is for |

1369 | jeanphilippe.bernardy@gmail.com**20060903133440] |

1370 | [fix hDuplicateTo on Windows |

1371 | Simon Marlow <simonmar@microsoft.com>**20060901150016 |

1372 | deja vu - I'm sure I remember fixing this before... |

1373 | ] |

1374 | [Improve documentation of atomically |

1375 | simonpj@microsoft**20060714120207] |

1376 | [Add missing method genRange for StdGen (fixes #794) |

1377 | simonpj@microsoft**20060707151901 |

1378 | |

1379 | MERGE TO STABLE |

1380 | |

1381 | Trac #794 reports (correctly) that the implementation of StdGen |

1382 | only returns numbers in the range (0..something) rather than |

1383 | (minBound, maxBound), which is what StdGen's genRange claims. |

1384 | |

1385 | This commit fixes the problem, by implementing genRange for StdGen |

1386 | (previously it just used the default method). |

1387 | |

1388 | |

1389 | ] |

1390 | [mark nhc98 import hack |

1391 | Ross Paterson <ross@soi.city.ac.uk>**20060831125219] |

1392 | [remove some outdated comments |

1393 | Simon Marlow <simonmar@microsoft.com>**20060831104200] |

1394 | [import Control.Arrow.ArrowZero to help nhc98's type checker |

1395 | Malcolm.Wallace@cs.york.ac.uk**20060831101105] |

1396 | [remove Text.Regex(.Posix) from nhc98 build |

1397 | Malcolm.Wallace@cs.york.ac.uk**20060831101016] |

1398 | [add Data.Foldable.{msum,asum}, plus tweaks to comments |

1399 | Ross Paterson <ross@soi.city.ac.uk>**20060830163521] |

1400 | [fix doc typo |

1401 | Ross Paterson <ross@soi.city.ac.uk>**20060830134123] |

1402 | [add Data.Foldable.{for_,forM_} and Data.Traversable.{for,forM} |

1403 | Ross Paterson <ross@soi.city.ac.uk>**20060830133805 |

1404 | |

1405 | generalizing Control.Monad.{forM_,forM} |

1406 | ] |

1407 | [Make length a good consumer |

1408 | simonpj@microsoft*-20060508142726 |

1409 | |

1410 | Make length into a good consumer. Fixes Trac bug #707. |

1411 | |

1412 | (Before length simply didn't use foldr.) |

1413 | |

1414 | ] |

1415 | [Add Control.Monad.forM and forM_ |

1416 | Don Stewart <dons@cse.unsw.edu.au>**20060824081118 |

1417 | |

1418 | flip mapM_ is more and more common, I find. Several suggestions have |

1419 | been made to add this, as foreach or something similar. This patch |

1420 | does just that: |

1421 | |

1422 | forM :: (Monad m) => [a] -> (a -> m b) -> m [b] |

1423 | forM_ :: (Monad m) => [a] -> (a -> m b) -> m () |

1424 | |

1425 | So we can write: |

1426 | |

1427 | Prelude Control.Monad> forM_ [1..4] $ \x -> print x |

1428 | 1 |

1429 | 2 |

1430 | 3 |

1431 | 4 |

1432 | |

1433 | ] |

1434 | [Hide internal module from haddock in Data.ByteString |

1435 | Don Stewart <dons@cse.unsw.edu.au>**20060828011515] |

1436 | [add advice on avoiding import ambiguities |

1437 | Ross Paterson <ross@soi.city.ac.uk>**20060827170407] |

1438 | [expand advice on importing these modules |

1439 | Ross Paterson <ross@soi.city.ac.uk>**20060827164044] |

1440 | [add Haddock marker |

1441 | Ross Paterson <ross@soi.city.ac.uk>**20060827115140] |

1442 | [Clarify how one hides Prelude.catch |

1443 | Don Stewart <dons@cse.unsw.edu.au>**20060826124346 |

1444 | |

1445 | User feedback indicated that an example was required, of how to hide |

1446 | Prelude.catch, so add such an example to the docs |

1447 | |

1448 | ] |

1449 | [Workaround for OSes that don't have intmax_t and uintmax_t |

1450 | Ian Lynagh <igloo@earth.li>**20060825134936 |

1451 | OpenBSD (and possibly others) do not have intmax_t and uintmax_t types: |

1452 | http://www.mail-archive.com/haskell-prime@haskell.org/msg01548.html |

1453 | so substitute (unsigned) long long if we have them, otherwise |

1454 | (unsigned) long. |

1455 | |

1456 | ] |

1457 | [add docs for par |

1458 | Simon Marlow <simonmar@microsoft.com>**20060825110610] |

1459 | [document minimal complete definition for Bits |

1460 | Ross Paterson <ross@soi.city.ac.uk>**20060824140504] |

1461 | [C regex library bits have moved to the regex-posix package |

1462 | Simon Marlow <simonmar@microsoft.com>**20060824132311] |

1463 | [Add shared Typeable support (ghc only) |

1464 | Esa Ilari Vuokko <ei@vuokko.info>**20060823003126] |

1465 | [this should have been removed with the previous patch |

1466 | Simon Marlow <simonmar@microsoft.com>**20060824121223] |

1467 | [remove Text.Regx & Text.Regex.Posix |

1468 | Simon Marlow <simonmar@microsoft.com>**20060824094615 |

1469 | These are subsumed by the new regex-base, regex-posix and regex-compat |

1470 | packages. |

1471 | ] |

1472 | [explicitly tag Data.ByteString rules with the FPS prefix. |

1473 | Don Stewart <dons@cse.unsw.edu.au>**20060824041326] |

1474 | [Add spec rules for sections in Data.ByteString |

1475 | Don Stewart <dons@cse.unsw.edu.au>**20060824012611] |

1476 | [Sync Data.ByteString with current stable branch, 0.7 |

1477 | Don Stewart <dons@cse.unsw.edu.au>**20060823143338] |

1478 | [add notes about why copyFile doesn't remove the target |

1479 | Simon Marlow <simonmar@microsoft.com>**20060823095059] |

1480 | [copyFile: try removing the target file before opening it for writing |

1481 | Simon Marlow <simonmar@microsoft.com>*-20060822121909] |

1482 | [copyFile: try removing the target file before opening it for writing |

1483 | Simon Marlow <simonmar@microsoft.com>**20060822121909] |

1484 | [add alternative functors and extra instances |

1485 | Ross Paterson <ross@soi.city.ac.uk>**20060821152151 |

1486 | |

1487 | * Alternative class, for functors with a monoid |

1488 | * instances for Const |

1489 | * instances for arrows |

1490 | ] |

1491 | [generate Haddock docs on all platforms |

1492 | Simon Marlow <simonmar@microsoft.com>**20060821131612] |

1493 | [remove extra comma from import |

1494 | Ross Paterson <ross@soi.city.ac.uk>**20060819173954] |

1495 | [fix docs for withC(A)StringLen |

1496 | Ross Paterson <ross@soi.city.ac.uk>**20060818170328] |

1497 | [use Haskell'98 compliant indentation in do blocks |

1498 | Malcolm.Wallace@cs.york.ac.uk**20060818130810] |

1499 | [use correct names of IOArray operations for nhc98 |

1500 | Malcolm.Wallace@cs.york.ac.uk**20060818130714] |

1501 | [add mapMaybe and mapEither, plus WithKey variants |

1502 | Ross Paterson <ross@soi.city.ac.uk>**20060817235041] |

1503 | [remove Text.Html from nhc98 build |

1504 | Malcolm.Wallace@cs.york.ac.uk**20060817135502] |

1505 | [eliminate more HOST_OS tests |

1506 | Ross Paterson <ross@soi.city.ac.uk>**20060815190609] |

1507 | [Hugs only: disable unused process primitives |

1508 | Ross Paterson <ross@soi.city.ac.uk>**20060813184435 |

1509 | |

1510 | These were the cause of Hugs bug #30, I think, and weren't used by Hugs anyway. |

1511 | ] |

1512 | [markup fix to Data.HashTable |

1513 | Ross Paterson <ross@soi.city.ac.uk>**20060812103835] |

1514 | [revert removal of ghcconfig.h from package.conf.in |

1515 | Ross Paterson <ross@soi.city.ac.uk>**20060812082702 |

1516 | |

1517 | as it's preprocessed with -undef (pointed out by Esa Ilari Vuokko) |

1518 | ] |

1519 | [fix Data.HashTable for non-GHC |

1520 | Ross Paterson <ross@soi.city.ac.uk>**20060811231521] |

1521 | [remove deprecated 'withObject' |

1522 | Simon Marlow <simonmar@microsoft.com>**20060811152350] |

1523 | [Jan-Willem Maessen's improved implementation of Data.HashTable |

1524 | Simon Marlow <simonmar@microsoft.com>**20060811151024 |

1525 | Rather than incrementally enlarging the hash table, this version |

1526 | just does it in one go when the table gets too full. |

1527 | ] |

1528 | [Warning police: Make some prototypes from the RTS known |

1529 | sven.panne@aedion.de**20060811144629] |

1530 | [Warning police: Removed useless catch-all clause |

1531 | sven.panne@aedion.de**20060811142208] |

1532 | [reduce dependency on ghcconfig.h |

1533 | Ross Paterson <ross@soi.city.ac.uk>**20060811124030 |

1534 | |

1535 | The only remaining use is in cbits/dirUtils.h, which tests solaris2_HOST_OS |

1536 | |

1537 | (Also System.Info uses ghcplatform.h and several modules import MachDeps.h |

1538 | to get SIZEOF_* and ALIGNMENT_* from ghcautoconf.h) |

1539 | ] |

1540 | [(non-GHC only) track MArray interface change |

1541 | Ross Paterson <ross@soi.city.ac.uk>**20060810182902] |

1542 | [move Text.Html to a separate package |

1543 | Simon Marlow <simonmar@microsoft.com>**20060810113017] |

1544 | [bump version to 2.0 |

1545 | Simon Marlow <simonmar@microsoft.com>**20060810112833] |

1546 | [Remove deprecated Data.FiniteMap and Data.Set interfaces |

1547 | Simon Marlow <simonmar@microsoft.com>**20060809153810] |

1548 | [move altzone test from ghc to base package |

1549 | Ross Paterson <ross@soi.city.ac.uk>**20060809124259] |

1550 | [remove unnecessary #include "ghcconfig.h" |

1551 | Ross Paterson <ross@soi.city.ac.uk>**20060809123812] |

1552 | [Change the API of MArray to allow resizable arrays |

1553 | Simon Marlow <simonmar@microsoft.com>**20060809100548 |

1554 | See #704 |

1555 | |

1556 | The MArray class doesn't currently allow a mutable array to change its |

1557 | size, because of the pure function |

1558 | |

1559 | bounds :: (HasBounds a, Ix i) => a i e -> (i,i) |

1560 | |

1561 | This patch removes the HasBounds class, and adds |

1562 | |

1563 | getBounds :: (MArray a e m, Ix i) => a i e -> m (i,i) |

1564 | |

1565 | to the MArray class, and |

1566 | |

1567 | bounds :: (IArray a e, Ix i) => a i e -> (i,i) |

1568 | |

1569 | to the IArray class. |

1570 | |

1571 | The reason that bounds had to be incorporated into the IArray class is |

1572 | because I couldn't make DiffArray work without doing this. DiffArray |

1573 | acts as a layer converting an MArray into an IArray, and there was no |

1574 | way (that I could find) to define an instance of HasBounds for |

1575 | DiffArray. |

1576 | ] |

1577 | [deprecate this module. |

1578 | Simon Marlow <simonmar@microsoft.com>**20060808100708] |

1579 | [add traceShow (see #474) |

1580 | Simon Marlow <simonmar@microsoft.com>**20060807155545] |

1581 | [remove spurious 'extern "C" {' |

1582 | Simon Marlow <simonmar@microsoft.com>**20060724160258] |

1583 | [Fix unsafeIndex for large ranges |

1584 | Simon Marlow <simonmar@microsoft.com>**20060721100225] |

1585 | [disambiguate uses of foldr for nhc98 to compile without errors |

1586 | Malcolm.Wallace@cs.york.ac.uk**20060711161614] |

1587 | [make Control.Monad.Instances compilable by nhc98 |

1588 | Malcolm.Wallace@cs.york.ac.uk**20060711160941] |

1589 | [breakpointCond |

1590 | Lemmih <lemmih@gmail.com>**20060708055528] |

1591 | [UNDO: Merge "unrecognized long opt" fix from 6.4.2 |

1592 | Simon Marlow <simonmar@microsoft.com>**20060705142537 |

1593 | This patch undid the previous patch, "RequireOrder: do not collect |

1594 | unrecognised options after a non-opt". I asked Sven to revert it, but |

1595 | didn't get an answer. |

1596 | |

1597 | See bug #473. |

1598 | ] |

1599 | [Avoid strictness in accumulator for unpackFoldr |

1600 | Don Stewart <dons@cse.unsw.edu.au>**20060703091806 |

1601 | |

1602 | The seq on the accumulator for unpackFoldr will break in the presence of |

1603 | head/build rewrite rules. The empty list case will be forced, producing |

1604 | an exception. This is a known issue with seq and rewrite rules that we |

1605 | just stumbled on to. |

1606 | |

1607 | ] |

1608 | [Disable unpack/build fusion |

1609 | Don Stewart <dons@cse.unsw.edu.au>**20060702083913 |

1610 | |

1611 | unpack/build on bytestrings seems to trigger a bug when interacting with |

1612 | head/build fusion in GHC.List. The bytestring001 testcase catches it. |

1613 | |

1614 | I'll investigate further, but best to disable this for now (its not |

1615 | often used anyway). |

1616 | |

1617 | Note that with -frules-off or ghc 6.4.2 things are fine. It seems to |

1618 | have emerged with the recent rules changes. |

1619 | |

1620 | ] |

1621 | [Import Data.ByteString.Lazy, improve ByteString Fusion, and resync with FPS head |

1622 | Don Stewart <dons@cse.unsw.edu.au>**20060701084345 |

1623 | |

1624 | This patch imports the Data.ByteString.Lazy module, and its helpers, |

1625 | providing a ByteString implemented as a lazy list of strict cache-sized |

1626 | chunks. This type allows the usual lazy operations to be written on |

1627 | bytestrings, including lazy IO, with much improved space and time over |

1628 | the [Char] equivalents. |

1629 | |

1630 | ] |

1631 | [Wibble in docs for new ForeignPtr functionsn |

1632 | Don Stewart <dons@cse.unsw.edu.au>**20060609075924] |

1633 | [comments for Applicative and Traversable |

1634 | Ross Paterson <ross@soi.city.ac.uk>**20060622170436] |

1635 | [default to NoBuffering on Windows for a read/write text file |

1636 | Simon Marlow <simonmar@microsoft.com>**20060622144446 |

1637 | Fixes (works around) #679 |

1638 | ] |

1639 | [remove dead code |

1640 | Simon Marlow <simonmar@microsoft.com>**20060622144433] |

1641 | [clarify and expand docs |

1642 | Simon Marlow <simonmar@microsoft.com>**20060622112911] |

1643 | [Add minView and maxView to Map and Set |

1644 | jeanphilippe.bernardy@gmail.com**20060616180121] |

1645 | [add signature for registerDelay |

1646 | Ross Paterson <ross@soi.city.ac.uk>**20060614114456] |

1647 | [a few doc comments |

1648 | Ross Paterson <ross@soi.city.ac.uk>**20060613142704] |

1649 | [Optimised foreign pointer representation, for heap-allocated objects |

1650 | Don Stewart <dons@cse.unsw.edu.au>**20060608015011] |

1651 | [Add the inline function, and many comments |

1652 | simonpj@microsoft.com**20060605115814 |

1653 | |

1654 | This commit adds the 'inline' function described in the |

1655 | related patch in the compiler. |

1656 | |

1657 | I've also added comments about the 'lazy' function. |

1658 | |

1659 | ] |

1660 | [small intro to exceptions |

1661 | Ross Paterson <ross@soi.city.ac.uk>**20060525111604] |

1662 | [export breakpoint |

1663 | Simon Marlow <simonmar@microsoft.com>**20060525090456] |

1664 | [Merge in changes from fps head. Highlights: |

1665 | Don Stewart <dons@cse.unsw.edu.au>**20060525065012 |

1666 | |

1667 | Wed May 24 15:49:38 EST 2006 sjanssen@cse.unl.edu |

1668 | * instance Monoid ByteString |

1669 | |

1670 | Wed May 24 15:04:04 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1671 | * Rearange export lists for the .Char8 modules |

1672 | |

1673 | Wed May 24 14:59:56 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1674 | * Implement mapAccumL and reimplement mapIndexed using loopU |

1675 | |

1676 | Wed May 24 14:47:32 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1677 | * Change the implementation of the unfoldr(N) functions. |

1678 | Use a more compact implementation for unfoldrN and change it's behaviour |

1679 | to only return Just in the case that it actually 'overflowed' the N, so |

1680 | the boundary case of unfolding exactly N gives Nothing. |

1681 | Implement unfoldr and Lazy.unfoldr in terms of unfoldrN. Use fibonacci |

1682 | growth for the chunk size in unfoldr |

1683 | |

1684 | Wed May 24 08:32:29 EST 2006 sjanssen@cse.unl.edu |

1685 | * Add unfoldr to ByteString and .Char8 |

1686 | A preliminary implementation of unfoldr. |

1687 | |

1688 | Wed May 24 01:39:41 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1689 | * Reorder the export lists to better match the Data.List api |

1690 | |

1691 | Tue May 23 14:04:32 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1692 | * pack{Byte,Char} -> singleton. As per fptools convention |

1693 | |

1694 | Tue May 23 14:00:51 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1695 | * elemIndexLast -> elemIndexEnd |

1696 | |

1697 | Tue May 23 13:57:34 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1698 | * In the search for a more orthogonal api, we kill breakFirst/breakLast, |

1699 | which were of dubious value |

1700 | |

1701 | Tue May 23 12:24:09 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1702 | * Abolish elems. It's name implied it was unpack, but its type didn't. it made no sense |

1703 | |

1704 | Tue May 23 10:42:09 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1705 | * Minor doc tidyup. Use haddock markup better. |

1706 | |

1707 | Tue May 23 11:00:31 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1708 | * Simplify the join() implementation. Spotted by Duncan. |

1709 | |

1710 | ] |

1711 | [add a way to ask the IO manager thread to exit |

1712 | Simon Marlow <simonmar@microsoft.com>**20060524121823] |

1713 | [Sync with FPS head, including the following patches: |

1714 | Don Stewart <dons@cse.unsw.edu.au>**20060520030436 |

1715 | |

1716 | Thu May 18 15:45:46 EST 2006 sjanssen@cse.unl.edu |

1717 | * Export unsafeTake and unsafeDrop |

1718 | |

1719 | Fri May 19 11:53:08 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1720 | * Add foldl1' |

1721 | |

1722 | Fri May 19 13:41:24 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1723 | * Add fuseable scanl, scanl1 + properties |

1724 | |

1725 | Fri May 19 18:20:40 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1726 | * Spotted another chance to use unsafeTake,Drop (in groupBy) |

1727 | |

1728 | Thu May 18 09:24:25 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1729 | * More effecient findIndexOrEnd based on the impl of findIndex |

1730 | |

1731 | Thu May 18 09:22:49 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1732 | * Eliminate special case in findIndex since it's handled anyway. |

1733 | |

1734 | Thu May 18 09:19:08 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1735 | * Add unsafeTake and unsafeDrop |

1736 | These versions assume the n is in the bounds of the bytestring, saving |

1737 | two comparison tests. Then use them in varous places where we think this |

1738 | holds. These cases need double checking (and there are a few remaining |

1739 | internal uses of take / drop that might be possible to convert). |

1740 | Not exported for the moment. |

1741 | |

1742 | Tue May 16 23:15:11 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1743 | * Handle n < 0 in drop and splitAt. Spotted by QC. |

1744 | |

1745 | Tue May 16 22:46:22 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1746 | * Handle n <= 0 cases for unfoldr and replicate. Spotted by QC |

1747 | |

1748 | Tue May 16 21:34:11 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1749 | * mapF -> map', filterF -> filter' |

1750 | |

1751 | ] |

1752 | [haddock fix |

1753 | Ross Paterson <ross@soi.city.ac.uk>**20060518154723] |

1754 | [simplify indexing in Data.Sequence |

1755 | Ross Paterson <ross@soi.city.ac.uk>**20060518154316] |

1756 | [Move Eq, Ord, Show instances for ThreadId to GHC.Conc |

1757 | Simon Marlow <simonmar@microsoft.com>**20060518113339 |

1758 | Eliminates orphans. |

1759 | ] |

1760 | [Better error handling in the IO manager thread |

1761 | Simon Marlow <simonmar@microsoft.com>**20060518113303 |

1762 | In particular, handle EBADF just like rts/posix/Select.c, by waking up |

1763 | all the waiting threads. Other errors are thrown, instead of just |

1764 | being ignored. |

1765 | ] |

1766 | [#define _REENTRANT 1 (needed to get the right errno on some OSs) |

1767 | Simon Marlow <simonmar@microsoft.com>**20060518104151 |

1768 | Part 2 of the fix for threaded RTS problems on Solaris and possibly |

1769 | *BSD (Part 1 was the same change in ghc/includes/Rts.h). |

1770 | ] |

1771 | [copyCString* should be in IO. Spotted by Tomasz Zielonka |

1772 | Don Stewart <dons@cse.unsw.edu.au>**20060518012154] |

1773 | [add import Prelude to get dependencies right for Data/Fixed.hs |

1774 | Duncan Coutts <duncan.coutts@worc.ox.ac.uk>**20060517222044 |

1775 | Hopefully this fixes parallel builds. |

1776 | ] |

1777 | [Fix negative index handling in splitAt, replicate and unfoldrN. Move mapF, filterF -> map', filter' while we're here |

1778 | Don Stewart <dons@cse.unsw.edu.au>**20060517020150] |

1779 | [Use our own realloc. Thus reduction functions (like filter) allocate on the Haskell heap. Makes around 10% difference. |

1780 | Don Stewart <dons@cse.unsw.edu.au>**20060513051736] |

1781 | [Last two CInt fixes for 64 bit, and bracket writeFile while we're here |

1782 | Don Stewart <dons@cse.unsw.edu.au>**20060512050750] |

1783 | [Some small optimisations, generalise the type of unfold |

1784 | Don Stewart <dons@cse.unsw.edu.au>**20060510043309 |

1785 | |

1786 | Tue May 9 22:36:29 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1787 | * Surely the error function should not be inlined. |

1788 | |

1789 | Tue May 9 22:35:53 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1790 | * Reorder memory writes for better cache locality. |

1791 | |

1792 | Tue May 9 23:28:09 EST 2006 Duncan Coutts <duncan.coutts@worc.ox.ac.uk> |

1793 | * Generalise the type of unfoldrN |

1794 | |

1795 | The type of unfoldrN was overly constrained: |

1796 | unfoldrN :: Int -> (Word8 -> Maybe (Word8, Word8)) -> Word8 -> ByteString |

1797 | |

1798 | if we compare that to unfoldr: |

1799 | unfoldr :: (b -> Maybe (a, b)) -> b -> [a] |

1800 | |

1801 | So we can generalise unfoldrN to this type: |

1802 | unfoldrN :: Int -> (a -> Maybe (Word8, a)) -> a -> ByteString |

1803 | |

1804 | and something similar for the .Char8 version. If people really do want to |

1805 | use it a lot with Word8/Char then perhaps we should add a specialise pragma. |

1806 | |

1807 | Wed May 10 13:26:40 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1808 | * Add foldl', and thus a fusion rule for length . {map,filter,fold}, |

1809 | that avoids creating an array at all if the end of the pipeline is a 'length' reduction |

1810 | |

1811 | **END OF DESCRIPTION*** |

1812 | |

1813 | Place the long patch description above the ***END OF DESCRIPTION*** marker. |

1814 | The first line of this file will be the patch name. |

1815 | |

1816 | |

1817 | This patch contains the following changes: |

1818 | |

1819 | M ./Data/ByteString.hs -8 +38 |

1820 | M ./Data/ByteString/Char8.hs -6 +12 |

1821 | ] |

1822 | [portable implementation of WordPtr/IntPtr for non-GHC |

1823 | Ross Paterson <ross@soi.city.ac.uk>**20060510001826 |

1824 | |

1825 | plus much tweaking of imports to avoid cycles |

1826 | ] |

1827 | [add WordPtr and IntPtr types to Foreign.Ptr, with associated conversions |

1828 | Simon Marlow <simonmar@microsoft.com>**20060509092606 |

1829 | |

1830 | As suggested by John Meacham. |

1831 | |

1832 | I had to move the Show instance for Ptr into GHC.ForeignPtr to avoid |

1833 | recursive dependencies. |

1834 | ] |

1835 | [add CIntPtr, CUIntPtr, CIntMax, CUIntMax types |

1836 | Simon Marlow <simonmar@microsoft.com>**20060509092427] |

1837 | [add GHC.Dynamic |

1838 | Simon Marlow <simonmar@microsoft.com>**20060509082739] |

1839 | [Two things. #if defined(__GLASGOW_HASKELL__) on INLINE [n] pragmas (for jhc). And careful use of INLINE on words/unwords halves runtime for those functions |

1840 | Don Stewart <dons@cse.unsw.edu.au>**20060509023425] |

1841 | [Make length a good consumer |

1842 | simonpj@microsoft**20060508142726 |

1843 | |

1844 | Make length into a good consumer. Fixes Trac bug #707. |

1845 | |

1846 | (Before length simply didn't use foldr.) |

1847 | |

1848 | ] |

1849 | [Trim imports |

1850 | simonpj@microsoft**20060508142557] |

1851 | [Make unsafePerformIO lazy |

1852 | simonpj@microsoft**20060508142507 |

1853 | |

1854 | The stricteness analyser used to have a HACK which ensured that NOINLNE things |

1855 | were not strictness-analysed. The reason was unsafePerformIO. Left to itself, |

1856 | the strictness analyser would discover this strictness for unsafePerformIO: |

1857 | unsafePerformIO: C(U(AV)) |

1858 | But then consider this sub-expression |

1859 | unsafePerformIO (\s -> let r = f x in |

1860 | case writeIORef v r s of (# s1, _ #) -> |

1861 | (# s1, r #) |

1862 | The strictness analyser will now find that r is sure to be eval'd, |

1863 | and may then hoist it out. This makes tests/lib/should_run/memo002 |

1864 | deadlock. |

1865 | |

1866 | Solving this by making all NOINLINE things have no strictness info is overkill. |

1867 | In particular, it's overkill for runST, which is perfectly respectable. |

1868 | Consider |

1869 | f x = runST (return x) |

1870 | This should be strict in x. |

1871 | |

1872 | So the new plan is to define unsafePerformIO using the 'lazy' combinator: |

1873 | |

1874 | unsafePerformIO (IO m) = lazy (case m realWorld# of (# _, r #) -> r) |

1875 | |

1876 | Remember, 'lazy' is a wired-in identity-function Id, of type a->a, which is |

1877 | magically NON-STRICT, and is inlined after strictness analysis. So |

1878 | unsafePerformIO will look non-strict, and that's what we want. |

1879 | |

1880 | ] |

1881 | [Sync with FPS head. |

1882 | Don Stewart <dons@cse.unsw.edu.au>**20060508122322 |

1883 | |

1884 | Mon May 8 10:40:14 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1885 | * Fix all uses for Int that should be CInt or CSize in ffi imports. |

1886 | Spotted by Igloo, dcoutts |

1887 | |

1888 | Mon May 8 16:09:41 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1889 | * Import nicer loop/loop fusion rule from ghc-ndp |

1890 | |

1891 | Mon May 8 17:36:07 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1892 | * Fix stack leak in split on > 60M strings |

1893 | |

1894 | Mon May 8 17:50:13 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1895 | * Try same fix for stack overflow in elemIndices |

1896 | |

1897 | ] |

1898 | [Fix all uses for Int that should be CInt or CSize in ffi imports. Spotted by Duncan and Ian |

1899 | Don Stewart <dons@cse.unsw.edu.au>**20060508010311] |

1900 | [Fixed import list syntax |

1901 | Sven Panne <sven.panne@aedion.de>**20060507155008] |

1902 | [Faster filterF, filterNotByte |

1903 | dons@cse.unsw.edu.au**20060507042301] |

1904 | [Much faster find, findIndex. Hint from sjanssen |

1905 | dons@cse.unsw.edu.au**20060507033048] |

1906 | [Merge "unrecognized long opt" fix from 6.4.2 |

1907 | Sven Panne <sven.panne@aedion.de>**20060506110519] |

1908 | [ |

1909 | dons@cse.unsw.edu.au**20060506061029 |

1910 | Sat May 6 13:01:34 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1911 | * Do loopU realloc on the Haskell heap. And add a really tough stress test |

1912 | |

1913 | Sat May 6 12:28:58 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1914 | * Use simple, 3x faster concat. Plus QC properties. Suggested by sjanssen and dcoutts |

1915 | |

1916 | Sat May 6 15:59:31 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1917 | * dcoutt's packByte bug squashed |

1918 | |

1919 | With inlinePerformIO, ghc head was compiling: |

1920 | |

1921 | packByte 255 `compare` packByte 127 |

1922 | |

1923 | into roughly |

1924 | |

1925 | case mallocByteString 2 of |

1926 | ForeignPtr f internals -> |

1927 | case writeWord8OffAddr# f 0 255 of _ -> |

1928 | case writeWord8OffAddr# f 0 127 of _ -> |

1929 | case eqAddr# f f of |

1930 | False -> case compare (GHC.Prim.plusAddr# f 0) |

1931 | (GHC.Prim.plusAddr# f 0) |

1932 | |

1933 | which is rather stunning. unsafePerformIO seems to prevent whatever |

1934 | magic inlining was leading to this. Only affected the head. |

1935 | |

1936 | ] |

1937 | [Add array fusion versions of map, filter and foldl |

1938 | dons@cse.unsw.edu.au**20060505060858 |

1939 | |

1940 | This patch adds fusable map, filter and foldl, using the array fusion |

1941 | code for unlifted, flat arrays, from the Data Parallel Haskell branch, |

1942 | after kind help from Roman Leshchinskiy, |

1943 | |

1944 | Pipelines of maps, filters and folds should now need to walk the |

1945 | bytestring once only, and intermediate bytestrings won't be constructed. |

1946 | |

1947 | ] |

1948 | [fix for non-GHC |

1949 | Ross Paterson <ross@soi.city.ac.uk>**20060504093044] |

1950 | [use bracket in appendFile (like writeFile) |

1951 | Ross Paterson <ross@soi.city.ac.uk>**20060504091528] |

1952 | [writeFile: close the file on error |

1953 | Simon Marlow <simonmar@microsoft.com>**20060504084505 |

1954 | Suggested by Ross Paterson, via Neil Mitchell |

1955 | |

1956 | ] |

1957 | [Sync with FPS head |

1958 | dons@cse.unsw.edu.au**20060503105259 |

1959 | |

1960 | This patch brings Data.ByteString into sync with the FPS head. |

1961 | The most significant of which is the new Haskell counting sort. |

1962 | |

1963 | Changes: |

1964 | |

1965 | Sun Apr 30 18:16:29 EST 2006 sjanssen@cse.unl.edu |

1966 | * Fix foldr1 in Data.ByteString and Data.ByteString.Char8 |

1967 | |

1968 | Mon May 1 11:51:16 EST 2006 Don Stewart <dons@cse.unsw.edu.au> |

1969 | * Add group and groupBy. Suggested by conversation between sjanssen and petekaz on #haskell |

1970 | |

1971 | Mon May 1 16:42:04 EST 2006 sjanssen@cse.unl.edu |

1972 | * Fix groupBy to match Data.List.groupBy. |

1973 | |

1974 | Wed May 3 15:01:07 EST 2006 sjanssen@cse.unl.edu |

1975 | * Migrate to counting sort. |

1976 | |

1977 | Data.ByteString.sort used C's qsort(), which is O(n log n). The new algorithm |

1978 | is O(n), and is faster for strings larger than approximately thirty bytes. We |

1979 | also reduce our dependency on cbits! |

1980 | |

1981 | ] |

1982 | [improve performance of Integer->String conversion |

1983 | Simon Marlow <simonmar@microsoft.com>**20060503113306 |

1984 | See |

1985 | http://www.haskell.org//pipermail/libraries/2006-April/005227.html |

1986 | |

1987 | Submitted by: bertram.felgenhauer@googlemail.com |

1988 | |

1989 | |

1990 | ] |

1991 | [inline withMVar, modifyMVar, modifyMVar_ |

1992 | Simon Marlow <simonmar@microsoft.com>**20060503111152] |

1993 | [Fix string truncating in hGetLine -- it was a pasto from Simon's code |

1994 | Simon Marlow <simonmar@microsoft.com>**20060503103504 |

1995 | (from Don Stewart) |

1996 | ] |

1997 | [Merge in Data.ByteString head. Fixes ByteString+cbits in hugs |

1998 | Don Stewart <dons@cse.unsw.edu.au>**20060429040733] |

1999 | [Import Data.ByteString from fps 0.5. |

2000 | Don Stewart <dons@cse.unsw.edu.au>**20060428130718 |

2001 | Fast, packed byte vectors, providing a better PackedString. |

2002 | |

2003 | ] |

2004 | [fix previous patch |

2005 | Ross Paterson <ross@soi.city.ac.uk>**20060501154847] |

2006 | [fixes for non-GHC |

2007 | Ross Paterson <ross@soi.city.ac.uk>**20060501144322] |

2008 | [fix imports for mingw32 && !GHC |

2009 | Ross Paterson <ross@soi.city.ac.uk>**20060427163248] |

2010 | [RequireOrder: do not collect unrecognised options after a non-opt |

2011 | Simon Marlow <simonmar@microsoft.com>**20060426121110 |

2012 | The documentation for RequireOrder says "no option processing after |

2013 | first non-option", so it doesn't seem right that we should process the |

2014 | rest of the arguments to collect the unrecognised ones. Presumably |

2015 | the client wants to know about the unrecognised options up to the |

2016 | first non-option, and will be using a different option parser for the |

2017 | rest of the command line. |

2018 | |

2019 | eg. before: |

2020 | |

2021 | Prelude System.Console.GetOpt> getOpt' RequireOrder [] ["bar","--foo"] |

2022 | ([],["bar","--foo"],["--foo"],[]) |

2023 | |

2024 | after: |

2025 | |

2026 | Prelude System.Console.GetOpt> getOpt' RequireOrder [] ["bar","--foo"] |

2027 | ([],["bar","--foo"],[],[]) |

2028 | ] |

2029 | [fix for Haddock 0.7 |

2030 | Ashley Yakeley <ashley@semantic.org>**20060426072521] |

2031 | [add Data.Fixed module |

2032 | Ashley Yakeley <ashley@semantic.org>**20060425071853] |

2033 | [add instances |

2034 | Ross Paterson <ross@soi.city.ac.uk>**20060424102146] |

2035 | [add superclasses to Applicative and Traversable |

2036 | Ross Paterson <ross@soi.city.ac.uk>**20060411144734 |

2037 | |

2038 | Functor is now a superclass of Applicative, and Functor and Foldable |

2039 | are now superclasses of Traversable. The new hierarchy makes clear the |

2040 | inclusions between the classes, but means more work in defining instances. |

2041 | Default definitions are provided to help. |

2042 | ] |

2043 | [add Functor and Monad instances for Prelude types |

2044 | Ross Paterson <ross@soi.city.ac.uk>**20060410111443] |

2045 | [GHC.Base.breakpoint |

2046 | Lemmih <lemmih@gmail.com>**20060407125827] |

2047 | [Track the GHC source tree reorganisation |

2048 | Simon Marlow <simonmar@microsoft.com>**20060407041631] |

2049 | [in the show instance for Exception, print the type of dynamic exceptions |

2050 | Simon Marlow <simonmar@microsoft.com>**20060406112444 |

2051 | Unfortunately this requires some recursve module hackery to get at |

2052 | the show instance for Typeable. |

2053 | ] |

2054 | [implement ForeignEnvPtr, newForeignPtrEnv, addForeignPtrEnv for GHC |

2055 | Simon Marlow <simonmar@microsoft.com>**20060405155448] |

2056 | [add forkOnIO :: Int -> IO () -> IO ThreadId |

2057 | Simon Marlow <simonmar@microsoft.com>**20060327135018] |

2058 | [Rework previous: not a gcc bug after all |

2059 | Simon Marlow <simonmar@microsoft.com>**20060323161229 |

2060 | It turns out that we were relying on behaviour that is undefined in C, |

2061 | and undefined behaviour in C means "the compiler can do whatever the |

2062 | hell it likes with your entire program". So avoid that. |

2063 | ] |

2064 | [work around a gcc 4.1.0 codegen bug in -O2 by forcing -O1 for GHC.Show |

2065 | Simon Marlow <simonmar@microsoft.com>**20060323134514 |

2066 | See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26824 |

2067 | ] |

2068 | [commit mysteriously missing parts of "runIOFastExit" patch |

2069 | Simon Marlow <simonmar@microsoft.com>**20060321101535] |

2070 | [add runIOFastExit :: IO a -> IO a |

2071 | Simon Marlow <simonmar@microsoft.com>**20060320124333 |

2072 | Similar to runIO, but calls stg_exit() directly to exit, rather than |

2073 | shutdownHaskellAndExit(). Needed for running GHCi in the test suite. |

2074 | ] |

2075 | [Fix a broken invariant |

2076 | Simon Marlow <simonmar@microsoft.com>**20060316134151 |

2077 | Patch from #694, for the problem "empty is an identity for <> and $$" is |

2078 | currently broken by eg. isEmpty (empty<>empty)" |

2079 | ] |

2080 | [Add unsafeSTToIO :: ST s a -> IO a |

2081 | Simon Marlow <simonmar@microsoft.com>**20060315160232 |

2082 | Implementation for Hugs is missing, but should be easy. We need this |

2083 | for the forthcoming nested data parallelism implementation. |

2084 | ] |

2085 | [Added 'alter' |

2086 | jeanphilippe.bernardy@gmail.com**20060315143539 |

2087 | Added 'alter :: (Maybe a -> Maybe a) -> k -> Map k a -> Map k a' to IntMap and Map |

2088 | This addresses ticket #665 |

2089 | ] |

2090 | [deprecate FunctorM in favour of Foldable and Traversable |

2091 | Ross Paterson <ross@soi.city.ac.uk>**20060315092942 |

2092 | as discussed on the libraries list. |

2093 | ] |

2094 | [Simplify Eq, Ord, and Show instances for UArray |

2095 | Simon Marlow <simonmar@microsoft.com>**20060313142701 |

2096 | The Eq, Ord, and Show instances of UArray were written out longhand |

2097 | with one instance per element type. It is possible to condense these |

2098 | into a single instance for each class, at the expense of using more |

2099 | extensions (non-std context on instance declaration). |

2100 | |

2101 | Suggestion by: Frederik Eaton <frederik@ofb.net> |

2102 | |

2103 | ] |

2104 | [Oops typo in intSet notMember |

2105 | jeanphilippe.bernardy@gmail.com**20060311224713] |

2106 | [IntMap lookup now returns monad instead of Maybe. |

2107 | jeanphilippe.bernardy@gmail.com**20060311224502] |

2108 | [Added notMember to Data.IntSet and Data.IntMap |

2109 | jeanphilippe.bernardy@gmail.com**20060311085221] |

2110 | [add Data.Set.notMember and Data.Map.notMember |

2111 | John Meacham <john@repetae.net>**20060309191806] |

2112 | [addToClockTime: handle picoseconds properly |

2113 | Simon Marlow <simonmar@microsoft.com>**20060310114532 |

2114 | fixes #588 |

2115 | ] |

2116 | [make head/build rule apply to all types, not just Bool. |

2117 | John Meacham <john@repetae.net>**20060303045753] |

2118 | [Avoid overflow when normalising clock times |

2119 | Ian Lynagh <igloo@earth.li>**20060210144638] |

2120 | [Years have 365 days, not 30*365 |

2121 | Ian Lynagh <igloo@earth.li>**20060210142853] |

2122 | [declare blkcmp() static |

2123 | Simon Marlow <simonmar@microsoft.com>**20060223134317] |

2124 | [typo in comment in Foldable class |

2125 | Ross Paterson <ross@soi.city.ac.uk>**20060209004901] |

2126 | [simplify fmap |

2127 | Ross Paterson <ross@soi.city.ac.uk>**20060206095048] |

2128 | [update ref in comment |

2129 | Ross Paterson <ross@soi.city.ac.uk>**20060206095139] |

2130 | [Give -foverlapping-instances to Data.Typeable |

2131 | simonpj@microsoft**20060206133439 |

2132 | |

2133 | For some time, GHC has made -fallow-overlapping-instances "sticky": |

2134 | any instance in a module compiled with -fallow-overlapping-instances |

2135 | can overlap when imported, regardless of whether the importing module |

2136 | allows overlap. (If there is an overlap, both instances must come from |

2137 | modules thus compiled.) |

2138 | |

2139 | Instances in Data.Typeable might well want to be overlapped, so this |

2140 | commit adds the flag to Data.Typeable (with an explanatory comment) |

2141 | |

2142 | |

2143 | ] |

2144 | [Add -fno-bang-patterns to modules using both bang and glasgow-exts |

2145 | simonpj@microsoft.com**20060203175759] |

2146 | [When splitting a bucket, keep the contents in the same order |

2147 | Simon Marlow <simonmar@microsoft.com>**20060201130427 |

2148 | To retain the property that multiple inserts shadow each other |

2149 | (see ticket #661, test hash001) |

2150 | ] |

2151 | [add foldr/build optimisation for take and replicate |

2152 | Simon Marlow <simonmar@microsoft.com>**20060126164603 |

2153 | This allows take to be deforested, and improves performance of |

2154 | replicate and replicateM/replicateM_. We have a separate problem that |

2155 | means expressions involving [n..m] aren't being completely optimised |

2156 | because eftIntFB isn't being inlined but otherwise the results look |

2157 | good. |

2158 | |

2159 | Sadly this has invalidated a number of the nofib benchmarks which were |

2160 | erroneously using take to duplicate work in a misguided attempt to |

2161 | lengthen their runtimes (ToDo). |

2162 | ] |

2163 | [Generate PrimopWrappers.hs with Haddock docs |

2164 | Simon Marlow <simonmar@microsoft.com>**20060124131121 |

2165 | Patch originally from Dinko Tenev <dinko.tenev@gmail.com>, modified |

2166 | to add log message by me. |

2167 | ] |

2168 | [[project @ 2006-01-19 14:47:15 by ross] |

2169 | ross**20060119144715 |

2170 | backport warning avoidance from Haddock |

2171 | ] |

2172 | [[project @ 2006-01-18 11:45:47 by malcolm] |

2173 | malcolm**20060118114547 |

2174 | Fix import of Ix for nhc98. |

2175 | ] |

2176 | [[project @ 2006-01-17 09:38:38 by ross] |

2177 | ross**20060117093838 |

2178 | add Ix instance for GeneralCategory. |

2179 | ] |

2180 | [TAG Initial conversion from CVS complete |

2181 | John Goerzen <jgoerzen@complete.org>**20060112154126] |

2182 | Patch bundle hash: |

2183 | f791729ca1f31b1f4e6c8302116954f247fc6606 |