Write a variadic fixed point combinator

Question

A fixed-point combinator is a higher order function \$\mathrm{fix}\$ that returns the fixed point of its argument function. If the function \$f\$ has one or more fixed points, then $$\mathrm{fix} f=f(\mathrm{fix} f).$$ The combinator \$Y\$ has such properties. Encoded in lambda calculus: $$Y=\lambda f.(\lambda x.f(x x))\ (\lambda x.f (x x))$$ You can extend a fixed-point combinator to find the fixed point of the \$i\$-th function out of \$n\$ given functions. $$ \mathrm{fix}_{i,n}f_1\dots f_n=f_i(\mathrm{fix}_{1,n}f_1\dots f_n)\dots(\mathrm{fix}_{n,n}f_1\dots f_n) $$ As an extension to the \$Y\$ combinator:

\begin{alignat*}{2} Y_{i,n}=\lambda f_1\dots f_n.&((\lambda x_1\dots x_n.f_i&&(x_1x_1\dots x_n)\\ & && \dots\\ & && (x_nx_1...x_n)))\\ &((\lambda x_1\dots x_n.f_1&&(x_1x_1\dots x_n)\\ & && \dots\\ & && (x_nx_1...x_n)))\\ &\dots\\ &((\lambda x_1\dots x_n.f_n&&(x_1x_1\dots x_n)\\ & && \dots\\ & && (x_nx_1...x_n))) \end{alignat*}

Example: \begin{alignat*}{3} Y_{1,1}&=Y && &&&\\ Y_{1,2}&=\lambda f_1f_2.&&((\lambda x_1x_2.f_1&&&(x_1x_1x_2)\\ & && &&& (x_2x_1x_2))\\ & &&((\lambda x_1x_2.f_1&&&(x_1x_1x_2)\\ & && &&& (x_2x_1x_2))\\ & &&((\lambda x_1x_2.f_2&&&(x_1x_1x_2)\\ & && &&& (x_2x_1x_2)) \end{alignat*}

Your task is to write a variadic fixed-point combinator \$\mathrm{fix}^*\$ that finds and returns the fixed-points of all given functions. $$ \mathrm{fix}^*f_1\dots f_n=\langle\mathrm{fix}_{1,n}f_1\dots f_n,\dots,\mathrm{fix}_{n,n}f_1\dots f_n\rangle $$ While the details are up to you, I suggest your program accepts a list of functions and returns a list of their fixed points.

For example, take the following pseudo-Haskell functions your program should be able to solve (basically \$\mathrm{fix}_{i,2}\$):

-- even/odd using fix* with lambdas as function arguments
f = (\f g n -> if n == 0 then True else (g (n - 1)))
g = (\f g n -> if n == 0 then False else (f (n - 1)))
isEven = head $ fix* [f,g]
isOdd = tail $ fix* [f,g]  

-- mod3 using fix* with lists as function arguments
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 $ fix* [h1, h2, h3]

Example (ungolfed) implementation:

Bruijn: y* [[[0 1] <$> 0] [[1 <! ([[1 2 0]] <$> 0)]] <$> 0]

Rules:

• Use any language you like, as long as fix* can accept functions and return their fixed points in your preferred format
• code-golf, the shortest implementation in bytes wins
• You can assume a fixed point exists for every given function, you do not need to solve the halting problem
• Bonus: Subtract 10 from your byte count if your solution does not use recursion (i.e. does not use the feature of your language that's typically responsible for recursion; fixed-point combinators are allowed)
• Have fun!

Related questions:

• fix combinator
• fix2 combinator

Answer 1

R, 24 bytes

y=\(a)Map(\(x)x(y(a)),a)

Attempt this Online!

A recursive function that takes a list of functions and returns a list of functions. The input list of functions should be a list of mutually recursive functions. Each function within this list should take a list of functions as an argument, and return a function that makes use of one or more members of the function list.

Inspiration taken from the Haskell answer in Bubbler’s comment, as well as @KevinCruijssen’s Java answer.

Examples shown in the ATO link above and below are even/odd, mod 3 and Collatz problem.

even_odd_fix = list(
 is_even=\(func)\(n)!n||func$is_odd(n-1),
 is_odd=\(func)\(n)!!n&&func$is_even(n-1)
)

mod3_fix = list(
 is_0_mod3 = \(func)\(n)!n||func$is_2_mod3(n-1),
 is_1_mod3 = \(func)\(n)!!n&&func$is_0_mod3(n-1),
 is_2_mod3 = \(func)\(n)!!n&&func$is_1_mod3(n-1)
)

# Somewhat contrived mutually recursive list of functions to determine how many steps of the Collatz procedure to get to 1
coll_fix = list(
 \(func)\(n,d=0)if(n==1)d else func[[2+n%%2]](n,d+1),
 \(func)\(n,d)func[[1]](n/2,d),
 \(func)\(n,d)func[[1]](3*n+1,d)
)

even_odd = y(even_odd_fix)
mod3 = y(mod3_fix)
collatz_depth = y(coll_fix)[[1]]

Answer 2

Java 8, 170 bytes

interface C{Object t(Object o);}interface F{C f();}interface P{C c(F[]f);static F[]g(P[]a){return java.util.Arrays.stream(a).map(p->(F)()->p.c(g(a))).toArray(F[]::new);}}

Based on @user's Java answer for the related Implement Fix2 combinator challenge, as well as my Java answer for the related Golfed fixed point combinator challenge.

Explanation:

interface C{           // Completed Function interface
  Object t(Object o);} //  Using a function that transforms a given Object

interface F{           // Function interface
  C f();}              //  A wrapper to pass the 'Completed Function' as function

interface P{           // Program interface
  C c(F[]f);           //  Which takes an array of 'Function's as argument,
                       //  and returns a 'Completed Function'
  
  static F[]g(P[]a){   //  Recursive function that accepts an array of 'Program's as argument,
                       //  and returns an array of 'Function's
    return java.util.Arrays.stream(a)
                       //   Convert the given 'Program's-array to a generic Stream
      .map(p->         //   Map each 'Program' in this Stream to:
             (F)       //    A casted 'Function' (necessary since it's a generic instead of typed Stream)
             ()->      //    which wraps:
               p.c(    //     A completed call to its own 'Program' interface
                 g(    //      Using a recursive call to its own function
                   a)) //      with the given 'Program's-array as argument
      .toArray(F[]::new);}}
                       //   After the map: convert the Stream to a 'Function's-array

The method to call is P::g, which takes an array of P as argument and returns an array of F. To obtain a completed function C from an F, we can call F::f on it. P represents the function to be fixed, and its method c takes F as argument to prevent immediate evaluation, returning a C that represents a complete function to transform a given Object o with C's t(o).

Example even/odd implementation:

P[] evenOddFix = {
  func -> n -> (int)n == 0 ? true : func[1].f().t((int)n-1),
  func -> n -> (int)n == 0 ? false : func[0].f().t((int)n-1)
};
F[] evenOddFunctions = P.g(evenOddFix);
C evenFunc = evenOddFunctions[0].f(),
  oddFunc = evenOddFunctions[1].f();
Object evenResult = evenFunc.t(input),
       oddResult = oddFunc.t(input);

Try it online.

Answer 3

Python 3, 55 51 bytes

y=lambda a:[(lambda x:lambda:x(y(a)))(x)for x in a]

Try it online!

A lambda taking a list of mutually recursive functions and returning a list of functions that return functions. Unlike R, Python doesn’t have lazy evaluation of function arguments so an extra step is needed to delay function evaluation from happening within the call to y itself; I think this is analogous to the Java answer from @KevinCruijsson.

The even odd and Collatz examples here look like this:

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=0:d if n==1  else f[int(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]()

[print(x, "Even:", even_odd[0](x), "Odd:", even_odd[1](x), "Collatz:", collatz(x)) for x in range(1,11)]

Note that the functions returned must be called without an argument to return the actual useful function.

Answer 4

JavaScript (ES6), 25 bytes

g=a=>a.map(p=>_=>p(g(a)))

;h=g([a=>n=>!n||a[1]()(n-1),a=>n=>!!n&&a[0]()(n-1)]);for(i=0;i<6;i++)console.log(h.map(f=>f()(i)));

Port of @KevinCruijssen's Java answer.

Answer 5

Scala, 161 bytes

Port of @Kevin Cruijssen'Java answer in Scala.

---

Golfed version. Try it online!

trait C{def t(o:Any):Any}
trait F{def f():C}
trait P{def c(func:Array[F]):C}
object P{def g(a:Array[P]):Array[F]={a.map(p=>new F{override def f():C=p.c(g(a))})}}

Ungolfed version. Try it online!

trait C {
  def t(o: Any): Any
}

trait F {
  def f(): C
}

trait P {
  def c(func: Array[F]): C
}

object P {
  def g(a: Array[P]): Array[F] = {
    a.map(p => new F { override def f(): C = p.c(g(a)) })
  }
}

object Main extends App {
  val evenOddFix: Array[P] = Array(
    new P { override def c(func: Array[F]) = new C { override def t(n: Any) = if (n.asInstanceOf[Int] == 0) true else func(1).f().t(n.asInstanceOf[Int]-1) } },
    new P { override def c(func: Array[F]) = new C { override def t(n: Any) = if (n.asInstanceOf[Int] == 0) false else func(0).f().t(n.asInstanceOf[Int]-1) } }
  )

  val evenOddFunctions: Array[F] = P.g(evenOddFix)
  val evenFunc = evenOddFunctions(0).f()
  val oddFunc = evenOddFunctions(1).f()

  for(input <- 0 to 5){
    val evenResult = evenFunc.t(input)
    val oddResult = oddFunc.t(input)
    println(s"Input: $input → Even: $evenResult; Odd: $oddResult")
  }
}