Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

This module exports a bunch of common folds.

For the classic example

import Control.Applicative import qualified Data.Fold.Common as C avg :: C.L' Double Double avg = (/) <$> C.sum <*> C.count main :: IO () main = print $ C.run [1 .. 10000000] avg

This will run in constant memory as we'd hope. In general the
rules for keeping memory usage low while using `folds`

are

- Don't try to consume a left fold lazily
- Don't try to consume a right fold strictly
- Never use
`>>=`

- Never use
`prefix`

on right folds - Never use
`postfix`

on left folds

Also note that monoidal folds can be combined with strict left ones
with `strictify`

.

- sum :: Num a => L' a a
- product :: Num a => L' a a
- count :: Enum e => L' a e
- mconcat :: Monoid m => L' m m
- minimum :: Ord a => L' a (Maybe a)
- maximum :: Ord a => L' a (Maybe a)
- nub :: Ord a => L' a [a]
- slowNub :: Eq a => L' a [a]
- intoSet :: Ord a => L' a (Set a)
- last :: L' a (Maybe a)
- nth :: (Eq b, Ord b, Num b) => b -> L' a (Maybe a)
- any :: (a -> Bool) -> M a Bool
- all :: (a -> Bool) -> M a Bool
- and :: M Bool Bool
- or :: M Bool Bool
- elem :: Eq a => a -> M a Bool
- notElem :: Eq a => a -> M a Bool
- find :: (a -> Bool) -> M a (Maybe a)
- head :: M a (Maybe a)
- null :: M a Bool
- strictify :: M a b -> L' a b
- intoList :: R a [a]
- take :: (Eq b, Ord b, Num b) => b -> R a [a]
- drop :: (Eq b, Ord b, Num b) => b -> R a [a]
- indexOf :: Enum e => (a -> Bool) -> R a (Maybe e)
- chunk :: (Show b, Eq b) => (a -> b) -> R a [[a]]
- concat :: R [a] [a]

# Left Folds

count :: Enum e => L' a e Source

Count the number of elements fed to a fold

`>>>`

10`run [1 .. 10] count`

Note: GHCi will default `Enum e`

to `()`

. If you see

*** Exception: Prelude.Enum.().succ: bad argument

You've been bitten by this.

mconcat :: Monoid m => L' m m Source

`mappend`

all the elements of a sequence together.

`>>>`

[1, 2, 3, 4, 5, 6, 7, 8]`run [[1, 2, 3, 4], [5, 6, 7, 8]] mconcat`

`>>>`

Sum {getSum = 10}`run (map Sum [1, 2, 3, 4]) mconcat`

minimum :: Ord a => L' a (Maybe a) Source

Minimum of all inputs. If no inputs are supplied this returns
`Nothing`

.

`>>>`

1`run [1, 2, 3] minimum`

`>>>`

... diverges ...`run [1 ..] minimum`

maximum :: Ord a => L' a (Maybe a) Source

Maximum of all inputs. If no inputs are supplied this returns
`Nothing`

.

`>>>`

3`run [1, 2, 3] maximum`

`>>>`

... diverges ...`run [1 ..] maximum`

nub :: Ord a => L' a [a] Source

De-duplicate all the inputs while preserving order. `O(n log(n))`

`>>>`

[1, 2]`run (replicate 10 1 ++ replicate 10 2) nub`

`>>>`

[1, 2]`run [1, 2, 1] nub`

intoSet :: Ord a => L' a (Set a) Source

Collect all members into a `Set`

.

`>>>`

fromList [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`run [1 .. 10] intoSet`

Grab the last element inputted

`>>>`

Just 10`run [1 .. 10] last`

`>>>`

Nothing`run [] last`

nth :: (Eq b, Ord b, Num b) => b -> L' a (Maybe a) Source

Grab the nth element inputted.

`>>>`

Just 6`run [1 .. 10] (nth 5)`

`>>>`

Nothing`run [1 .. 10] (nth 20)`

# Monoidal Folds

any :: (a -> Bool) -> M a Bool Source

Check that if predicate holds for any inputs to the fold.

`>>>`

True`run [1, 2, 3, 4] (any even)`

`>>>`

False`run [] (any $ const False)`

all :: (a -> Bool) -> M a Bool Source

Check that if predicate holds for all inputs to the fold.

`>>>`

True`run [1, 2, 3, 4] (all (< 6))`

`>>>`

False`run [1, 2, 3, 4] (all (> 1))`

Check whether all elements are `True`

.

`>>>`

False`run (repeat False) and`

`>>>`

... diverges ...`run (repeat True) and`

Check whether any elements are `True`

.

`>>>`

True`run (True : repeat False) or`

`>>>`

... diverges ...`run (repeat False) or`

elem :: Eq a => a -> M a Bool Source

Check whether an element is fed into the fold.

`>>>`

True`run [1, 2, 3] (elem 3)`

`>>>`

False`run [] (elem 1)`

notElem :: Eq a => a -> M a Bool Source

Check whther an element isn't fed into the fold. >>> run [1, 2, 3] (notElem 3) False

`>>>`

True`run [] (notElem 1)`

find :: (a -> Bool) -> M a (Maybe a) Source

Find the first element for which a predicate holds.

`>>>`

Just 2`run [1, 2, 3, 4] (find even)`

`>>>`

Nothing`run [1, 2, 3, 4] (find (> 4))`

Grab the first inputted element.

`>>>`

Just 1`run [1 ..] head`

`>>>`

Nothing`run [] head`

Check whether a fold was fed any elements.

`>>>`

True`run [] null`

`>>>`

False`run [1..] null`

strictify :: M a b -> L' a b Source

Occasionally we want to use a short-circuiting fold with other,
nonlazy folds. This function drops laziness on the floor for a `L'`

fold. This is dangerous because it can potentially effect
termination behavior.

`>>>`

False`run (repeat False) and`

`>>>`

... diverges ...`run (repeat False) (strictify and)`

This is generally an advantage when we want to combine a monoidal fold with a left one.

`>>>`

0.25`run [1.0, 2, 3, 4] $ (/) <$> strictify head <*> maximum`

# Right Folds

An extremely boring fold. You can almost view this as an identity fold across lists.

`>>>`

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`run [1 .. 10] intoLists`

take :: (Eq b, Ord b, Num b) => b -> R a [a] Source

Take the first `n`

inputs to the fold. If less then `n`

inputs
are fed in total then take as many as possible.

`>>>`

[1, 2, 3]`run [1 .. 10] (take 3)`

`>>>`

[1, 2, 3]`run [1, 2, 3] (take 100)`

drop :: (Eq b, Ord b, Num b) => b -> R a [a] Source

Drop the first `n`

items. If less then `n`

items are supplied
then return the empty list.

`>>>`

[2, 3]`run [1, 2, 3] (drop 1)`

`>>>`

[]`run [1, 2, 3] (drop 100)`

indexOf :: Enum e => (a -> Bool) -> R a (Maybe e) Source

Find the first index for which a predicate holds.

`>>>`

Just 3`run [1, 2, 3, 4] (indexOf (== 4))`

`>>>`

Nothing`run [1, 2, 3, 4] (indexOf (> 4))`

chunk :: (Show b, Eq b) => (a -> b) -> R a [[a]] Source

Chunk the input into partitions according to a function. While the values from the function are equal elements are collected into a chunk. Note that partitioning according to a predicate is just a special case of this.

`>>>`

[[1, 1], [2], [3]]`run [1, 1, 2, 3] (chunk id)`

`>>>`

[[1, -1], 2, [1]]`run [1, -1, 2, 1] (chunk abs)`

`>>>`

[[1], [2, 4, 6], 5]`run [1, 2, 4, 6, 5] (chunk even)`

Lazily produce a flattened list of the inputted lists.

`>>>`

[1, 2, 3]`run [[1], [2], [3]] concat`

`>>>`

1`head $ run (map return [1..]) concat`

Note: The right fold ensures that all applications of `++`

associate to the right. This makes this fold ideal for streaming
but slow when completely forced.