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/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.

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

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 [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 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