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


% Reduction. 
% First type = sequence type (must support S$elements and yield R)
% Second type = right (input) datatype
% Third type = left (output) datatype 
reduce = proc [S,R,L: type] (f: proctype (L,R) returns (L),
                             id: L,
                             seq: S)
         returns (L)
         where S has elements: itertype (S) yields (R)
 
    for elem: R in S$elements(seq) do
        id := f(id, elem)
    end
    return(id)
end reduce
 
% This is necessary to get rid of the exceptions
add = proc (a,b: int) returns (int) return (a+b) end add
mul = proc (a,b: int) returns (int) return (a*b) end mul
 
% Usage
start_up = proc ()
    % abbreviation - reducing int->int->int function over an array[int]
    int_reduce = reduce[array[int], int, int]
 
    po: stream := stream$primary_output()
    nums: array[int] := array[int]$[1,2,3,4,5,6,7,8,9,10]
 
    % find the sum and the product using reduce
    sum: int := int_reduce(add, 0, nums)
    product: int := int_reduce(mul, 1, nums)
 
    stream$putl(po, "The sum of [1..10] is: " || int$unparse(sum))
    stream$putl(po, "The product of [1..10] is: " || int$unparse(product))
end start_up