Catamorphism: Difference between revisions
(+J) |
|||
Line 95: | Line 95: | ||
# let product = List.fold_left ( * ) 0 nums;; |
# let product = List.fold_left ( * ) 0 nums;; |
||
val product : int = 0</lang> |
val product : int = 0</lang> |
||
=={{header|Perl}}== |
|||
Perl's reduce function is in a standard pacakage. |
|||
<lang perl>use List::Util 'reduce'; |
|||
# note the use of the odd $a and $b globals |
|||
print +(reduce {$a + $b} 1 .. 10), "\n"; |
|||
# 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> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
Revision as of 20:27, 28 November 2012
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 in your language.
- Cf.
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")
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>
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>
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]
- let sum = List.fold_left (+) 0 nums;;
val sum : int = 55
- let product = List.fold_left ( * ) 0 nums;;
val product : int = 0</lang>
Perl
Perl's reduce function is in a standard pacakage. <lang perl>use List::Util 'reduce';
- note the use of the odd $a and $b globals
print +(reduce {$a + $b} 1 .. 10), "\n";
- 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>
REXX
This REXX program is modeled after the Perl 6 example. <lang rexx>/*REXX program shows a method of catamorphism (show, +, *, MIN, MAX∙∙∙)*/ @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 f=='MIN' | f=='MAX' | f=='LCM' | f=='GCD' then interpret 'return' zf if f=='SHOW' then return z return 'illegal function:' arg(2) /*───────────────────────────────────GCD subroutine─────────────────────*/ gcd: procedure; parse arg x; do i=2 to arg(); x=x arg(i); end
parse var x x $ 1 . z .; x=abs(x); if x=0 then x=abs(z) do j=1 for words($); y=abs(word($,j)); if y=0 then iterate do until _==0; _=x//y; x=y; y=_; end; end; return x
/*───────────────────────────────────LCM subroutine─────────────────────*/ lcm: procedure; parse arg x .; do j=1 for arg(); y=arg(j)
do k=1 for words(y); !=abs(word(y,k)); if !=0 then return 0 x=x*!/gcd(x,!); end; end; return x</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