Catamorphism: Difference between revisions

{{task}}

''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.

 

 

=={{header|Ada}}==

 

 

procedure Catamorphism is

NIO.Put(Fold_Left(Add'Access, (1,2,3,4)), Width => 3);

NIO.Put(Fold_Left(Mul'Access, (1,2,3,4)), Width => 3);

 

{{out}}

 

<pre> 1 4 10 24</pre>

 

=={{header|ALGOL 68}}==

# the result is 0 if there are no values #

PROC reduce = ( []INT values, PROC( INT, INT )INT fn )INT:

; print( ( reduce( ( 1, 2, 3, 4, 5 ), ( INT a, b )INT: a * b ), newline ) ) # product #

; print( ( reduce( ( 1, 2, 3, 4, 5 ), ( INT a, b )INT: a - b ), newline ) ) # difference #

{{out}}

<pre>

-13

</pre>

 

=={{header|AppleScript}}==

 

 

 

 

-- the arguments available to the called function f(a, x, i, l) are

-- x: current item in list

-- i: [ 1-based index in list ] optional

-- l: [ a reference to the list itself ] optional

 

 

-- the arguments available to the called function f(a, x, i, l) are

-- x: current item in list

-- i: [ 1-based index in list ] optional

-- l: [ a reference to the list itself ] optional

 

 

 

 

script

end script

 

 

 

a & b

 

 

{{out}}

 

 

 

=={{header|BBC BASIC}}==

DIM a(4)

a() = 1, 2, 3, 4, 5

NEXT

= tmp

 

{{out}}

-13

120</pre>

 

=={{header|C}}==

 

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

printf("%d\n", reduce(mul, 5, nums));

return 0;

 

{{out}}

-13

120</pre>

 

=={{header|C++}}==

#include <numeric>

#include <functional>

std::cout << "nums_added: " << nums_added << std::endl;

std::cout << "nums_other: " << nums_other << std::endl;

 

{{out}}

<pre>nums_added: 15

nums_other: 30</pre>

=={{header|Clojure}}==

For more detail, check Rich Hickey's [http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html blog post on Reducers].

 

> (reduce * '(1 2 3 4 5))

120

> (reduce + 100 '(1 2 3 4 5))

115

 

=={{header|Common Lisp}}==

> (reduce #'* '(1 2 3 4 5))

120

; Compare with

> (reduce #'expt '(2 3 4))

=={{header|D}}==

 

auto list = iota(1, 11);

 

foreach (op; ops)

// std.algorithm.reduce supports multiple functions in parallel:

reduce!(ops[0], ops[3], text)(tuple(0, 0.0, ""), list).writeln;

{{out}}

<pre>"a + b": 55

Tuple!(int,double,string)(55, 10, "12345678910")</pre>

=={{header|DCL}}==

$ call reduce list "+"

$ show symbol result

$ result == value

$ exit

{{out}}

<pre>$ @catamorphism

RESULT == -5 Hex = FFFFFFFB Octal = 37777777773

RESULT == 120 Hex = 00000078 Octal = 00000000170</pre>

=={{header|Déjà Vu}}==

This is a foldl:

if lst:

f reduce @f lst init pop-from lst

!. reduce @+ [ 1 10 200 ] 4

!. reduce @- [ 1 10 200 ] 4

{{out}}

<pre>215

-207</pre>

=={{header|EchoLisp}}==

;; rem : the foldX family always need an initial value

;; fold left a list

(scanl * 1 '( 1 2 3 4 5))

→ (1 1 2 6 24 120)

=={{header|Elixir}}==

55

iex(2)> Enum.reduce(1..10, fn i,acc -> i*acc end)

3628800

iex(3)> Enum.reduce(10..-10, "", fn i,acc -> acc <> to_string(i) end)

=={{header|Erlang}}==

{{trans|Haskell}}

 

-module(catamorphism).

 

Nums),

{Summation, Product, Concatenation}.

 

Output:

{55,3628800,"12345678910"}

</pre>

 

=={{header|Forth}}==

Forth has three traditions for iterating over the members of a data

Some helper words for these examples:

 

[char] a [ char z 1+ ] literal within ;

 

: char-upcase ( c -- C )

 

Using normal looping words:

 

nip + c@ ;

: string-at! ( c-addr u +n c -- )

0 -rot dup 0 ?do

2dup i string-at lowercase? if rot 1+ -rot then

 

Briefly, a variation:

 

dup if 2dup 1 /string 2swap drop c@ true

else 2drop 0 then ;

begin next-char while

dup lowercase? if emit else drop then

 

Using dedicated looping words:

 

postpone BOUNDS postpone ?DO

postpone I postpone C@ ; immediate

 

: count-lowercase ( c-addr u -- n )

 

Using higher-order words:

 

{: xt :} bounds ?do

i c@ xt execute

 

: count-lowercase ( c-addr u -- n )

 

In these examples COUNT-LOWERCASE updates an accumulator, UPCASE

(mostly) modifies the string in-place, and TYPE-LOWERCASE performs

side-effects and returns nothing to the higher-order word.

 

=={{header|Go}}==

 

import (

}

return r

{{out}}

<pre>

120

</pre>

=={{header|Groovy}}==

Groovy provides an "inject" method for all aggregate classes that performs a classic tail-recursive reduction, driven by a closure argument. The result of each iteration (closure invocation) is used as the accumulated valued for the next iteration. If a first argument is provided as well as a second closure argument, that first argument is used as a seed accumulator for the first iteration. Otherwise, the first element of the aggregate is used as the seed accumulator, with reduction iteration proceeding across elements 2 through n.

def vector2 = [7,6,5,4,3,2,1]

def map1 = [a:1, b:2, c:3, d:4]

println (map1.inject { Map.Entry accEntry, Map.Entry entry -> // some sort of weird map-based reduction

[(accEntry.key + entry.key):accEntry.value + entry.value ].entrySet().toList().pop()

 

{{out}}

84

abcd=10</pre>

=={{header|Haskell}}==

 

 

 

 

=={{header|Icon}} and {{header|Unicon}}==

 

Works in both languages:

write(A[1],": ",curry(A[1],A[2:0]))

end

every r := f(r, !A[2:0])

return r

 

Sample runs:

||: 314159

</pre>

=={{header|J}}==

15

*/ 1 2 3 4 5

120

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

=={{header|Java}}==

{{works with|Java|8}}

 

public class ReduceTask {

System.out.println(Stream.of(1, 2, 3, 4, 5).reduce(1, (a, b) -> a * b));

}

 

{{out}}

<pre>15

120</pre>

=={{header|JavaScript}}==

 

function add(a, b) {

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

 

 

 

Note that the JavaScript Array methods include a right fold ( '''.reduceRight()''' ) as well as a left fold:

 

'use strict';

 

});

 

 

{{Out}}

"18 16 14 12 10 8 6 4 2 0 "]</pre>

 

=={{header|jq}}==

jq has an unusual and unusually powerful "reduce" control structure. A full description is beyond the scope of this short article, but an important point is that "reduce" is stream-oriented. Reduction of arrays is however trivially achieved using the ".[]" filter for converting an array to a stream of its values.

 

The "reduce" operator is typically used within a map/reduce framework, but the implicit state variable can be any JSON entity, and so "reduce" is also a general-purpose iterative control structure, the only limitation being that it does not have the equivalent of "break". For that, the "foreach" control structure in recent versions of jq can be used.

=={{header|Julia}}==

 

{{out}}

 

=={{header|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.

:- object(folding_examples).

 

 

:- end_object.

{{out}}

<pre>

yes

</pre>

=={{header|LOLCODE}}==

 

{{trans|C}}

 

 

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

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

 

 

{{out}}

-13

120</pre>

=={{header|Lua}}==

table.unpack = table.unpack or unpack -- 5.1 compatibility

local nums = {1,2,3,4,5,6,7,8,9}

print("cat {1..9}: ",reduce(cat,table.unpack(nums)))

 

 

{{out}}

5! : 120

cat {1..9}: 123456789

</pre>

 

=={{header|Maple}}==

The left fold operator in Maple is foldl, and foldr is the right fold operator.

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

 

 

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

Compute the horner form of a (sorted) polynomial:

=={{header|Mathematica}} / {{header|Wolfram Language}}==

{{Out}}

<pre>f[f[f[f[x, a], b], c], d]</pre>

=={{header|Maxima}}==

 

 

=={{header|Nemerle}}==

The <tt>Nemerle.Collections</tt> namespace defines <tt>FoldLeft</tt>, <tt>FoldRight</tt> and <tt>Fold</tt> (an alias for <tt>FoldLeft</tt>) on any sequence that implements the <tt>IEnumerable[T]</tt> interface.

=={{header|Nim}}==

 

block:

substraction = foldl(numbers, a - b)

multiplication = foldl(numbers, a * b)

concatenation = foldl(words, a & b)

 

substraction = foldr(numbers, a - b)

multiplication = foldr(numbers, a * b)

=={{header|Oberon-2}}==

{{Works with| oo2c Version 2}}

MODULE Catamorphism;

IMPORT

END

END Catamorphism.

{{out}}

<pre>

-14400

</pre>

 

=={{header|OCaml}}==

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 ( * ) 1 nums;;

=={{header|Oforth}}==

reduce is already defined into Collection class :

 

=={{header|PARI/GP}}==

my(t=v[1]);

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

t

};

 

{{works with|PARI/GP|2.8.1+}}

=={{header|Pascal}}==

{{works with|Free Pascal}}

Should work with many pascal dialects

 

type

writeln(reduce(@sub,ma));

writeln(reduce(@mul,ma));

output

<pre>-5,-4,-3,-2,-1,1,1,2,3,4,5

-11

-1440</pre>

=={{header|Perl}}==

Perl's reduce function is in a standard package.

 

# note the use of the odd $a and $b globals

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

sub func { $b & 1 ? "$a $b" : "$b $a" }

{{out}}

 

=={{header|PicoLisp}}==

(let "A" (car "Lst")

(for "N" (cdr "Lst")

(reduce * (1 2 3 4 5)) )

=={{header|Prolog}}==

 

catamorphism :-

numlist(1,10,L),

foldl(\XC^YC^ZC^(string_to_atom(XS, XC),string_concat(YC,XS,ZC)),

L, LV, Concat),

{{out}}

<pre> ?- catamorphism.

</pre>

 

=={{header|Python}}==

>>> listoflists = [['the', 'cat'], ['sat', 'on'], ['the', 'mat']]

>>> help(reduce)

>>> reduce(add, listoflists, [])

['the', 'cat', 'sat', 'on', 'the', 'mat']

===Additional example===

from operator import add, mul

 

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

 

 

 

=={{header|Racket}}==

#lang racket

(define (fold f xs init)

 

(fold + '(1 2 3) 0) ; the result is 6

 

=={{header|REXX}}==

@list= 1 2 3 4 5 6 7 8 9 10

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

return x

/*──────────────────────────────────────────────────────────────────────────────────────*/

<pre>

list: 1 2 3 4 5 6 7 8 9 10

 

=={{header|Ring}}==

n = list(10)

for i = 1 to 10

see " +: " + cat(10,"+") + nl+

func cat count,op

if op = "avg" cat = cat / count ok

if op = "cat" decimals(0) cat = string(n[1])+cat2 ok

return cat

 

=={{header|Ruby}}==

The method inject (and it's alias reduce) can be used in several ways; the simplest is to give a methodname as argument:

p (1..10).inject(:+)

# smallest number divisible by all numbers from 1 to 20:

p (1..20).inject(:lcm) #lcm: lowest common multiple

10.times{p row = row.each_cons(2).inject([1,1]){|ar,(a,b)| ar.insert(-2, a+b)} }

 

# [1, 6, 15, 20, 15, 6, 1]

# etc

 

=={{header|Run BASIC}}==

 

print " +: ";" ";cat(10,"+")

if op$ = "avg" then cat = cat / count

if op$ = "cat" then cat = val(str$(n(1))+cat$)

<pre> +: 55

-: -53

avg: 5.5

cat: 12345678910</pre>

 

 

=={{header|Standard ML}}==

val nums = [1,2,3,4,5,6,7,8,9,10] : int list

- val sum = foldl op+ 0 nums;

val sum = 55 : int

- val product = foldl op* 1 nums;

 

=={{header|Tcl}}==

Tcl does not come with a built-in <tt>fold</tt> command, but it is easy to construct:

set accumulator $zero

foreach item $list {

}

return $accumulator

Demonstrating:

 

puts [fold {{a b} {expr {$a+$b}}} 0 $1to5]

puts [fold {{a b} {expr {$a*$b}}} 1 $1to5]

{{out}}

<pre>

</pre>

Note that these particular operations would more conventionally be written as:

puts [::tcl::mathop::* {*}$1to5]

But those are not general catamorphisms.

 

=={{header|Wortel}}==

You can reduce an array with the <code>!/</code> operator.

If you want to reduce with an initial value, you'll need the <code>@fold</code> operator.

 

=={{header|zkl}}==

Most sequence objects in zkl have a reduce method.

"123four5".reduce(fcn(p,c){p+(c.matches("[0-9]") and c or 0)}, 0) //-->11