Catamorphism: Difference between revisions
m
→{{header|Binary Lambda Calculus}}
(Added Chipmunk Basic) |
|||
| (6 intermediate revisions by 4 users not shown) | |||
Line 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 2,508 ⟶ 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,565 ⟶ 2,587:
LCM: 2520
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
Line 2,605 ⟶ 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,624 ⟶ 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,973 ⟶ 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}}==
| |||