sort 0.0.0.1 → 0.1.0.0
raw patch · 4 files changed
+166/−19 lines, 4 filesdep ~basesetup-changed
Dependency ranges changed: base
Files
- README.markdown +28/−0
- Setup.hs +2/−0
- sort.cabal +6/−8
- src/Data/Sort.hs +130/−11
+ README.markdown view
@@ -0,0 +1,28 @@+# sort++A library of general-purpose sorting utilities.+++## Roadmap and Changelog++See the [roadmap](https://github.com/cdornan/sort/tree/master/roadmap.md) for news of upcoming releases and the [benchmarks](https://github.com/cdornan/sort/tree/master/benchmarks) for+details of previous releases.+++## Build Status++[](https://hackage.haskell.org/package/sort) [](https://tldrlegal.com/license/bsd-3-clause-license-%28revised%29) [](https://travis-ci.org/cdornan/sort) [](https://ci.appveyor.com/project/cdornan/sort/branch/master)+++## Benchmarks and Tests++We maintain [benchmarks](https://github.com/cdornan/sort/tree/master/benchmarks)+for this package.+++## Helping out++As always your input is crucial for the success of the package!++ * [the issues](https://github.com/cdornan/sort/issues)+ * [the pull requests](https://github.com/cdornan/sort/pulls)
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
sort.cabal view
@@ -1,5 +1,5 @@ Name: sort-Version: 0.0.0.1+Version: 0.1.0.0 Synopsis: A Haskell sorting toolkit Description: A library of general-purpose sorting utilities. Homepage: https://github.com/cdornan/sort@@ -10,20 +10,18 @@ Copyright: Chris Dornan 2017 Category: Text Build-type: Simple-Stability: Experimental+Stability: RFC bug-reports: https://github.com/cdornan/sort/issues +Extra-Source-Files:+ README.markdown+ Cabal-Version: >= 1.10 Source-Repository head type: git location: https://github.com/cdornan/sort.git -Source-Repository this- Type: git- Location: https://github.com/cdornan/sort.git- Tag: 0.0.0.1- Library Hs-Source-Dirs: src @@ -36,4 +34,4 @@ -fwarn-tabs Build-depends:- base >= 4 && < 5+ base >= 4.8 && < 5
src/Data/Sort.hs view
@@ -1,29 +1,148 @@+ module Data.Sort- ( groupSort- , groupSortWith+ (+ -- * The Vanilla Sorts+ L.sort+ , L.sortBy+ , L.sortOn+ -- * Sorting Associations+ , monoidSortAssocs+ , monoidSortAssocsBy+ , groupSortAssocs+ , groupSortAssocsBy+ -- * Sorting with Monoids+ , monoidSort+ , monoidSortOn+ , monoidSortBy+ -- * Unique Sorts+ , uniqueSort+ , uniqueSortOn+ , uniqueSortBy+ -- * Group Sorting+ , groupSort+ , groupSortOn+ , groupSortBy ) where -import Data.List+import qualified Data.List as L+import Data.Monoid+import Data.Ord --- | sort a list of elements with a stable sort, grouping together the--- equal elements with the argument grouping function-groupSort :: Ord a => (a->[a]->b) -> [a] -> [b]-groupSort = groupSortWith compare+-- | Sort the list of associations, aggregating duplicates with the+-- monoid.+monoidSortAssocs :: (Monoid a,Ord k)+ => [(k,a)]+ -> [(k,a)]+monoidSortAssocs = monoidSortAssocsBy compare +-- | Sort the list of associations, aggregating duplicates with the+-- monoid and ordering the keys with the argument compare function.+monoidSortAssocsBy :: (Monoid a)+ => (k->k->Ordering)+ -> [(k,a)]+ -> [(k,a)]+monoidSortAssocsBy cmp = groupSortAssocsBy cmp $ const monoid_group --- | sort a list of elements with a stable sort, using the argument+-- | Sort the list of associations, aggregating duplicates with the+-- supplied function.+groupSortAssocs :: Ord k+ => (k->a->[a]->b)+ -> [(k,a)]+ -> [(k,b)]+groupSortAssocs = groupSortAssocsBy compare++-- | Sort the list of associations, aggregating duplicates with the+-- supplied function and ordering the keys with the argument+-- compare function.+groupSortAssocsBy :: (k->k->Ordering)+ -> (k->a->[a]->b)+ -> [(k,a)]+ -> [(k,b)]+groupSortAssocsBy cmp0 grp0 = groupSortBy cmp grp+ where+ cmp (k,_) (k',_) = cmp0 k k'++ grp (k,y) ps = (,) k $ grp0 k y $ map snd ps+++-- | Sort the list, agregating duplicates with the monoid.+monoidSort :: (Monoid a,Ord a) => [a] -> [a]+monoidSort = monoidSortBy compare++-- | Sort the list, agregating duplicates with the monoid and+-- ordering the elements by the items generated by the+-- argument function.+monoidSortOn :: (Monoid a,Ord k) => (a->k) -> [a] -> [a]+monoidSortOn chg = groupSortOn chg $ const monoid_group++-- | Sort the list, agregating duplicates with the monoid+-- and ordering the keys with the argument compare function.+monoidSortBy :: Monoid a => (a->a->Ordering) -> [a] -> [a]+monoidSortBy cmp = groupSortBy cmp monoid_group+++-- | Sort the list, discarding duplicates.+uniqueSort :: Ord a => [a] -> [a]+uniqueSort = uniqueSortBy compare++-- | Sort the list, discarding duplicates and+-- ordering the elements by the items generated by the+-- argument function.+uniqueSortOn :: Ord k => (a->k) -> [a] -> [a]+uniqueSortOn chg = groupSortOn chg $ const const++-- | Sort the list, discarding duplicates and ordering the keys with+-- the argument compare function.+uniqueSortBy :: (a->a->Ordering) -> [a] -> [a]+uniqueSortBy cmp = groupSortBy cmp const+++-- | Sort a list of elements with a stable sort, grouping together the+-- equal elements with the argument grouping function+groupSort :: (Ord a) => (a->[a]->b) -> [a] -> [b]+groupSort = groupSortBy compare++-- | Sort a list of elements with a stable sort, using the argument -- @compare@ function determine the ordering, grouping together the -- equal elements with the grouping function-groupSortWith :: (a->a->Ordering) -> (a->[a]->b) -> [a] -> [b]-groupSortWith cmp grp = aggregate . sortBy cmp+groupSortOn :: Ord k+ => (a->k)+ -> (k->a->[a]->b)+ -> [a]+ -> [b]+groupSortOn chg grp = groupSortBy (comparing fst) grp_val . map inj where+ grp_val a as = grp k (snd a) $ map snd as+ where+ k = fst a++ inj x = k `seq` (k,x)+ where+ k = chg x+++-- | Sort a list of elements with a stable sort, grouping together the+-- equal elements with the argument grouping function.+groupSortBy :: (a->a->Ordering)+ -> (a->[a]->b)+ -> [a]+ -> [b]+groupSortBy cmp grp = aggregate . L.sortBy cmp+ where aggregate [] = []- aggregate (h:t) = grp h eqs : aggregate rst+ aggregate (h:t) = seq g $ g : aggregate rst where+ g = grp h eqs (eqs,rst) = span is_le t is_le x = case cmp x h of LT -> True EQ -> True GT -> False+++-- the monoid_group helper++monoid_group :: Monoid a => a -> [a] -> a+monoid_group x xs = x <> mconcat xs