Safe Haskell	Safe
Language	Haskell2010

Data.Fold.Common

Contents

Left Folds
Monoidal Folds
Right Folds

Description

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.

Synopsis

Documentation

module Data.Fold

Left Folds

sum :: Num a => L' a a Source

Sum of the inputs

>>> run [1 .. 10] sum
55

product :: Num a => L' a a Source

Product of the input

>>> run [1 .. 10] product
3628800

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

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.

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

mappend all the elements of a sequence together.

>>> 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}

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

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

>>> run [1, 2, 3] minimum
1
>>> run [1 ..] minimum
... diverges ...

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

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

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

>>> run [1 ..] maximum
... diverges ...

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

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]

slowNub :: Eq a => L' a [a] Source

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]

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

Collect all members into a Set.

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

last :: L' a (Maybe a) Source

Grab the last element inputted

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

>>> run [] last
Nothing

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

Grab the nth element inputted.

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

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

Monoidal Folds

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

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

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

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

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

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

and :: M Bool Bool Source

Check whether all elements are True.

>>> run (repeat False) and
False

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

or :: M Bool Bool Source

Check whether any elements are True.

>>> run (True : repeat False) or
True
>>> run (repeat False) or
... diverges ...

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

Check whether an element is fed into the fold.

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

>>> run [] (elem 1)
False

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

>>> run [] (notElem 1)
True

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

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

head :: M a (Maybe a) Source

Grab the first inputted element.

>>> run [1 ..] head
Just 1

>>> run [] head
Nothing

null :: M a Bool Source

Check whether a fold was fed any elements.

>>> run [] null
True

>>> run [1..] null
False

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.

>>> run (repeat False) and
False

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

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

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

Right Folds

intoList :: R a [a] Source

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

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

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.

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

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

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.

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

>>> 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.

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

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

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.

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

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

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

concat :: R [a] [a] Source

Lazily produce a flattened list of the inputted lists.

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

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

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.