foldl

Left-associative fold of a structure, lazy in the accumulator. This is rarely what you want, but can work well for structures with efficient right-to-left sequencing and an operator that is lazy in its left argument. In the case of lists, foldl, when applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

Note that to produce the outermost application of the operator the entire input list must be traversed. Like all left-associative folds, foldl will diverge if given an infinite list. If you want an efficient strict left-fold, you probably want to use foldl' instead of foldl. The reason for this is that the latter does not force the inner results (e.g. z `f` x1 in the above example) before applying them to the operator (e.g. to (`f` x2)). This results in a thunk chain O(n) elements long, which then must be evaluated from the outside-in. For a general Foldable structure this should be semantically identical to:

foldl f z = foldl f z . toList

Examples

The first example is a strict fold, which in practice is best performed with foldl'.

>>> foldl (+) 42 [1,2,3,4]
52

Though the result below is lazy, the input is reversed before prepending it to the initial accumulator, so corecursion begins only after traversing the entire input string.

>>> foldl (\acc c -> c : acc) "abcd" "efgh"
"hgfeabcd"

A left fold of a structure that is infinite on the right cannot terminate, even when for any finite input the fold just returns the initial accumulator:

>>> foldl (\a _ -> a) 0 $ repeat 1
* Hangs forever *

WARNING: When it comes to lists, you always want to use either foldl' or foldr instead.

foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

The list must be finite.

>>> foldl (+) 0 [1..4]
10

>>> foldl (+) 42 []
42

>>> foldl (-) 100 [1..4]
90

>>> foldl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
"dcbafoo"

>>> foldl (+) 0 [1..]
* Hangs forever *

foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a ByteString, reduces the ByteString using the binary operator, from left to right.

foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a ByteString, reduces the ByteString using the binary operator, from left to right.

foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a ShortByteString, reduces the ShortByteString using the binary operator, from left to right.

O(n) foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a Text, reduces the Text using the binary operator, from left to right.

foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a Stream, reduces the Stream using the binary operator, from left to right. Properties

foldl f z0 . stream = foldl f z0

Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems. For example,

elems = reverse . foldl (flip (:)) []

let f len a = len + (length a)
foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

Fold the elements in the set using the given left-associative binary operator, such that foldl f z == foldl f z . toAscList. For example,

toDescList set = foldl (flip (:)) [] set

Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems. For example,

elems = reverse . foldl (flip (:)) []

let f len a = len + (length a)
foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

Fold the elements in the set using the given left-associative binary operator, such that foldl f z == foldl f z . toAscList. For example,

toDescList set = foldl (flip (:)) [] set

Reduce this map by applying a binary operator to all elements, using the given starting value (typically the left-identity of the operator).

Reduce this set by applying a binary operator to all elements, using the given starting value (typically the left-identity of the operator).

A strict left fold. Subject to fusion

Traverse a bytestring (left biased). This function is strict in the accumulator.

Traverse a bytestring (left biased). This function is strict in the accumulator.

Traverse a bytestring (left biased). This function is strict in the accumulator.

Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems. For example,

elems = reverse . foldl (flip (:)) []

let f len a = len + (length a)
foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

Fold the elements in the set using the given left-associative binary operator, such that foldl f z == foldl f z . toAscList. For example,

toDescList set = foldl (flip (:)) [] set

Composable, streaming, and efficient left folds This library provides strict left folds that stream in constant memory, and you can combine folds using Applicative style to derive new folds. Derived folds still traverse the container just once and are often as efficient as hand-written folds.

Left-associative fold of a structure. In the case of lists, foldl, when applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

Note that to produce the outermost application of the operator the entire input list must be traversed. This means that foldl' will diverge if given an infinite list. Also note that if you want an efficient left-fold, you probably want to use foldl' instead of foldl. The reason for this is that latter does not force the "inner" results (e.g. z `f` x1 in the above example) before applying them to the operator (e.g. to (`f` x2)). This results in a thunk chain <math> elements long, which then must be evaluated from the outside-in. For a general Foldable structure this should be semantically identical to,

foldl f z = foldl f z . toList

O(n). Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems. For example,

elems = reverse . foldl (flip (:)) []

let f len a = len + (length a)
foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4