Catamorphism: Difference between revisions

* Wikipedia article:   [[wp:Catamorphism|Catamorphism]]

<br><br>

=={{header|11l}}==

print((1..3).reduce(3, (x, y) -> x + y))

print([1, 1, 3].reduce((x, y) -> x + y))

=={{header|6502 Assembly}}==

{{works with|https://skilldrick.github.io/easy6502/ Easy6502}}

define catbuf_temp $12

 

cpx #$ff

bne clear_ram</syntaxhighlight>

=={{header|ABAP}}==

This works in ABAP version 7.40 and above.

 

report z_catamorphism.

 

concatenation(strings) = reduce in ABAP

</pre>

=={{header|Ada}}==

 

 

procedure Catamorphism is

 

<pre> 1 4 10 24</pre>

=={{header|Aime}}==

 

s = 0;

{{Out}}

<pre>45</pre>

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

# the result is 0 if there are no values #

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

-13

</pre>

=={{header|APL}}==

<em>Reduce</em> is a built-in APL operator, written as <code>/</code>.

 

28

×/ 1 2 3 4 5 6 7

For built-in functions, the seed value is automatically chosen to make sense.

 

0

×/⍬

called, and calling <code>F/</code> with the empty list is an error.

 

Input: 4 5

Input: 3 9

{⎕←'Input:',⍺,⍵ ⋄ ⍺+⍵}/ ⍬

DOMAIN ERROR</syntaxhighlight>

=={{header|AppleScript}}==

{{Trans|JavaScript}}

(Note that to obtain first-class functions from user-defined AppleScript handlers, we have to 'lift' them into script objects).

 

 

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

{{out}}

<pre>{55, 3628800, "12345678910"}</pre>

=={{header|Arturo}}==

 

print fold [1 2 3 4] => add

 

<pre>10

24</pre>

=={{header|BASIC}}==

==={{header|BASIC256}}===

{{trans|Run BASIC}}

global n

dim n = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

end function</syntaxhighlight>

 

 

==={{header|QBasic}}===

{{works with|QBasic|1.1}}

{{trans|Run BASIC}}

FOR i = 1 TO 10: n(i) = i: NEXT i

 

PRINT "max: "; " "; cat(10, "max")

PRINT "avg: "; " "; cat(10, "avg")</syntaxhighlight>

 

==={{header|True BASIC}}===

FOR i = 1 to 10

LET n(i) = i

PRINT "cat: "; " "; cat(10, "cat")

END</syntaxhighlight>

 

==={{header|Yabasic}}===

{{trans|Run BASIC}}

for i = 1 to 10 : n(i) = i : next i

return cat

end sub</syntaxhighlight>

 

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

DIM a(4)

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

-13

120</pre>

=={{header|BCPL}}==

 

let reduce(f, v, len, seed) =

<pre>28

5040</pre>

 

=={{header|BQN}}==

┘

⟨ 9 7 12 ⟩</pre>

=={{header|Bracmat}}==

= f xs init first rest

. !arg:(?f.?xs.?init)

<pre>15

120</pre>

=={{header|C}}==

 

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

-13

120</pre>

=={{header|C sharp|C#}}==

 

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

 

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

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

#include <numeric>

#include <functional>

<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

115

</syntaxhighlight>

=={{header|CLU}}==

% First type = sequence type (must support S$elements and yield R)

% Second type = right (input) datatype

<pre>The sum of [1..10] is: 55

The product of [1..10] is: 3628800</pre>

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

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

120

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

4096</syntaxhighlight>

=={{header|D}}==

import std.stdio, std.algorithm, std.range, std.meta, std.numeric,

std.conv, std.typecons;

gcd(T): 1

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

=={{header|DCL}}==

$ call reduce list "+"

$ show symbol result

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

<pre>215

-207</pre>

=={{header|EchoLisp}}==

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

;; fold left a list

→ (1 1 2 6 24 120)

</syntaxhighlight>

=={{header|Elena}}==

ELENA 5.0 :

import system'routines;

import extensions;

55 362880 12345678910

</pre>

=={{header|Elixir}}==

55

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

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

"109876543210-1-2-3-4-5-6-7-8-9-10"</syntaxhighlight>

=={{header|Erlang}}==

{{trans|Haskell}}

 

-module(catamorphism).

 

{55,3628800,"12345678910"}

</pre>

=={{header|Excel}}==

===LAMBDA===

 

{{Works with|Office 365 betas 2021}}

=LAMBDA(op,

LAMBDA(a,

| ][ [[[ [ ]]] [[[ ]]] [[[ [] ]]] ]

|}

=={{header|F_Sharp|F#}}==

<p>In the REPL:</p>

val concatenation : string = "12345678910"

</pre>

=={{header|Factor}}==

 

{{out}}

<pre>

23

</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 ;

 

Using normal looping words:

 

nip + c@ ;

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

Briefly, a variation:

 

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

else 2drop 0 then ;

Using dedicated looping words:

 

postpone BOUNDS postpone ?DO

postpone I postpone C@ ; immediate

Using higher-order words:

 

{: xt :} bounds ?do

i c@ xt execute

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

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

=={{header|Fortran}}==

INTEGER t

BYNAME F

However, only programmer diligence in devising functions with the correct type of result and the correct type and number of parameters will evade mishaps. Note that the EXTERNAL statement does not specify the number or type of parameters. If the function is invoked multiple times within a subroutine, the compiler may check for consistency. This may cause trouble when [[Leonardo_numbers#Fortran|some parameters are optional]] so that different invocations do not match.

 

INTEGER F !We're working only with integers.

EXTERNAL F !This is a function, not an array.

Ivid 6

</pre>

=={{header|FreeBASIC}}==

 

Type IntFunc As Function(As Integer, As Integer) As Integer

No op is : 0

</pre>

=={{header|Go}}==

 

import (

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]

84

abcd=10</pre>

=={{header|Haskell}}==

main =

putStrLn . unlines $

and the generality of folds is such that if we replace all three of these (function, identity) combinations ((+), 0), ((*), 1) ((++), "") with the Monoid operation '''mappend''' (<>) and identity '''mempty''', we can still obtain the same results:

 

 

main :: IO ()

 

''Prelude'' folds work only on lists, module ''Data.Foldable'' a typeclass for more general fold - interface remains the same.

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

 

Works in both languages:

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

end

||: 314159

</pre>

=={{header|J}}==

15

*/ 1 2 3 4 5

becomes

1 * 2 * 3 * 4 * 5

1 * 2 * 3 * 20

1 * 2 * 60

What are the implications for -/ ?

For %/ ?

=={{header|Java}}==

{{works with|Java|8}}

 

public class ReduceTask {

<pre>15

120</pre>

=={{header|JavaScript}}==

 

===ES5===

 

 

function add(a, b) {

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

 

'use strict';

 

===ES6===

 

 

console.log(nums.reduce((a, b) => a + b, 0)); // sum of 1..10

console.log(nums.reduce((a, b) => a * b, 1)); // product of 1..10

console.log(nums.reduce((a, b) => a + b, '')); // concatenation of 1..10</syntaxhighlight>

=={{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}}==

{{Works with|Julia 1.2}}

println([foldl(op, 1:5) for op in [+, -, *]])

println([foldr(op, 1:5) for op in [+, -, *]])</syntaxhighlight>

 

=={{header|Kotlin}}==

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

println("Array : ${a.joinToString(", ")}")

Maximum : 5

</pre>

 

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

 

yes

</pre>

=={{header|LOLCODE}}==

 

{{trans|C}}

 

 

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

-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}

cat {1..9}: 123456789

</pre>

=={{header|M2000 Interpreter}}==

Module CheckIt {

Function Reduce (a, f) {

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

 

3628800</syntaxhighlight>

Compute the horner form of a (sorted) polynomial:

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

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

{{Out}}

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

=={{header|Maxima}}==

/* (%o1) f(f(f(f(x0, a), b), c), d) */</syntaxhighlight>

 

/* (%o1) 110 */</syntaxhighlight>

=={{header|min}}==

{{works with|min|0.19.3}}

(1 2 3 4) 1 '* reduce puts! ; product</syntaxhighlight>

{{out}}

24

</pre>

=={{header|Modula-2}}==

FROM InOut IMPORT WriteString, WriteCard, WriteLn;

 

<pre>Sum of [1..5]: 15

Product of [1..5]: 120</pre>

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

def sum = seq.Fold(0, _ + _); // Fold takes an initial value and a function, here the + operator</syntaxhighlight>

=={{header|Nim}}==

 

block:

words = @["nim", "is", "cool"]

concatenation = foldr(words, a & b)</syntaxhighlight>

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

{{Works with| oo2c Version 2}}

MODULE Catamorphism;

IMPORT

-14400

</pre>

=={{header|Objeck}}==

use Collection;

 

120

</pre>

=={{header|OCaml}}==

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

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

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

val product : int = 3628800</syntaxhighlight>

=={{header|Oforth}}==

reduce is already defined into Collection class :

 

[ "abc", "def", "gfi" ] reduce(#+)</syntaxhighlight>

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

my(t=v[1]);

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

 

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

=={{header|Pascal}}==

{{works with|Free Pascal}}

Should work with many pascal dialects

 

type

-11

-1440</pre>

=={{header|Perl}}==

Perl's reduce function is in a standard package.

 

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

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

print +(reduce \&func, 1 .. 10), "\n"</syntaxhighlight>

=={{header|Phix}}==

{{trans|C}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">add</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">b</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

120

</pre>

=={{header|Phixmonti}}==

 

def add + enddef

getid sub reduce ?

getid mul reduce ?</syntaxhighlight>

=={{header|PicoLisp}}==

(let "A" (car "Lst")

(for "N" (cdr "Lst")

(bye)</syntaxhighlight>

=={{header|PowerShell}}==

'Filter' is a more common sequence function in PowerShell than 'reduce' or 'map', but here is one way to accomplish 'reduce':

1..5 | ForEach-Object -Begin {$result = 0} -Process {$result += $_} -End {$result}

</syntaxhighlight>

15

</pre>

=={{header|Prolog}}==

 

* '''Ulrich Neumerkel''' wrote `library(lambda)` which can be found [http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl here]. (However, SWI-Prolog's Lambda Expressions are by default based on Paulo Moura's [https://www.swi-prolog.org/search?for=yall library(yall)])

 

 

catamorphism :-

* The list is terminated by the special atomic thing <code>[]</code> (the empty list)

 

% List to be folded:

%

====linear <code>foldl</code>====

 

% Computes "Out" as:

%

====linear <code>foldr</code>====

 

% Computes "Out" as:

%

Functions (in predicate form) of interest for our test cases:

 

:- use_module(library(clpfd)). % We are using #= instead of the raw "is".

 

</syntaxhighlight>

 

:- begin_tests(foldr).

 

rt :- run_tests(foldr),run_tests(foldl).

</syntaxhighlight>

=={{header|PureBasic}}==

If FirstElement(l())

x=l()

-13

120</pre>

=={{header|Python}}==

>>> from operator import add

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

>>> </syntaxhighlight>

===Additional example===

 

from functools import reduce

 

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

=={{header|Quackery}}==

Among its many other uses, <code>witheach</code> can act like reduce. In the Quackery shell (REPL):

... 1 ' [ 1 2 3 4 5 ] witheach *

...

 

Stack: 15 120</syntaxhighlight>

=={{header|R}}==

 

Sum the numbers in a vector:

 

Reduce('+', c(2,30,400,5000))

5432

Put a 0 between each pair of numbers:

 

Reduce(function(a,b){c(a,0,b)}, c(2,3,4,5))

2 0 3 0 4 0 5

Generate all prefixes of a string:

 

Reduce(paste0, unlist(strsplit("freedom", NULL)), accum=T)

"f" "fr" "fre" "free" "freed" "freedo" "freedom"

Filter and map:

 

Reduce(function(x,acc){if (0==x%%3) c(x*x,acc) else acc}, 0:22,

init=c(), right=T)

0 9 36 81 144 225 324 441

</syntaxhighlight>

=={{header|Racket}}==

#lang racket

(define (fold f xs init)

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

</syntaxhighlight>

=={{header|Raku}}==

(formerly Perl 6)

{{works with|Rakudo|2018.03}}

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.

say [+] @list;

say [*] @list;

2520</pre>

In addition to the reduce metaoperator, a general higher-order function, <tt>reduce</tt>, can apply any appropriate function. Reproducing the above in this form, using the function names of those operators, we have:

say reduce &infix:<+>, @list;

say reduce &infix:<*>, @list;

say reduce &infix:<max>, @list;

say reduce &infix:<lcm>, @list;</syntaxhighlight>

 

=={{header|REXX}}==

aren't a catamorphism, as they don't produce or reduce the values to a &nbsp; ''single'' &nbsp; value, but

are included here to help display the values in the list.

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

say 'list:' fold(@list, "list")

 

=={{header|Ring}}==

n = list(10)

for i = 1 to 10

return cat

</syntaxhighlight>

 

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

</syntaxhighlight>The most versatile way uses a accumulator object (memo) and a block. In this example Pascal's triangle is generated by using an array [1,1] and inserting the sum of each consecutive pair of numbers from the previous row.

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

 

 

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

 

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

avg: 5.5

cat: 12345678910</pre>

=={{header|Rust}}==

 

println!("Sum: {}", (1..10).fold(0, |acc, n| acc + n));

println!("Product: {}", (1..10).fold(1, |acc, n| acc * n));

Concatenation: bcdef

</pre>

=={{header|Scala}}==

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

println(s"Array : ${a.mkString(", ")}")

println(s"Maximum : ${a.max}")

}</syntaxhighlight>

=={{header|Scheme}}==

===Implementation===

reduce implemented for a single list:

(do ((val init (fn (car rem) val)) ; accumulated value passed as second argument

(rem lst (cdr rem)))

21

</pre>

=={{header|Sidef}}==

say (1..10 -> reduce{|a,b| a + b});</syntaxhighlight>

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

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

- val sum = foldl op+ 0 nums;

- val product = foldl op* 1 nums;

val product = 3628800 : int</syntaxhighlight>

=={{header|Swift}}==

 

print(nums.reduce(0, +))

3628800

12345678910</pre>

=={{header|Tailspin}}==

It is probably easier to just write the whole thing as an inline transform rather than create a utility.

[1..5] -> \(@: $(1); $(2..last)... -> @: $@ + $; $@!\) -> '$;

' -> !OUT::write

 

If you really want to make a utility, it could look like this:

templates fold&{op:}

@: $(1);

120

</pre>

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

}</syntaxhighlight>

Demonstrating:

 

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

</pre>

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

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

puts x,[join $1to5 ,]</syntaxhighlight>

But those are not general catamorphisms.

=={{header|uBasic/4tH}}==

{{trans|FreeBASIC}}

uBasic/4tH has only got one single array so passing its address makes little sense. Instead, its bounds are passed.

For x = 0 To s: @(x) = Pop(): Next

 

 

=={{header|VBA}}==

s = [{1,2,3,4,5}]

Debug.Print WorksheetFunction.Sum(s)

Debug.Print WorksheetFunction.Product(s)

End Sub</syntaxhighlight>

{{trans|go}}

n := [1, 2, 3, 4, 5]

Translated from the JavaScript ES6 example with a few modifications.

 

let s => import 'stream';

let str => import 'strings';

# And here's a concatenation:

s.range 1 11 -> s.reduce '' (str.format '{}{}') -- io.writeln io.stdout;</syntaxhighlight>

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

 

{{out}}

3628800

12345678910</pre>

=={{header|Wren}}==

var sum = a.reduce { |acc, i| acc + i }

var prod = a.reduce { |acc, i| acc * i }

Sum of squares is 55

</pre>

 

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

File("foo.zkl").reduce('+(1).fpM("0-"),0) //->5 (lines in file)</syntaxhighlight>

=={{header|ZX Spectrum Basic}}==

{{trans|BBC_BASIC}}

20 FOR i=1 TO 5

30 READ a(i)