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

{{out}}

<pre>

7

</pre>

 

=={{header|ABAP}}==

This works in ABAP version 7.40 and above.

 

report z_catamorphism.

 

for string in strings

next text = |{ text } { string }| ) }|, /.

 

{{out}}

concatenation(strings) = reduce in ABAP

</pre>

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

 

s = 0;

list(1, 2, 3, 4, 5, 6, 7, 8, 9).ucall(add_i, 1, s);

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

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

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

 

 

 

on concat(xs)

end concat

 

-- product :: Num a => [a] -> a

foldr(result, 1, xs)

end product

 

-- sum :: Num a => [a] -> a

 

 

on run

set xs to {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

--> {55, 3628800, "10987654321"}

 

 

 

-- Lift 2nd class handler function into 1st class script wrapper

end script

end if

{{out}}

 

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

DIM a(4)

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

NEXT

= tmp

 

{{out}}

-13

120</pre>

 

=={{header|Bracmat}}==

= f xs init first rest

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

& (product=a b.!arg:(?a.?b)&!a*!b)

& out$(fold$(product.1 2 3 4 5.1))

Output:

<pre>15

120</pre>

=={{header|C}}==

 

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

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

return 0;

 

{{out}}

-13

120</pre>

 

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

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

 

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

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

std.conv, std.typecons;

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

gcd(T): 1

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

ELENA 5.0 :

import system'routines;

import extensions;

console.printLine(summary," ",product," ",concatenation)

{{out}}

<pre>

55 362880 12345678910

</pre>

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

 

: 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|Fortran}}==

INTEGER t

BYNAME F

END SUBROUTINE FOLD !Result in temp.

 

Here, the function manifests as the expression that is the second parameter of subroutine FOLD, and the "by name" protocol for parameter F means that within the subroutine whenever there is a reference to F, its value is evaluated afresh in the caller's environment using the current values of ''temp'' and ''i'' as modified by the subroutine - they being passed by reference so that changes within the subroutine affect the originals. An evaluation for a different function requires merely another statement with a different expression.

 

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.

WRITE (MSG,*) "Ivid",IFOLD(IVID,A,ENUFF)

END PROGRAM POKE

Output:

<pre>

Ivid 6

</pre>

=={{header|FreeBASIC}}==

 

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

Print "Press any key to quit"

Sleep

 

{{out}}

No op is : 0

</pre>

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

main =

putStrLn . unlines $

, foldr ((++) . show) "" -- concatenation

] <*>

{{Out}}

<pre>55

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 ()

, (show . foldr (<>) mempty) (words

"Love is one damned thing after each other")

{{Out}}

<pre>55

 

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

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"

Insert * into 1 2 3 4 5

becomes

1 * 2 * 3 * 4 * 5

1 * 2 * 3 * 20

1 * 2 * 60

1 * 120

120

What are the implications for -/ ?

For %/ ?

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

 

===ES5===

 

 

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

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

=={{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 [+, -, *]])

{{out}}

<pre>[15, -13, 120]

 

=={{header|Kotlin}}==

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

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

println("Minimum : ${a.reduce { x, y -> if (x < y) x else y }}")

println("Maximum : ${a.reduce { x, y -> if (x > y) x else y }}")

 

{{out}}

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

 

 

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

cat {1..9}: 123456789

</pre>

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

Module CheckIt {

Function Reduce (a, f) {

}

CheckIt

{{out}}

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

{{works with|min|0.19.3}}

{{out}}

<pre>

24

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

=={{header|Nim}}==

 

block:

multiplication = foldr(numbers, a * b)

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

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

{{Works with| oo2c Version 2}}

MODULE Catamorphism;

IMPORT

END

END Catamorphism.

{{out}}

<pre>

-14400

</pre>

=={{header|Objeck}}==

use Collection;

 

return a * b;

}

Output

<pre>

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

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

=={{header|Phix}}==

{{trans|C}}

{{out}}

<pre>

120

</pre>

=={{header|Phixmonti}}==

 

def add + enddef

getid add reduce ?

getid sub reduce ?

=={{header|PicoLisp}}==

(let "A" (car "Lst")

(for "N" (cdr "Lst")

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

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

{{Out}}

<pre>

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

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

L, LV, Concat),

{{out}}

<pre> ?- catamorphism.

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

 

% List to be folded:

%

% a b c d <-- list items/entries/elements/members

%

 

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

 

% Computes "Out" as:

%

foldl(_,[],Acc,Result) :- % case of empty list

Acc=Result. % unification not in head for clarity

 

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

 

% Computes "Out" as:

%

foldr(_,[],Starter,AccUp) :- % empty list: bounce Starter "upwards" into AccUp

AccUp=Starter. % unification not in head for clarity

 

====Unit tests====

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

 

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

 

foldy_expr(Functor,Item,ThreadIn,ThreadOut) :-

ThreadOut =.. [Functor,Item,ThreadIn].

 

:- begin_tests(foldr).

 

 

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

 

=={{header|Python}}==

>>> from operator import add

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

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

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

===Additional example===

 

from functools import reduce

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

 

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

...

 

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

=={{header|Racket}}==

#lang racket

(define (fold f xs init)

 

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

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

say min @list;

say max @list;

{{out}}

<pre>55

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:<min>, @list;

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

 

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

x= x*! / GCD(x, !) /*GCD does the heavy work*/

end /*k*/

{{out|output|:}}

<pre>

 

=={{header|Ring}}==

n = list(10)

for i = 1 to 10

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

 

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

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

println!("Concatenation: {}",

chars.iter().map(|&c| (c as u8 + 1) as char).collect::<String>());

 

{{out}}

Concatenation: bcdef

</pre>

=={{header|Scala}}==

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

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

println(s"Minimum : ${a.min}")

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

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

 

(display (reduce + 0 '(1 2 3 4 5))) (newline) ; => 15

===Using SRFI 1===

There is also an implementation of fold and fold-right in SRFI-1, for lists.

21

</pre>

=={{header|Sidef}}==

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

 

print(nums.reduce(0, +))

print(nums.reduce(1, *))

 

{{out}}

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

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

' -> !OUT::write

{{out}}

<pre>

 

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

templates fold&{op:}

@: $(1);

[1..5] -> fold&{op:mul} -> '$;

' -> !OUT::write

{{out}}

<pre>

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 {

}

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

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

Debug.Print WorksheetFunction.Sum(s)

Debug.Print WorksheetFunction.Product(s)

 

=={{header|WDTE}}==

Translated from the JavaScript ES6 example with a few modifications.

 

let s => import 'stream';

let str => import 'strings';

 

# And here's a concatenation:

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

System.print("Sum is %(sum)")

System.print("Product is %(prod)")

 

{{out}}

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

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

{{trans|BBC_BASIC}}

20 FOR i=1 TO 5

30 READ a(i)

1030 LET tmp=VAL ("tmp"+o$+"a(i)")

1040 NEXT i