9
\$\begingroup\$

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:

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'd like to see mutual recurrence relations with three or more functions, such that the usage of fix* could actually make sense! \$\endgroup\$ Commented Oct 18, 2023 at 15:37
  • 4
    \$\begingroup\$ Just to note, Anders's 14-byte Haskell answer on the fix2 challenge works here as well. Try it online! \$\endgroup\$
    – Bubbler
    Commented Oct 19, 2023 at 5:52
  • \$\begingroup\$ @Bubbler wow, you're right! That's some weird dark magic.. \$\endgroup\$ Commented Oct 19, 2023 at 9:37

5 Answers 5

5
\$\begingroup\$

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]]
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Great answer, I hoped I'd get some answers for not (purely) functional languages :) I suppose you should use Object as input and output, for the sake of universality \$\endgroup\$ Commented Oct 18, 2023 at 15:29
  • 1
    \$\begingroup\$ @LegendaryWizard I've changed the input-type to an Object as well and removed the int-fluff. \$\endgroup\$ Commented Oct 18, 2023 at 15:42
  • \$\begingroup\$ 170... if I've understood correctly, this is 26 bytes in ES6... \$\endgroup\$
    – Neil
    Commented Oct 18, 2023 at 16:50
  • 1
    \$\begingroup\$ @Neil Ikr.. And it's probably <20 bytes in Haskell I'd assume. Insert_Java_is_verbose_meme_here. 🤷 \$\endgroup\$ Commented Oct 18, 2023 at 17:04
  • \$\begingroup\$ (25... I accidentally counted a semicolon...) \$\endgroup\$
    – Neil
    Commented Oct 19, 2023 at 23:46
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Just posted an identical JavaScript answer before realising you’d got there 5 minutes earlier! \$\endgroup\$ Commented Oct 19, 2023 at 23:52
  • 1
    \$\begingroup\$ Actually if you read my comment on @KevinCruijssen's answer you'll see exactly how much earlier I'd actually got there, I'd just not got around to posting it. \$\endgroup\$
    – Neil
    Commented Oct 19, 2023 at 23:57
1
\$\begingroup\$

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")
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.