folds-common 0.1.0.0 → 0.1.1.0
raw patch · 3 files changed
+134/−12 lines, 3 files
Files
- folds-common.cabal +1/−1
- src/Data/Fold/Common/L'.hs +70/−6
- src/Data/Fold/Common/M.hs +63/−5
folds-common.cabal view
@@ -1,5 +1,5 @@ name: folds-common-version: 0.1.0.0+version: 0.1.1.0 synopsis: A playground of common folds for folds description: In an effort to make @folds@ a more usable package this package provides a battery of common folds. These can be
src/Data/Fold/Common/L'.hs view
@@ -1,3 +1,7 @@+-- | A collection of common left folds. Note that all of these are+-- strict and do not short circuit. These are useful for operations+-- that require inspecting the entire list to calculate the final+-- state. module Data.Fold.Common.L' where import Data.Fold import Data.Fold.Internal@@ -5,23 +9,49 @@ import qualified Data.Set as S -- | Sum of the inputs+--+-- >>> run [1 .. 10] sum+-- 55 sum :: Num a => L' a a sum = L' id (+) 0 -- | Product of the input+--+-- >>> run [1 .. 10] product+-- 3628800 product :: Num a => L' a a product = L' id (*) 1 -- | Count the number of elements fed to a fold+--+-- >>> run [1 .. 10] count+-- 10+--+-- Note: GHCi will default @Enum e@ to @()@. If you see+--+-- > *** Exception: Prelude.Enum.().succ: bad argument+--+-- You've been bitten by this. count :: Enum e => L' a e count = L' id (\c _ -> succ c) (toEnum 0) -- | 'mappend' all the elements of a sequence together.-msum :: Monoid m => L' m m-msum = L' id mappend mempty+--+-- >>> run [[1, 2, 3, 4], [5, 6, 7, 8]] mconcat+-- [1, 2, 3, 4, 5, 6, 7, 8]+--+-- >>> run (map Sum [1, 2, 3, 4]) mconcat+-- Sum {getSum = 10}+mconcat :: Monoid m => L' m m+mconcat = L' id mappend mempty -- | Minimum of all inputs. If no inputs are supplied this returns -- 'Nothing'.+--+-- >>> run [1, 2, 3] minimum+-- 1+-- >>> run [1 ..] minimum+-- ... diverges ... minimum :: Ord a => L' a (Maybe a) minimum = L' id comp Nothing where comp Nothing a = Just a@@ -29,34 +59,68 @@ -- | Maximum of all inputs. If no inputs are supplied this returns -- 'Nothing'.+--+-- >>> run [1, 2, 3] maximum+-- 3+--+-- >>> run [1 ..] maximum+-- ... diverges ... maximum :: Ord a => L' a (Maybe a) maximum = L' id comp Nothing where comp Nothing a = Just a comp (Just b) a = Just (max a b) -- | De-duplicate all the inputs while preserving order. @O(n log(n))@+--+-- >>> run (replicate 10 1 ++ replicate 10 2) nub+-- [1, 2]+--+-- >>> run [1, 2, 1] nub+-- [1, 2] nub :: Ord a => L' a [a] nub = L' (\(Pair' _ l) -> reverse l) step (Pair' S.empty []) where step st@(Pair' s as) a | S.member a s = st | otherwise = Pair' (S.insert a s) (a : as) --- | De-duplicate all the inputs while preserving order. @O(n^2)@+-- | De-duplicate all the inputs while preserving+-- order. @O(n^2)@. This should be equivalent (but slower) then 'nub'+-- for 'Ord' types.+--+-- >>> run (replicate 10 1 ++ replicate 10 2) slowNub+-- [1, 2]+--+-- >>> run [1, 2, 1] slowNub+-- [1, 2] slowNub :: Eq a => L' a [a] slowNub = L' id step [] where step as a | a `elem` as = as | otherwise = a : as -- | Collect all members into a @Set@.+--+-- >>> run [1 .. 10] intoSet+-- fromList [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] intoSet :: Ord a => L' a (S.Set a) intoSet = L' id (flip S.insert) S.empty -- | Grab the last element inputted+--+-- >>> run [1 .. 10] last+-- Just 10+--+-- >>> run [] last+-- Nothing last :: L' a (Maybe a) last = L' id step Nothing- where step Nothing = Just- step x = const x+ where step _ = Just --- | Grab the nth element inputted+-- | Grab the nth element inputted.+--+-- >>> run [1 .. 10] (nth 5)+-- Just 6+--+-- >>> run [1 .. 10] (nth 20)+-- Nothing nth :: (Eq b, Num b) => b -> L' a (Maybe a) nth b = L' (\(Pair' e _) -> maybe' Nothing Just e) step (Pair' Nothing' b) where step st@(Pair' (Just' _) _) _ = st
src/Data/Fold/Common/M.hs view
@@ -1,3 +1,7 @@+-- | A collection of right folds. These are all short circuiting and+-- are designed to handle certain infinite cases properly. These are+-- useful for operations which don't require the full list to+-- calculate the output. module Data.Fold.Common.M where import Prelude hiding (any, all) import Data.Fold@@ -5,27 +9,62 @@ import Data.Monoid -- | Check that if predicate holds for any inputs to the fold.+--+-- >>> run [1, 2, 3, 4] (any even)+-- True+--+-- >>> run [] (any $ const False)+-- False any :: (a -> Bool) -> M a Bool any p = M getAny (Any . p) (<>) (Any False) -- | Check that if predicate holds for all inputs to the fold.+--+-- >>> run [1, 2, 3, 4] (all (< 6))+-- True+--+-- >>> run [1, 2, 3, 4] (all (> 1))+-- False all :: (a -> Bool) -> M a Bool all p = M getAll (All . p) (<>) (All False) --- | Check whether all elements are 'True'+-- | Check whether all elements are 'True'.+--+-- >>> run (repeat False) and+-- False+--+-- >>> run (repeat True) and+-- ... diverges ... and :: M Bool Bool and = all id --- | Check whether any elements are 'True'+-- | Check whether any elements are 'True'.+--+-- >>> run (True : repeat False) or+-- True+-- >>> run (repeat False) or+-- ... diverges ... or :: M Bool Bool or = any id -- | Find the first element for which a predicate holds.+--+-- >>> run [1, 2, 3, 4] (find even)+-- Just 2+--+-- >>> run [1, 2, 3, 4] (find (> 4))+-- Nothing find :: (a -> Bool) -> M a (Maybe a) find p = M getFirst to (<>) (First Nothing) where to a = First $ if p a then Just a else Nothing -- | Find the first index for which a predicate holds.+--+-- >>> run [1, 2, 3, 4] (indexOf (== 4))+-- Just 3+--+-- >>> run [1, 2, 3, 4] (indexOf (> 4))+-- Nothing indexOf :: Enum e => (a -> Bool) -> M a (Maybe e) indexOf p = M (maybe' Nothing Just) to m Nothing' where to a = if p a then Just' (toEnum 0) else Nothing'@@ -33,12 +72,31 @@ m _ (Just' a) = Just' (succ a) m _ _ = Nothing' --- | Grab the first inputted element+-- | Grab the first inputted element.+--+-- >>> run [1 ..] head+-- Just 1+--+-- >>> run [] head+-- Nothing head :: M a (Maybe a) head = M getFirst (First . Just) (<>) (First Nothing) -- | Occasionally we want to use a short-circuiting fold with other,--- nonlazy folds. This function drops laziness on the floor for a--- 'L\'' fold.+-- nonlazy folds. This function drops laziness on the floor for a @L'@+-- fold. This is dangerous because it can potentially effect+-- termination behavior.+--+-- >>> run (repeat False) and+-- False+--+-- >>> run (repeat False) (strictify and)+-- ... diverges ...+--+-- This means it is only advisable to use when combining a monoidal+-- fold with something that requires left folding.+--+-- >>> run [1.0, 2, 3, 4] $ (/) <$> strictify head <*> maximum+-- 0.25 strictify :: M a b -> L' a b strictify (M p to m z) = L' p (\z a -> z `m` to a) z