summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorChrisDornan <>2017-05-19 09:51:00 (GMT)
committerhdiff <hdiff@hdiff.luite.com>2017-05-19 09:51:00 (GMT)
commite14f733a7c295aa103732ded8056e6aa5d531db8 (patch)
tree0525d8470cfd3fed340e0a6569e9394557e607e5
parent00af5e97500b0f5339bc32254232494d0c837046 (diff)
version 0.1.0.0HEAD0.1.0.0master
-rw-r--r--README.markdown28
-rw-r--r--Setup.hs2
-rw-r--r--sort.cabal14
-rw-r--r--src/Data/Sort.hs141
4 files changed, 166 insertions, 19 deletions
diff --git a/README.markdown b/README.markdown
new file mode 100644
index 0000000..79f44d8
--- /dev/null
+++ b/README.markdown
@@ -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
+
+[![hackage](https://img.shields.io/hackage/v/sort.svg)](https://hackage.haskell.org/package/sort) [![license](http://img.shields.io/badge/license-BSD3-brightgreen.svg)](https://tldrlegal.com/license/bsd-3-clause-license-%28revised%29) [![Linux+macOS](https://travis-ci.org/cdornan/sort.svg?branch=master)](https://travis-ci.org/cdornan/sort) [![Windows](https://ci.appveyor.com/api/projects/status/whik8b8w7ho29rn6/branch/master?svg=true)](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)
diff --git a/Setup.hs b/Setup.hs
new file mode 100644
index 0000000..9a994af
--- /dev/null
+++ b/Setup.hs
@@ -0,0 +1,2 @@
+import Distribution.Simple
+main = defaultMain
diff --git a/sort.cabal b/sort.cabal
index 6cf05ec..14ba1c0 100644
--- a/sort.cabal
+++ b/sort.cabal
@@ -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 @@ Maintainer: Chris Dornan <chris@chrisdornan.com>
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 @@ Library
-fwarn-tabs
Build-depends:
- base >= 4 && < 5
+ base >= 4.8 && < 5
diff --git a/src/Data/Sort.hs b/src/Data/Sort.hs
index 176501c..bb98f9e 100644
--- a/src/Data/Sort.hs
+++ b/src/Data/Sort.hs
@@ -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 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 a list of elements with a stable sort, using the argument
+-- | 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