Variadic fixed-point combinator: Difference between revisions
(New post.) |
(Have removed my own post as I misunderstood the task.) Tag: Manual revert |
||
(One intermediate revision by the same user not shown) | |||
Line 60: | Line 60: | ||
:test (odd? (+5)) ([[1]]) |
:test (odd? (+5)) ([[1]]) |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
=={{header|C++}}== |
|||
<syntaxhighlight lang="c++"> |
|||
#include <cstdint> |
|||
#include <iostream> |
|||
template <typename T, typename R> |
|||
class fixer { |
|||
public: |
|||
const virtual R fix(const T& x) { |
|||
return f(x); |
|||
} |
|||
virtual ~fixer() = default; |
|||
private: |
|||
virtual R f(T) = 0; |
|||
}; |
|||
uint64_t factorial(uint32_t x) { |
|||
class fact : public fixer<uint32_t, uint64_t> { |
|||
virtual uint64_t f(uint32_t x) { |
|||
return ( x == 0 ) ? 1 : x * fix(x - 1); |
|||
} |
|||
}; |
|||
return fact().fix(x); |
|||
} |
|||
uint32_t fibonacci(uint32_t x) { |
|||
class fib : public fixer<uint32_t, uint32_t> { |
|||
virtual uint32_t f(uint32_t x) { |
|||
return ( x == 0 ) ? 0 : ( x <= 2 ) ? 1 : fix(x - 1 ) + fix(x - 2); |
|||
} |
|||
}; |
|||
return fib().fix(x); |
|||
} |
|||
template <typename T, typename U, typename R> |
|||
class bi_fixer { |
|||
public: |
|||
const virtual R bi_fix(const T& x, const U& y) { |
|||
return g(x, y); |
|||
} |
|||
virtual ~bi_fixer() = default; |
|||
private: |
|||
virtual R g(T, U) = 0; |
|||
}; |
|||
uint32_t collatz(uint32_t n, uint32_t c) { |
|||
class coll : public bi_fixer<uint32_t, uint32_t, uint32_t> { |
|||
virtual uint32_t g(uint32_t n, uint32_t c) { |
|||
return ( n == 1 ) ? c : ( n % 2 == 0 ) ? bi_fix(n / 2, c + 1) : bi_fix(3 * n + 1, c + 1); |
|||
} |
|||
}; |
|||
return coll().bi_fix(n, c); |
|||
} |
|||
uint64_t ackermann(uint32_t m, uint32_t n) { |
|||
class acker : public bi_fixer<uint32_t, uint32_t, uint64_t> { |
|||
virtual uint64_t g(uint32_t m, uint32_t n) { |
|||
return ( m == 0 ) ? n + 1 : ( n == 0 ) ? g(m - 1, 1) : g(m - 1, g(m, n - 1)); |
|||
} |
|||
}; |
|||
return acker().bi_fix(m, n); |
|||
} |
|||
int main() { |
|||
for ( int i = 1; i <= 10; ++i ) { |
|||
std::cout << "factorial(" << i << ") = " << factorial(i) << std::endl; |
|||
std::cout << "fibonacci(" << i << ") = " << fibonacci(i) << std::endl; |
|||
std::cout << "collatz(" << i << ") = " << collatz(i, 0) << std::endl; |
|||
std::cout << "ackermann(3, " << i << ") = " << ackermann(3, i) << std::endl; |
|||
std::cout << std::endl; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
factorial(1) = 1 |
|||
fibonacci(1) = 1 |
|||
collatz(1) = 0 |
|||
ackermann(3, 1) = 13 |
|||
factorial(2) = 2 |
|||
fibonacci(2) = 1 |
|||
collatz(2) = 1 |
|||
ackermann(3, 2) = 29 |
|||
factorial(3) = 6 |
|||
fibonacci(3) = 2 |
|||
collatz(3) = 7 |
|||
ackermann(3, 3) = 61 |
|||
factorial(4) = 24 |
|||
fibonacci(4) = 3 |
|||
collatz(4) = 2 |
|||
ackermann(3, 4) = 125 |
|||
factorial(5) = 120 |
|||
fibonacci(5) = 5 |
|||
collatz(5) = 5 |
|||
ackermann(3, 5) = 253 |
|||
factorial(6) = 720 |
|||
fibonacci(6) = 8 |
|||
collatz(6) = 8 |
|||
ackermann(3, 6) = 509 |
|||
factorial(7) = 5040 |
|||
fibonacci(7) = 13 |
|||
collatz(7) = 16 |
|||
ackermann(3, 7) = 1021 |
|||
factorial(8) = 40320 |
|||
fibonacci(8) = 21 |
|||
collatz(8) = 3 |
|||
ackermann(3, 8) = 2045 |
|||
factorial(9) = 362880 |
|||
fibonacci(9) = 34 |
|||
collatz(9) = 19 |
|||
ackermann(3, 9) = 4093 |
|||
factorial(10) = 3628800 |
|||
fibonacci(10) = 55 |
|||
collatz(10) = 6 |
|||
ackermann(3, 10) = 8189 |
|||
</pre> |
|||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |
||
Line 270: | Line 131: | ||
{{out}} |
{{out}} |
||
<code>[0,1,2,0,1,2,0,1,2,0,1]</code> |
<code>[0,1,2,0,1,2,0,1,2,0,1]</code> |
||
=={{header|Java}}== |
|||
Note that the yCombinator is defined strictly correctly, that is, its variable name does not appear inside the definition. |
|||
<syntaxhighlight lang="java"> |
|||
import java.util.function.BiFunction; |
|||
import java.util.function.Function; |
|||
public final class VariadicFixedPointCombinator { |
|||
public static void main(String[] args) { |
|||
Function<Integer, Integer> fibonacci = yCombinator( |
|||
function -> n -> ( n <= 2 ) ? 1 : function.apply(n - 1) + function.apply(n - 2)); |
|||
Function<Integer, Integer> factorial = yCombinator( |
|||
function -> n -> ( n <= 1 ) ? 1 : n * function.apply(n - 1)); |
|||
BiFunction<Integer, Integer, Integer> collatz = uncurry(yCombinator( |
|||
function -> n -> c -> ( n == 1 ) ? |
|||
c : ( n % 2 == 0 ) ? |
|||
function.apply(n / 2).apply(c + 1) : function.apply(3 * n + 1).apply(c + 1) |
|||
)); |
|||
BiFunction<Integer, Integer, Integer> ackermann = uncurry(yCombinator( |
|||
function -> m -> n -> ( m == 0 ) ? |
|||
n + 1 : ( n == 0 ) ? |
|||
function.apply(m - 1).apply(1) : function.apply(m - 1).apply(function.apply(m).apply(n - 1)) |
|||
)); |
|||
for ( int value = 1; value < 5; value++ ) { |
|||
System.out.println("fibonacci(" + value + ") = " + fibonacci.apply(value)); |
|||
System.out.println("factorial(" + value + ") = " + factorial.apply(value)); |
|||
System.out.println("collatz(" + value + ") = " + collatz.apply(value, 0)); |
|||
System.out.println("ackermann(3, " + value + ") = " + ackermann.apply(3, value)); |
|||
System.out.println(); |
|||
} |
|||
} |
|||
private static interface MetaFunction<T> extends Function<MetaFunction<T>, T> { } |
|||
private static <T, R> Function<T, R> yCombinator(Function<Function<T, R>, Function<T, R>> function) { |
|||
MetaFunction<Function<T, R>> metaFunction = w -> function.apply( x -> w.apply(w).apply(x) ); |
|||
return metaFunction.apply(metaFunction); |
|||
} |
|||
private static <T, U, R> BiFunction<T, U, R> uncurry(Function<T, Function<U, R>> function) { |
|||
return (x, y) -> function.apply(x).apply(y); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
fibonacci(1) = 1 |
|||
factorial(1) = 1 |
|||
collatz(1) = 0 |
|||
ackermann(3, 1) = 13 |
|||
fibonacci(2) = 1 |
|||
factorial(2) = 2 |
|||
collatz(2) = 1 |
|||
ackermann(3, 2) = 29 |
|||
fibonacci(3) = 2 |
|||
factorial(3) = 6 |
|||
collatz(3) = 7 |
|||
ackermann(3, 3) = 61 |
|||
fibonacci(4) = 3 |
|||
factorial(4) = 24 |
|||
collatz(4) = 2 |
|||
ackermann(3, 4) = 125 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
Revision as of 15:21, 18 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]])
F#
The following uses Y_combinator#March_2024
// 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 ""
- Output:
0 1 2 0 1 2 0 1 2 0 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 [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().
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.
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