Variadic fixed-point combinator: Difference between revisions
m (→{{header|Phix}}: f3->f*6) |
m (Python example) |
||
| Line 183: | Line 183: | ||
10: even:true, odd:false, collatz:6 |
10: even:true, odd:false, collatz:6 |
||
</pre> |
</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}}== |
=={{header|Wren}}== |
||
Revision as of 01:30, 11 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]])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