Search
View source code
Display the source code in std/algorithm/iteration.d from which this page was generated on github.
Report a bug
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

# Module `std.algorithm.iteration`

This is a submodule of `std.algorithm`. It contains generic iteration algorithms.

Cheat Sheet
Function Name Description
`cache` Eagerly evaluates and caches another range's `front`.
`cacheBidirectional` As above, but also provides `back` and `popBack`.
`chunkBy` `chunkBy!((a,b) => a == b)([[1, 1], [1, 2], [2, 2], [2, 1]])` returns a range containing 3 subranges: the first with just `[1, 1]`; the second with the elements `[1, 2]` and `[2, 2]`; and the third with just `[2, 1]`.
`cumulativeFold` `cumulativeFold!((a, b) => a + b)([1, 2, 3, 4])` returns a lazily-evaluated range containing the successive reduced values `1`, `3`, `6`, `10`.
`each` `each!writeln([1, 2, 3])` eagerly prints the numbers `1`, `2` and `3` on their own lines.
`filter` `filter!(a => a > 0)([1, -1, 2, 0, -3])` iterates over elements `1` and `2`.
`filterBidirectional` Similar to `filter`, but also provides `back` and `popBack` at a small increase in cost.
`fold` `fold!((a, b) => a + b)([1, 2, 3, 4])` returns `10`.
`group` `group([5, 2, 2, 3, 3])` returns a range containing the tuples `tuple(5, 1)`, `tuple(2, 2)`, and `tuple(3, 2)`.
`joiner` `joiner(["hello", "world!"], "; ")` returns a range that iterates over the characters `"hello; world!"`. No new string is created - the existing inputs are iterated.
`map` `map!(a => a * 2)([1, 2, 3])` lazily returns a range with the numbers `2`, `4`, `6`.
`mean` Colloquially known as the average, `mean([1, 2, 3])` returns `2`.
`permutations` Lazily computes all permutations using Heap's algorithm.
`reduce` `reduce!((a, b) => a + b)([1, 2, 3, 4])` returns `10`. This is the old implementation of `fold`.
`splitWhen` Lazily splits a range by comparing adjacent elements.
`splitter` Lazily splits a range by a separator.
`substitute` `[1, 2].substitute(1, 0.1)` returns `[0.1, 2]`.
`sum` Same as `fold`, but specialized for accurate summation.
`uniq` Iterates over the unique elements in a range, which is assumed sorted.

## Functions

NameDescription
``` cache(range) ``` `cache` eagerly evaluates front of `range` on each construction or call to popFront, to store the result in a cache. The result is then directly returned when front is called, rather than re-evaluated.
``` cacheBidirectional(range) ``` `cache` eagerly evaluates front of `range` on each construction or call to popFront, to store the result in a cache. The result is then directly returned when front is called, rather than re-evaluated.
``` chunkBy(r) ``` Chunks an input range into subranges of equivalent adjacent elements. In other languages this is often called `partitionBy`, `groupBy` or `sliceWhen`.
``` group(r) ``` Groups consecutively equivalent elements into a single tuple of the element and the number of its repetitions.
``` joiner(r, sep) ``` Lazily joins a range of ranges with a separator. The separator itself is a range. If a separator is not provided, then the ranges are joined directly without anything in between them (often called `flatten` in other languages).
``` mean(r) ``` Finds the mean (colloquially known as the average) of a range.
``` permutations(r) ``` Lazily computes all permutations of `r` using Heap's algorithm.
``` splitter(r, s) ``` Lazily splits a range using an element or range as a separator. Separator ranges can be any narrow string type or sliceable range type.
``` splitter(s) ``` Lazily splits the character-based range `s` into words, using whitespace as the delimiter.
``` splitWhen(r) ``` Splits a forward range into subranges in places determined by a binary predicate.
``` substitute(r, substs) ``` Returns a range with all occurrences of `substs` in `r`. replaced with their substitution.
``` sum(r) ``` Sums elements of `r`, which must be a finite input range. Although conceptually `sum(r)` is equivalent to `fold`!((a, b) => a + b)(r, 0), `sum` uses specialized algorithms to maximize accuracy, as follows.
``` uniq(r) ``` Lazily iterates unique consecutive elements of the given range, which is assumed to be sorted (functionality akin to the uniq system utility). Equivalence of elements is assessed by using the predicate `pred`, by default `"a == b"`. The predicate is passed to `binaryFun`, and can either accept a string, or any callable that can be executed via `pred(element, element)`. If the given range is bidirectional, `uniq` also yields a bidirectional range.

## Structs

NameDescription
``` Group ``` Groups consecutively equivalent elements into a single tuple of the element and the number of its repetitions.
``` Permutations ``` Lazily computes all permutations of `r` using Heap's algorithm.

## Templates

NameDescription
``` cumulativeFold ``` Similar to `fold`, but returns a range containing the successive reduced values. The call `cumulativeFold!(fun)(range, seed)` first assigns `seed` to an internal variable `result`, also called the accumulator. The returned range contains the values `result = fun(result, x)` lazily evaluated for each element `x` in `range`. Finally, the last element has the same value as `fold!(fun)(seed, range)`. The one-argument version `cumulativeFold!(fun)(range)` works similarly, but it returns the first element unchanged and uses it as seed for the next elements. This function is also known as partial_sum, accumulate, scan, Cumulative Sum.
``` each ``` Eagerly iterates over `r` and calls `fun` with each element.
``` filter ``` `filter!(predicate)(range)` returns a new range containing only elements `x` in `range` for which `predicate(x)` returns `true`.
``` filterBidirectional ``` Similar to `filter`, except it defines a bidirectional range. There is a speed disadvantage - the constructor spends time finding the last element in the range that satisfies the filtering condition (in addition to finding the first one). The advantage is that the filtered range can be spanned from both directions. Also, `std.range.retro` can be applied against the filtered range.
``` fold ``` Implements the homonym function (also known as `accumulate`, `compress`, `inject`, or `foldl`) present in various programming languages of functional flavor. The call `fold!(fun)(range, seed)` first assigns `seed` to an internal variable `result`, also called the accumulator. Then, for each element `x` in `range`, `result = fun(result, x)` gets evaluated. Finally, `result` is returned. The one-argument version `fold!(fun)(range)` works similarly, but it uses the first element of the range as the seed (the range must be non-empty).
``` map ``` Implements the homonym function (also known as `transform`) present in many languages of functional flavor. The call `map!(fun)(range)` returns a range of which elements are obtained by applying `fun(a)` left to right for all elements `a` in `range`. The original ranges are not changed. Evaluation is done lazily.
``` reduce ``` Implements the homonym function (also known as `accumulate`, `compress`, `inject`, or `foldl`) present in various programming languages of functional flavor. There is also `fold` which does the same thing but with the opposite parameter order. The call `reduce!(fun)(seed, range)` first assigns `seed` to an internal variable `result`, also called the accumulator. Then, for each element `x` in `range`, `result = fun(result, x)` gets evaluated. Finally, `result` is returned. The one-argument version `reduce!(fun)(range)` works similarly, but it uses the first element of the range as the seed (the range must be non-empty).
``` substitute ``` Returns a range with all occurrences of `substs` in `r`. replaced with their substitution.