Part 18: Algorithms

From here on the course tours the standard packages, and it starts with the one every program reaches for sooner or later. The Algorithms package is a set of generic functions over slices: sort them, search them, find their extremes, fold them into one answer. Because every function takes a slice, one function serves an array of any length, part of an array, or the contents of a collection — and none of them ever allocates memory. The last two lessons go a step further: Core's lazy adaptors, which change any iterator item by item, and scans, which keep every step of a fold.

What you will learn

• Sorting a slice in place through a writable view, by the element's own < or by an order function of yours.
• Searching any slice from the front, and handling the none that "not found" is.
• Searching sorted data in logarithmic time, and the promise that comes with it.
• The smaller of two values, and the position of the smallest in a slice — which may not exist.
• Collapsing a slice into one answer with Fold and a step function.
• Chaining lazy adaptors such as Map, Filter and Take over any iterator, computing each item only when it is asked for.
• Running totals and other scans, counting sequences with Iota, and a Midpoint that cannot overflow.

Which function?

flowchart LR
    q(["What do you want<br/>from a slice?"]) --> order["to put it in order"]
    q --> find["to find a value"]
    q --> ext["its smallest or<br/>largest element"]
    q --> one["one answer<br/>from every element"]
    q --> run["the running answer<br/>after every element"]
    q --> lazy["a changed sequence,<br/>item by item"]
    order --> sort["`Sort`, `SortDescending`, `SortBy`<br/>(18.1)"]
    find --> sorted{"is it sorted?"}
    sorted -- "no, or not sure" --> lin["`IndexOf`, `LastIndexOf`, `Contains`<br/>(18.2)"]
    sorted -- "yes" --> bin["`BinarySearch`, `LowerBound`, `UpperBound`<br/>(18.3)"]
    ext --> mm["`MinIndex`, `MaxIndex`<br/>(18.4)"]
    one --> fold["`Fold`, `FoldRight`<br/>(18.5)"]
    run --> scan["`PartialSum`, `InclusiveScan`, `ExclusiveScan`<br/>(18.7)"]
    lazy --> adapt["`Map`, `Filter`, `Take`, …<br/>(18.6)"]

The functions share a few habits, and knowing them makes the rest of the package predictable:

Lessons

Before you start

The lessons lean on Slice and Writable slice from Part 5, Callback and Generic from Part 4, Presence and Coalesce from Part 8: Optionals, Comparable, Iterator and Iterable from Part 12, and Wrapping arithmetic from Part 16. Each lesson's package is in the Examples repository's Algorithms/ folder:

cd Examples/Algorithms/Sort
rux run

After this part

The checkpoint project Statistics puts the whole part to work: it sorts, finds extremes and folds slices of numbers into a count, a mean, a variance and a median, including the awkward cases of one value and none. Then Part 19: Files leaves memory behind and reads and writes the disk.

For the rules underneath this part, see Slices, Function types, Generic functions and Iteration in the Rux Reference.