Variadic fixed-point combinator

A fixed-point combinator is a higher order function $\operatorname {fix}$ that returns the fixed point of its argument function. If the function $f$ has one or more fixed points, then $\operatorname {fix} f=f(\operatorname {fix} f)$ .

You can extend a fixed-point combinator to find the fixed point of the i-th function out of n given functions: $\operatorname {fix} _{i,n}f_{1}\dots f_{n}=f_{i}(\operatorname {fix} _{1,n}f_{1}\dots f_{n})\dots (\operatorname {fix} _{n,n}f_{1}\dots f_{n})$

Task

Your task is to implement a variadic fixed-point combinator $\operatorname {fix} ^{*}$ that finds and returns the fixed points of all given functions: $\operatorname {fix} ^{*}f_{1}\dots f_{n}=\langle \operatorname {fix} _{1,n}f_{1}\dots f_{n},\dots ,\operatorname {fix} _{n,n}f_{1}\dots f_{n}\rangle$

The variadic input and output may be implemented using any feature of the language (e.g. using lists).

If possible, try not to use explicit recursion and implement the variadic fixed-point combinator using a fixed-point combinator like the Y combinator.

Also try to come up with examples where $\operatorname {fix} ^{*}$ could actually be somewhat useful.

Related tasks

See also

Mayer Goldberg: A Variadic Extension of Curry’s Fixed-Point Combinator

Bruijn

Derived from the linked Goldberg paper, as explained in Variadic Fixed-Point Combinators.

:import std/Number .
:import std/List .

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

# --- example usage ---
# mutual recurrence relation of odd?/even?

# equiv of "even? x = if x == 0 then true else odd? (x-1)"
g [[[=?0 [[1]] (1 --0)]]]

# equiv of "odd? x = if x == 0 then false else even? (x-1)"
h [[[=?0 [[0]] (2 --0)]]]

even? ^(y* (g : {}h))

odd? _(y* (g : {}h))

:test (even? (+5)) ([[0]])
:test (odd? (+5)) ([[1]])

Haskell

A fix2 implementation in Haskell (as originally by Anders Kaseorg) is equivalent to fix*:

vfix lst = map ($vfix lst) lst

-- example usage: mutual recurrence relation of mod3

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 $ vfix [h1, h2, h3]

main = print $ mod3 <$> [0 .. 10]

Output:

[0,1,2,0,1,2,0,1,2,0,1]