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]])

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, 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  ## 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