group-with 0.1.0.0 → 0.2.0.0
raw patch · 5 files changed
+147/−14 lines, 5 files
Files
- Control/GroupWith.hs +79/−10
- GroupWithTest.hs +55/−1
- README.md +1/−1
- changelog +10/−0
- group-with.cabal +2/−2
Control/GroupWith.hs view
@@ -1,4 +1,4 @@-+{-# LANGUAGE Safe, ScopedTypeVariables #-} ----------------------------------------------------------------------------- -- | -- Module : Control.GroupWiths@@ -7,29 +7,42 @@ -- Maintainer : ukoehler@techoverflow.net -- Stability : provisional -- Portability : portable---+-- -- A collection of grouping utility functions. -- For a given function that assigns a key to objects, -- provides functions that group said objects into a multimap -- by said key.---+-- -- This can be used similarly to the SQL GROUP BY statement.---+-- -- Provides a more flexible approach to GHC.Exts.groupWith---+-- -- > groupWith (take 1) ["a","ab","bc"] == Map.fromList [("a",["a","ab"]), ("b",["bc"])]+--+-- In order to use monadic / applicative functions as key generators,+-- use the A- or M-postfixed variants like 'groupWithA' or 'groupWithMultipleM'+--+-- -- ----------------------------------------------------------------------------- module Control.GroupWith( MultiMap, groupWith, groupWithMultiple,- groupWithUsing+ groupWithUsing,+ groupWithA,+ groupWithM,+ groupWithMultipleM,+ groupWithUsingM ) where -import Data.Map (Map)-import qualified Data.Map as Map+import Data.Map.Strict (Map)+import qualified Data.Map.Strict as Map +import Control.Arrow (first, second)+import Control.Applicative (Applicative, (<$>), liftA2, pure)+import Data.Traversable (sequenceA)+ type MultiMap a b = Map a [b] -- | Group values in a list by a key, generated@@ -42,7 +55,7 @@ -> MultiMap b a -- ^ The resulting key --> value multimap groupWith f xs = Map.fromListWith (++) [(f x, [x]) | x <- xs] --- | Like groupWith, but the identifier-generating function+-- | Like 'groupWith', but the identifier-generating function -- may generate multiple keys for each value (or none at all). -- The corresponding value from the original list will be placed -- in the identifier-corresponding map entry for each generated@@ -53,7 +66,7 @@ -> [a] -- ^ The list to be grouped -> MultiMap b a -- ^ The resulting map groupWithMultiple f xs = - let identifiers x = [(val, [x]) | val <- f x]+ let identifiers x = [(val, [x]) | val <- vals] where vals = f x in Map.fromListWith (++) $ concat [identifiers x | x <- xs] -- | Like groupWith, but uses a custom combinator function@@ -65,3 +78,59 @@ -> [a] -- ^ The list to be grouped -> Map b c -- ^ The resulting key --> transformed value map groupWithUsing t c f xs = Map.fromListWith c $ map (\v -> (f v, t v)) xs++-- | Fuse the functor from a tuple+fuseT2 :: Applicative f => (f a, f b) -> f (a,b)+fuseT2 = uncurry $ liftA2 (,)++-- | Like 'fuseT2', but only requires the first element to be boxed in the functor+fuseFirst :: Applicative f => (f a, b) -> f (a,b)+fuseFirst = fuseT2 . second pure++-- | Move the applicative functor to the outmost level by first mapping+-- fuseT2First and then applying 'Data.Traversable.sequenceA' to move+-- the functor outside the list+fuseFirstList :: Applicative f => [(f a, b)] -> f [(a,b)]+fuseFirstList = sequenceA . map fuseFirst++-- | Group values in a list by a key, generated by a given applicative function.+-- Applicative version of 'groupWith'. See 'groupWith' for documentation.+groupWithA :: (Ord b, Applicative f) =>+ (a -> f b) -- ^ The function used to map a list value to its key+ -> [a] -- ^ The list to be grouped+ -> f (MultiMap b a) -- ^ The resulting key --> value multimap+groupWithA f xs =+ Map.fromListWith (++) <$> fuseFirstList [(f x, [x]) | x <- xs]++-- | Alias for 'groupWithA', with additional monad constraint+groupWithM :: (Ord b, Monad m, Applicative m) =>+ (a -> m b) -- ^ The function used to map a list value to its key+ -> [a] -- ^ The list to be grouped+ -> m (MultiMap b a) -- ^ The resulting key --> value multimap+groupWithM = groupWithA++-- | Like 'groupWithM', but the identifier-generating function+-- may generate multiple keys for each value (or none at all).+-- See 'groupWithMultiple' for further behavioural details.+-- +-- Note that it's impossible to define this for applicatives:+-- See http://stackoverflow.com/a/6032260/2597135+groupWithMultipleM :: (Ord b, Monad m, Applicative m) =>+ (a -> m [b]) -- ^ The function used to map a list value to its keys+ -> [a] -- ^ The list to be grouped+ -> m (MultiMap b a) -- ^ The resulting map+groupWithMultipleM f xs = + let identifiers x = (\vals -> [(val, [x]) | val <- vals]) <$> f x+ idMap = concat <$> (mapM identifiers xs)+ in Map.fromListWith (++) <$> idMap++-- | Like 'groupWithM', but uses a custom combinator function+groupWithUsingM :: (Ord b, Monad m, Applicative m) =>+ (a -> m c) -- ^ Transformer function used to map a value to the resulting type+ -> (c -> c -> c) -- ^ The combinator used to combine an existing value+ -- for a given key with a new value+ -> (a -> m b) -- ^ The function used to map a list value to its key+ -> [a] -- ^ The list to be grouped+ -> m (Map b c) -- ^ The resulting key --> transformed value map+groupWithUsingM t c f xs =+ Map.fromListWith c <$> mapM (\v -> fuseT2 (f v, t v)) xs
GroupWithTest.hs view
@@ -4,6 +4,7 @@ import Control.Monad import Control.GroupWith import Data.Map (Map)+import Data.Maybe (fromJust) import Data.List (sort) import qualified Data.Map as Map @@ -47,7 +48,7 @@ -- We need to specialize here, because it's ⊥ let fn = error "This function should never be called" :: Int -> Int data_ = [] :: [Int]- result = groupWith fn data_+ result = groupWithUsing id (+) fn data_ in result `shouldSatisfy` ((==) 0 . Map.size) it "should be usable for counting" $ -- Instead of building up lists, we count the number of elements@@ -76,3 +77,56 @@ data_ = [] :: [Int] result = groupWithMultiple fn data_ in result `shouldSatisfy` ((==) 0 . Map.size)+ {-+ NOTE: We will use Maybe as monad / applicative functor for this test+ -}+ describe "groupWithM" $ do+ it "should group a simple value correctly" $+ let data_ = ["a","abc","ab","bc"]+ fn = Just . take 1+ ref = Map.fromList [("a",["a","abc","ab"]),("b",["bc"])]+ result = groupWithM fn data_+ in (fromJust result, ref) `shouldSatisfy` multimapTupleEq+ it "should return an empty map when given an empty list" $+ -- We need to specialize here, because it's ⊥+ let fn = error "This function should never be called" :: Int -> Maybe Int+ data_ = [] :: [Int]+ result = groupWithM fn data_+ in (fromJust result) `shouldSatisfy` ((==) 0 . Map.size)+ -- Fuzzing, couldn't get this to compile properly yet+ -- it "should not crash for any input string list" $+ -- property $ (\d -> groupWith (take 1) d `seq` True)+ describe "groupWithMultipleM" $ do+ it "should group correctly given a simple list" $+ let data_ = ["a","abc","ab","bc"]+ fn x = Just [take 1 x, take 2 x]+ -- Note the multiple "a"s in the first line:+ -- one from `take 1`, one from `take 2`+ ref = Map.fromList [("a",["a","a","abc","ab"]),+ ("ab",["ab","abc"]),+ ("b",["bc"]),+ ("bc",["bc"])]+ result = groupWithMultipleM fn data_+ in (fromJust result, ref) `shouldSatisfy` multimapTupleEq+ it "should return an empty map when given an empty list" $+ -- We need to specialize here, because it's ⊥+ let fn = error "This function should never be called" :: Int -> Maybe [Int]+ data_ = [] :: [Int]+ result = groupWithMultipleM fn data_+ in (fromJust result) `shouldSatisfy` ((==) 0 . Map.size)+ describe "groupWithUsingM" $ do+ it "should return an empty map when given an empty list" $+ -- We need to specialize here, because it's ⊥+ let fn = error "This function should never be called" :: Int -> Maybe Int+ data_ = [] :: [Int]+ result = groupWithUsingM return (+) fn data_+ in (fromJust result) `shouldSatisfy` ((==) 0 . Map.size)+ it "should be usable for counting" $+ -- Instead of building up lists, we count the number of elements+ let t n = return 1 -- For each x, count 1+ c = (+) -- Sum up the counts+ fn = return . take 1+ data_ = ["a","abc","ab","bc"]+ ref = Map.fromList [("a",3),("b",1)] :: Map String Int+ result = groupWithUsingM t c fn data_+ in fromJust result `shouldBe` ref
README.md view
@@ -1,4 +1,4 @@-group-by+group-with ======== A Haskell library to classify objects by a function value, just like SQL GROUP BY
+ changelog view
@@ -0,0 +1,10 @@+** 0.2.x++0.1.0.0 --> 0.2.0.0+===============++* Support monadic and applicative (where possible) grouping++* Add and fix unit tests for monadic and pure grouping++* Use strict map by default to avoid buildup of thunks
group-with.cabal view
@@ -1,5 +1,5 @@ name: group-with-version: 0.1.0.0+version: 0.2.0.0 synopsis: Classify objects by key-generating function, like SQL GROUP BY description: A library to classify objects into multimaps by using a function generating keys for any object in the list.@@ -15,7 +15,7 @@ -- copyright: category: Data build-type: Simple-extra-source-files: README.md+extra-source-files: README.md changelog cabal-version: >=1.10 source-repository head