Fold

higher-order functions fold combinator

syntax

  • fold(domain, step, initial state)
  • fold(domain, F(a, _, _), initial state)
  • instantiate fold(domain, step, initial state)

definition

fold(domain, step, initial state) applies the function step once for each element of the Unit domain, in the order of the elements. Each application takes an element of domain and a state, and returns the next state. The first application takes initial state, each next one the state that the application before it returned, and fold yields the state that the last application returns. A domain without elements yields initial state.

unit<uint32> D : nrofrows = 5;

function AddElem(parameter<D> e; parameter<uint32> acc) -> parameter<uint32> := acc + uint32(e);

parameter<uint32> total := fold(D, AddElem, 0u); // 0 + 1 + 2 + 3 + 4 = 10

The step has two parameters. The first takes the element, a Parameter with domain as its values unit; the step may also declare it with the value type of domain, such as parameter<uint32> for a unit<uint32>, which a step that is used with more than one domain has to do. The second takes the state. The result of the step must fit its second parameter, since the next application takes it as its state. A step that does not need the element still declares the parameter.

The state can be a Parameter, an Attribute or a Unit with subitems. When the state is a unit, fold yields a unit with the subitems that the step declares for its result, and an item defined by fold gets those subitems:

unit<uint32> Vals : nrofrows = 5
{
    attribute<float64> v : [5, 3, 8, 1, 4];
}

function DropMax(parameter<uint32> e; unit<uint32> s { attribute<float64> v; }) -> unit<uint32> := kept
{
    unit<uint32> kept := select_with_org_rel(s/v < max(s/v))
    {
        attribute<float64> v := s/v[kept/org_rel];
    }
}

unit<uint32> Twice : nrofrows = 2;
unit<uint32> left := fold(Twice, DropMax, Vals); // the rows of Vals without its two largest values: left/v is [3, 1, 4]

the number of applications

At meta-information time, when GeoDMS determines the item that fold defines and before any data is calculated, fold calculates domain, and with it the parameters that its number of elements depends on, and expands into one application of step per element; the data of the applications is calculated after that, as for any other expression. fold makes no item per application: the item that fold defines holds the final state. To view the intermediate states, write instantiate fold(...) (see below). domain may be a parameter of the function in which fold is used, so the number of applications can be an argument:

function Halve(unit<uint32> dom; parameter<uint32> i; attribute<float64> x (dom)) -> attribute<float64> (dom) := x * 0.5;
function HalveN(unit<uint32> dom; unit<uint32> iterations; attribute<float64> x (dom)) -> attribute<float64> (dom) := fold(iterations, Halve(dom, _, _), x);

The definition check of a function does not know how many elements domain will have. It checks the types of the step twice, first for initial state and then for the state that the step returns, so a step whose result does not fit its own input is reported when the function is defined. This holds for a function and for a partial application of one, as in HalveN above; a step that holds variants is refused at meta-information time.

partial application

When the step needs more arguments than the element and the state, fix them with a partial application that leaves exactly two _ holes, the first for the element and the second for the state:

function AddScaled(parameter<uint32> factor; parameter<uint32> e; parameter<uint32> acc) -> parameter<uint32> := acc + factor * uint32(e);

parameter<uint32> total2 := fold(D, AddScaled(2u, _, _), 0u); // 2 * (0 + 1 + 2 + 3 + 4) = 20

A step with another number of open parameters is refused.

instantiate fold

container trace := instantiate fold(domain, step, initial state) makes an item for each element of domain: step0, step1, …, each holding the state after the step for that element, and result, the final state. With an empty domain there is only result, which is then initial state. When the state is a Unit, each step item is a unit with the subitems of that state, and an Attribute among them has that step item as its domain, so trace/step1/v can be shown in a table of trace/step1.

container trace := instantiate fold(Twice, DropMax, Vals); // trace/step0/v is [5, 3, 1, 4], trace/step1/v and trace/result/v are [3, 1, 4]

The items exist only where there is an item to hold them: a container in the configuration, or a container in the body of a function that is copied with instantiate F(args). In such a copy every parameter of the function has its argument, so domain may depend on an argument, as in this function, where instantiate HalveTrace(Vals, Twice, Vals/v) gives the copy a trace with two steps:

function HalveTrace(unit<uint32> dom; unit<uint32> iterations; attribute<float64> x (dom)) -> attribute<float64> (dom) := x
{
    container trace := instantiate fold(iterations, Halve(dom, _, _), x);
}

When a function is applied as a value, as in HalveResult(Vals, Twice, Vals/v), its body items are not made, but its result can still refer to the states, as trace/result and as a step such as trace/step0, and, with a unit state as in the DropMax example above, to their subitems, such as trace/result/v.

function HalveResult(unit<uint32> dom; unit<uint32> iterations; attribute<float64> x (dom)) -> attribute<float64> (dom) := trace/result
{
    container trace := instantiate fold(iterations, Halve(dom, _, _), x);
}

How many steps there are is known only at the meta-information time of the item that applies the function, so a step that the fold does not reach, such as trace/step2 with two steps, is reported then and not when the function is defined. trace itself has no value: x + trace is an error.

applies to

  • domain: a Unit with one dimension and an integer value type, such as unit<uint32>. A number is not accepted: write a unit with that number of elements, for instance range(uint32, 0, n).
  • step: a function of two parameters, or a partial application with two _ holes; not a function that holds variants.
  • initial state: a Parameter, an Attribute or a Unit, not a function.

example

The convex hull example script repeats its step DropReflexCorners with Fold_c, until the step drops no more points. With fold, the same step is repeated a fixed number of times:

function ConvexHull(
    unit<fpoint> crd;
    unit<uint32> domain;
    unit<uint32> iterations;
    unit<uint32> seq { attribute<crd> point; attribute<domain> sequence_rel; }
)
-> attribute<crd> (domain, poly) := ClosedRings(crd, domain, fold(iterations, DropReflexCorners(crd, domain, _, _), seq));

DropReflexCorners drops the corners where a ring turns inward; fold applies it once for each element of iterations, each time to the points that the application before it kept. When a ring needs more steps than iterations has elements, the ring that fold returns is not convex, and nothing reports that; fold_c, with a condition that tests whether the step still drops a point, stops when the hull is reached.

see also

since version

20.29.0