9
\$\begingroup\$

Background

The fixed-point combinator \$\textsf{fix}\$ is a higher-order function that computes the fixed point of the given function.

$$\textsf{fix}\ f = f\ (\textsf{fix}\ f)$$

In terms of programming, it is used to implement recursion in lambda calculus, where the function body does not normally have access to its own name. A common example is recursive factorial (written in Haskell-like syntax). Observe how the use of fix "unknots" the recursive call of fac.

fix f = f (fix f)
fac = fix facFix where
  facFix fac' n =
    if n == 0
    then 1
    else fac' (n - 1) * n
-- which is equivalent to the following recursive function:
fac n =
  if n == 0
  then 1
  else fac (n - 1) * n

Now, have you ever thought about how you would do the same for mutually recursive functions? This article describes the fully general \$\textsf{Y}^*\$ combinator, which takes a list (or equivalent) of unknotted definitions and returns the list of mutually recursive ("knotted") functions. This challenge will focus on a simpler situation with exactly 2 mutually recursive functions; the respective combinator will be called fix2 throughout this challenge.

A common example of mutual recursion is even and odd defined like this:

even n =
  if n == 0
  then true
  else odd (n - 1)
odd n =
  if n == 0
  then false
  else even (n - 1)

The unknotted version of these would look like this (note that mutually recursive definitions should have access to every single function being defined):

evenFix (even, odd) n =
  if n == 0
  then true
  else odd (n - 1)
oddFix (even, odd) n =
  if n == 0
  then false
  else even (n - 1)

Then we can knot the two definitions using fix2 to get the recursive even and odd back:

fix2 (a, b) = fix (\self -> (a self, b self))
  where fix f = f (fix f)
let (even, odd) = fix2 (evenFix, oddFix)

Challenge

Implement fix2. To be more precise, write a function or program that takes two unknotted black-box functions fFix and gFix and a non-negative integer n, and outputs the two results (f(n), g(n)) of the knotted equivalents f and g. Each f and g is guaranteed to be a function that takes and returns a non-negative integer.

You can choose how fFix and gFix (and also fix2) will take their arguments (curried or not). It is recommended to demonstrate how the even-odd example works with your implementation of fix2.

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
12
  • 3
    \$\begingroup\$ I must admit that the description of this challenge seems to rely on (pseudo?)-code that I find rather difficult to understand. \$\endgroup\$ – Dominic van Essen Jun 14 at 7:30
  • \$\begingroup\$ It might be easier to read if the ifs were broken onto multiple lines. But currently I have no issue reading this. \$\endgroup\$ – Wheat Wizard Jun 14 at 7:43
  • \$\begingroup\$ @DominicvanEssen I replaced some special names with plain arithmetic (which I admit I should have done already), and spread out the if-clauses. Would it help if I explain some of the syntax, like fix f = f (fix f) is def fix(f): return f(fix(f)), f x is a function application f(x), and \x -> smth is lambda x: smth? \$\endgroup\$ – Bubbler Jun 14 at 8:09
  • 2
    \$\begingroup\$ @Neil fix f = (\ x -> f (x x)) (\ x -> f (x x)) \$\endgroup\$ – Wheat Wizard Jun 14 at 10:44
  • 1
    \$\begingroup\$ @WheatWizard I see. So fix outputs the fixed points of f, not a function \$\endgroup\$ – Luis Mendo Jun 15 at 17:31
5
\$\begingroup\$

Haskell, 14 bytes

f l=map($f l)l

Takes a two-element list of functions that take two-element lists, and returns a two-element list.

Try it online!

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

Scala, 82 bytes

type R=Int=>Int
type T=(=>Stream[R])=>R
def>(f:Stream[T]):Stream[R]=f.map(_(>(f)))

Try it in Scastie!

This is very similar to Anders Kaseorg's answer, but it takes a lot more effort to avoid stack overflows and infinite recursion in Scala because it doesn't have lazy evaluation by default.

//The result type, a complete function
type R=Int=>Int
//A function that needs to be fixed. Takes a by-name parameter, a lazily evaluated
//list that contains complete functions, and returns a complete function
type T=(=>Stream[R])=>R
//The meat of the answer. This is practically the same as the Haskell answer.
def>(f:Stream[T]): Stream[R] =
  f.map(    //For every incomplete function in f
   _(       //apply it to
    >(f)))  //the result of applying > on f again (not immediately evaluated)

A possible implementation of evenFix and oddFix:

val evenFix: T = fns => n => if (n == 0) 1 else fns(1)(n - 1)
val oddFix: T = fns => n => if (n == 0) 0 else fns(0)(n - 1)

Note that since fns is a by-name parameter, using it more than once causes it to be evaluated again. It can also not be pattern-matched on, since that causes it to be evaluated.

\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 137 bytes

interface L{C g();}interface C{int a(int x);}interface P{C a(L[]l);static L[]z(P[]p){return new L[]{()->p[0].a(z(p)),()->p[1].a(z(p))};}}

Try it online!

I was actually hoping this would turn out longer so it'd be a better shitpost.

The method to call is P::z, which takes two-element array of Ps and returns a two-element array of L's. To obtain a completed function (C) from an L, one has to call L::g on it. P represents a function to be fixed, and its a method takes a two-element array of Ls to prevent evaluation immediately, returning a C that represents a complete function that an int n can be applied to.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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