Variadic fixed-point combinator: Difference between revisions
m (Python example) |
(Added FreeBASIC) |
||
Line 60: | Line 60: | ||
:test (odd? (+5)) ([[1]]) |
:test (odd? (+5)) ([[1]]) |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
=={{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}}== |
=={{header|Haskell}}== |
Revision as of 19:18, 13 March 2024
You are encouraged to solve this task according to the task description, using any language you may know.
A fixed-point combinator is a higher order function that returns the fixed point of its argument function. If the function has one or more fixed points, then .
You can extend a fixed-point combinator to find the fixed point of the i-th function out of n given functions:
- Task
Your task is to implement a variadic fixed-point combinator that finds and returns the fixed points of all given functions:
The variadic input and output may be implemented using any feature of the language (e.g. using lists).
If possible, try not to use explicit recursion and implement the variadic fixed-point combinator using a fixed-point combinator like the Y combinator.
Also try to come up with examples where could actually be somewhat useful.
- Related tasks
- See also
Binary Lambda Calculus
As shown in https://github.com/tromp/AIT/blob/master/rosetta/variadicY.lam, a variadic Y combinator can take the list-based form
Ygen = \fs. map (\fi.fi (Ygen fs)) fs
which translates to a 276 bit BLC program to determine the parity of the input length:
000100010110010101010001101000000101000100011010000001011000000000010110011111111011110010111111101111110111010000110010111101110110100101100000010110000000010101111110000010000011011000001100101100000010110000000010111111000001101101000001000001101100000100000000101101110110
$ echo -n "hello" | ./blc run rosetta/variadicY.lam
1
Bruijn
Derived from the linked Goldberg paper, as explained in Variadic Fixed-Point Combinators.
:import std/Number .
:import std/List .
y* [[[0 1] <$> 0] ([[1 <! ([[1 2 0]] <$> 0)]] <$> 0)]
# --- example usage ---
# mutual recurrence relation of odd?/even?
# equiv of "even? x = if x == 0 then true else odd? (x-1)"
g [[[=?0 [[1]] (1 --0)]]]
# equiv of "odd? x = if x == 0 then false else even? (x-1)"
h [[[=?0 [[0]] (2 --0)]]]
even? ^(y* (g : {}h))
odd? _(y* (g : {}h))
:test (even? (+5)) ([[0]])
:test (odd? (+5)) ([[1]])
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.
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
- Output:
Similar to Julia/Python/Wren entry.
Haskell
A fix2
implementation in Haskell (as originally by Anders Kaseorg) is equivalent to fix*
:
vfix lst = map ($vfix lst) lst
-- example usage: mutual recurrence relation of mod3
h1 [h1, h2, h3] n = if n == 0 then 0 else h2 (n - 1)
h2 [h1, h2, h3] n = if n == 0 then 1 else h3 (n - 1)
h3 [h1, h2, h3] n = if n == 0 then 2 else h1 (n - 1)
mod3 = head $ vfix [h1, h2, h3]
main = print $ mod3 <$> [0 .. 10]
- Output:
[0,1,2,0,1,2,0,1,2,0,1]
Julia
let
Y = (a) -> [((x) -> () -> x(Y(a)))(f) for f in a]
even_odd_fix = [
(f) -> (n) -> n == 0 || f[begin+1]()(n - 1),
(f) -> (n) -> n != 0 && f[begin]()(n - 1),
]
collatz_fix = [
(f) -> (n, d) -> n == 1 ? d : f[isodd(n)+2]()(n, d + 1),
(f) -> (n, d) -> f[begin]()(n ÷ 2, d),
(f) -> (n, d) -> f[begin]()(3 * n + 1, d),
]
evenodd = [f() for f in Y(even_odd_fix)]
collatz = Y(collatz_fix)[begin]()
for i = 1:10
e = evenodd[begin](i)
o = evenodd[begin+1](i)
c = collatz(i, 0)
println(lpad(i, 2), ": Even: $e Odd: $o Collatz: $c")
end
end
- Output:
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
Phix
Translation of Wren/Julia/JavaScript/Python... The file closures.e was added for 1.0.5, which has not yet shipped, and has the somewhat non-standard requirement of needing any captures explicitly stated [and returned if updated], and invokable only via the [new] call_lambda() function, rather than directly or the usual call_func() or the implicit invocation of that. Not yet properly documented, or for that matter fully tested...
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
- Output:
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
Python
A re-translation of the Wren version.
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}')
Wren
This is a translation of the Python code here.
import "./fmt" for Fmt
var Y = Fn.new { |a|
var ly = []
for (x in a) {
ly.add(Fn.new { |x| Fn.new { x.call(Y.call(a)) } }.call(x))
}
return ly
}
var evenOddFix = [
Fn.new { |f| Fn.new { |n|
if (n == 0) return true
return f[1].call().call(n-1)
}},
Fn.new { |f| Fn.new { |n|
if (n == 0) return false
return f[0].call().call(n-1)
}}
]
var collatzFix = [
Fn.new { |f| Fn.new { |n, d|
if (n == 1) return d
return f[n%2 + 1].call().call(n, d+1)
} },
Fn.new { |f| Fn.new { |n, d| f[0].call().call((n/2).floor, d) } },
Fn.new { |f| Fn.new { |n, d| f[0].call().call(3*n+1, d) } }
]
var evenOdd = Y.call(evenOddFix).map { |f| f.call() }.toList
var collatz = Y.call(collatzFix)[0].call()
for (x in 1..10) {
var e = evenOdd[0].call(x)
var o = evenOdd[1].call(x)
var c = collatz.call(x, 0)
Fmt.print("$2d: Even: $5s Odd: $5s Collatz: $n", x, e, o, c)
}
- Output:
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