Catamorphism

Catamorphism is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

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

Cf.

• Fold
• Catamorphism

C

<lang C>#include <stdio.h>

typedef int (*intFn)(int, int);

int reduce(intFn fn, int size, int *elms) {

   int i, val = *elms;
   for (i = 1; i < size; ++i)
       val = fn(val, elms[i]);
   return val;

}

int add(int a, int b) { return a + b; } int sub(int a, int b) { return a - b; } int mul(int a, int b) { return a * b; }

int main(void) {

   int nums[] = {1, 2, 3, 4, 5};
   printf("%d\n", reduce(add, 5, nums));
   printf("%d\n", reduce(sub, 5, nums));
   printf("%d\n", reduce(mul, 5, nums));
   return 0;

}</lang>

Output:

15
-13
120

C#

<lang csharp>var nums = Enumerable.Range(1, 10);

int summation = nums.Aggregate((a, b) => a + b);

int product = nums.Aggregate((a, b) => a * b);

string concatenation = nums.Aggregate(String.Empty, (a, b) => a.ToString() + b.ToString());

Console.WriteLine("{0} {1} {2}", summation, product, concatenation);</lang>

D

<lang d>import std.stdio, std.algorithm, std.range, std.numeric,

      std.conv, std.typecons, std.typetuple;

void main() {

   auto list = iota(1, 11);
   alias TypeTuple!(q{a + b}, q{a * b}, min, max, gcd) ops;

   foreach (op; ops)
       writeln(op.stringof, ": ", list.reduce!op());

   // std.algorithm.reduce supports multiple functions in parallel:
   reduce!(ops[0], ops[3], text)(tuple(0, 0.0, ""), list).writeln();

}</lang>

Output:

"a + b": 55
"a * b": 3628800
min(T1,T2,T...) if (is(typeof(a < b))): 1
max(T1,T2,T...) if (is(typeof(a < b))): 10
gcd(T): 1
Tuple!(int,double,string)(55, 10, "12345678910")

Déjà Vu

This is a foldl: <lang dejavu>reduce f lst init: if lst: f reduce @f lst init pop-from lst else: init

!. reduce @+ [ 1 10 200 ] 4 !. reduce @- [ 1 10 200 ] 4 </lang>

Output:

215
-207

J

Solution:<lang j> /</lang> Example:<lang j> +/ 1 2 3 4 5 15

  */ 1 2 3 4 5

120

  !/ 1 2 3 4 5  NB.  "n ! k" is "n choose k"

45</lang>

JavaScript

<lang javascript>var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function add(a, b) {

   return a + b;

}

var summation = nums.reduce(add);

function mul(a, b) {

   return a * b;

}

var product = nums.reduce(mul, 1);

var concatenation = nums.reduce(add, "");

console.log(summation, product, concatenation);</lang>

Logtalk

The Logtalk standard library provides implementations of common meta-predicates such as fold left. The example that follow uses Logtalk's native support for lambda expressions to avoid the need for auxiliary predicates. <lang logtalk>

- object(folding_examples).

   :- public(show/0).
   show :-
       integer::sequence(1, 10, List),
       write('List: '), write(List), nl,
       meta::fold_left([Acc,N,Sum0]>>(Sum0 is Acc+N), 0, List, Sum),
       write('Sum of all elements: '), write(Sum), nl,
       meta::fold_left([Acc,N,Product0]>>(Product0 is Acc*N), 1, List, Product),
       write('Product of all elements: '), write(Product), nl,
       meta::fold_left([Acc,N,Concat0]>>(number_codes(N,NC), atom_codes(NA,NC), atom_concat(Acc,NA,Concat0)), , List, Concat),
       write('Concatenation of all elements: '), write(Concat), nl.

- end_object.

</lang> Output: <lang text> | ?- folding_examples::show. List: [1,2,3,4,5,6,7,8,9,10] Sum of all elements: 55 Product of all elements: 3628800 Concatenation of all elements: 12345678910 yes </lang>

LOLCODE

Translation of: C

<lang LOLCODE>HAI 1.3

HOW IZ I reducin YR array AN YR size AN YR fn

   I HAS A val ITZ array'Z SRS 0
   IM IN YR loop UPPIN YR i TIL BOTH SAEM i AN DIFF OF size AN 1
       val R I IZ fn YR val AN YR array'Z SRS SUM OF i AN 1 MKAY
   IM OUTTA YR loop
   FOUND YR val

IF U SAY SO

O HAI IM array

   I HAS A SRS 0 ITZ 1
   I HAS A SRS 1 ITZ 2
   I HAS A SRS 2 ITZ 3
   I HAS A SRS 3 ITZ 4
   I HAS A SRS 4 ITZ 5

KTHX

HOW IZ I add YR a AN YR b, FOUND YR SUM OF a AN b, IF U SAY SO HOW IZ I sub YR a AN YR b, FOUND YR DIFF OF a AN b, IF U SAY SO HOW IZ I mul YR a AN YR b, FOUND YR PRODUKT OF a AN b, IF U SAY SO

VISIBLE I IZ reducin YR array AN YR 5 AN YR add MKAY VISIBLE I IZ reducin YR array AN YR 5 AN YR sub MKAY VISIBLE I IZ reducin YR array AN YR 5 AN YR mul MKAY

KTHXBYE</lang>

Output:

15
-13
120

Maple

The left fold operator in Maple is foldl, and foldr is the right fold operator. <lang Maple>> nums := seq( 1 .. 10 );

                         nums := 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

> foldl( `+`, 0, nums ); # compute sum using foldl

                         55

> foldr( `*`, 1, nums ); # compute product using foldr

                         3628800</lang>

Compute the horner form of a (sorted) polynomial: <lang Maple>> foldl( (a,b) ->a*T+b, op(map2(op,1,[op( 72*T^5+37*T^4-23*T^3+87*T^2+44*T+29 )])));

                   ((((72 T + 37) T - 23) T + 87) T + 44) T + 29</lang>

Mathematica

<lang mathematica>Fold[f, x, {a, b, c, d}]</lang>

Output:

f[f[f[f[x, a], b], c], d]

Nemerle

The Nemerle.Collections namespace defines FoldLeft, FoldRight and Fold (an alias for FoldLeft) on any sequence that implements the IEnumerable[T] interface. <lang Nemerle>def seq = [1, 4, 6, 3, 7]; def sum = seq.Fold(0, _ + _); // Fold takes an initial value and a function, here the + operator</lang>

OCaml

<lang ocaml># let nums = [1;2;3;4;5;6;7;8;9;10];; val nums : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

1. let sum = List.fold_left (+) 0 nums;;

val sum : int = 55

1. let product = List.fold_left ( * ) 0 nums;;

val product : int = 0</lang>

PARI/GP

<lang parigp>reduce(f, v)={

 my(t=v[1]);
 for(i=2,#v,t=f(t,v[i]));
 t

}; reduce((a,b)->a+b, [1,2,3,4,5,6,7,8,9,10])</lang>

Perl

Perl's reduce function is in a standard package. <lang perl>use List::Util 'reduce';

1. note the use of the odd $a and $b globals

print +(reduce {$a + $b} 1 .. 10), "\n";

1. first argument is really an anon function; you could also do this:

sub func { $b & 1 ? "$a $b" : "$b $a" } print +(reduce \&func, 1 .. 10), "\n"</lang>

Perl 6

Any associative infix operator, either built-in or user-defined, may be turned into a reduce operator by putting it into square brackets (known as "the reduce metaoperator") and using it as a list operator. The operations will work left-to-right or right-to-left automatically depending on the natural associativity of the base operator. <lang perl6>my @list = 1..10; say [+] @list; say [*] @list; say [~] @list; say [min] @list; say [max] @list; say [lcm] @list;</lang>

Output:

55
3628800
12345678910
1
10
2520

In addition to the reduce metaoperator, a general higher-order function, reduce, can apply any appropriate function. Reproducing the above in this form, using the function names of those operators, we have: <lang perl6>say reduce &infix:<+>, @list; say reduce &infix:<*>, @list; say reduce &infix:<~>, @list; say reduce &infix:<min>, @list; say reduce &infix:<max>, @list; say reduce &infix:<lcm>, @list;</lang>

Prolog

SWI-Prolog has native foldl in version 6.3.1
Module lambda was written by Ulrich Neumerkel and can be found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl <lang Prolog>:- use_module(library(lambda)).

% foldl is now a predicate of SWI-Prolog 6.3.1 % catamorphism :- numlist(1,10,L), foldl(\XS^YS^ZS^(ZS is XS+YS), L, 0, Sum), format('Sum of ~w is ~w~n', [L, Sum]), foldl(\XP^YP^ZP^(ZP is XP*YP), L, 1, Prod), format('Prod of ~w is ~w~n', [L, Prod]), string_to_list(LV, ""), foldl(\XC^YC^ZC^(string_to_atom(XS, XC),string_concat(YC,XS,ZC)), L, LV, Concat), format('Concat of ~w is ~w~n', [L, Concat]).</lang>

Output:

 ?- catamorphism.
Sum of [1,2,3,4,5,6,7,8,9,10] is 55
Prod of [1,2,3,4,5,6,7,8,9,10] is 3628800
Concat of [1,2,3,4,5,6,7,8,9,10] is 12345678910
true.

Python

<lang python>>>> from operator import add >>> listoflists = [['the', 'cat'], ['sat', 'on'], ['the', 'mat']] >>> help(reduce) Help on built-in function reduce in module __builtin__:

reduce(...)

   reduce(function, sequence[, initial]) -> value
   
   Apply a function of two arguments cumulatively to the items of a sequence,
   from left to right, so as to reduce the sequence to a single value.
   For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
   ((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
   of the sequence in the calculation, and serves as a default when the
   sequence is empty.

>>> reduce(add, listoflists, []) ['the', 'cat', 'sat', 'on', 'the', 'mat'] >>> </lang>

Additional example

<lang python>from functools import reduce from operator import add, mul

nums = range(1,11)

summation = reduce(add, nums)

product = reduce(mul, nums)

concatenation = reduce(lambda a, b: str(a) + str(b), nums)

print(summation, product, concatenation)</lang>

Racket

<lang racket>

1. lang racket

(define (fold f xs init)

 (if (empty? xs)
     init
     (f (first xs)
        (fold f (rest xs) init))))

(fold + '(1 2 3) 0)  ; the result is 6 </lang>

REXX

This REXX example is modeled after the Perl 6 example (it is NOT a translation). <lang rexx>/*REXX pgm shows a method for catamorphism for some simple functions. */ @list = 1 2 3 4 5 6 7 8 9 10

                              say 'show:'  fold(@list, 'show')
                              say ' sum:'  fold(@list, '+')
                              say 'prod:'  fold(@list, '*')
                              say ' cat:'  fold(@list, '||')
                              say ' min:'  fold(@list, 'min')
                              say ' max:'  fold(@list, 'max')
                              say ' avg:'  fold(@list, 'avg')
                              say ' GCD:'  fold(@list, 'GCD')
                              say ' LCM:'  fold(@list, 'LCM')

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────FOLD subroutine─────────────────────*/ fold: procedure; parse arg z; arg ,f; z=space(z) /*F is uppercased.*/ za=translate(z, f, " "); zf=f'('translate(z,',' ," ")')' if f=='+' | f=='*' then interpret 'return' za if f=='||' then return space(z,0) if f=='AVG' then interpret 'return' fold(z,'+') "/" words(z) if wordpos(f,'MIN MAX LCM GCD')\==0 then interpret 'return' zf if f=='SHOW' then return z return 'illegal function:' arg(2) /*──────────────────────────────────LCM subroutine──────────────────────*/ lcm: procedure; $=; do j=1 for arg(); $=$ arg(j); end x=abs(word($,1)) /* [↑] build a list of arguments.*/

           do k=2  to words($);   !=abs(word($,k));  if !=0 then return 0
           x=x*! / gcd(x,!)           /*have  GCD do the heavy lifting.*/
           end   /*k*/

return x /*return with the money. */ /*──────────────────────────────────GCD subroutine──────────────────────*/ gcd: procedure; $=; do j=1 for arg(); $=$ arg(j); end parse var $ x z .; if x=0 then x=z /* [↑] build a list of arguments.*/ x=abs(x)

           do k=2  to words($);    y=abs(word($,k));  if y=0 then iterate
             do until _==0;   _=x//y;   x=y;   y=_;   end   /*until*/
           end   /*k*/

return x /*return with the money. */</lang>

Output:

list: 1 2 3 4 5 6 7 8 9 10
 sum: 55
prod: 3628800
 cat: 12345678910
 min: 1
 max: 10
 avg: 5.5
 GCD: 1
 LCM: 2520

Run BASIC

<lang runbasic>for i = 1 to 10 :n(i) = i:next i

print " +: ";" ";cat(10,"+") print " -: ";" ";cat(10,"-") print " *: ";" ";cat(10,"*") print " /: ";" ";cat(10,"/") print " ^: ";" ";cat(10,"^") print "min: ";" ";cat(10,"min") print "max: ";" ";cat(10,"max") print "avg: ";" ";cat(10,"avg") print "cat: ";" ";cat(10,"cat")

function cat(count,op$) cat = n(1) for i = 2 to count

if op$ = "+" 	then cat = cat + n(i)
if op$ = "-" 	then cat = cat - n(i)
if op$ = "*" 	then cat = cat * n(i) 
if op$ = "/" 	then cat = cat / n(i)
if op$ = "^" 	then cat = cat ^ n(i)
if op$ = "max"	then cat = max(cat,n(i))
if op$ = "min"	then cat = min(cat,n(i))
if op$ = "avg"	then cat = cat + n(i)
if op$ = "cat"	then cat$ = cat$ + str$(n(i))

next i if op$ = "avg" then cat = cat / count if op$ = "cat" then cat = val(str$(n(1))+cat$) end function</lang>

  +:  55
  -:  -53
  *:  3628800
  /:  2.75573205e-7
  ^:  1
min:  1
max:  10
avg:  5.5
cat:  12345678910

Tcl

Tcl does not come with a built-in fold command, but it is easy to construct: <lang tcl>proc fold {lambda zero list} {

   set accumulator $zero
   foreach item $list {

set accumulator [apply $lambda $accumulator $item]

   }
   return $accumulator

}</lang> Demonstrating: <lang tcl>set 1to5 {1 2 3 4 5}

puts [fold {{a b} {expr {$a+$b}}} 0 $1to5] puts [fold {{a b} {expr {$a*$b}}} 1 $1to5] puts [fold {{a b} {return $a,$b}} x $1to5]</lang>

Output:

15
120
x,1,2,3,4,5

Note that these particular operations would more conventionally be written as: <lang tcl>puts [::tcl::mathop::+ {*}$1to5] puts [::tcl::mathop::* {*}$1to5] puts x,[join $1to5 ,]</lang> But those are not general catamorphisms.

Wortel

You can reduce an array with the !/ operator. <lang wortel>!/ ^+ [1 2 3] ; returns 6</lang> If you want to reduce with an initial value, you'll need the @fold operator. <lang wortel>@fold ^+ 1 [1 2 3] ; returns 7</lang>