Fold_c

higher-order functions fold_c combinator

syntax

  • fold_c(step, condition, maxN, initial state)
  • fold_c(F(a, _, _), G(b, _), maxN, initial state)
  • instantiate fold_c(step, condition, maxN, initial state)

definition

fold_c(step, condition, maxN, initial state) applies the function step for as long as the function condition is true for the state, at most maxN times. It starts from initial state, tests condition on the state before each application, and yields the first state for which condition is false. When condition is false for initial state, fold_c yields initial state.

function AddStep(parameter<uint32> k; parameter<uint32> acc) -> parameter<uint32> := acc + k + 1u;
function Below(parameter<uint32> limit; parameter<uint32> acc) -> parameter<bool> := acc < limit;

parameter<uint32> total := fold_c(AddStep, Below(20u, _), 100u, 0u); // 0, 1, 3, 6, 10, 15, 21: total is 21

The step has two parameters. The first takes the number of the step, a parameter<uint32> that counts from 0; 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 number still declares the parameter, so the same step can serve Fold, whose step takes an element of a domain in that place.

The condition has one parameter, the state, and returns a parameter<bool>: true to take another step, false to stop.

maxN is a ceiling, not a stopping rule. When condition is still true after maxN steps, fold_c reports an error instead of yielding a state that has not converged. Choose maxN as a bound that a correct calculation never exceeds, such as the number of points when each step removes at least one.

The state can be a Parameter, an Attribute or a Unit with subitems, as with Fold:

unit<uint32> Vals5 : 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];
    }
}
function Longer(parameter<uint32> n; unit<uint32> s) -> parameter<bool> := #s > n;

unit<uint32> two := fold_c(DropMax, Longer(2u, _), 10u, Vals5); // the two smallest values: two/v is [3, 1]

when the condition is calculated

Whether to take another step depends on data, so GeoDMS calculates the condition of each state at meta-information time, when it determines the item that fold_c defines and before the data of that item is calculated. Determining that item, for instance by opening it in the GUI, therefore calculates the states up to the one where fold_c stops. The data of each state is kept while the next one is calculated, so the conditions cost one pass over the steps. When the state is an attribute, its data is released after that pass, and the steps are calculated again when the data of the item is requested, so each step is calculated twice, where a Fold over the same number of steps calculates it once. With a parameter or a unit as the state the steps are not calculated again.

The definition check of a function does not depend on that data. It checks the types of the step twice, first for initial state and then for the state that the step returns, and those of the condition on both, so a step whose result does not fit its own input, or a condition that does not return a parameter<bool>, is reported when the function is defined. This holds for a function and for a partial application of one, as in Below(20u, _) above.

instantiate fold_c

container trace := instantiate fold_c(...) makes an item for each step that is taken, as instantiate fold(...) does (Fold): step0, step1, …, each holding the state after that step, and result, the state that fold_c yields. How many items there are depends on the data, so the items appear once the states have been calculated. In a function body it works as instantiate fold(...) does there: a copy of the function made with instantiate F(args) gets the items, and the result of a function that is applied as a value can refer to trace/result and to the steps.

container trace := instantiate fold_c(DropMax, Longer(2u, _), 10u, Vals5); // step0, step1, step2 and result

applies to

  • step: a function of two parameters, or a partial application with two _ holes; not a function that holds variants.
  • condition: a function of one parameter that returns a parameter<bool>, or a partial application with one _ hole.
  • maxN: a Parameter with an integer value type, such as parameter<uint32>.
  • initial state: a Parameter, an Attribute or a Unit, not a function.

see also

since version

20.29.0