This is a WIP port of the [`foldl`](https://hackage.haskell.org/package/foldl) library in Haskell. Most of the documentation here has been adapted from the Hackage docs.
This is a WIP port of the foldl library in Haskell. Most of the documentation here has been adapted from the Hackage docs.
This library provides efficient left folds that you can combine using Applicative style.
- 💾 Install
- 📖 Tutorial
- 🚀 Benchmarks
Uses fp-ts as a peer dependency.
``bash`
yarn add fp-ts fp-ts-foldl
or
`bash`
npm install fp-ts fp-ts-foldl
This tutorial assumes the following imports:
`ts`
import * as L from "fp-ts-foldl";
import { pipe } from "fp-ts/function";
import * as N from "fp-ts/number";
import * as RA from "fp-ts/ReadonlyArray";
import * as RNEA from "fp-ts/ReadonlyNonEmptyArray";
import * as RR from "fp-ts/ReadonlyRecord";
A Fold is a representation of a left fold that preserves the fold's step function, initial accumulator, and extraction function. This allows the Applicative instance to assemble derived folds that traverse the container only once.
A Fold processes elements of type A and results in a value of type B.
We can use the fold function to _apply_ a Fold to a ReadonlyArray:
`ts`
L.fold(RA.Foldable)(L.sum)([1, 2, 3]); //-> 6
fold works with any type that implements fp-ts's Foldable type class (or any type that has a reduce function matching the method from that class), but we can use foldArray for the common use case where the Foldable instance is for ReadonlyArray:
`ts`
L.foldArray(L.sum)([1, 2, 3]);
Folds are Applicatives, so you can combine them using Applicative combinators:
`tsaverage
// has the inferred type Fold
const average = pipe(
L.Do,
L.apS("sum", L.sum),
L.apSW("length", L.length),
L.map(({ sum, length }) => sum / length)
);
// Taking the sum, the sum of squares, ..., up to the sum of x ** 5
const powerSums = pipe(
[1, 2, 3, 4, 5],
RA.traverse(L.Applicative)(n =>
pipe(
L.sum,
L.premap((x: number) => x ** n)
)
)
);
L.foldArray(powerSums)(RNEA.range(1, 10));
//-> [ 55, 385, 3025, 25333, 220825 ]
These combined folds will still traverse the array only once:
`ts
L.foldArray(average)(RNEA.range(1, 10_000_000));
//-> 5000000.5
pipe(
RNEA.range(1, 10_000_000),
L.foldArray(
L.Do,
L.apS("minimum", L.minimum(N.Ord)),
L.apS("maximum", L.maximum(N.Ord))
)
);
//-> { minimum: O.some(1), maximum: O.some(10_000_000) }
`
Now that we have the basics, let's look at a dataset of Flower measurements.
`ts
type Flower = {
sepalLength: number;
sepalWidth: number;
petalLength: number;
petalWidth: number;
species: "setosa" | "versicolor" | "virginica";
};
const flowers = [
{
sepalLength: 5.1,
sepalWidth: 3.5,
petalLength: 1.4,
petalWidth: 0.2,
species: "setosa",
},
{
sepalLength: 4.9,
sepalWidth: 3,
petalLength: 1.4,
petalWidth: 0.2,
species: "setosa",
},
{
sepalLength: 4.7,
sepalWidth: 3.2,
petalLength: 1.3,
petalWidth: 0.2,
species: "setosa",
},
// ...
];
`
We can get the mean petal-length of all flowers:
`tsmap
pipe(
flowers,
L.foldArray(
L.mean,
L.premap((flower: Flower) => flower.petalLength),
L.map(n => n.toPrecision(3)) // transforms the final result of the Fold
)
);
//-> "3.76"
We can also use prefilter to just look at the petal-lengths of the _virginica_ species:
`ts`
pipe(
flowers,
L.foldArray(
L.mean,
L.premap((flower: Flower) => flower.petalLength),
L.prefilter(flower => flower.species === "virginica"),
L.map(n => n.toPrecision(3))
)
);
//-> "5.55"
Finally we can use Applicative combinators to get the standard deviation of all flower attributes, while only traversing the array once:
`ts`
pipe(
flowers,
L.foldArray(
L.Do,
L.apS(
"petalLength",
pipe(
L.std,
L.premap((flower: Flower) => flower.petalLength)
)
),
L.apS(
"petalWidth",
pipe(
L.std,
L.premap(flower => flower.petalWidth)
)
),
L.apS(
"sepalLength",
pipe(
L.std,
L.premap(flower => flower.sepalLength)
)
),
L.apS(
"sepalWidth",
pipe(
L.std,
L.premap(flower => flower.sepalWidth)
)
),
L.map(RR.map(n => n.toPrecision(3)))
)
);
//-> { petalLength: '1.76', petalWidth: '0.761', sepalLength: '0.825', sepalWidth: '0.432' }
foldl performs favorably against transducer implementations in ramda and transducers-js in the following benchmarks. (Note that this library does not support early termination, unlike most transducer implementations, so will perform much worse in cases where that's a requirement. See: https://github.com/Gabriella439/foldl/issues/85.)
map, filter, sum on an Array of 1,000,000 numbers
!array4 (2)
map, filter, sum on an immutable/List of 1,000,000 numbers
!imm4 (1)
map, filter, sum on a funkia/List` of 1,000,000 numbers
!funkia4 (1)