Variadic fixed-point combinator: Difference between revisions
Content deleted Content added
m Improved coding. |
|||
| (15 intermediate revisions by 6 users not shown) | |||
Line 27:
As shown in https://github.com/tromp/AIT/blob/master/rosetta/variadicY.lam, a variadic Y combinator can take the list-based form
<pre>Ygen = \fs. map (\fi.fi (Ygen fs)) fs</pre>
which translates to a 276 bit BLC program to determine the parity of the input length:
<pre>000100010110010101010001101000000101000100011010000001011000000000010110011111111011110010111111101111110111010000110010111101110110100101100000010110000000010101111110000010000011011000001100101100000010110000000010111111000001101101000001000001101100000100000000101101110110</pre>
<syntaxhighlight lang="bash">$ echo -n "hello" | ./blc run rosetta/variadicY.lam
1
</syntaxhighlight>
=={{header|Bruijn}}==
Line 59 ⟶ 60:
:test (odd? (+5)) ([[1]])
</syntaxhighlight>
=={{header|F Sharp|F#}}==
The following uses [[Y_combinator#March_2024]]
<syntaxhighlight lang="fsharp">
// Variadic fixed-point combinator. Nigel Galloway: March 15th., 2024
let h2 n = function 0->2 |g-> n (g-1)
let h1 n = function 0->1 |g->h2 n (g-1)
let h0 n = function 0->0 |g->h1 n (g-1)
let mod3 n=Y h0 n
[0..10] |> List.iter(mod3>>printf "%d "); printfn ""
</syntaxhighlight>
{{output}}
<pre>
0 1 2 0 1 2 0 1 2 0 1
</pre>
=={{header|FreeBASIC}}==
Unfortunately, due to the limitations of the FreeBASIC language, implementing a variadic fixed-point combinator without explicit recursion is extremely difficult, if not impossible. FreeBASIC does not support higher-order functions in a way that allows this type of metaprogramming.
An alternative would be to implement recursion explicitly, although this does not satisfy your original requirement of avoiding explicit recursion.
<syntaxhighlight lang="vbnet">Declare Function Even(n As Integer) As Integer
Declare Function Odd(n As Integer) As Integer
Function Even(n As Integer) As Integer
If n = 0 Then Return 1
Return Odd(n - 1)
End Function
Function Odd(n As Integer) As Integer
If n = 0 Then Return 0
Return Even(n - 1)
End Function
Function Collatz(n As Integer) As Integer
Dim As Integer d = 0
While n <> 1
n = Iif(n Mod 2 = 0, n \ 2, 3 * n + 1)
d += 1
Wend
Return d
End Function
Dim As String e, o
Dim As Integer i, c
For i = 1 To 10
e = Iif(Even(i), "True ", "False")
o = Iif(Odd(i), "True ", "False")
c = Collatz(i)
Print Using "##: Even: & Odd: & Collatz: &"; i; e; o; c
Next i
Sleep</syntaxhighlight>
{{out}}
<pre>Similar to Julia/Python/Wren entry.</pre>
=={{header|Haskell}}==
Line 77 ⟶ 131:
{{out}}
<code>[0,1,2,0,1,2,0,1,2,0,1]</code>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.List;
public final class VariadicFixedPointCombinator {
public interface CompletedFunction {
boolean f(int x);
}
public interface FunctionFixed {
CompletedFunction g();
}
public interface FunctionToBeFixed {
CompletedFunction h(List<FunctionFixed> functionFixed);
static List<FunctionFixed> k(List<FunctionToBeFixed> functionToBeFixed) {
return List.of( () -> functionToBeFixed.get(0).h(k(functionToBeFixed)),
() -> functionToBeFixed.get(1).h(k(functionToBeFixed)) );
}
}
public static void main(String[] args) {
List<FunctionToBeFixed> evenOddFix = List.of(
functions -> n -> n == 0 ? true : functions.get(1).g().f(n - 1),
functions -> n -> n == 0 ? false : functions.get(0).g().f(n - 1)
);
List<FunctionFixed> evenOdd = FunctionToBeFixed.k(evenOddFix);
CompletedFunction even = evenOdd.get(0).g();
CompletedFunction odd = evenOdd.get(1).g();
for ( int i = 0; i <= 9; i++ ) {
System.out.println(i + ": Even: " + even.f(i) + ", Odd: " + odd.f(i));
}
}
}
</syntaxhighlight>
{{ out }}
<pre>
0: Even: true, Odd: false
1: Even: false, Odd: true
2: Even: true, Odd: false
3: Even: false, Odd: true
4: Even: true, Odd: false
5: Even: false, Odd: true
6: Even: true, Odd: false
7: Even: false, Odd: true
8: Even: true, Odd: false
9: Even: false, Odd: true
</pre>
=={{header|Julia}}==
Line 117 ⟶ 225:
10: Even: true Odd: false Collatz: 6
</pre>
=={{header|Phix}}==
Translation of Wren/Julia/JavaScript/Python... The file closures.e was added for 1.0.5 [not yet shipped], with the somewhat non-standard requirement of needing captures explicitly stated [and returned if updated], and invokable only via call_lambda(), not direct or [implicit] call_func().<br>
Disclaimer: Don't ask me if this is a proper Y combinator, all I know for sure is it converts a set of functions into a set of closures, without recursion.
<syntaxhighlight lang="phix">
include builtins/closures.e -- auto-include in 1.0.5+ (needs to be manually installed and included prior to that)
function Y(sequence a)
for i,ai in a do
-- a[i] = define_lambda(ai,{a})
a[i] = define_lambda(ai,{0})
end for
-- using {a} above would stash partially-updated copies,
-- so instead use a dummy {0} and blat all at the end
set_captures(a, {a})
return a
end function
function e(sequence f, integer n)
return n==0 or call_lambda(f[2],n-1)
end function
function o(sequence f, integer n)
return n!=0 and call_lambda(f[1],n-1)
end function
function c1(sequence f, integer n, d)
if n=1 then return d end if
return call_lambda(f[2+odd(n)],{n,d+1})
end function
function c2(sequence f, integer n, d)
return call_lambda(f[1],{floor(n/2),d})
end function
function c3(sequence f, integer n, d)
return call_lambda(f[1],{3*n+1,d})
end function
sequence f2 = Y({e,o}),
f3 = Y({c1,c2,c3})
object even_func = f2[1],
odd_func = f2[2],
collatz = f3[1]
for x=1 to 10 do
bool bE = call_lambda(even_func,x),
bO = call_lambda(odd_func,x)
integer c = call_lambda(collatz,{x,0})
printf(1,"%2d: even:%t, odd:%t, collatz:%d\n",{x,bE,bO,c})
end for
</syntaxhighlight>
{{out}}
<pre>
1: even:false, odd:true, collatz:0
2: even:true, odd:false, collatz:1
3: even:false, odd:true, collatz:7
4: even:true, odd:false, collatz:2
5: even:false, odd:true, collatz:5
6: even:true, odd:false, collatz:8
7: even:false, odd:true, collatz:16
8: even:true, odd:false, collatz:3
9: even:false, odd:true, collatz:19
10: even:true, odd:false, collatz:6
</pre>
=={{header|Python}}==
A re-translation of the Wren version.
<syntaxhighlight lang="python">Y = lambda a: [(lambda x: lambda: x(Y(a)))(f) for f in a]
even_odd_fix = [
lambda f: lambda n: n == 0 or f[1]()(n - 1),
lambda f: lambda n: n != 0 and f[0]()(n - 1),
]
collatz_fix = [
lambda f: lambda n, d: d if n == 1 else f[(n % 2)+1]()(n, d+1),
lambda f: lambda n, d: f[0]()(n//2, d),
lambda f: lambda n, d: f[0]()(3*n+1, d),
]
even_odd = [f() for f in Y(even_odd_fix)]
collatz = Y(collatz_fix)[0]()
for i in range(1, 11):
e = even_odd[0](i)
o = even_odd[1](i)
c = collatz(i, 0)
print(f'{i :2d}: Even: {e} Odd: {o} Collatz: {c}')
</syntaxhighlight>
=={{header|Wren}}==
| |||