Reduce is a function or method that is used to take the values in an array or a list and apply a function to successive members of the list to produce (or reduce them to), a single value.



Task

Show how reduce (or foldl or foldr etc), work (or would be implemented) in your language.



See also

 Wikipedia article:   Fold
 Wikipedia article:   Catamorphism


MODULE Catamorphism;
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
 
(* Alas, there are no generic types. This function works for
   CARDINAL only - you would have to copy it and change the types
   to reduce functions of other types. *)
TYPE Reduction = PROCEDURE (CARDINAL, CARDINAL): CARDINAL;
PROCEDURE reduce(func:  Reduction; 
                 arr:   ARRAY OF CARDINAL;
                 first: CARDINAL): CARDINAL;
    VAR i: CARDINAL;
BEGIN
    FOR i := 0 TO HIGH(arr) DO
        first := func(first, arr[i]);
    END;
    RETURN first;
END reduce;
 
(* Demonstration *)
PROCEDURE add(a,b: CARDINAL): CARDINAL;
BEGIN RETURN a+b; END add;
PROCEDURE mul(a,b: CARDINAL): CARDINAL;
BEGIN RETURN a*b; END mul;
 
PROCEDURE Demonstration;
    VAR a: ARRAY [1..5] OF CARDINAL;
        i: CARDINAL;
BEGIN
    FOR i := 1 TO 5 DO a[i] := i; END;
 
    WriteString("Sum of [1..5]: ");
    WriteCard(reduce(add, a, 0), 3);
    WriteLn;
    WriteString("Product of [1..5]: ");
    WriteCard(reduce(mul, a, 1), 3);
    WriteLn;
END Demonstration;
 
BEGIN Demonstration;
END Catamorphism.