data-ordlist 0.4.5 → 0.4.6
raw patch · 6 files changed
+131/−332 lines, 6 files
Files
- AUTHORS +0/−1
- CHANGES +0/−114
- CHANGES.md +121/−0
- Data/List/Ordered.hs +5/−5
- data-ordlist.cabal +5/−4
- test/data-list-ordered-tests.hs +0/−208
− AUTHORS
@@ -1,1 +0,0 @@-"Leon P Smith" <leon@melding-monads.com>
− CHANGES
@@ -1,114 +0,0 @@-Version 0.4.5: (2012-03-12)-- * New function, `minus'`-- * Exported `foldt` and `foldt'`-- * Documentation improvements-- * Reverted the implementation of `mergeAll` and `unionAll` to version- 0.4.2 because the simplified implementation would force the head of- the inner list appearing at the next highest power of 2 well before- it was necessary to do so.--Version 0.4.4: (2010-12-24)-- * Simplified the implementation of `mergeAll` and `unionAll` based on- comments from Will Ness.-- <http://www.haskell.org/pipermail/haskell-cafe/2010-December/087587.html>--Version 0.4.3: (2010-03-02)-- * Improved the implementation of `nubSort`, mirroring the improvements made- to `Data.List.sort` in GHC-6.13.20091224 and first released in GHC-7.0.1.- Thanks to Gwern Branwen for calling the change to my attention. Instead- of initially breaking the input list into singletons before the merge- process, the improved version breaks the input list into monotonic runs.-- <http://www.haskell.org/pipermail/libraries/2010-March/013066.html>-- * Minor formatting improvements in the Haddock documentation.--Version 0.4.2: (2010-02-18)-- * Fixed non-productive loop in `unionAll` when applied to an infinite list- of lists. Thanks to Omar Antolín Camarena for reporting the bug and- Heinrich Apfelmus for some useful comments.-- <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073403.html>- <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073437.html>-- * Added regression test to test suite.--Version 0.4.1: (2010-02-17)-- * Simplified the implementation of `mergeAll` and `unionAll` thanks- to some pointers by Heinrich Apfelmus. This introduced an infinite- non-productive loop into `unionAll`, which was fixed in 0.4.2 without- giving up the simplifications.-- <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073356.html>-- * Minor documentation fixes--Version 0.4: (2010-02-15)-- * The "CHANGES" file was added to document the changes between releases.-- * Documentation Improvements-- * A rough first pass at a test suite-- * The functions `mergeAll` and `unionAll` were added. They operate- on a possibly infinite list of possibly infinite ordered lists; assuming- the heads of the lists are ordered.-- Thanks goes to Omar Antolín Camarena, Heinrich Apfelmus, and Dave Bayer.-- Omar Antolín Camarena suggested the addition, located the article- used as the basis for the implementation, and was quite helpful with- testing and debugging.-- Heinrich Apfelmus wrote his "Implicit Heaps" article, where he- simplified an algorithm by Dave Bayer. It is this article that forms- the basis of our implementation.-- <http://apfelmus.nfshost.com/articles/implicit-heaps.html>-- Dave Bayer posted his 'venturi' implementation to the haskell-cafe- mailing list on 2007 Jul 22. It also appears as "BayerPrimes.hs"- inside of Melissa O'Neill's "haskell-primes.zip":-- <http://www.haskell.org/pipermail/haskell-cafe/2007-July/029391.html>- <http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip>--Version 0.2: (2010-02-07)-- * The module name was changed from `Data.OrdList` to `Data.List.Ordered`-- * Fixed bugs in `insertSetBy`, `insertBagBy`, and `nub`. The insertion- functions assumed reversed lists, while `nub` failed to remove duplicates.-- Thanks to Topi Karvonen for reporting the first issue!-- * Changed semantics of `insertSetBy` slightly: the new version replaces an- element if it is already there. If the old semantics turns out to be- important, a new function can be added at a later date.-- * Changed semantics of `nubBy`: the new version negates the binary relation,- so that `new_nubBy f == old_nubBy (not . f)`. It is now in better keeping- with the spirit of the rest of the library, and mades the bug in `nub`- more obvious.-- * Better documentation, I hope. At the very least, the process of- documenting `nubBy` revealed the bug in `nub`.---Version 0.0.1: (2009-07-10)-- * The initial release, sadly, did not contain the source file--Version 0.0: (2009-07-10)-- * Initial Release
+ CHANGES.md view
@@ -0,0 +1,121 @@+Version 0.4.6: (2014-02-15)++ * Generalized type signature of `isectBy`, `minusBy`, and `minusBy'`,+ leaving the definition unchanged.++ * Made the documentation of `union` more precise.++Version 0.4.5: (2012-03-12)++ * New function, `minus'`++ * Exported `foldt` and `foldt'`++ * Documentation improvements++ * Reverted the implementation of `mergeAll` and `unionAll` to version+ 0.4.2 because the simplified implementation would force the head of+ the inner list appearing at the next highest power of 2 well before+ it was necessary to do so.++Version 0.4.4: (2010-12-24)++ * Simplified the implementation of `mergeAll` and `unionAll` based on+ comments from Will Ness.++ <http://www.haskell.org/pipermail/haskell-cafe/2010-December/087587.html>++Version 0.4.3: (2010-03-02)++ * Improved the implementation of `nubSort`, mirroring the improvements made+ to `Data.List.sort` in GHC-6.13.20091224 and first released in GHC-7.0.1.+ Thanks to Gwern Branwen for calling the change to my attention. Instead+ of initially breaking the input list into singletons before the merge+ process, the improved version breaks the input list into monotonic runs.++ <http://www.haskell.org/pipermail/libraries/2010-March/013066.html>++ * Minor formatting improvements in the Haddock documentation.++Version 0.4.2: (2010-02-18)++ * Fixed non-productive loop in `unionAll` when applied to an infinite list+ of lists. Thanks to Omar Antolín Camarena for reporting the bug and+ Heinrich Apfelmus for some useful comments.++ <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073403.html>+ <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073437.html>++ * Added regression test to test suite.++Version 0.4.1: (2010-02-17)++ * Simplified the implementation of `mergeAll` and `unionAll` thanks+ to some pointers by Heinrich Apfelmus. This introduced an infinite+ non-productive loop into `unionAll`, which was fixed in 0.4.2 without+ giving up the simplifications.++ <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073356.html>++ * Minor documentation fixes++Version 0.4: (2010-02-15)++ * The "CHANGES" file was added to document the changes between releases.++ * Documentation Improvements++ * A rough first pass at a test suite++ * The functions `mergeAll` and `unionAll` were added. They operate+ on a possibly infinite list of possibly infinite ordered lists; assuming+ the heads of the lists are ordered.++ Thanks goes to Omar Antolín Camarena, Heinrich Apfelmus, and Dave Bayer.++ Omar Antolín Camarena suggested the addition, located the article+ used as the basis for the implementation, and was quite helpful with+ testing and debugging.++ Heinrich Apfelmus wrote his "Implicit Heaps" article, where he+ simplified an algorithm by Dave Bayer. It is this article that forms+ the basis of our implementation.++ <http://apfelmus.nfshost.com/articles/implicit-heaps.html>++ Dave Bayer posted his 'venturi' implementation to the haskell-cafe+ mailing list on 2007 Jul 22. It also appears as "BayerPrimes.hs"+ inside of Melissa O'Neill's "haskell-primes.zip":++ <http://www.haskell.org/pipermail/haskell-cafe/2007-July/029391.html>+ <http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip>++Version 0.2: (2010-02-07)++ * The module name was changed from `Data.OrdList` to `Data.List.Ordered`++ * Fixed bugs in `insertSetBy`, `insertBagBy`, and `nub`. The insertion+ functions assumed reversed lists, while `nub` failed to remove duplicates.++ Thanks to Topi Karvonen for reporting the first issue!++ * Changed semantics of `insertSetBy` slightly: the new version replaces an+ element if it is already there. If the old semantics turns out to be+ important, a new function can be added at a later date.++ * Changed semantics of `nubBy`: the new version negates the binary relation,+ so that `new_nubBy f == old_nubBy (not . f)`. It is now in better keeping+ with the spirit of the rest of the library, and mades the bug in `nub`+ more obvious.++ * Better documentation, I hope. At the very least, the process of+ documenting `nubBy` revealed the bug in `nub`.+++Version 0.0.1: (2009-07-10)++ * The initial release, sadly, did not contain the source file++Version 0.0: (2009-07-10)++ * Initial Release
Data/List/Ordered.hs view
@@ -204,7 +204,7 @@ isect = isectBy compare -- | The 'isectBy' function is the non-overloaded version of 'isect'.-isectBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]+isectBy :: (a -> b -> Ordering) -> [a] -> [b] -> [a] isectBy cmp = loop where loop [] _ys = []@@ -217,8 +217,8 @@ -- | The 'union' function computes the union of two ordered lists. -- An element occurs in the output as many times as the maximum number--- of occurrences in either input. If both inputs are sets, then the--- output is a set.+-- of occurrences in either input. The output is a set if and only if+-- both inputs are sets. -- -- > union [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2, 3,4, 5,6 ] -- > union [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1,1, 2,2,2 ]@@ -248,7 +248,7 @@ minus = minusBy compare -- | The 'minusBy' function is the non-overloaded version of 'minus'.-minusBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]+minusBy :: (a -> b -> Ordering) -> [a] -> [b] -> [a] minusBy cmp = loop where loop [] _ys = []@@ -271,7 +271,7 @@ minus' = minusBy' compare -- | The 'minusBy'' function is the non-overloaded version of 'minus''.-minusBy' :: (a -> a -> Ordering) -> [a] -> [a] -> [a]+minusBy' :: (a -> b -> Ordering) -> [a] -> [b] -> [a] minusBy' cmp = loop where loop [] _ys = []
data-ordlist.cabal view
@@ -1,5 +1,5 @@ Name: data-ordlist-Version: 0.4.5+Version: 0.4.6 Description: This module provides set and multiset operations on ordered lists. License: BSD3@@ -10,6 +10,7 @@ Category: Data, List Synopsis: Set and bag operations on ordered lists Cabal-Version: >=1.6+Extra-Doc-Files: CHANGES.md Library Build-Depends: base >= 2 && < 5@@ -17,9 +18,9 @@ source-repository head type: darcs- location: http://patch-tag.com/r/lpsmith/data-ordlist/pullrepo+ location: http://hub.darcs.net/lpsmith/data-ordlist source-repository this type: darcs- location: http://patch-tag.com/r/lpsmith/data-ordlist/pullrepo- tag: 0.4.5+ location: http://hub.darcs.net/lpsmith/data-ordlist+ tag: 0.4.6
− test/data-list-ordered-tests.hs
@@ -1,208 +0,0 @@-module Main where--import qualified Data.List as List-import Data.List.Ordered-import Test.QuickCheck-import Test.QuickCheck.Arbitrary--prop_member :: NonNegative Int -> Positive Int -> Bool-prop_member (NonNegative n) (Positive d)- = member n [0,d..] == (n `mod` d == 0)--prop_insertBag_sort :: [Int] -> Bool-prop_insertBag_sort xs = foldr insertBag [] xs == sort xs--prop_insertSet_nubSort :: [Int] -> Bool-prop_insertSet_nubSort xs = foldr insertSet [] xs == nubSort xs--prop_nub :: OrderedList Int -> Bool-prop_nub (Ordered xs) = List.nub xs == nub xs--prop_nub_isSorted :: [Int] -> Bool-prop_nub_isSorted xs = isSortedBy (<) (nub xs)--prop_nubSort_isSorted :: [Int] -> Bool-prop_nubSort_isSorted xs = isSortedBy (<) (nubSort xs)--prop_isect_subset :: OrderedList Int -> OrderedList Int -> Bool-prop_isect_subset (Ordered xs) (Ordered ys)- = let zs = isect xs ys- in zs `subset` xs && zs `subset` ys--prop_isect_examples- = isect [1,2,3,4] [3,4,5,6] == [3,4]- && isect [1,3,5] [2,4,6] == []- && isect [2,4,6,8] [3,6,9] == [6]- && isect [1,2,2,2] [1,1,1,2,2] == [1,2,2]--prop_union_subset :: OrderedList Int -> OrderedList Int -> Bool-prop_union_subset (Ordered xs) (Ordered ys)- = let zs = union xs ys- in xs `subset` zs && ys `subset` zs--prop_isect_subset_union :: OrderedList Int -> OrderedList Int -> Bool-prop_isect_subset_union (Ordered xs) (Ordered ys)- = isect xs ys `subset` union xs ys--prop_union_examples- = union [1,2,3,4] [3,4,5,6] == [1..6]- && union [1,3,5] [2,4,6] == [1..6]- && union [2,4,6,8] [3,6,9] == [2,3,4,6,8,9]- && union [1,2,2,2] [1,1,1,2,2] == [1,1,1,2,2,2]--prop_minus_subset :: OrderedList Int -> OrderedList Int -> Bool-prop_minus_subset (Ordered xs) (Ordered ys)- = minus xs ys `subset` xs--prop_minus_examples- = minus [1,2,3,4] [3,4,5,6] == [1,2]- && minus [1,3,5] [2,4,6] == [1,3,5]- && minus [2,4,6,8] [3,6,9] == [2,4,8]- && minus [1,2,2,2] [1,1,1,2,2] == [2]--prop_xunion_subset_union :: OrderedList Int -> OrderedList Int -> Bool-prop_xunion_subset_union (Ordered xs) (Ordered ys)- = xunion xs ys `subset` union xs ys--prop_merge_xunion_isect_union :: OrderedList Int -> OrderedList Int -> Bool-prop_merge_xunion_isect_union (Ordered xs) (Ordered ys)- = merge (xunion xs ys) (isect xs ys) == union xs ys--prop_merge_union_isect_merge :: OrderedList Int -> OrderedList Int -> Bool-prop_merge_union_isect_merge (Ordered xs) (Ordered ys)- = merge (union xs ys) (isect xs ys) == merge xs ys--prop_minus_merge_isect_union :: OrderedList Int -> OrderedList Int -> Bool-prop_minus_merge_isect_union (Ordered xs) (Ordered ys)- = minus (merge xs ys) (isect xs ys) == union xs ys--prop_minus_union_isect_xunion :: OrderedList Int -> OrderedList Int -> Bool-prop_minus_union_isect_xunion (Ordered xs) (Ordered ys)- = minus (union xs ys) (isect xs ys) == xunion xs ys--prop_xunion_examples- = xunion [1,2,3,4] [3,4,5,6] == [1,2,5,6]- && xunion [1,3,5] [2,4,6] == [1..6]- && xunion [2,4,6,8] [3,6,9] == [2,3,4,8,9]- && xunion [1,2,2,2] [1,1,1,2,2] == [1,1,2]--prop_merge_subset :: OrderedList Int -> OrderedList Int -> Bool-prop_merge_subset (Ordered xs) (Ordered ys)- = union xs ys `subset` merge xs ys--prop_merge_examples- = merge [1,2,3,4] [3,4,5,6] == [1,2,3,3,4,4,5,6]- && merge [1,3,5] [2,4,6] == [1,2,3,4,5,6]- && merge [2,4,6,8] [3,6,9] == [2,3,4,6,6,8,9]- && merge [1,2,2,2] [1,1,1,2,2] == [1,1,1,1,2,2,2,2,2]--prop_nub_examples- = nub [1,1,1,2,2] == [1,2]- && nub [2,0,1,3,3] == [2,3]--safeHead [] = Nothing-safeHead (a:_) = Just a--newtype HeadOrderedLists x = HeadOrdered [[x]] deriving (Eq, Ord, Show, Read)--instance (Ord a, Arbitrary a) => Arbitrary (HeadOrderedLists a) where- arbitrary = (HeadOrdered . sortOn' safeHead . map sort) `fmap` arbitrary- shrink _ = []--prop_mergeAll :: HeadOrderedLists Int -> Bool-prop_mergeAll (HeadOrdered xss)- = foldr merge [] xss == mergeAll xss--approxEq xs ys = take n xs == take n ys- where n = 1000--triangle n = replicate n n ++ triangle (n+1)--prop_mergeAll_productive = mergeAll [ [n..] | n <- [1..] ] `approxEq` triangle 1--prop_unionAll :: HeadOrderedLists Int -> Bool-prop_unionAll (HeadOrdered xss)- = foldr union [] xss == unionAll xss--prop_unionAll_productive = unionAll [ [n..] | n <- [1..] ] `approxEq` [1..]--quickCheckOnce = quickCheckWith (stdArgs {maxSuccess = 1})--main = do- putStr "\nprop_member\n"- quickCheck prop_member-- putStr "\nprop_insertBag_sort\n"- quickCheck prop_insertBag_sort-- putStr "\nprop_insertSet_nubSort\n"- quickCheck prop_insertSet_nubSort-- putStr "\nprop_nub\n"- quickCheck prop_nub-- putStr "\nprop_nub_isSorted\n"- quickCheck prop_nub_isSorted-- putStr "\nprop_nubSort_isSorted\n"- quickCheck prop_nubSort_isSorted-- putStr "\nprop_isect_subset\n"- quickCheck prop_isect_subset-- putStr "\nprop_isect_examples\n"- quickCheckOnce prop_isect_examples-- putStr "\nprop_union_subset\n"- quickCheck prop_union_subset-- putStr "\nprop_isect_subset_union\n"- quickCheck prop_isect_subset_union-- putStr "\nprop_union_examples\n"- quickCheckOnce prop_union_examples-- putStr "\nprop_minus_subset\n"- quickCheck prop_minus_subset-- putStr "\nprop_minus_examples\n"- quickCheckOnce prop_minus_examples-- putStr "\nprop_xunion_subset_union\n"- quickCheck prop_xunion_subset_union-- putStr "\nprop_merge_xunion_isect_union\n"- quickCheck prop_merge_xunion_isect_union-- putStr "\nprop_merge_union_isect_merge\n"- quickCheck prop_merge_union_isect_merge-- putStr "\nprop_minus_merge_isect_union\n"- quickCheck prop_minus_merge_isect_union-- putStr "\nprop_minus_union_isect_xunion\n"- quickCheck prop_minus_union_isect_xunion-- putStr "\nprop_xunion_examples\n"- quickCheckOnce prop_xunion_examples-- putStr "\nprop_merge_subset\n"- quickCheck prop_merge_subset-- putStr "\nprop_merge_examples\n"- quickCheckOnce prop_merge_examples-- putStr "\nprop_nub_examples\n"- quickCheckOnce prop_nub_examples-- putStr "\nprop_mergeAll\n"- quickCheck prop_mergeAll-- putStr "\nprop_mergeAll_productive\n"- quickCheckOnce prop_mergeAll_productive-- putStr "\nprop_unionAll\n"- quickCheck prop_unionAll-- putStr "\nprop_unionAll_productive\n"- quickCheckOnce prop_unionAll_productive