# Implement Fix2 combinator

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

• I must admit that the description of this challenge seems to rely on (pseudo?)-code that I find rather difficult to understand. Jun 14 at 7:30
• It might be easier to read if the ifs were broken onto multiple lines. But currently I have no issue reading this. Jun 14 at 7:43
• @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? Jun 14 at 8:09
• @Neil fix f = (\ x -> f (x x)) (\ x -> f (x x)) Jun 14 at 10:44
• @WheatWizard I see. So fix outputs the fixed points of f, not a function Jun 15 at 17:31

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!

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

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