Implement Fix2 combinator

Question

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 code-golf rules apply. The shortest code in bytes wins.

• Dominic van Essen: I must admit that the description of this challenge seems to rely on (pseudo?)-code that I find rather difficult to understand.
• Wheat Wizard: It might be easier to read if the ifs were broken onto multiple lines. But currently I have no issue reading this.
• Bubbler: @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?
• Wheat Wizard: @Neil fix f = (\ x -> f (x x)) (\ x -> f (x x))
• Luis Mendo: @WheatWizard I see. So fix outputs the fixed points of f, not a function

Answer 1

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!

Answer 2

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.

Answer 3

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.