Variadic fixed-point combinator: Difference between revisions
Have removed my own post as I misunderstood the task.
(julia example) |
(Have removed my own post as I misunderstood the task.) Tag: Manual revert |
||
| (16 intermediate revisions by 6 users not shown) | |||
Line 24:
<br><br>
=={{header|
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}}==
Derived from the linked Goldberg paper, as explained in [https://text.marvinborner.de/2023-06-18-15.html Variadic Fixed-Point Combinators].
Line 50 ⟶ 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 75 ⟶ 138:
even_odd_fix = [
(f) -> (n) -> n == 0 || f[begin+1]()(n - 1),
(f)
]
collatz_fix = [
(f) ->
(f)
(f) -> (n, d) -> f[begin]()(3 * n + 1, d),
]
Line 105 ⟶ 158:
end
end
</syntaxhighlight>{{out}}
<pre>
Line 119 ⟶ 171:
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}}==
| |||