Catamorphism: Difference between revisions
m
→{{header|Binary Lambda Calculus}}
(Added uBasic/4tH version) |
|||
| (11 intermediate revisions by 8 users not shown) | |||
Line 420:
end function</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{trans|Run BASIC}}
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="qbasic">100 DIM n(10)
110 FOR i = 1 TO 10 : n(i) = i : NEXT i
120 SUB cat(cnt,op$)
130 temp = n(1)
140 FOR i = 2 TO cnt
150 IF op$ = "+" THEN temp = temp+n(i)
160 IF op$ = "-" THEN temp = temp-n(i)
170 IF op$ = "*" THEN temp = temp*n(i)
180 IF op$ = "/" THEN temp = temp/n(i)
190 IF op$ = "^" THEN temp = temp^n(i)
200 IF op$ = "max" THEN temp = FN MAX(temp,n(i))
210 IF op$ = "min" THEN temp = FN MIN(temp,n(i))
220 IF op$ = "avg" THEN temp = temp+n(i)
230 IF op$ = "cat" THEN temp$ = temp$+STR$(n(i))
240 NEXT i
250 IF op$ = "avg" THEN temp = temp/cnt
260 IF op$ = "cat" THEN temp = VAL(STR$(n(1))+temp$)
270 cat = temp
280 END SUB
290 '
300 PRINT " +: ";cat(10,"+")
310 PRINT " -: ";cat(10,"-")
320 PRINT " *: ";cat(10,"*")
330 PRINT " /: ";cat(10,"/")
340 PRINT " ^: ";cat(10,"^")
350 PRINT "min: ";cat(10,"min")
360 PRINT "max: ";cat(10,"max")
370 PRINT "avg: ";cat(10,"avg")
380 PRINT "cat: ";cat(10,"cat")
390 END</syntaxhighlight>
==={{header|QBasic}}===
Line 458 ⟶ 491:
PRINT "max: "; " "; cat(10, "max")
PRINT "avg: "; " "; cat(10, "avg")</syntaxhighlight>
==={{header|True BASIC}}===
Line 508 ⟶ 540:
END</syntaxhighlight>
==={{header|Yabasic}}===
{{trans|Run BASIC}}
Line 614 ⟶ 613:
<pre>28
5040</pre>
=={{header|Binary Lambda Calculus}}==
A minimal size (right) fold in lambda calculus is <code>fold = \f\z (let go = \l.l(\h\t\z.f h (go t))z in go)</code> which corresponds to the 69-bit BLC program
<pre>000001000110100000010110000000010111111110111001011111101111101101110</pre>
=={{header|BQN}}==
Line 1,663 ⟶ 1,669:
[15, -13, 120]
[15, 3, 120]</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">fun main(args: Array<String>) {
Line 1,683 ⟶ 1,690:
Maximum : 5
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def nums 1 2 3 4 5}
-> nums
{S.reduce {lambda {:a :b} {+ :a :b}} {nums}}
-> 15
{S.reduce {lambda {:a :b} {- :a :b}} {nums}}
-> -13
{S.reduce {lambda {:a :b} {* :a :b}} {nums}}
-> 120
{S.reduce min {nums}}
-> 1
{S.reduce max {nums}}
-> 5
</syntaxhighlight>
=={{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.
Line 1,818 ⟶ 1,842:
Maximum 5
</pre>
=={{header|Maple}}==
The left fold operator in Maple is foldl, and foldr is the right fold operator.
Line 2,490 ⟶ 2,515:
say reduce &infix:<max>, @list;
say reduce &infix:<lcm>, @list;</syntaxhighlight>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, 1 2 3 4 5 6 7: e.List
= <Prout <Reduce Add e.List>>
<Prout <Reduce Mul e.List>>;
};
Reduce {
s.F t.I = t.I;
s.F t.I t.J e.X = <Reduce s.F <Mu s.F t.I t.J> e.X>;
};</syntaxhighlight>
{{out}}
<pre>28
5040</pre>
=={{header|REXX}}==
This REXX example is modeled after the Raku example (it is NOT a translation).
Line 2,547 ⟶ 2,587:
LCM: 2520
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
Line 2,587 ⟶ 2,628:
≪ → array op
≪ array 1 GET 2
'''WHILE''' DUP array SIZE ≤ '''REPEAT'''
array OVER GET ROT SWAP op EVAL
SWAP 1 +
'''END''' DROP
≫ ≫ '<span style="color:blue">REDUCE</span>' STO
[ 1 2 3 4 5 6 7 8 9 10 ] ≪ + ≫ <span style="color:blue">REDUCE</span>
[ 1 2 3 4 5 6 7 8 9 10 ] ≪ - ≫ <span style="color:blue">REDUCE</span>
[ 1 2 3 4 5 6 7 8 9 10 ] ≪ * ≫ <span style="color:blue">REDUCE</span>
[ 1 2 3 4 5 6 7 8 9 10 ] ≪ MAX ≫ <span style="color:blue">REDUCE</span>
[ 1 2 3 4 5 6 7 8 9 10 ] ≪ SQ + ≫ <span style="color:blue">REDUCE</span>
{{out}}
<pre>
Line 2,606 ⟶ 2,647:
1: 385
</pre>
From HP-48G models, a built-in function named <code>STREAM</code> performs exactly the same as the above <code>REDUCE</code> one, but only with lists.
=={{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:
Line 2,815 ⟶ 2,858:
{{trans|FreeBASIC}}
uBasic/4tH has only got one single array so passing its address makes little sense. Instead, its bounds are passed.
<syntaxhighlight lang="uBasic/4tH">For x = 1 To 5 : @(x-1) = x : Next ' initialize array
' try different reductions
Print "Sum is : "; FUNC(_Reduce(_add, 5))
Print "Difference is : "; FUNC(_Reduce(_subtract, 5))
Print "Product is : "; FUNC(_Reduce(_multiply, 5))
Print "Maximum is : "; FUNC(_Reduce(_max, 5))
Print "Minimum is : "; FUNC(_Reduce(_min, 5))
End
' several functions
_add Param (2) : Return (a@ + b@)
_subtract Param (2) : Return (a@ - b@)
_multiply Param (2) : Return (a@ * b@)
_min Param (2) : Return (Min (a@, b@))
_max Param (2) : Return (Max (a@, b@))
_Reduce
Param (2) ' function and array size
Local (2) ' loop index and result
' set result and iterate array
d@ = @(0) : For c@ = 1 To b@-1 : d@ = FUNC(a@ (d@, @(c@))) : Next
Return (d@)</syntaxhighlight>
This version incorporates a "no op" as well.
<syntaxhighlight lang="text">Push 5, 4, 3, 2, 1: s = Used() - 1
For x = 0 To s: @(x) = Pop(): Next
Line 2,852 ⟶ 2,918:
0 OK, 0:378
</pre>
=={{header|VBA}}==
<syntaxhighlight lang="vb">Public Sub reduce()
Line 2,915 ⟶ 2,982:
12345678910</pre>
=={{header|Wren}}==
<syntaxhighlight lang="
var sum = a.reduce { |acc, i| acc + i }
var prod = a.reduce { |acc, i| acc * i }
Line 2,931 ⟶ 2,998:
Sum of squares is 55
</pre>
=={{header|Zig}}==
'''Works with:''' 0.10.x, 0.11.x, 0.12.0-dev.1591+3fc6a2f11
===Reduce a slice===
<syntaxhighlight lang="zig">/// Asserts that `array`.len >= 1.
pub fn reduce(comptime T: type, comptime applyFn: fn (T, T) T, array: []const T) T {
var val: T = array[0];
for (array[1..]) |elem| {
val = applyFn(val, elem);
}
return val;
}</syntaxhighlight>
Usage:
<syntaxhighlight lang="zig">const std = @import("std");
fn add(a: i32, b: i32) i32 {
return a + b;
}
fn mul(a: i32, b: i32) i32 {
return a * b;
}
fn min(a: i32, b: i32) i32 {
return @min(a, b);
}
fn max(a: i32, b: i32) i32 {
return @max(a, b);
}
pub fn main() void {
const arr: [5]i32 = .{ 1, 2, 3, 4, 5 };
std.debug.print("Array: {any}\n", .{arr});
std.debug.print(" * Reduce with add: {d}\n", .{reduce(i32, add, &arr)});
std.debug.print(" * Reduce with mul: {d}\n", .{reduce(i32, mul, &arr)});
std.debug.print(" * Reduce with min: {d}\n", .{reduce(i32, min, &arr)});
std.debug.print(" * Reduce with max: {d}\n", .{reduce(i32, max, &arr)});
}</syntaxhighlight>
{{out}}
<pre>
Array: { 1, 2, 3, 4, 5 }
* Reduce with add: 15
* Reduce with mul: 120
* Reduce with min: 1
* Reduce with max: 5
</pre>
===Reduce a vector===
We use @reduce builtin function here to leverage special instructions if available, but only small set of reduce operators are available.
@Vector and related builtings will use SIMD instructions if possible. If target platform does not support SIMD instructions, vectors operations will be compiled like in previous example (represented as arrays and operating with one element at a time).
<syntaxhighlight lang="zig">const std = @import("std");
pub fn main() void {
const vec: @Vector(5, i32) = .{ 1, 2, 3, 4, 5 };
std.debug.print("Vec: {any}\n", .{vec});
std.debug.print(" * Reduce with add: {d}\n", .{@reduce(.Add, vec)});
std.debug.print(" * Reduce with mul: {d}\n", .{@reduce(.Mul, vec)});
std.debug.print(" * Reduce with min: {d}\n", .{@reduce(.Min, vec)});
std.debug.print(" * Reduce with max: {d}\n", .{@reduce(.Max, vec)});
}</syntaxhighlight>
{{out}}
<pre>
Vec: { 1, 2, 3, 4, 5 }
* Reduce with add: 15
* Reduce with mul: 120
* Reduce with min: 1
* Reduce with max: 5
</pre>
Note that std.builtin.ReduceOp.Add and std.builtin.ReduceOp.Mul operators wrap on overflow and underflow, unlike regular Zig operators, where they are considered illegal behaviour and checked in safe optimize modes. This can be demonstrated by this example (ReleaseSafe optimize mode, zig 0.11.0, Linux 6.5.11 x86_64):
<syntaxhighlight lang="zig">const std = @import("std");
pub fn main() void {
const vec: @Vector(2, i32) = .{ std.math.minInt(i32), std.math.minInt(i32) + 1 };
std.debug.print("Vec: {any}\n", .{vec});
std.debug.print(" * Reduce with .Add: {d}\n", .{@reduce(.Add, vec)});
std.debug.print(" * Reduce with .Mul: {d}\n", .{@reduce(.Mul, vec)});
var zero: usize = 0; // Small trick to make compiler not emit compile error for overflow below:
std.debug.print(" * Reduce with regular add operator: {d}\n", .{vec[zero] + vec[1]});
std.debug.print(" * Reduce with regular mul operator: {d}\n", .{vec[zero] * vec[1]});
}</syntaxhighlight>
{{out}}
<pre>
Vec: { -2147483648, -2147483647 }
* Reduce with .Add: 1
* Reduce with .Mul: -2147483648
thread 5908 panic: integer overflow
/home/bratishkaerik/test/catamorphism.zig:10:79: 0x20c4b0 in main (catamorphism)
std.debug.print(" * Reduce with regular add operator: {d}\n", .{vec[zero] + vec[1]});
^
/usr/lib64/zig/0.11.0/lib/std/start.zig:564:22: 0x20bee4 in posixCallMainAndExit (catamorphism)
root.main();
^
/usr/lib64/zig/0.11.0/lib/std/start.zig:243:5: 0x20bdc1 in _start (catamorphism)
asm volatile (switch (native_arch) {
^
???:?:?: 0x0 in ??? (???)
[1] 5908 IOT instruction ./catamorphism
</pre>
For well-defined overflow/underflow behaviour you can use wrapping and saturating operators (for addition they are +% and +| respectively). With +% and *% (wrapping multiplication) operators, behaviour should be identical to .Add and .Mul reduce operators.
=={{header|zkl}}==
Most sequence objects in zkl have a reduce method.
| |||