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 ${\displaystyle \operatorname {fix} }$ that returns the fixed point of its argument function. If the function ${\displaystyle f}$ has one or more fixed points, then ${\displaystyle \operatorname {fix} f=f(\operatorname {fix} f)}$.

You can extend a fixed-point combinator to find the fixed point of the i-th function out of n given functions: ${\displaystyle \operatorname {fix} _{i,n}f_{1}\dots f_{n}=f_{i}(\operatorname {fix} _{1,n}f_{1}\dots f_{n})\dots (\operatorname {fix} _{n,n}f_{1}\dots f_{n})}$

Your task is to implement a variadic fixed-point combinator ${\displaystyle \operatorname {fix} ^{*}}$ that finds and returns the fixed points of all given functions: ${\displaystyle \operatorname {fix} ^{*}f_{1}\dots f_{n}=\langle \operatorname {fix} _{1,n}f_{1}\dots f_{n},\dots ,\operatorname {fix} _{n,n}f_{1}\dots f_{n}\rangle }$

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 ${\displaystyle \operatorname {fix} ^{*}}$ could actually be somewhat useful.

## 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/Combinator . :import std/Number . :import std/List . # --------------- # explicit Church # --------------- # passes all functions explicitly explicit-y* [[[0 1] <$> 0] ([[1 <! ([[1 2 0]] <$> 0)]] <$> 0)]

# even x = if x == 0 then true else odd? (x-1)
g [[[=?0 [[1]] (1 --0)]]]

# odd x = if x == 0 then false else even? (x-1)
h [[[=?0 [[0]] (2 --0)]]]

# merged even/odd
rec explicit-y* (g : {}h)

:test (^rec (+5)) ([[0]])
:test (_rec (+5)) ([[1]])

# n % 3
mod3 ^(explicit-y* (zero : (one : {}two)))
zero [[[[=?0 (+0) (2 --0)]]]]
one [[[[=?0 (+1) (1 --0)]]]]
two [[[[=?0 (+2) (3 --0)]]]]

:test ((mod3 (+5)) =? (+2)) ([[1]])

# ----------------
# explicit tupling
# ----------------

# passes all functions explicitly
# requires a tuple mapping function first
tupled-y* [y [[2 (1 0) 0]]]

# merged even odd
rec tupled-y* map [0 g h]
map [&[[[0 (3 2) (3 1)]]]]

# [[1]] / [[0]] are tuple selectors:

:test (rec [[1]] (+5)) ([[0]])
:test (rec [[0]] (+5)) ([[1]])

# n % 3, [[[2]]] selects first tuple element
mod3 tupled-y* map [0 zero one two] [[[2]]]
map [&[[[[0 (4 3) (4 2) (4 1)]]]]]
zero [[[[=?0 (+0) (2 --0)]]]]
one [[[[=?0 (+1) (1 --0)]]]]
two [[[[=?0 (+2) (3 --0)]]]]

:test ((mod3 (+5)) =? (+2)) ([[1]])

# ---------------
# implicit Church
# ---------------

# passes all functions in a single list
implicit-y* y [[&(1 0) <$> 0]] # even x = if x == 0 then true else odd? (x-1) g [[=?0 [[1]] (_1 --0)]] # odd x = if x == 0 then false else even? (x-1) h [[=?0 [[0]] (^1 --0)]] # merged even/odd rec implicit-y* (g : {}h) :test (^rec (+5)) ([[0]]) :test (_rec (+5)) ([[1]]) # n % 3 mod3 ^(implicit-y* (zero : (one : {}two))) zero [[=?0 (+0) (_1 --0)]] one [[=?0 (+1) (^(~1) --0)]] two [[=?0 (+2) (^1 --0)]] :test ((mod3 (+5)) =? (+2)) ([[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] ## 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)); } } }  Output: 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  ## Julia Translation of: Wren 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, 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}')


## Raku

Translation of: Julia
Translation of: Python
# 20240726 Raku programming solution

my &Y = -> \a { a.map: -> \f { -> &x { -> { x(Y(a)) } }(f) } }

my \even_odd_fix = -> \f { -> \n { n == 0  or f[1]()(n - 1) } },
-> \f { -> \n { n != 0 and f[0]()(n - 1) } };

my \collatz_fix = -> \f { -> \n, \d { n == 1 ?? d !! f[(n % 2)+1]()(n, d+1) } },
-> \f { -> \n, \d { f[0]()( n div 2, d ) } },
-> \f { -> \n, \d { f[0]()(   3*n+1, d ) } };

my \even_odd = Y(even_odd_fix).map: -> &f { f() }; # or { $_() } my &collatz = Y(collatz_fix)[0](); for 1..10 -> \i { my ( \e, \o, \c ) = even_odd[0](i), even_odd[1](i), collatz(i, 0); printf "%2d: Even: %s Odd: %s Collatz: %s\n", i, e, o, c }  You may Attempt This Online! ## Wren Library: Wren-fmt 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