packages feed

raft 0.3.2.2 → 0.3.7.0

raw patch · 5 files changed

+490/−2 lines, 5 filesdep +parallel

Dependencies added: parallel

Files

raft.cabal view
@@ -1,5 +1,5 @@ name              : raft-version           : 0.3.2.2+version           : 0.3.7.0 synopsis          : Miscellaneous Haskell utilities for data structures and data manipulation. description       : This Haskell library contains miscellaneous data structures and data manipulation functions for general uses. @@ -14,7 +14,7 @@ cabal-version     : >= 1.10 homepage          : https://bitbucket.org/functionally/raft bug-reports       : https://bwbush.atlassian.net/projects/HRAFT/issues/-package-url       : https://bitbucket.org/functionally/raft/downloads/raft-0.3.2.2.tar.gz+package-url       : https://bitbucket.org/functionally/raft/downloads/raft-0.3.7.0.tar.gz  source-repository head   type            : mercurial@@ -30,6 +30,9 @@                     Data.Functor.Util                     Data.Function.Excel                     Data.Function.Finance+                    Data.Function.MapReduce+                    Data.Function.MapReduce.Internal+                    Data.Function.MapReduce.Parallel                     Data.Function.Tabulated                     Data.Function.Util                     Data.List.Util@@ -60,6 +63,7 @@                   , data-default >= 0.7.1                   , ghc-prim     >= 0.4.0                   , mtl          >= 2.2.1+                  , parallel     >= 3.2.0                   , scientific   >= 0.3.3                   , split        >= 0.2.2                   , text         >= 1.2.1
+ src/Data/Function/MapReduce.hs view
@@ -0,0 +1,146 @@+-----------------------------------------------------------------------------+--+-- Module      :  Data.Function.MapReduce+-- Copyright   :  (c) 2016 Brian W Bush+-- License     :  MIT+--+-- Maintainer  :  Brian W Bush <consult@brianwbush.info>+-- Stability   :  Stable+-- Portability :  Portable+--+-- | Various map-reduce functions.+--+-----------------------------------------------------------------------------+++{-# LANGUAGE Safe #-}+++module Data.Function.MapReduce (+-- * Grouping+  groupReduce+, groupReduceFlatten+, groupReduceByKey+, groupReduceFlattenByKey+, groupExtract+-- * Map-Reduce+, mapReduce+, mapReduceFlatten+, mapReduceFinalize+-- * Aggregation+, aggregate+, aggregateByKey+, aggregateWithKey+) where+++import Data.List.Util (sortedGroups)++import qualified Data.Function.MapReduce.Internal as I+++-- | Reduce values by group.+groupReduce :: Ord k+            => (a -> k)   -- ^ Function for extracting keys for grouping.+            -> ([a] -> b) -- ^ Function for reducing values.+            -> [a]        -- ^ The values.+            -> [b]        -- ^ The reduced values.+groupReduce = I.groupReduce mapReduce+++-- | Reduce values by group, and flatten the result.+groupReduceFlatten :: Ord k+                   => (a -> k)     -- ^ Function for extracting keys for grouping.+                   -> ([a] -> [b]) -- ^ Function for reducing values.+                   -> [a]          -- ^ The values.+                   -> [b]          -- ^ The reduced values.+groupReduceFlatten = I.groupReduceFlatten mapReduce+++-- | Reduce values by group, where the reducer receives the key.+groupReduceByKey :: Ord k+                 => (a -> k)        -- ^ Function for extracting keys for grouping.+                 -> (k -> [a] -> b) -- ^ Function for reducing values.+                 -> [a]             -- ^ The values.+                 -> [b]             -- ^ The reduced values.+groupReduceByKey = I.groupReduceByKey mapReduce+++-- | Reduce values by group, and flatten the result, where the reducer receives the key.+groupReduceFlattenByKey :: Ord k+                        => (a -> k)          -- ^ Function for extracting keys for grouping.+                        -> (k -> [a] -> [b]) -- ^ Function for reducing values.+                        -> [a]               -- ^ The values.+                        -> [b]               -- ^ The reduced values.+groupReduceFlattenByKey = I.groupReduceFlattenByKey mapReduce+++-- | Order and extract values.+groupExtract :: Ord k+             => (a -> k) -- ^ Function for extracting keys for grouping.+             -> (a -> b) -- ^ Function for extracting values.+             -> [a]      -- ^ The values.+             -> [b]      -- ^ The extract.+groupExtract = I.groupExtract mapReduce+++-- | Reduce values by keying them.+mapReduce :: Ord k+          => (a -> (k, v))   -- ^ Function for mapping to keys and values.+          -> (k -> [v] -> b) -- ^ Function for reducing values.+          -> [a]             -- ^ The values.+          -> [b]             -- ^ The reduced values.+mapReduce mapper reducer =+  map (uncurry reducer)+    . sortedGroups+    . map mapper+++-- | Reduce values by keying them, and flatten the result.+mapReduceFlatten :: Ord k+                 => (a -> (k, v))     -- ^ Function for mapping to keys and values.+                 -> (k -> [v] -> [b]) -- ^ Function for reducing values.+                 -> [a]               -- ^ The values.+                 -> [b]               -- ^ The reduced values.+mapReduceFlatten = I.mapReduceFlatten mapReduce+++-- | Reduce values by keying them, transforming the result.+mapReduceFinalize :: Ord k+                  => (a -> (k, v))   -- ^ Function for mapping to keys and values.+                  -> (k -> [v] -> v) -- ^ Function for reducing values.+                  -> (k -> v -> b)   -- ^ Function for transforming the reduced values.+                  -> [a]             -- ^ The values.+                  -> [b]             -- ^ The reduced values.+mapReduceFinalize = I.mapReduceFinalize mapReduce+++-- | Aggregate values.+aggregate :: (a -> v)   -- ^ Function to extract values.+          -> ([v] -> b) -- ^ Function to aggregate a list of values.+          -> [a]        -- ^ The values.+          -> b          -- ^ The aggregate.+aggregate = I.aggregate mapReduce+{- FIXME: The following probably performs better?+  flip (.) . map+-}+++-- | Aggregate values by key.+aggregateByKey :: Ord k+               => (a -> k)   -- ^ Function for extracting keys.+               -> (a -> v)   -- ^ Function for extracting values.+               -> ([v] -> b) -- ^ Function to aggregate a list of values.+               -> [a]        -- ^ The values.+               -> [b]        -- ^ The aggregates.+aggregateByKey = I.aggregateByKey mapReduce+++-- | Aggregate values by key.+aggregateWithKey :: Ord k+                 => (a -> k)        -- ^ Function for extracting keys.+                 -> (a -> v)        -- ^ Function for extracting values.+                 -> (k -> [v] -> b) -- ^ Function to aggregate a list of values.+                 -> [a]             -- ^ The values.+                 -> [b]             -- ^ The aggregates.+aggregateWithKey = I.aggregateWithKey mapReduce
+ src/Data/Function/MapReduce/Internal.hs view
@@ -0,0 +1,169 @@+-----------------------------------------------------------------------------+--+-- Module      :  Data.Function.MapReduce.Internal+-- Copyright   :  (c) 2016 Brian W Bush+-- License     :  MIT+--+-- Maintainer  :  Brian W Bush <consult@brianwbush.info>+-- Stability   :  Stable+-- Portability :  Portable+--+-- | Generic implementation of various map-reduce functions.+--+-----------------------------------------------------------------------------+++{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE RankNTypes       #-}+{-# LANGUAGE Safe             #-}+++module Data.Function.MapReduce.Internal (+-- * Types+  MapReduce+-- * Grouping+, groupReduce+, groupReduceFlatten+, groupReduceByKey+, groupReduceFlattenByKey+, groupExtract+-- * Map-Reduce+, mapReduceFlatten+, mapReduceFinalize+-- * Aggregation+, aggregate+, aggregateByKey+, aggregateWithKey+) where+++import Control.Applicative (liftA2)+import Control.Arrow ((&&&))+++-- | Functiom for mapping and then reducing.+type MapReduce a k v b =  Ord k+               => (a -> (k, v))   -- ^ Function for mapping to keys and values.+               -> (k -> [v] -> b) -- ^ Function for reducing values.+               -> [a]             -- ^ The values.+               -> [b]             -- ^ The reduced values.+++-- | Reduce values by group.+groupReduce :: Ord k+            => MapReduce a k a b +            -> (a -> k)          -- ^ Function for extracting keys for grouping.+            -> ([a] -> b)        -- ^ Function for reducing values.+            -> [a]               -- ^ The values.+            -> [b]               -- ^ The reduced values.+groupReduce mapReduce =+  (. const)+    . mapReduce+    . (&&& id)+++-- | Reduce values by group, and flatten the result.+groupReduceFlatten :: Ord k+                   => MapReduce a k a [b]+                   -> (a -> k)            -- ^ Function for extracting keys for grouping.+                   -> ([a] -> [b])        -- ^ Function for reducing values.+                   -> [a]                 -- ^ The values.+                   -> [b]                 -- ^ The reduced values.+groupReduceFlatten mapReduce =+  ((concat .) .)+    . groupReduce mapReduce+++-- | Reduce values by group, where the reducer receives the key.+groupReduceByKey :: Ord k+                 => MapReduce a k a b+                 -> (a -> k)          -- ^ Function for extracting keys for grouping.+                 -> (k -> [a] -> b)   -- ^ Function for reducing values.+                 -> [a]               -- ^ The values.+                 -> [b]               -- ^ The reduced values.+groupReduceByKey mapReduce =+  mapReduce+    . (&&& id)+++-- | Reduce values by group, and flatten the result, where the reducer receives the key.+groupReduceFlattenByKey :: Ord k+                        => MapReduce a k a [b]+                        -> (a -> k)            -- ^ Function for extracting keys for grouping.+                        -> (k -> [a] -> [b])   -- ^ Function for reducing values.+                        -> [a]                 -- ^ The values.+                        -> [b]                 -- ^ The reduced values.+groupReduceFlattenByKey mapReduce =+  ((concat .) . )+    . groupReduceByKey mapReduce+++-- | Order and extract values.+groupExtract :: Ord k+             => MapReduce a k a [b]+             -> (a -> k)            -- ^ Function for extracting keys for grouping.+             -> (a -> b)            -- ^ Function for extracting values.+             -> [a]                 -- ^ The values.+             -> [b]                 -- ^ The extract.+groupExtract mapReduce =+  (. map)+    . groupReduceFlatten mapReduce+++-- | Reduce values by keying them, and flatten the result.+mapReduceFlatten :: Ord k+                 => MapReduce a k v [b]+                 -> (a -> (k, v))       -- ^ Function for mapping to keys and values.+                 -> (k -> [v] -> [b])   -- ^ Function for reducing values.+                 -> [a]                 -- ^ The values.+                 -> [b]                 -- ^ The reduced values.+mapReduceFlatten mapReduce =+  ((concat .) .)+    . mapReduce+++-- | Reduce values by keying them, transforming the result.+mapReduceFinalize :: Ord k+                  => MapReduce a k v b+                  -> (a -> (k, v))     -- ^ Function for mapping to keys and values.+                  -> (k -> [v] -> v)   -- ^ Function for reducing values.+                  -> (k -> v -> b)     -- ^ Function for transforming the reduced values.+                  -> [a]               -- ^ The values.+                  -> [b]               -- ^ The reduced values.+mapReduceFinalize mapReduce mapper reducer finalizer =+  mapReduce mapper+    $ liftA2 (.) finalizer reducer+++-- | Aggregate values.+aggregate :: MapReduce a () v b+          -> (a -> v)           -- ^ Function to extract values.+          -> ([v] -> b)         -- ^ Function to aggregate a list of values.+          -> [a]                -- ^ The values.+          -> b                  -- ^ The aggregate.+aggregate mapReduce =+  ((head .) .) . aggregateByKey mapReduce (const ())+++-- | Aggregate values by key.+aggregateByKey :: Ord k+               => MapReduce a k v b+               -> (a -> k)          -- ^ Function for extracting keys.+               -> (a -> v)          -- ^ Function for extracting values.+               -> ([v] -> b)        -- ^ Function to aggregate a list of values.+               -> [a]               -- ^ The values.+               -> [b]               -- ^ The aggregates.+aggregateByKey mapReduce keyer extractor =+  aggregateWithKey mapReduce keyer extractor . const+++-- | Aggregate values by key.+aggregateWithKey :: Ord k+                 => MapReduce a k v b+                 -> (a -> k)          -- ^ Function for extracting keys.+                 -> (a -> v)          -- ^ Function for extracting values.+                 -> (k -> [v] -> b)   -- ^ Function to aggregate a list of values.+                 -> [a]               -- ^ The values.+                 -> [b]               -- ^ The aggregates.+aggregateWithKey mapReduce keyer extractor =+  mapReduce (keyer &&& extractor)
+ src/Data/Function/MapReduce/Parallel.hs view
@@ -0,0 +1,159 @@+-----------------------------------------------------------------------------+--+-- Module      :  Data.Function.MapReduce.Parallel+-- Copyright   :  (c) 2016 Brian W Bush+-- License     :  MIT+--+-- Maintainer  :  Brian W Bush <consult@brianwbush.info>+-- Stability   :  Stable+-- Portability :  Portable+--+-- | Various map-reduce functions, with parallelism.+--+-----------------------------------------------------------------------------+++{-# LANGUAGE ExplicitForAll #-}+{-# LANGUAGE RankNTypes     #-}+++module Data.Function.MapReduce.Parallel (+-- * Grouping+  groupReduce+, groupReduceFlatten+, groupReduceByKey+, groupReduceFlattenByKey+, groupExtract+-- * Map-Reduce+, mapReduce+, mapReduceFlatten+, mapReduceFinalize+-- * Aggregation+, aggregate+, aggregateByKey+, aggregateWithKey+) where+++import Control.Parallel.Strategies (Strategy, parMap)+import Data.List.Util (sortedGroups)++import qualified Data.Function.MapReduce.Internal as I+++-- | Reduce values by group.+groupReduce :: Ord k+            => (forall z . Strategy z) -- ^ The evaluation strategy.+            -> (a -> k)                -- ^ Function for extracting keys for grouping.+            -> ([a] -> b)              -- ^ Function for reducing values.+            -> [a]                     -- ^ The values.+            -> [b]                     -- ^ The reduced values.+{- FIXME: Why can't this be written in pointfree style?+groupReduce = I.groupReduce . mapReduce+-}+groupReduce strategy = I.groupReduce $ mapReduce strategy+++-- | Reduce values by group, and flatten the result.+groupReduceFlatten :: Ord k+                   => (forall z . Strategy z) -- ^ The evaluation strategy.+                   -> (a -> k)                -- ^ Function for extracting keys for grouping.+                   -> ([a] -> [b])            -- ^ Function for reducing values.+                   -> [a]                     -- ^ The values.+                   -> [b]                     -- ^ The reduced values.+groupReduceFlatten strategy = I.groupReduceFlatten $ mapReduce strategy+++-- | Reduce values by group, where the reducer receives the key.+groupReduceByKey :: Ord k+                 => (forall z . Strategy z) -- ^ The evaluation strategy.+                 -> (a -> k)                -- ^ Function for extracting keys for grouping.+                 -> (k -> [a] -> b)         -- ^ Function for reducing values.+                 -> [a]                     -- ^ The values.+                 -> [b]                     -- ^ The reduced values.+groupReduceByKey strategy = I.groupReduceByKey $ mapReduce strategy+++-- | Reduce values by group, and flatten the result, where the reducer receives the key.+groupReduceFlattenByKey :: Ord k+                        => (forall z . Strategy z) -- ^ The evaluation strategy.+                        -> (a -> k)                -- ^ Function for extracting keys for grouping.+                        -> (k -> [a] -> [b])       -- ^ Function for reducing values.+                        -> [a]                     -- ^ The values.+                        -> [b]                     -- ^ The reduced values.+groupReduceFlattenByKey strategy = I.groupReduceFlattenByKey $ mapReduce strategy+++-- | Order and extract values.+groupExtract :: Ord k+             => (forall z . Strategy z) -- ^ The evaluation strategy.+             -> (a -> k)                -- ^ Function for extracting keys for grouping.+             -> (a -> b)                -- ^ Function for extracting values.+             -> [a]                     -- ^ The values.+             -> [b]                     -- ^ The extract.+groupExtract strategy = I.groupExtract $ mapReduce strategy+++-- | Reduce values by keying them.+mapReduce :: Ord k+          => (forall z . Strategy z) -- ^ The evaluation strategy.+          -> (a -> (k, v))           -- ^ Function for mapping to keys and values.+          -> (k -> [v] -> b)         -- ^ Function for reducing values.+          -> [a]                     -- ^ The values.+          -> [b]                     -- ^ The reduced values.+mapReduce strategy mapper reducer =+  parMap strategy (uncurry reducer)+    . sortedGroups+    . parMap strategy mapper+++-- | Reduce values by keying them, and flatten the result.+mapReduceFlatten :: Ord k+                 => (forall z . Strategy z) -- ^ The evaluation strategy.+                 -> (a -> (k, v))           -- ^ Function for mapping to keys and values.+                 -> (k -> [v] -> [b])       -- ^ Function for reducing values.+                 -> [a]                     -- ^ The values.+                 -> [b]                     -- ^ The reduced values.+mapReduceFlatten strategy = I.mapReduceFlatten $ mapReduce strategy+++-- | Reduce values by keying them, transforming the result.+mapReduceFinalize :: Ord k+                  => (forall z . Strategy z) -- ^ The evaluation strategy.+                  -> (a -> (k, v))           -- ^ Function for mapping to keys and values.+                  -> (k -> [v] -> v)         -- ^ Function for reducing values.+                  -> (k -> v -> b)           -- ^ Function for transforming the reduced values.+                  -> [a]                     -- ^ The values.+                  -> [b]                     -- ^ The reduced values.+mapReduceFinalize strategy = I.mapReduceFinalize $ mapReduce strategy+++-- | Aggregate values.+aggregate :: (forall z . Strategy z) -- ^ The evaluation strategy.+          -> (a -> v)                -- ^ Function to extract values.+          -> ([v] -> b)              -- ^ Function to aggregate a list of values.+          -> [a]                     -- ^ The values.+          -> b                       -- ^ The aggregate.+aggregate strategy = I.aggregate $ mapReduce strategy+++-- | Aggregate values by key.+aggregateByKey :: Ord k+               => (forall z . Strategy z) -- ^ The evaluation strategy.+               -> (a -> k)                -- ^ Function for extracting keys.+               -> (a -> v)                -- ^ Function for extracting values.+               -> ([v] -> b)              -- ^ Function to aggregate a list of values.+               -> [a]                     -- ^ The values.+               -> [b]                     -- ^ The aggregates.+aggregateByKey strategy = I.aggregateByKey $ mapReduce strategy+++-- | Aggregate values by key.+aggregateWithKey :: Ord k+                 => (forall z . Strategy z) -- ^ The evaluation strategy.+                 -> (a -> k)                -- ^ Function for extracting keys.+                 -> (a -> v)                -- ^ Function for extracting values.+                 -> (k -> [v] -> b)         -- ^ Function to aggregate a list of values.+                 -> [a]                     -- ^ The values.+                 -> [b]                     -- ^ The aggregates.+aggregateWithKey strategy = I.aggregateWithKey $ mapReduce strategy
src/Data/List/Util.hs view
@@ -52,6 +52,7 @@ , lookupWithDefault , lookupWithDefaultFunction -- * Padding, stripping, and pruning.+, replicateHead , padHead , padTail , chunk@@ -226,6 +227,15 @@   -> [(a, b)] -- ^ The associations.   -> b        -- ^ The value for the key, or the default if the key is not present. lookupWithDefaultFunction f x = fromMaybe (f x) . lookup x+++-- | Relicating the head of a list.+replicateHead :: Int -- ^ Number of times to replicate the head.+              -> [a] -- ^ The list.+              -> [a] -- ^ The list with the replicas of the head.+replicateHead n =+  uncurry (++)+    . (replicate n . head &&& id)   -- | Pad the head of a list.