New patches:
[Ranged sets added
Paul Johnson **20061107192229] {
adddir ./Data/Ranged
addfile ./Data/Ranged.hs
hunk ./Data/Ranged.hs 1
+
+ 
+ Module : Data.Ranged
+ Copyright : (c) Paul Johnson 2006
+ License : BSDstyle
+ Maintainer : paul@cogito.org.uk
+ Stability : experimental
+ Portability : portable
+
+ Ranged sets represent a set of ordered values as a list of ranges. Each
+ range has an upper and lower boundary, and each boundary divides values
+ into those above and below: no value can ever sit on a boundary.
+
+
+  Reexports 'Data.Ranged.Boundaries', 'Data.Ranged.Ranges' and
+ 'Data.Ranged.RangedSet' for convenience.
+
+module Data.Ranged (
+ module Data.Ranged.Boundaries,
+ module Data.Ranged.Ranges,
+ module Data.Ranged.RangedSet
+) where
+
+import Data.Ranged.Boundaries
+import Data.Ranged.Ranges
+import Data.Ranged.RangedSet
addfile ./Data/Ranged/Boundaries.hs
hunk ./Data/Ranged/Boundaries.hs 1
+{# OPTIONS_GHC fglasgowexts #}
+module Data.Ranged.Boundaries (
+ DiscreteOrdered,
+ adjacent,
+ enumAdjacent,
+ boundedAdjacent,
+ Boundary (..),
+ above,
+ (/>/)
+) where
+
+import Test.QuickCheck
+
+infix 4 />/
+
+{ 
+Distinguish between dense and sparse ordered types. A dense type is
+one in which any two values @v1 < v2@ have a third value @v3@ such that
+@v1 < v3 < v2@.
+
+In theory the floating types are dense, although in practice they can only have
+finitely many values. This class treats them as dense.
+
+Tuples up to 4 members are declared as instances. Larger tuples may be added
+if necessary.
+
+This approach was suggested by Ben RudiakGould on comp.lang.functional.
+}
+class Ord a => DiscreteOrdered a where
+   Two values @x@ and @y@ are adjacent if @x < y@ and there does not
+  exist a third value between them. Always @False@ for dense types.
+ adjacent :: a > a > Bool
+
+instance DiscreteOrdered Bool where adjacent = boundedAdjacent
+instance DiscreteOrdered Ordering where adjacent = boundedAdjacent
+instance DiscreteOrdered Char where adjacent = boundedAdjacent
+instance DiscreteOrdered Int where adjacent = boundedAdjacent
+instance DiscreteOrdered Integer where adjacent = enumAdjacent
+instance DiscreteOrdered Rational where adjacent _ _ = False
+instance DiscreteOrdered Float where adjacent _ _ = False
+instance DiscreteOrdered Double where adjacent _ _ = False
+instance Ord a => DiscreteOrdered [a] where adjacent _ _ = False
+instance (Ord a, DiscreteOrdered b) => DiscreteOrdered (a, b)
+ where adjacent (x1, x2) (y1, y2) = (x1 == y1) && adjacent x2 y2
+instance (Ord a, Ord b, DiscreteOrdered c) => DiscreteOrdered (a, b, c)
+ where
+ adjacent (x1, x2, x3) (y1, y2, y3) =
+ (x1 == y1) && (x2 == y2) && adjacent x3 y3
+instance (Ord a, Ord b, Ord c, DiscreteOrdered d) =>
+ DiscreteOrdered (a, b, c, d)
+ where
+ adjacent (x1, x2, x3, x4) (y1, y2, y3, y4) =
+ (x1 == y1) && (x2 == y2) && (x3 == y3) && adjacent x4 y4
+
+  Check adjacency for sparse enumerated types (i.e. where there
+ is no value between @x@ and @succ x@). Use as the definition of
+ "adjacent" for most enumerated types.
+enumAdjacent :: (Ord a, Enum a) => a > a > Bool
+enumAdjacent x y = (succ x == y)
+
+  Check adjacency, allowing for case where x = maxBound. Use as the
+ definition of "adjacent" for bounded enumerated types such as Int and Char.
+boundedAdjacent :: (Ord a, Enum a) => a > a > Bool
+boundedAdjacent x y = if x < y then succ x == y else False
+
+
+{ 
+A Boundary is a division of an ordered type into values above
+and below the boundary. No value can sit on a boundary.
+
+Known bug: for Bounded types
+
+* @BoundaryAbove maxBound < BoundaryAboveAll@
+
+* @BoundaryBelow minBound > BoundaryBelowAll@
+
+This is incorrect because there are no possible values in between the left
+and right sides of these inequalities.
+}
+
+data Boundary a =
+   The argument is the highest value below the boundary.
+ BoundaryAbove a 
+   The argument is the lowest value above the boundary.
+ BoundaryBelow a 
+   The boundary above all values.
+ BoundaryAboveAll 
+   The boundary below all values.
+ BoundaryBelowAll
+ deriving (Eq, Show)
+
+  True if the value is above the boundary, false otherwise.
+above :: Ord v => Boundary v > v > Bool
+above (BoundaryAbove b) v = v > b
+above (BoundaryBelow b) v = v >= b
+above BoundaryAboveAll _ = False
+above BoundaryBelowAll _ = True
+
+  Same as 'above', but with the arguments reversed for more intuitive infix
+ usage.
+(/>/) :: Ord v => v > Boundary v > Bool
+(/>/) = flip above
+
+instance (DiscreteOrdered a) => Ord (Boundary a) where
+  Comparison alogrithm based on brute force and ignorance:
+  enumerate all combinations.
+
+ compare boundary1 boundary2 =
+ case boundary1 of
+ BoundaryAbove b1 >
+ case boundary2 of
+ BoundaryAbove b2 > compare b1 b2
+ BoundaryBelow b2 >
+ if b1 < b2
+ then
+ if adjacent b1 b2 then EQ else LT
+ else GT
+ BoundaryAboveAll > LT
+ BoundaryBelowAll > GT
+ BoundaryBelow b1 >
+ case boundary2 of
+ BoundaryAbove b2 >
+ if b1 > b2
+ then
+ if adjacent b2 b1 then EQ else GT
+ else LT
+ BoundaryBelow b2 > compare b1 b2
+ BoundaryAboveAll > LT
+ BoundaryBelowAll > GT
+ BoundaryAboveAll >
+ case boundary2 of
+ BoundaryAboveAll > EQ
+ otherwise > GT
+ BoundaryBelowAll >
+ case boundary2 of
+ BoundaryBelowAll > EQ
+ otherwise > LT
+
+
+ QuickCheck Generator
+
+instance Arbitrary a => Arbitrary (Boundary a) where
+ arbitrary = frequency [
+ (1, return BoundaryAboveAll),
+ (1, return BoundaryBelowAll),
+ (18, do
+ v < arbitrary
+ oneof [return $ BoundaryAbove v, return $ BoundaryBelow v]
+ )]
+ coarbitrary BoundaryBelowAll = variant 0
+ coarbitrary BoundaryAboveAll = variant 1
+ coarbitrary (BoundaryBelow v) = variant 2 . coarbitrary v
+ coarbitrary (BoundaryAbove v) = variant 3 . coarbitrary v
+
addfile ./Data/Ranged/RangedSet.hs
hunk ./Data/Ranged/RangedSet.hs 1

+{# OPTIONS_GHC fglasgowexts #}
+
+module Data.Ranged.RangedSet (
+  ** Ranged Set Type
+ RSet,
+ rSetRanges,
+ rSetRanges1,
+  ** Ranged Set construction functions and their Preconditions
+ rangedSet,
+ unsafeRangedSet,
+ validRangeList,
+ normaliseRangeList,
+  ** Predicates
+ rSetIsEmpty,
+ (?), rSetHas,
+ (<=), rSetSubset,
+ (<), rSetSubsetStrict,
+  ** Set Operations
+ (\/), rSetUnion,
+ (/\), rSetIntersection,
+ (!), rSetDifference,
+ rSetNegation,
+  ** Useful Sets
+ rSetEmpty,
+ rSetFull,
+ rSetUnfold
+
+  ** QuickCheck Properties
+
+  *** Construction
+  $ConstructionProperties
+
+  *** Basic Operations
+  $BasicOperationProperties
+
+  *** Some Identities and Inequalities
+  $SomeIdentitiesAndInequalities
+) where
+
+import Data.Ranged.Boundaries
+import Data.Ranged.Ranges
+
+import Data.List
+import Test.QuickCheck
+
+infixl 7 /\
+infixl 6 \/, !
+infixl 5 <=, <, ?
+
+  An RSet (for Ranged Set) is a list of ranges. The ranges must be sorted
+ and not overlap.
+
+newtype DiscreteOrdered v => RSet v = RSet {rSetRanges :: [Range v]}
+ deriving Show
+
+  RSet is an instance of @Eq@, but is likely to diverge on infinite sets.
+instance DiscreteOrdered v => Eq (RSet v) where
+ (==) rs1 rs2 =
+ rSetRanges1 rs1 == rSetRanges1 rs2
+
+
+  A strict version of rSetRanges. Empty ranges are filtered out, and
+ touching ranges are merged. However it may diverge on the unions,
+ intersections and differences of certain infinite sets.
+rSetRanges1 :: DiscreteOrdered v => RSet v > [Range v]
+rSetRanges1 rs = normalise1 $ filter (not.rangeIsEmpty) $ rSetRanges rs
+ where
+ normalise1 (r1:r2:rs) =
+ if rangeUpper r1 >= rangeLower r2
+ then normalise1 (Range (rangeLower r1) (rangeUpper r2) : rs)
+ else r1 : normalise1 (r2 : rs)
+ normalise1 rs = rs
+
+  Determine if the ranges in the list are both in order and nonoverlapping.
+ If so then they are suitable input for the unsafeRangedSet function.
+validRangeList :: DiscreteOrdered v => [Range v] > Bool
+
+validRangeList [] = True
+validRangeList [Range lower upper] = lower <= upper
+validRangeList ranges = and $ zipWith okAdjacent ranges (tail ranges)
+ where
+ okAdjacent (Range lower1 upper1) (Range lower2 upper2) =
+ lower1 <= upper1 && upper1 <= lower2 && lower2 <= upper2
+
+
+  Rearrange and merge the ranges in the list so that they are in order and
+ nonoverlapping.
+normaliseRangeList :: DiscreteOrdered v => [Range v] > [Range v]
+
+normaliseRangeList ranges = normalise $ sort $ filter nonEmpty ranges
+ where
+ nonEmpty (Range lower upper) = lower < upper
+
+
+ Private routine: normalise a range list that is known to be already sorted.
+ This precondition is not checked.
+normalise :: DiscreteOrdered v => [Range v] > [Range v]
+normalise (r1:r2:rs) =
+ if overlap r1 r2
+ then normalise $
+ Range (rangeLower r1)
+ (max (rangeUpper r1) (rangeUpper r2))
+ : rs
+ else r1 : (normalise $ r2 : rs)
+ where
+ overlap (Range _ upper1) (Range lower2 _) = upper1 >= lower2
+
+normalise rs = rs
+
+  Create a new Ranged Set from a list of ranges. The list may contain
+ ranges that overlap or are not in ascending order.
+rangedSet :: DiscreteOrdered v => [Range v] > RSet v
+rangedSet = RSet . normaliseRangeList
+
+  Create a new Ranged Set from a list of ranges. @validRangeList ranges@
+ must return @True@. This precondition is not checked.
+unsafeRangedSet :: DiscreteOrdered v => [Range v] > RSet v
+unsafeRangedSet = RSet
+
+
+  True if the set has no members. Warning: if the argument is the result
+ of operations on infinite sets then this can only ever return False.
+rSetIsEmpty :: DiscreteOrdered v => RSet v > Bool
+rSetIsEmpty rs = null $ filter (not.rangeIsEmpty) $ rSetRanges rs
+
+
+  True if the value is within the ranged set. Infix precedence is left 5.
+rSetHas, (?) :: DiscreteOrdered v => RSet v > v > Bool
+rSetHas (RSet ls) value = rSetHas1 ls
+ where
+ rSetHas1 [] = False
+ rSetHas1 (r:rs)
+  value />/ rangeLower r = rangeHas r value  rSetHas1 rs
+  otherwise = False
+
+(?) = rSetHas
+
+  True if the first argument is a subset of the second argument, or is
+ equal. Warning: if both arguments are infinite then this can never
+ return True. Infix precedence is left 5.
+rSetSubset, (<=) :: DiscreteOrdered v => RSet v > RSet v > Bool
+rSetSubset rs1 rs2 = rSetIsEmpty (rs1 ! rs2)
+(<=) = rSetSubset
+
+
+  True if the first argument is a strict subset of the second argument.
+ Warning: if both arguments are infinite then this can never return True.
+ Infix precedence is left 5.
+rSetSubsetStrict, (<) :: DiscreteOrdered v => RSet v > RSet v > Bool
+rSetSubsetStrict rs1 rs2 =
+ rSetIsEmpty (rs1 ! rs2)
+ && not (rSetIsEmpty (rs2 ! rs1))
+
+(<) = rSetSubsetStrict
+
+  Set union for ranged sets. Infix precedence is left 6.
+rSetUnion, (\/) :: DiscreteOrdered v => RSet v > RSet v > RSet v
+ Implementation note: rSetUnion merges the two lists into a single
+ sorted list and then calls normalise to combine overlapping ranges.
+rSetUnion (RSet ls1) (RSet ls2) = RSet $ normalise $ merge ls1 ls2
+ where
+ merge ls1 [] = ls1
+ merge [] ls2 = ls2
+ merge ls1@(h1:t1) ls2@(h2:t2) =
+ if h1 < h2
+ then h1 : merge t1 ls2
+ else h2 : merge ls1 t2
+
+(\/) = rSetUnion
+
+  Set intersection for ranged sets. Infix precedence is left 7.
+rSetIntersection, (/\) :: DiscreteOrdered v => RSet v > RSet v > RSet v
+rSetIntersection (RSet ls1) (RSet ls2) =
+ RSet $ filter (not . rangeIsEmpty) $ merge ls1 ls2
+ where
+ merge ls1@(h1:t1) ls2@(h2:t2) =
+ rangeIntersection h1 h2
+ : if rangeUpper h1 < rangeUpper h2
+ then merge t1 ls2
+ else merge ls1 t2
+ merge _ _ = []
+
+(/\) = rSetIntersection
+
+
+  Set difference. Infix precedence is left 6.
+rSetDifference, (!) :: DiscreteOrdered v => RSet v > RSet v > RSet v
+rSetDifference rs1 rs2 = rs1 /\ (rSetNegation rs2)
+(!) = rSetDifference
+
+
+  Set negation.
+rSetNegation :: DiscreteOrdered a => RSet a > RSet a
+rSetNegation set = RSet $ ranges $ setBounds1
+ where
+ ranges (b1:b2:bs) = Range b1 b2 : ranges bs
+ ranges [BoundaryAboveAll] = []
+ ranges [b] = [Range b BoundaryAboveAll]
+ ranges _ = []
+ setBounds1 = case setBounds of
+ (BoundaryBelowAll : bs) > bs
+ _ > BoundaryBelowAll : setBounds
+ setBounds = bounds $ rSetRanges set
+ bounds (r:rs) = rangeLower r : rangeUpper r : bounds rs
+ bounds _ = []
+
+
+  The empty set.
+rSetEmpty :: DiscreteOrdered a => RSet a
+rSetEmpty = RSet []
+
+  The set that contains everything.
+rSetFull :: DiscreteOrdered a => RSet a
+rSetFull = RSet [Range BoundaryBelowAll BoundaryAboveAll]
+
+
+  Construct a range set.
+rSetUnfold :: DiscreteOrdered a =>
+ Boundary a
+  ^ A first lower boundary.
+ > (Boundary a > Boundary a)
+  ^ A function from a lower boundary to an upper boundary, which must
+  return a result greater than the argument (not checked).
+ > (Boundary a > Maybe (Boundary a))
+  ^ A function from a lower boundary to @Maybe@ the successor lower boundary,
+  which must return a result greater than the argument (not checked).
+ > RSet a
+rSetUnfold bound upperFunc succFunc = RSet $ normalise $ ranges bound
+ where
+ ranges b =
+ Range b (upperFunc bound)
+ : case succFunc b of
+ Just b2 > ranges b2
+ Nothing > []
+
+
+ QuickCheck Generators
+
+instance (Arbitrary v, DiscreteOrdered v, Show v) =>
+ Arbitrary (RSet v)
+ where
+ arbitrary = do
+ ls < arbitrary
+ return $ rangedSet $ rangeList $ sort ls
+ where
+  Arbitrary lists of ranges don't give many interesting sets after
+  normalisation. So instead generate a sorted list of boundaries
+  and pair them off. Odd boundaries are dropped.
+ rangeList (b1:b2:bs) = Range b1 b2 : rangeList bs
+ rangeList _ = []
+
+ coarbitrary (RSet ls) = variant 0 . coarbitrary ls
+
+ ==================================================================
+ QuickCheck Properties
+ ==================================================================
+
+ Note for maintenance: Haddock does not include QuickCheck properties,
+ so they have to be copied into documentation blocks manually. This
+ process must be repeated for new or modified properties.
+
+
+
+ Construction properties
+
+
+{ $ConstructionProperties
+
+A normalised range list is valid for unsafeRangedSet
+
+> prop_validNormalised ls = validRangeList $ normaliseRangeList ls
+> where types = ls :: [Range Double]
+
+Iff a value is in a range list then it is in a ranged set
+constructed from that list.
+
+> prop_has (ls :: [Range Double], v :: Double) =
+> (ls `rangeListHas` v) == rangedSet ls ? v
+
+}
+
+ A normalised range list is valid for unsafeRangedSet
+prop_validNormalised ls = validRangeList $ normaliseRangeList ls
+ where types = ls :: [Range Double]
+
+ Iff a value is in a range list then it is in a ranged set
+ constructed from that list.
+prop_has (ls :: [Range Double], v :: Double) =
+ (ls `rangeListHas` v) == rangedSet ls ? v
+
+
+ Basic operation properties
+
+
+{ $BasicOperationProperties
+Iff a value is in either of two ranged sets then it is in the union of
+those two sets.
+
+> prop_union (rs1, rs2 :: RSet Double, v :: Double) =
+> (rs1 ? v  rs2 ? v) == ((rs1 \/ rs2) ? v)
+
+Iff a value is in both of two ranged sets then it is in the intersection
+of those two sets.
+
+> prop_intersection (rs1, rs2 :: RSet Double, v :: Double) =
+> (rs1 ? v && rs2 ? v) ==
+> ((rs1 `rSetIntersection` rs2) ? v)
+
+
+Iff a value is in ranged set 1 and not in ranged set 2 then it is in the
+difference of the two.
+
+> prop_difference (rs1, rs2 :: RSet Double, v :: Double) =
+> (rs1 ? v && not (rs2 ? v)) == ((rs1 ! rs2) ? v)
+
+
+Iff a value is not in a ranged set then it is in its negation.
+
+> prop_negation (rs :: RSet Double, v :: Double) =
+> rs ? v == not (rSetNegation rs ? v)
+
+
+A set that contains a value is not empty
+
+> prop_not_empty (rs :: RSet Double, v :: Double) =
+> (rs ? v) ==> not (rSetIsEmpty rs)
+}
+
+ Iff a value is in either of two ranged sets then it is in the union of
+ those two sets.
+prop_union (rs1, rs2 :: RSet Double, v :: Double) =
+ (rs1 ? v  rs2 ? v) == ((rs1 \/ rs2) ? v)
+
+ Iff a value is in both of two ranged sets then it is in the intersection
+ of those two sets.
+prop_intersection (rs1, rs2 :: RSet Double, v :: Double) =
+ (rs1 ? v && rs2 ? v) ==
+ ((rs1 `rSetIntersection` rs2) ? v)
+
+
+ Iff a value is in ranged set 1 and not in ranged set 2 then it is in the
+ difference of the two.
+prop_difference (rs1, rs2 :: RSet Double, v :: Double) =
+ (rs1 ? v && not (rs2 ? v)) == ((rs1 ! rs2) ? v)
+
+
+ Iff a value is not in a ranged set then it is in its negation.
+prop_negation (rs :: RSet Double, v :: Double) =
+ rs ? v == not (rSetNegation rs ? v)
+
+
+ A set that contains a value is not empty
+prop_not_empty (rs :: RSet Double, v :: Double) =
+ (rs ? v) ==> not (rSetIsEmpty rs)
+
+
+ Some identities and inequalities of sets
+
+
+{ $SomeIdentitiesAndInequalities
+The intersection of a set with its negation is empty.
+
+> prop_empty_intersection rs =
+> rSetIsEmpty (rs /\ rSetNegation rs)
+> where types = rs :: RSet Double
+
+
+The union of a set with its negation is full.
+
+> prop_full_union (rs :: RSet Double, v :: Double) =
+> (rs \/ rSetNegation rs) ? v
+
+
+The union of two sets is the nonstrict superset of both.
+
+> prop_union_superset (rs1, rs2 :: RSet Double) =
+> rs1 <= u && rs2 <= u
+> where
+> u = rs1 \/ rs2
+
+The intersection of two sets is the nonstrict subset of both.
+
+> prop_intersection_subset (rs1, rs2 :: RSet Double) =
+> i <= rs1 && i <= rs2
+> where
+> i = rs1 /\ rs2
+
+The difference of two sets intersected with the subtractand is empty.
+
+> prop_diff_intersect (rs1, rs2 :: RSet Double) =
+> rSetIsEmpty ((rs1 ! rs2) /\ rs2)
+
+A set is the nonstrict subset of itself.
+
+> prop_subset rs =
+> rs <= rs
+> where types = rs :: RSet Double
+
+A set is not the strict subset of itself.
+
+> prop_strict_subset rs =
+> not (rs < rs)
+> where types = rs :: RSet Double
+
+
+If rs1  rs2 is not empty then the union of rs1 and rs2 will be a strict
+superset of rs2.
+
+> prop_union_strict_superset (rs1, rs2 :: RSet Double) =
+> (not $ rSetIsEmpty (rs1 ! rs2))
+> ==> (rs2 < (rs1 \/ rs2))
+
+Intersection commutes
+
+> prop_intersection_commutes (rs1, rs2 :: RSet Double) =
+> (rs1 /\ rs2) == (rs2 /\ rs1)
+
+Union commutes
+
+> prop_union_commutes (rs1, rs2 :: RSet Double) =
+> (rs1 \/ rs2) == (rs2 \/ rs1)
+
+Intersection associates
+
+> prop_intersection_associates (rs1, rs2, rs3 :: RSet Double) =
+> ((rs1 /\ rs2) /\ rs3) == (rs1 /\ (rs2 /\ rs3))
+
+Union associates
+
+> prop_union_associates (rs1, rs2, rs3 :: RSet Double) =
+> ((rs1 \/ rs2) \/ rs3) == (rs1 \/ (rs2 \/ rs3))
+
+}
+
+ The intersection of a set with its negation is empty.
+prop_empty_intersection rs =
+ rSetIsEmpty (rs /\ rSetNegation rs)
+ where types = rs :: RSet Double
+
+
+ The union of a set with its negation is full.
+prop_full_union (rs :: RSet Double, v :: Double) =
+ (rs \/ rSetNegation rs) ? v
+
+
+ The union of two sets is the nonstrict superset of both.
+prop_union_superset (rs1, rs2 :: RSet Double) =
+ rs1 <= u && rs2 <= u
+ where
+ u = rs1 \/ rs2
+
+ The intersection of two sets is the nonstrict subset of both.
+prop_intersection_subset (rs1, rs2 :: RSet Double) =
+ i <= rs1 && i <= rs2
+ where
+ i = rs1 /\ rs2
+
+ The difference of two sets intersected with the subtractand is empty.
+prop_diff_intersect (rs1, rs2 :: RSet Double) =
+ rSetIsEmpty ((rs1 ! rs2) /\ rs2)
+
+
+ A set is the nonstrict subset of itself.
+prop_subset rs =
+ rs <= rs
+ where types = rs :: RSet Double
+
+ A set is not the strict subset of itself.
+prop_strict_subset rs =
+ not (rs < rs)
+ where types = rs :: RSet Double
+
+
+ If rs1  rs2 is not empty then the union of rs1 and rs2 will be a strict
+ superset of rs2.
+prop_union_strict_superset (rs1, rs2 :: RSet Double) =
+ (not $ rSetIsEmpty (rs1 ! rs2))
+ ==> (rs2 < (rs1 \/ rs2))
+
+ Intersection commutes
+prop_intersection_commutes (rs1, rs2 :: RSet Double) =
+ (rs1 /\ rs2) == (rs2 /\ rs1)
+
+ Union commutes
+prop_union_commutes (rs1, rs2 :: RSet Double) =
+ (rs1 \/ rs2) == (rs2 \/ rs1)
+
+ Intersection associates
+prop_intersection_associates (rs1, rs2, rs3 :: RSet Double) =
+ ((rs1 /\ rs2) /\ rs3) == (rs1 /\ (rs2 /\ rs3))
+
+ Union associates
+prop_union_associates (rs1, rs2, rs3 :: RSet Double) =
+ ((rs1 \/ rs2) \/ rs3) == (rs1 \/ (rs2 \/ rs3))
+
+
+
+
addfile ./Data/Ranged/Ranges.hs
hunk ./Data/Ranged/Ranges.hs 1
+{# OPTIONS_GHC fglasgowexts #}
+
+  A range has an upper and lower boundary.
+module Data.Ranged.Ranges (
+  ** Construction
+ Range (..),
+ emptyRange,
+ fullRange,
+  ** Predicates
+ rangeIsEmpty,
+ rangeOverlap,
+ rangeEncloses,
+  ** Membership
+ rangeHas,
+ rangeListHas,
+  ** Set Operations
+ rangeIntersection,
+ rangeUnion,
+ rangeDifference
+  ** QuickCheck Properties
+  $properties
+) where
+
+import Data.Ranged.Boundaries
+import Data.Maybe
+import Test.QuickCheck
+
+  A Range has upper and lower boundaries.
+data Ord v => Range v = Range {rangeLower, rangeUpper :: Boundary v}
+
+instance (DiscreteOrdered a) => Eq (Range a) where
+ r1 == r2 = (rangeIsEmpty r1 && rangeIsEmpty r2) 
+ (rangeLower r1 == rangeLower r2 &&
+ rangeUpper r1 == rangeUpper r2)
+
+
+instance (DiscreteOrdered a) => Ord (Range a) where
+ compare r1 r2
+  r1 == r2 = EQ
+  rangeIsEmpty r1 = LT
+  rangeIsEmpty r2 = GT
+  otherwise = compare (rangeLower r1, rangeUpper r1)
+ (rangeLower r2, rangeUpper r2)
+
+instance (Show a, DiscreteOrdered a) => Show (Range a) where
+ show r
+  rangeIsEmpty r = "Empty"
+  otherwise = lowerBound ++ "x" ++ upperBound
+ where
+ lowerBound = case rangeLower r of
+ BoundaryBelowAll > ""
+ BoundaryBelow v > show v ++ " <= "
+ BoundaryAbove v > show v ++ " < "
+ BoundaryAboveAll > error "show Range: lower bound is BoundaryAboveAll"
+ upperBound = case rangeUpper r of
+ BoundaryBelowAll > error "show Range: upper bound is BoundaryBelowAll"
+ BoundaryBelow v > " < " ++ show v
+ BoundaryAbove v > " <=" ++ show v
+ BoundaryAboveAll > ""
+
+
+  True if the value is within the range.
+rangeHas :: Ord v => Range v > v > Bool
+
+rangeHas (Range b1 b2) v =
+ (v />/ b1) && not (v />/ b2)
+
+
+  True if the value is within one of the ranges.
+rangeListHas :: Ord v =>
+ [Range v] > v > Bool
+rangeListHas ls v = or $ map (\r > rangeHas r v) ls
+
+ The empty range
+emptyRange :: DiscreteOrdered v => Range v
+emptyRange = Range BoundaryAboveAll BoundaryBelowAll
+
+ The full range. All values are within it.
+fullRange :: DiscreteOrdered v => Range v
+fullRange = Range BoundaryBelowAll BoundaryAboveAll
+
+  A range is empty unless its upper boundary is greater than its lower
+ boundary.
+rangeIsEmpty :: DiscreteOrdered v => Range v > Bool
+rangeIsEmpty (Range lower upper) = upper <= lower
+
+
+  Two ranges overlap if their intersection is nonempty.
+rangeOverlap :: DiscreteOrdered v => Range v > Range v > Bool
+rangeOverlap r1 r2 =
+ not (rangeIsEmpty r1)
+ && not (rangeIsEmpty r2)
+ && not (rangeUpper r1 <= rangeLower r2  rangeUpper r2 <= rangeLower r1)
+
+  The first range encloses the second if every value in the second range is
+ also within the first range. If the second range is empty then this is
+ always true.
+
+rangeEncloses :: DiscreteOrdered v => Range v > Range v > Bool
+rangeEncloses r1 r2 =
+ (rangeLower r1 <= rangeLower r2 && rangeUpper r2 <= rangeUpper r1)
+  rangeIsEmpty r2
+
+
+  Intersection of two ranges, if any.
+rangeIntersection :: DiscreteOrdered v => Range v > Range v > Range v
+
+rangeIntersection (Range lower1 upper1) (Range lower2 upper2) =
+ Range (max lower1 lower2) (min upper1 upper2)
+
+
+  Union of two ranges. Returns one or two results.
+
+ If there are two results then they are guaranteed to have a nonempty
+ gap in between, but may not be in ascending order.
+rangeUnion :: DiscreteOrdered v => Range v > Range v > [Range v]
+
+rangeUnion r1@(Range lower1 upper1) r2@(Range lower2 upper2) =
+ if touching
+ then [Range lower upper]
+ else [r1, r2]
+ where
+ touching = (max lower1 lower2) <= (min upper1 upper2)
+ lower = min lower1 lower2
+ upper = max upper1 upper2
+
+  @range1@ minus @range2@. Zero, one or two results.
+rangeDifference :: DiscreteOrdered v => Range v > Range v > [Range v]
+
+rangeDifference r1@(Range lower1 upper1) r2@(Range lower2 upper2) =
+  There are six possibilities
+  1: r2 completely less than r1
+  2: r2 overlaps bottom of r1
+  3: r2 encloses r1
+  4: r1 encloses r2
+  5: r2 overlaps top of r1
+  6: r2 completely greater than r1
+ if intersects
+ then  Cases 2,3,4,5
+ filter (not . rangeIsEmpty) [Range lower1 lower2, Range upper2 upper1]
+ else  Cases 1, 6
+ [r1]
+ where
+ intersects = (max lower1 lower2) < (min upper1 upper2)
+
+ QuickCheck generators
+
+instance (Arbitrary v, DiscreteOrdered v, Show v) =>
+ Arbitrary (Range v) where
+
+ arbitrary = frequency [
+ (18, do
+ (b1 :: Boundary v) < arbitrary
+ (b2 :: Boundary v) < arbitrary
+ if b1 < b2
+ then return $ Range b1 b2
+ else return $ Range b2 b1
+ ),
+ (1, return emptyRange),
+ (1, return fullRange)
+ ]
+
+ coarbitrary (Range lower upper) =
+ variant 0 . coarbitrary lower . coarbitrary upper
+
+
+
+ QuickCheck Properties
+
+{ $properties
+Range union
+
+> prop_union (r1, r2 :: Range Double, n :: Double) =
+> (r1 `rangeHas` n  r2 `rangeHas` n)
+> == (r1 `rangeUnion` r2) `rangeListHas` n
+
+Range intersection
+
+> prop_intersection (r1, r2 :: Range Double, n :: Double) =
+> (r1 `rangeHas` n && r2 `rangeHas` n)
+> == (r1 `rangeIntersection` r2) `rangeHas` n
+
+Range difference
+
+> prop_difference (r1, r2 :: Range Double, n :: Double) =
+> (r1 `rangeHas` n && not (r2 `rangeHas` n))
+> == (r1 `rangeDifference` r2) `rangeListHas` n
+
+}
+
+ Range union
+prop_union (r1, r2 :: Range Double, n :: Double) =
+ (r1 `rangeHas` n  r2 `rangeHas` n)
+ == (r1 `rangeUnion` r2) `rangeListHas` n
+
+ Range intersection
+prop_intersection (r1, r2 :: Range Double, n :: Double) =
+ (r1 `rangeHas` n && r2 `rangeHas` n)
+ == (r1 `rangeIntersection` r2) `rangeHas` n
+
+ Range difference
+prop_difference (r1, r2 :: Range Double, n :: Double) =
+ (r1 `rangeHas` n && not (r2 `rangeHas` n))
+ == (r1 `rangeDifference` r2) `rangeListHas` n
}
[Submission to base library
Paul Johnson **20061109203014
Ranged sets with QuickCheck properties. All tests passed 100 times.
] {
hunk ./Data/Ranged/Boundaries.hs 2
+
+ 
+ Module : Data.Ranged.Boundaries
+ Copyright : (c) Paul Johnson 2006
+ License : BSDstyle
+ Maintainer : paul@cogito.org.uk
+ Stability : experimental
+ Portability : portable
+
+
+
+
+
hunk ./Data/Ranged/Boundaries.hs 90
This is incorrect because there are no possible values in between the left
and right sides of these inequalities.
+This is incorrect because there are no possible values in
+between the left and right sides of these inequalities.
hunk ./Data/Ranged/Boundaries.hs 103
 deriving (Eq, Show)
+ deriving (Show)
hunk ./Data/Ranged/Boundaries.hs 117
+instance (DiscreteOrdered a) => Eq (Boundary a) where
+ b1 == b2 = compare b1 b2 == EQ
+
hunk ./Data/Ranged/Boundaries.hs 155

hunk ./Data/Ranged/Boundaries.hs 169

+
hunk ./Data/Ranged/RangedSet.hs 7
 rSetRanges1,
hunk ./Data/Ranged/RangedSet.hs 8
 rangedSet,
+ makeRangedSet,
hunk ./Data/Ranged/RangedSet.hs 14
 (?), rSetHas,
 (<=), rSetSubset,
 (<), rSetSubsetStrict,
+ (?), rSetHas,
+ (<=), rSetIsSubset,
+ (<), rSetIsSubsetStrict,
hunk ./Data/Ranged/RangedSet.hs 20
 (!), rSetDifference,
+ (!), rSetDifference,
hunk ./Data/Ranged/RangedSet.hs 53
 deriving Show
+ deriving (Eq, Show)
hunk ./Data/Ranged/RangedSet.hs 55
  RSet is an instance of @Eq@, but is likely to diverge on infinite sets.
instance DiscreteOrdered v => Eq (RSet v) where
 (==) rs1 rs2 =
 rSetRanges1 rs1 == rSetRanges1 rs2


  A strict version of rSetRanges. Empty ranges are filtered out, and
 touching ranges are merged. However it may diverge on the unions,
 intersections and differences of certain infinite sets.
rSetRanges1 :: DiscreteOrdered v => RSet v > [Range v]
rSetRanges1 rs = normalise1 $ filter (not.rangeIsEmpty) $ rSetRanges rs
 where
 normalise1 (r1:r2:rs) =
 if rangeUpper r1 >= rangeLower r2
 then normalise1 (Range (rangeLower r1) (rangeUpper r2) : rs)
 else r1 : normalise1 (r2 : rs)
 normalise1 rs = rs
hunk ./Data/Ranged/RangedSet.hs 72
normaliseRangeList ranges = normalise $ sort $ filter nonEmpty ranges
 where
 nonEmpty (Range lower upper) = lower < upper
+normaliseRangeList ranges =
+ normalise $ sort $ filter (not . rangeIsEmpty) ranges
hunk ./Data/Ranged/RangedSet.hs 91
+
hunk ./Data/Ranged/RangedSet.hs 94
rangedSet :: DiscreteOrdered v => [Range v] > RSet v
rangedSet = RSet . normaliseRangeList
+makeRangedSet :: DiscreteOrdered v => [Range v] > RSet v
+makeRangedSet = RSet . normaliseRangeList
+
hunk ./Data/Ranged/RangedSet.hs 104
  True if the set has no members. Warning: if the argument is the result
 of operations on infinite sets then this can only ever return False.
+  True if the set has no members.
hunk ./Data/Ranged/RangedSet.hs 106
rSetIsEmpty rs = null $ filter (not.rangeIsEmpty) $ rSetRanges rs
+rSetIsEmpty = null . rSetRanges
+
+
+  True if the negation of the set has no members.
+rSetIsFull :: DiscreteOrdered v => RSet v > Bool
+rSetIsFull = rSetIsEmpty . rSetNegation
hunk ./Data/Ranged/RangedSet.hs 126
 equal. Warning: if both arguments are infinite then this can never
 return True. Infix precedence is left 5.
rSetSubset, (<=) :: DiscreteOrdered v => RSet v > RSet v > Bool
rSetSubset rs1 rs2 = rSetIsEmpty (rs1 ! rs2)
(<=) = rSetSubset
+ equal.
+
+ Infix precedence is left 5.
+rSetIsSubset, (<=) :: DiscreteOrdered v => RSet v > RSet v > Bool
+rSetIsSubset rs1 rs2 = rSetIsEmpty (rs1 ! rs2)
+(<=) = rSetIsSubset
hunk ./Data/Ranged/RangedSet.hs 135
 Warning: if both arguments are infinite then this can never return True.
+
hunk ./Data/Ranged/RangedSet.hs 137
rSetSubsetStrict, (<) :: DiscreteOrdered v => RSet v > RSet v > Bool
rSetSubsetStrict rs1 rs2 =
+rSetIsSubsetStrict, (<) :: DiscreteOrdered v => RSet v > RSet v > Bool
+rSetIsSubsetStrict rs1 rs2 =
hunk ./Data/Ranged/RangedSet.hs 142
(<) = rSetSubsetStrict
+(<) = rSetIsSubsetStrict
hunk ./Data/Ranged/RangedSet.hs 213
  ^ A function from a lower boundary to @Maybe@ the successor lower boundary,
  which must return a result greater than the argument (not checked).
+  ^ A function from a lower boundary to @Maybe@ the successor lower
+  boundary, which must return a result greater than the argument
+  (not checked).
hunk ./Data/Ranged/RangedSet.hs 231
 arbitrary = do
 ls < arbitrary
 return $ rangedSet $ rangeList $ sort ls
+ arbitrary = frequency [
+ (1, return rSetEmpty),
+ (1, return rSetFull),
+ (18, do
+ ls < arbitrary
+ return $ makeRangedSet $ rangeList $ sort ls
+ )]
hunk ./Data/Ranged/RangedSet.hs 277
 where types = ls :: [Range Double]
+ where types = ls :: [Range Integer]
hunk ./Data/Ranged/RangedSet.hs 281
prop_has (ls :: [Range Double], v :: Double) =
 (ls `rangeListHas` v) == rangedSet ls ? v
+prop_has (ls :: [Range Integer], v :: Integer) =
+ (ls `rangeListHas` v) == makeRangedSet ls ? v
hunk ./Data/Ranged/RangedSet.hs 292
> prop_union (rs1, rs2 :: RSet Double, v :: Double) =
+> prop_union (rs1, rs2 :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 298
> prop_intersection (rs1, rs2 :: RSet Double, v :: Double) =
+> prop_intersection (rs1, rs2 :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 306
> prop_difference (rs1, rs2 :: RSet Double, v :: Double) =
+> prop_difference (rs1, rs2 :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 312
> prop_negation (rs :: RSet Double, v :: Double) =
+> prop_negation (rs :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 318
> prop_not_empty (rs :: RSet Double, v :: Double) =
+> prop_not_empty (rs :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 324
prop_union (rs1, rs2 :: RSet Double, v :: Double) =
+prop_union (rs1, rs2 :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 329
prop_intersection (rs1, rs2 :: RSet Double, v :: Double) =
+prop_intersection (rs1, rs2 :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 336
prop_difference (rs1, rs2 :: RSet Double, v :: Double) =
+prop_difference (rs1, rs2 :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 341
prop_negation (rs :: RSet Double, v :: Double) =
+prop_negation (rs :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 346
prop_not_empty (rs :: RSet Double, v :: Double) =
+prop_not_empty (rs :: RSet Integer, v :: Integer) =
hunk ./Data/Ranged/RangedSet.hs 354
+
+The empty set has no members.
+
+> prop_empty (v :: Integer) = not (rSetEmpty ? v)
+
+
+The full set has every member.
+
+> prop_full (v :: Integer) = rSetFull ? v
+
+
hunk ./Data/Ranged/RangedSet.hs 367
> prop_empty_intersection rs =
+> prop_empty_intersection (rs :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 369
> where types = rs :: RSet Double
hunk ./Data/Ranged/RangedSet.hs 373
> prop_full_union (rs :: RSet Double, v :: Double) =
> (rs \/ rSetNegation rs) ? v
+> prop_full_union (rs :: RSet Integer, v :: Integer) =
+> rSetIsFull (rs \/ rSetNegation rs)
hunk ./Data/Ranged/RangedSet.hs 379
> prop_union_superset (rs1, rs2 :: RSet Double) =
+> prop_union_superset (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 386
> prop_intersection_subset (rs1, rs2 :: RSet Double) =
+> prop_intersection_subset (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 393
> prop_diff_intersect (rs1, rs2 :: RSet Double) =
+> prop_diff_intersect (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 400
> where types = rs :: RSet Double
+> where types = rs :: RSet Integer
hunk ./Data/Ranged/RangedSet.hs 406
> where types = rs :: RSet Double
+> where types = rs :: RSet Integer
hunk ./Data/Ranged/RangedSet.hs 412
> prop_union_strict_superset (rs1, rs2 :: RSet Double) =
+> prop_union_strict_superset (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 418
> prop_intersection_commutes (rs1, rs2 :: RSet Double) =
+> prop_intersection_commutes (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 423
> prop_union_commutes (rs1, rs2 :: RSet Double) =
+> prop_union_commutes (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 428
> prop_intersection_associates (rs1, rs2, rs3 :: RSet Double) =
+> prop_intersection_associates (rs1, rs2, rs3 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 433
> prop_union_associates (rs1, rs2, rs3 :: RSet Double) =
+> prop_union_associates (rs1, rs2, rs3 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 436
+De Morgan's Law for Intersection
+
+> prop_de_morgan_intersection (rs1, rs2 :: RSet Integer) =
+> rSetNegation (rs1 /\ rs2) == (rSetNegation rs1 \/ rSetNegation rs2)
+
+De Morgan's Law for Union
+
+> prop_de_morgan_union (rs1, rs2 :: RSet Integer) =
+> rSetNegation (rs1 \/ rs2) == (rSetNegation rs1 /\ rSetNegation rs2)
+
hunk ./Data/Ranged/RangedSet.hs 448
+ The empty set has no members.
+prop_empty (v :: Integer) = not (rSetEmpty ? v)
+
+
+ The full set has every member.
+prop_full (v :: Integer) = rSetFull ? v
+
+
hunk ./Data/Ranged/RangedSet.hs 457
prop_empty_intersection rs =
+prop_empty_intersection (rs :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 459
 where types = rs :: RSet Double
hunk ./Data/Ranged/RangedSet.hs 462
prop_full_union (rs :: RSet Double, v :: Double) =
 (rs \/ rSetNegation rs) ? v
+prop_full_union (rs :: RSet Integer, v :: Integer) =
+ rSetIsFull (rs \/ rSetNegation rs)
hunk ./Data/Ranged/RangedSet.hs 467
prop_union_superset (rs1, rs2 :: RSet Double) =
+prop_union_superset (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 473
prop_intersection_subset (rs1, rs2 :: RSet Double) =
+prop_intersection_subset (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 479
prop_diff_intersect (rs1, rs2 :: RSet Double) =
+prop_diff_intersect (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 486
 where types = rs :: RSet Double
+ where types = rs :: RSet Integer
hunk ./Data/Ranged/RangedSet.hs 491
 where types = rs :: RSet Double
+ where types = rs :: RSet Integer
hunk ./Data/Ranged/RangedSet.hs 496
prop_union_strict_superset (rs1, rs2 :: RSet Double) =
+prop_union_strict_superset (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 501
prop_intersection_commutes (rs1, rs2 :: RSet Double) =
+prop_intersection_commutes (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 505
prop_union_commutes (rs1, rs2 :: RSet Double) =
+prop_union_commutes (rs1, rs2 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 509
prop_intersection_associates (rs1, rs2, rs3 :: RSet Double) =
+prop_intersection_associates (rs1, rs2, rs3 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 513
prop_union_associates (rs1, rs2, rs3 :: RSet Double) =
+prop_union_associates (rs1, rs2, rs3 :: RSet Integer) =
hunk ./Data/Ranged/RangedSet.hs 516
+ De Morgan's Law for Intersection
+prop_de_morgan_intersection (rs1, rs2 :: RSet Integer) =
+ rSetNegation (rs1 /\ rs2) == (rSetNegation rs1 \/ rSetNegation rs2)
hunk ./Data/Ranged/RangedSet.hs 520
+ De Morgan's Law for Union
+prop_de_morgan_union (rs1, rs2 :: RSet Integer) =
+ rSetNegation (rs1 \/ rs2) == (rSetNegation rs1 /\ rSetNegation rs2)
hunk ./Data/Ranged/RangedSet.hs 524

hunk ./Data/Ranged/Ranges.hs 1
{# OPTIONS_GHC fglasgowexts #}
+{# OPTIONS_GHC cpp fglasgowexts #}
+
+ 
+ Module : Data.Ranged.Ranges
+ Copyright : (c) Paul Johnson 2006
+ License : BSDstyle
+ Maintainer : paul@cogito.org.uk
+ Stability : experimental
+ Portability : portable
+
+
+
hunk ./Data/Ranged/Ranges.hs 31
  ** QuickCheck Properties
+  ** QuickCheck properties
hunk ./Data/Ranged/Ranges.hs 69
 BoundaryAbove v > " <=" ++ show v
+ BoundaryAbove v > " <= " ++ show v
hunk ./Data/Ranged/Ranges.hs 93
+
hunk ./Data/Ranged/Ranges.hs 106

+
+
hunk ./Data/Ranged/Ranges.hs 111

hunk ./Data/Ranged/Ranges.hs 138

  @range1@ minus @range2@. Zero, one or two results.
+
+
+  @range1@ minus @range2@. Returns zero, one or two results. Multiple
+ results are guaranteed to have nonempty gaps in between, but may not be in
+ ascending order.
hunk ./Data/Ranged/Ranges.hs 160

+
+
hunk ./Data/Ranged/Ranges.hs 222
+
hunk ./Data/Ranged.hs 13
+
}
Context:
[redefine writeFile and appendFile using withFile
Ross Paterson **20061107140359]
[add withFile and withBinaryFile (#966)
Ross Paterson **20061107134510]
[remove conflicting import for nhc98
Malcolm.Wallace@cs.york.ac.uk**20061108111215]
[Add intercalate to Data.List (ticket #971)
Josef Svenningsson **20061102122052]
[nonGHC: fix canonicalizeFilePath
Ross Paterson **20061107133902
I've also removed the #ifdef __GLASGOW_HASKELL__ from the proper
Windows versions of a few functions. These will need testing with
Hugs on Windows.
]
[enable canonicalizePath for nonGHC platforms
Simon Marlow **20061107121141]
[Update documentation for hWaitForInput
Simon Marlow **20061107111430
See #972
Merge to 6.6 branch.
]
[Use unchecked shifts to implement Data.Bits.rotate
Samuel Bronson **20061012125553
This should get rid of those cases, maybe lower the size enough that the inliner will like it?
]
[fix Haddock module headers
Ross Paterson **20061106124140]
[fix example in docs
Ross Paterson **20061106115628]
[Add intercalate and split to Data.List
Josef Svenningsson *20061024172357]
[Data.Generics.Basics is GHConly
Ross Paterson **20061102111736]
[#ifdef around nonportable Data.Generics.Basics
Malcolm.Wallace@cs.york.ac.uk**20061102103445]
[Add deriving Data to Complex
simonpj@microsoft**20061101102059]
[minor clarification of RandomGen doc
Ross Paterson **20061030230842]
[rearrange docs a bit
Ross Paterson **20061030161223]
[Add intercalate and split to Data.List
Josef Svenningsson **20061024172357]
[Export pseq from Control.Parallel, and use it in Control.Parallel.Strategies
Simon Marlow **20061027150141]
[`par` should be infixr 0
Simon Marlow **20061027130800
Alas, I didn't spot this due to lack of testing, and the symptom is
that an expression like x `par` y `seq z will have exactly the wrong
parallelism properties. The workaround is to add parantheses.
I think we could push this to the 6.6 branch.
]
[fix example in comment
Ross Paterson **20061023163925]
[Use the new Any type for dynamics (GHC only)
simonpj@microsoft**20061019160408]
[add Data.Sequence to nhc98 build
Malcolm.Wallace@cs.york.ac.uk**20061012135200]
[Remove Data.FiniteMap, add Control.Applicative, Data.Traversable, and
Malcolm.Wallace@cs.york.ac.uk**20061012095605
Data.Foldable to the nhc98 build.
]
[STM invariants
tharris@microsoft.com**20061007123253]
[Inline shift in GHC's Bits instances for {Int,Word}{,8,16,32,64}
Samuel Bronson **20061009020906]
[Don't create GHC.Prim when bootstrapping; we can't, and we don't need it
Ian Lynagh **20061004165355]
[Data.ByteString: fix lazyness of take, drop & splitAt
Don Stewart **20061005011703
ByteString.Lazy's take, drop and splitAt were too strict when demanding
a byte string. Spotted by Einar Karttunen. Thanks to him and to Bertram
Felgenhauer for explaining the problem and the fix.
]
[Fix syntax error that prevents building Haddock documentation on Windows
brianlsmith@gmail.com**20060917013530]
[Hugs only: unbreak typeRepKey
Ross Paterson **20060929102743]
[make hGetBufNonBlocking do something on Windows w/ threaded
Simon Marlow **20060927145811
hGetBufNonBlocking will behave the same as hGetBuf on Windows now, which
is better than just crashing (which it did previously).
]
[add typeRepKey :: TypeRep > IO Int
Simon Marlow **20060927100342
See feature request #880
]
[fix header comment
Ross Paterson **20060926135843]
[Add strict versions of insertWith and insertWithKey (Data.Map)
jeanphilippe.bernardy@gmail.com**20060910162443]
[doc tweaks, including more precise equations for evaluate
Ross Paterson **20060910115259]
[Sync Data.ByteString with stable branch
Don Stewart **20060909050111
This patch:
* hides the LPS constructor (its in .Base if you need it)
* adds functions to convert between strict and lazy bytestrings
* and adds readInteger
]
[Typeable1 instances for STM and TVar
Ross Paterson **20060904231425]
[remove obsolete Hugs stuff
Ross Paterson **20060904223944]
[Cleaner isInfixOf suggestion from Ross Paterson
John Goerzen **20060901143654]
[New function isInfixOf that searches a list for a given sublist
John Goerzen **20060831151556
Example:
isInfixOf "Haskell" "I really like Haskell." > True
isInfixOf "Ial" "I really like Haskell." > False
This function was first implemented in MissingH as MissingH.List.contains
]
[Better doc on Data.Map.lookup: explain what the monad is for
jeanphilippe.bernardy@gmail.com**20060903133440]
[fix hDuplicateTo on Windows
Simon Marlow **20060901150016
deja vu  I'm sure I remember fixing this before...
]
[Improve documentation of atomically
simonpj@microsoft**20060714120207]
[Add missing method genRange for StdGen (fixes #794)
simonpj@microsoft**20060707151901
MERGE TO STABLE
Trac #794 reports (correctly) that the implementation of StdGen
only returns numbers in the range (0..something) rather than
(minBound, maxBound), which is what StdGen's genRange claims.
This commit fixes the problem, by implementing genRange for StdGen
(previously it just used the default method).
]
[mark nhc98 import hack
Ross Paterson **20060831125219]
[remove some outdated comments
Simon Marlow **20060831104200]
[import Control.Arrow.ArrowZero to help nhc98's type checker
Malcolm.Wallace@cs.york.ac.uk**20060831101105]
[remove Text.Regex(.Posix) from nhc98 build
Malcolm.Wallace@cs.york.ac.uk**20060831101016]
[add Data.Foldable.{msum,asum}, plus tweaks to comments
Ross Paterson **20060830163521]
[fix doc typo
Ross Paterson **20060830134123]
[add Data.Foldable.{for_,forM_} and Data.Traversable.{for,forM}
Ross Paterson **20060830133805
generalizing Control.Monad.{forM_,forM}
]
[Make length a good consumer
simonpj@microsoft*20060508142726
Make length into a good consumer. Fixes Trac bug #707.
(Before length simply didn't use foldr.)
]
[Add Control.Monad.forM and forM_
Don Stewart **20060824081118
flip mapM_ is more and more common, I find. Several suggestions have
been made to add this, as foreach or something similar. This patch
does just that:
forM :: (Monad m) => [a] > (a > m b) > m [b]
forM_ :: (Monad m) => [a] > (a > m b) > m ()
So we can write:
Prelude Control.Monad> forM_ [1..4] $ \x > print x
1
2
3
4
]
[Hide internal module from haddock in Data.ByteString
Don Stewart **20060828011515]
[add advice on avoiding import ambiguities
Ross Paterson **20060827170407]
[expand advice on importing these modules
Ross Paterson **20060827164044]
[add Haddock marker
Ross Paterson **20060827115140]
[Clarify how one hides Prelude.catch
Don Stewart **20060826124346
User feedback indicated that an example was required, of how to hide
Prelude.catch, so add such an example to the docs
]
[Workaround for OSes that don't have intmax_t and uintmax_t
Ian Lynagh **20060825134936
OpenBSD (and possibly others) do not have intmax_t and uintmax_t types:
http://www.mailarchive.com/haskellprime@haskell.org/msg01548.html
so substitute (unsigned) long long if we have them, otherwise
(unsigned) long.
]
[add docs for par
Simon Marlow **20060825110610]
[document minimal complete definition for Bits
Ross Paterson **20060824140504]
[C regex library bits have moved to the regexposix package
Simon Marlow **20060824132311]
[Add shared Typeable support (ghc only)
Esa Ilari Vuokko **20060823003126]
[this should have been removed with the previous patch
Simon Marlow **20060824121223]
[remove Text.Regx & Text.Regex.Posix
Simon Marlow **20060824094615
These are subsumed by the new regexbase, regexposix and regexcompat
packages.
]
[explicitly tag Data.ByteString rules with the FPS prefix.
Don Stewart **20060824041326]
[Add spec rules for sections in Data.ByteString
Don Stewart **20060824012611]
[Sync Data.ByteString with current stable branch, 0.7
Don Stewart **20060823143338]
[add notes about why copyFile doesn't remove the target
Simon Marlow **20060823095059]
[copyFile: try removing the target file before opening it for writing
Simon Marlow *20060822121909]
[copyFile: try removing the target file before opening it for writing
Simon Marlow **20060822121909]
[add alternative functors and extra instances
Ross Paterson **20060821152151
* Alternative class, for functors with a monoid
* instances for Const
* instances for arrows
]
[generate Haddock docs on all platforms
Simon Marlow **20060821131612]
[remove extra comma from import
Ross Paterson **20060819173954]
[fix docs for withC(A)StringLen
Ross Paterson **20060818170328]
[use Haskell'98 compliant indentation in do blocks
Malcolm.Wallace@cs.york.ac.uk**20060818130810]
[use correct names of IOArray operations for nhc98
Malcolm.Wallace@cs.york.ac.uk**20060818130714]
[add mapMaybe and mapEither, plus WithKey variants
Ross Paterson **20060817235041]
[remove Text.Html from nhc98 build
Malcolm.Wallace@cs.york.ac.uk**20060817135502]
[eliminate more HOST_OS tests
Ross Paterson **20060815190609]
[Hugs only: disable unused process primitives
Ross Paterson **20060813184435
These were the cause of Hugs bug #30, I think, and weren't used by Hugs anyway.
]
[markup fix to Data.HashTable
Ross Paterson **20060812103835]
[revert removal of ghcconfig.h from package.conf.in
Ross Paterson **20060812082702
as it's preprocessed with undef (pointed out by Esa Ilari Vuokko)
]
[fix Data.HashTable for nonGHC
Ross Paterson **20060811231521]
[remove deprecated 'withObject'
Simon Marlow **20060811152350]
[JanWillem Maessen's improved implementation of Data.HashTable
Simon Marlow **20060811151024
Rather than incrementally enlarging the hash table, this version
just does it in one go when the table gets too full.
]
[Warning police: Make some prototypes from the RTS known
sven.panne@aedion.de**20060811144629]
[Warning police: Removed useless catchall clause
sven.panne@aedion.de**20060811142208]
[reduce dependency on ghcconfig.h
Ross Paterson **20060811124030
The only remaining use is in cbits/dirUtils.h, which tests solaris2_HOST_OS
(Also System.Info uses ghcplatform.h and several modules import MachDeps.h
to get SIZEOF_* and ALIGNMENT_* from ghcautoconf.h)
]
[(nonGHC only) track MArray interface change
Ross Paterson **20060810182902]
[move Text.Html to a separate package
Simon Marlow **20060810113017]
[bump version to 2.0
Simon Marlow **20060810112833]
[Remove deprecated Data.FiniteMap and Data.Set interfaces
Simon Marlow **20060809153810]
[move altzone test from ghc to base package
Ross Paterson **20060809124259]
[remove unnecessary #include "ghcconfig.h"
Ross Paterson **20060809123812]
[Change the API of MArray to allow resizable arrays
Simon Marlow **20060809100548
See #704
The MArray class doesn't currently allow a mutable array to change its
size, because of the pure function
bounds :: (HasBounds a, Ix i) => a i e > (i,i)
This patch removes the HasBounds class, and adds
getBounds :: (MArray a e m, Ix i) => a i e > m (i,i)
to the MArray class, and
bounds :: (IArray a e, Ix i) => a i e > (i,i)
to the IArray class.
The reason that bounds had to be incorporated into the IArray class is
because I couldn't make DiffArray work without doing this. DiffArray
acts as a layer converting an MArray into an IArray, and there was no
way (that I could find) to define an instance of HasBounds for
DiffArray.
]
[deprecate this module.
Simon Marlow **20060808100708]
[add traceShow (see #474)
Simon Marlow **20060807155545]
[remove spurious 'extern "C" {'
Simon Marlow **20060724160258]
[Fix unsafeIndex for large ranges
Simon Marlow **20060721100225]
[disambiguate uses of foldr for nhc98 to compile without errors
Malcolm.Wallace@cs.york.ac.uk**20060711161614]
[make Control.Monad.Instances compilable by nhc98
Malcolm.Wallace@cs.york.ac.uk**20060711160941]
[breakpointCond
Lemmih **20060708055528]
[UNDO: Merge "unrecognized long opt" fix from 6.4.2
Simon Marlow **20060705142537
This patch undid the previous patch, "RequireOrder: do not collect
unrecognised options after a nonopt". I asked Sven to revert it, but
didn't get an answer.
See bug #473.
]
[Avoid strictness in accumulator for unpackFoldr
Don Stewart **20060703091806
The seq on the accumulator for unpackFoldr will break in the presence of
head/build rewrite rules. The empty list case will be forced, producing
an exception. This is a known issue with seq and rewrite rules that we
just stumbled on to.
]
[Disable unpack/build fusion
Don Stewart **20060702083913
unpack/build on bytestrings seems to trigger a bug when interacting with
head/build fusion in GHC.List. The bytestring001 testcase catches it.
I'll investigate further, but best to disable this for now (its not
often used anyway).
Note that with frulesoff or ghc 6.4.2 things are fine. It seems to
have emerged with the recent rules changes.
]
[Import Data.ByteString.Lazy, improve ByteString Fusion, and resync with FPS head
Don Stewart **20060701084345
This patch imports the Data.ByteString.Lazy module, and its helpers,
providing a ByteString implemented as a lazy list of strict cachesized
chunks. This type allows the usual lazy operations to be written on
bytestrings, including lazy IO, with much improved space and time over
the [Char] equivalents.
]
[Wibble in docs for new ForeignPtr functionsn
Don Stewart **20060609075924]
[comments for Applicative and Traversable
Ross Paterson **20060622170436]
[default to NoBuffering on Windows for a read/write text file
Simon Marlow **20060622144446
Fixes (works around) #679
]
[remove dead code
Simon Marlow **20060622144433]
[clarify and expand docs
Simon Marlow **20060622112911]
[Add minView and maxView to Map and Set
jeanphilippe.bernardy@gmail.com**20060616180121]
[add signature for registerDelay
Ross Paterson **20060614114456]
[a few doc comments
Ross Paterson **20060613142704]
[Optimised foreign pointer representation, for heapallocated objects
Don Stewart **20060608015011]
[Add the inline function, and many comments
simonpj@microsoft.com**20060605115814
This commit adds the 'inline' function described in the
related patch in the compiler.
I've also added comments about the 'lazy' function.
]
[small intro to exceptions
Ross Paterson **20060525111604]
[export breakpoint
Simon Marlow **20060525090456]
[Merge in changes from fps head. Highlights:
Don Stewart **20060525065012
Wed May 24 15:49:38 EST 2006 sjanssen@cse.unl.edu
* instance Monoid ByteString
Wed May 24 15:04:04 EST 2006 Duncan Coutts
* Rearange export lists for the .Char8 modules
Wed May 24 14:59:56 EST 2006 Duncan Coutts
* Implement mapAccumL and reimplement mapIndexed using loopU
Wed May 24 14:47:32 EST 2006 Duncan Coutts
* Change the implementation of the unfoldr(N) functions.
Use a more compact implementation for unfoldrN and change it's behaviour
to only return Just in the case that it actually 'overflowed' the N, so
the boundary case of unfolding exactly N gives Nothing.
Implement unfoldr and Lazy.unfoldr in terms of unfoldrN. Use fibonacci
growth for the chunk size in unfoldr
Wed May 24 08:32:29 EST 2006 sjanssen@cse.unl.edu
* Add unfoldr to ByteString and .Char8
A preliminary implementation of unfoldr.
Wed May 24 01:39:41 EST 2006 Duncan Coutts
* Reorder the export lists to better match the Data.List api
Tue May 23 14:04:32 EST 2006 Don Stewart
* pack{Byte,Char} > singleton. As per fptools convention
Tue May 23 14:00:51 EST 2006 Don Stewart
* elemIndexLast > elemIndexEnd
Tue May 23 13:57:34 EST 2006 Don Stewart
* In the search for a more orthogonal api, we kill breakFirst/breakLast,
which were of dubious value
Tue May 23 12:24:09 EST 2006 Don Stewart
* Abolish elems. It's name implied it was unpack, but its type didn't. it made no sense
Tue May 23 10:42:09 EST 2006 Duncan Coutts
* Minor doc tidyup. Use haddock markup better.
Tue May 23 11:00:31 EST 2006 Don Stewart
* Simplify the join() implementation. Spotted by Duncan.
]
[add a way to ask the IO manager thread to exit
Simon Marlow **20060524121823]
[Sync with FPS head, including the following patches:
Don Stewart **20060520030436
Thu May 18 15:45:46 EST 2006 sjanssen@cse.unl.edu
* Export unsafeTake and unsafeDrop
Fri May 19 11:53:08 EST 2006 Don Stewart
* Add foldl1'
Fri May 19 13:41:24 EST 2006 Don Stewart
* Add fuseable scanl, scanl1 + properties
Fri May 19 18:20:40 EST 2006 Don Stewart
* Spotted another chance to use unsafeTake,Drop (in groupBy)
Thu May 18 09:24:25 EST 2006 Duncan Coutts
* More effecient findIndexOrEnd based on the impl of findIndex
Thu May 18 09:22:49 EST 2006 Duncan Coutts
* Eliminate special case in findIndex since it's handled anyway.
Thu May 18 09:19:08 EST 2006 Duncan Coutts
* Add unsafeTake and unsafeDrop
These versions assume the n is in the bounds of the bytestring, saving
two comparison tests. Then use them in varous places where we think this
holds. These cases need double checking (and there are a few remaining
internal uses of take / drop that might be possible to convert).
Not exported for the moment.
Tue May 16 23:15:11 EST 2006 Don Stewart
* Handle n < 0 in drop and splitAt. Spotted by QC.
Tue May 16 22:46:22 EST 2006 Don Stewart
* Handle n <= 0 cases for unfoldr and replicate. Spotted by QC
Tue May 16 21:34:11 EST 2006 Don Stewart
* mapF > map', filterF > filter'
]
[haddock fix
Ross Paterson **20060518154723]
[simplify indexing in Data.Sequence
Ross Paterson **20060518154316]
[Move Eq, Ord, Show instances for ThreadId to GHC.Conc
Simon Marlow **20060518113339
Eliminates orphans.
]
[Better error handling in the IO manager thread
Simon Marlow **20060518113303
In particular, handle EBADF just like rts/posix/Select.c, by waking up
all the waiting threads. Other errors are thrown, instead of just
being ignored.
]
[#define _REENTRANT 1 (needed to get the right errno on some OSs)
Simon Marlow **20060518104151
Part 2 of the fix for threaded RTS problems on Solaris and possibly
*BSD (Part 1 was the same change in ghc/includes/Rts.h).
]
[copyCString* should be in IO. Spotted by Tomasz Zielonka
Don Stewart **20060518012154]
[add import Prelude to get dependencies right for Data/Fixed.hs
Duncan Coutts **20060517222044
Hopefully this fixes parallel builds.
]
[Fix negative index handling in splitAt, replicate and unfoldrN. Move mapF, filterF > map', filter' while we're here
Don Stewart **20060517020150]
[Use our own realloc. Thus reduction functions (like filter) allocate on the Haskell heap. Makes around 10% difference.
Don Stewart **20060513051736]
[Last two CInt fixes for 64 bit, and bracket writeFile while we're here
Don Stewart **20060512050750]
[Some small optimisations, generalise the type of unfold
Don Stewart **20060510043309
Tue May 9 22:36:29 EST 2006 Duncan Coutts
* Surely the error function should not be inlined.
Tue May 9 22:35:53 EST 2006 Duncan Coutts
* Reorder memory writes for better cache locality.
Tue May 9 23:28:09 EST 2006 Duncan Coutts
* Generalise the type of unfoldrN
The type of unfoldrN was overly constrained:
unfoldrN :: Int > (Word8 > Maybe (Word8, Word8)) > Word8 > ByteString
if we compare that to unfoldr:
unfoldr :: (b > Maybe (a, b)) > b > [a]
So we can generalise unfoldrN to this type:
unfoldrN :: Int > (a > Maybe (Word8, a)) > a > ByteString
and something similar for the .Char8 version. If people really do want to
use it a lot with Word8/Char then perhaps we should add a specialise pragma.
Wed May 10 13:26:40 EST 2006 Don Stewart
* Add foldl', and thus a fusion rule for length . {map,filter,fold},
that avoids creating an array at all if the end of the pipeline is a 'length' reduction
**END OF DESCRIPTION***
Place the long patch description above the ***END OF DESCRIPTION*** marker.
The first line of this file will be the patch name.
This patch contains the following changes:
M ./Data/ByteString.hs 8 +38
M ./Data/ByteString/Char8.hs 6 +12
]
[portable implementation of WordPtr/IntPtr for nonGHC
Ross Paterson **20060510001826
plus much tweaking of imports to avoid cycles
]
[add WordPtr and IntPtr types to Foreign.Ptr, with associated conversions
Simon Marlow **20060509092606
As suggested by John Meacham.
I had to move the Show instance for Ptr into GHC.ForeignPtr to avoid
recursive dependencies.
]
[add CIntPtr, CUIntPtr, CIntMax, CUIntMax types
Simon Marlow **20060509092427]
[add GHC.Dynamic
Simon Marlow **20060509082739]
[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
Don Stewart **20060509023425]
[Make length a good consumer
simonpj@microsoft**20060508142726
Make length into a good consumer. Fixes Trac bug #707.
(Before length simply didn't use foldr.)
]
[Trim imports
simonpj@microsoft**20060508142557]
[Make unsafePerformIO lazy
simonpj@microsoft**20060508142507
The stricteness analyser used to have a HACK which ensured that NOINLNE things
were not strictnessanalysed. The reason was unsafePerformIO. Left to itself,
the strictness analyser would discover this strictness for unsafePerformIO:
unsafePerformIO: C(U(AV))
But then consider this subexpression
unsafePerformIO (\s > let r = f x in
case writeIORef v r s of (# s1, _ #) >
(# s1, r #)
The strictness analyser will now find that r is sure to be eval'd,
and may then hoist it out. This makes tests/lib/should_run/memo002
deadlock.
Solving this by making all NOINLINE things have no strictness info is overkill.
In particular, it's overkill for runST, which is perfectly respectable.
Consider
f x = runST (return x)
This should be strict in x.
So the new plan is to define unsafePerformIO using the 'lazy' combinator:
unsafePerformIO (IO m) = lazy (case m realWorld# of (# _, r #) > r)
Remember, 'lazy' is a wiredin identityfunction Id, of type a>a, which is
magically NONSTRICT, and is inlined after strictness analysis. So
unsafePerformIO will look nonstrict, and that's what we want.
]
[Sync with FPS head.
Don Stewart **20060508122322
Mon May 8 10:40:14 EST 2006 Don Stewart
* Fix all uses for Int that should be CInt or CSize in ffi imports.
Spotted by Igloo, dcoutts
Mon May 8 16:09:41 EST 2006 Don Stewart
* Import nicer loop/loop fusion rule from ghcndp
Mon May 8 17:36:07 EST 2006 Don Stewart
* Fix stack leak in split on > 60M strings
Mon May 8 17:50:13 EST 2006 Don Stewart
* Try same fix for stack overflow in elemIndices
]
[Fix all uses for Int that should be CInt or CSize in ffi imports. Spotted by Duncan and Ian
Don Stewart **20060508010311]
[Fixed import list syntax
Sven Panne **20060507155008]
[Faster filterF, filterNotByte
dons@cse.unsw.edu.au**20060507042301]
[Much faster find, findIndex. Hint from sjanssen
dons@cse.unsw.edu.au**20060507033048]
[Merge "unrecognized long opt" fix from 6.4.2
Sven Panne **20060506110519]
[
dons@cse.unsw.edu.au**20060506061029
Sat May 6 13:01:34 EST 2006 Don Stewart
* Do loopU realloc on the Haskell heap. And add a really tough stress test
Sat May 6 12:28:58 EST 2006 Don Stewart
* Use simple, 3x faster concat. Plus QC properties. Suggested by sjanssen and dcoutts
Sat May 6 15:59:31 EST 2006 Don Stewart
* dcoutt's packByte bug squashed
With inlinePerformIO, ghc head was compiling:
packByte 255 `compare` packByte 127
into roughly
case mallocByteString 2 of
ForeignPtr f internals >
case writeWord8OffAddr# f 0 255 of _ >
case writeWord8OffAddr# f 0 127 of _ >
case eqAddr# f f of
False > case compare (GHC.Prim.plusAddr# f 0)
(GHC.Prim.plusAddr# f 0)
which is rather stunning. unsafePerformIO seems to prevent whatever
magic inlining was leading to this. Only affected the head.
]
[Add array fusion versions of map, filter and foldl
dons@cse.unsw.edu.au**20060505060858
This patch adds fusable map, filter and foldl, using the array fusion
code for unlifted, flat arrays, from the Data Parallel Haskell branch,
after kind help from Roman Leshchinskiy,
Pipelines of maps, filters and folds should now need to walk the
bytestring once only, and intermediate bytestrings won't be constructed.
]
[fix for nonGHC
Ross Paterson **20060504093044]
[use bracket in appendFile (like writeFile)
Ross Paterson **20060504091528]
[writeFile: close the file on error
Simon Marlow **20060504084505
Suggested by Ross Paterson, via Neil Mitchell
]
[Sync with FPS head
dons@cse.unsw.edu.au**20060503105259
This patch brings Data.ByteString into sync with the FPS head.
The most significant of which is the new Haskell counting sort.
Changes:
Sun Apr 30 18:16:29 EST 2006 sjanssen@cse.unl.edu
* Fix foldr1 in Data.ByteString and Data.ByteString.Char8
Mon May 1 11:51:16 EST 2006 Don Stewart
* Add group and groupBy. Suggested by conversation between sjanssen and petekaz on #haskell
Mon May 1 16:42:04 EST 2006 sjanssen@cse.unl.edu
* Fix groupBy to match Data.List.groupBy.
Wed May 3 15:01:07 EST 2006 sjanssen@cse.unl.edu
* Migrate to counting sort.
Data.ByteString.sort used C's qsort(), which is O(n log n). The new algorithm
is O(n), and is faster for strings larger than approximately thirty bytes. We
also reduce our dependency on cbits!
]
[improve performance of Integer>String conversion
Simon Marlow **20060503113306
See
http://www.haskell.org//pipermail/libraries/2006April/005227.html
Submitted by: bertram.felgenhauer@googlemail.com
]
[inline withMVar, modifyMVar, modifyMVar_
Simon Marlow **20060503111152]
[Fix string truncating in hGetLine  it was a pasto from Simon's code
Simon Marlow **20060503103504
(from Don Stewart)
]
[Merge in Data.ByteString head. Fixes ByteString+cbits in hugs
Don Stewart **20060429040733]
[Import Data.ByteString from fps 0.5.
Don Stewart **20060428130718
Fast, packed byte vectors, providing a better PackedString.
]
[fix previous patch
Ross Paterson **20060501154847]
[fixes for nonGHC
Ross Paterson **20060501144322]
[fix imports for mingw32 && !GHC
Ross Paterson **20060427163248]
[RequireOrder: do not collect unrecognised options after a nonopt
Simon Marlow **20060426121110
The documentation for RequireOrder says "no option processing after
first nonoption", so it doesn't seem right that we should process the
rest of the arguments to collect the unrecognised ones. Presumably
the client wants to know about the unrecognised options up to the
first nonoption, and will be using a different option parser for the
rest of the command line.
eg. before:
Prelude System.Console.GetOpt> getOpt' RequireOrder [] ["bar","foo"]
([],["bar","foo"],["foo"],[])
after:
Prelude System.Console.GetOpt> getOpt' RequireOrder [] ["bar","foo"]
([],["bar","foo"],[],[])
]
[fix for Haddock 0.7
Ashley Yakeley **20060426072521]
[add Data.Fixed module
Ashley Yakeley **20060425071853]
[add instances
Ross Paterson **20060424102146]
[add superclasses to Applicative and Traversable
Ross Paterson **20060411144734
Functor is now a superclass of Applicative, and Functor and Foldable
are now superclasses of Traversable. The new hierarchy makes clear the
inclusions between the classes, but means more work in defining instances.
Default definitions are provided to help.
]
[add Functor and Monad instances for Prelude types
Ross Paterson **20060410111443]
[GHC.Base.breakpoint
Lemmih **20060407125827]
[Track the GHC source tree reorganisation
Simon Marlow **20060407041631]
[in the show instance for Exception, print the type of dynamic exceptions
Simon Marlow **20060406112444
Unfortunately this requires some recursve module hackery to get at
the show instance for Typeable.
]
[implement ForeignEnvPtr, newForeignPtrEnv, addForeignPtrEnv for GHC
Simon Marlow **20060405155448]
[add forkOnIO :: Int > IO () > IO ThreadId
Simon Marlow **20060327135018]
[Rework previous: not a gcc bug after all
Simon Marlow **20060323161229
It turns out that we were relying on behaviour that is undefined in C,
and undefined behaviour in C means "the compiler can do whatever the
hell it likes with your entire program". So avoid that.
]
[work around a gcc 4.1.0 codegen bug in O2 by forcing O1 for GHC.Show
Simon Marlow **20060323134514
See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26824
]
[commit mysteriously missing parts of "runIOFastExit" patch
Simon Marlow **20060321101535]
[add runIOFastExit :: IO a > IO a
Simon Marlow **20060320124333
Similar to runIO, but calls stg_exit() directly to exit, rather than
shutdownHaskellAndExit(). Needed for running GHCi in the test suite.
]
[Fix a broken invariant
Simon Marlow **20060316134151
Patch from #694, for the problem "empty is an identity for <> and $$" is
currently broken by eg. isEmpty (empty<>empty)"
]
[Add unsafeSTToIO :: ST s a > IO a
Simon Marlow **20060315160232
Implementation for Hugs is missing, but should be easy. We need this
for the forthcoming nested data parallelism implementation.
]
[Added 'alter'
jeanphilippe.bernardy@gmail.com**20060315143539
Added 'alter :: (Maybe a > Maybe a) > k > Map k a > Map k a' to IntMap and Map
This addresses ticket #665
]
[deprecate FunctorM in favour of Foldable and Traversable
Ross Paterson **20060315092942
as discussed on the libraries list.
]
[Simplify Eq, Ord, and Show instances for UArray
Simon Marlow **20060313142701
The Eq, Ord, and Show instances of UArray were written out longhand
with one instance per element type. It is possible to condense these
into a single instance for each class, at the expense of using more
extensions (nonstd context on instance declaration).
Suggestion by: Frederik Eaton
]
[Oops typo in intSet notMember
jeanphilippe.bernardy@gmail.com**20060311224713]
[IntMap lookup now returns monad instead of Maybe.
jeanphilippe.bernardy@gmail.com**20060311224502]
[Added notMember to Data.IntSet and Data.IntMap
jeanphilippe.bernardy@gmail.com**20060311085221]
[add Data.Set.notMember and Data.Map.notMember
John Meacham **20060309191806]
[addToClockTime: handle picoseconds properly
Simon Marlow **20060310114532
fixes #588
]
[make head/build rule apply to all types, not just Bool.
John Meacham **20060303045753]
[Avoid overflow when normalising clock times
Ian Lynagh **20060210144638]
[Years have 365 days, not 30*365
Ian Lynagh **20060210142853]
[declare blkcmp() static
Simon Marlow **20060223134317]
[typo in comment in Foldable class
Ross Paterson **20060209004901]
[simplify fmap
Ross Paterson **20060206095048]
[update ref in comment
Ross Paterson **20060206095139]
[Give foverlappinginstances to Data.Typeable
simonpj@microsoft**20060206133439
For some time, GHC has made fallowoverlappinginstances "sticky":
any instance in a module compiled with fallowoverlappinginstances
can overlap when imported, regardless of whether the importing module
allows overlap. (If there is an overlap, both instances must come from
modules thus compiled.)
Instances in Data.Typeable might well want to be overlapped, so this
commit adds the flag to Data.Typeable (with an explanatory comment)
]
[Add fnobangpatterns to modules using both bang and glasgowexts
simonpj@microsoft.com**20060203175759]
[When splitting a bucket, keep the contents in the same order
Simon Marlow **20060201130427
To retain the property that multiple inserts shadow each other
(see ticket #661, test hash001)
]
[add foldr/build optimisation for take and replicate
Simon Marlow **20060126164603
This allows take to be deforested, and improves performance of
replicate and replicateM/replicateM_. We have a separate problem that
means expressions involving [n..m] aren't being completely optimised
because eftIntFB isn't being inlined but otherwise the results look
good.
Sadly this has invalidated a number of the nofib benchmarks which were
erroneously using take to duplicate work in a misguided attempt to
lengthen their runtimes (ToDo).
]
[Generate PrimopWrappers.hs with Haddock docs
Simon Marlow **20060124131121
Patch originally from Dinko Tenev , modified
to add log message by me.
]
[[project @ 20060119 14:47:15 by ross]
ross**20060119144715
backport warning avoidance from Haddock
]
[[project @ 20060118 11:45:47 by malcolm]
malcolm**20060118114547
Fix import of Ix for nhc98.
]
[[project @ 20060117 09:38:38 by ross]
ross**20060117093838
add Ix instance for GeneralCategory.
]
[TAG Initial conversion from CVS complete
John Goerzen **20060112154126]
Patch bundle hash:
f791729ca1f31b1f4e6c8302116954f247fc6606