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

Binary Lambda Calculus

As shown in https://github.com/tromp/AIT/blob/master/rosetta/variadicY.lam, a variadic Y combinator can take the list-based form

Ygen = \fs. map (\fi.fi (Ygen fs)) fs

which translates to a 276 bit BLC program to determine the parity of the input length:

000100010110010101010001101000000101000100011010000001011000000000010110011111111011110010111111101111110111010000110010111101110110100101100000010110000000010101111110000010000011011000001100101100000010110000000010111111000001101101000001000001101100000100000000101101110110

$ echo -n "hello" | ./blc run rosetta/variadicY.lam 
1

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]])

F#

The following uses Y_combinator#March_2024

// Variadic fixed-point combinator. Nigel Galloway: March 15th., 2024
let h2 n = function 0->2 |g->   n (g-1) 
let h1 n = function 0->1 |g->h2 n (g-1) 
let h0 n = function 0->0 |g->h1 n (g-1)
let mod3 n=Y h0 n
[0..10] |> List.iter(mod3>>printf "%d "); printfn ""

Output:

0 1 2 0 1 2 0 1 2 0 1

FreeBASIC

Unfortunately, due to the limitations of the FreeBASIC language, implementing a variadic fixed-point combinator without explicit recursion is extremely difficult, if not impossible. FreeBASIC does not support higher-order functions in a way that allows this type of metaprogramming.

An alternative would be to implement recursion explicitly, although this does not satisfy your original requirement of avoiding explicit recursion.

Declare Function Even(n As Integer) As Integer
Declare Function Odd(n As Integer) As Integer

Function Even(n As Integer) As Integer
    If n = 0 Then Return 1
    Return Odd(n - 1)
End Function

Function Odd(n As Integer) As Integer
    If n = 0 Then Return 0
    Return Even(n - 1)
End Function

Function Collatz(n As Integer) As Integer
    Dim As Integer d = 0
    While n <> 1
        n = Iif(n Mod 2 = 0, n \ 2, 3 * n + 1)
        d += 1
    Wend
    Return d
End Function

Dim As String e, o
Dim As Integer i, c
For i = 1 To 10
    e = Iif(Even(i), "True ", "False")
    o = Iif(Odd(i),  "True ", "False")
    c = Collatz(i)
    Print Using "##: Even: &  Odd: &  Collatz: &"; i; e; o; c
Next i

Sleep

Output:

Similar to Julia/Python/Wren entry.

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]

Julia

Translation of: Wren

let
    Y = (a) -> [((x) -> () -> x(Y(a)))(f) for f in a]

    even_odd_fix = [
        (f) -> (n) -> n == 0 || f[begin+1]()(n - 1),
        (f) -> (n) -> n != 0 && f[begin]()(n - 1),
    ]

    collatz_fix = [
        (f) -> (n, d) -> n == 1 ? d : f[isodd(n)+2]()(n, d + 1),
        (f) -> (n, d) -> f[begin]()(n ÷ 2, d),
        (f) -> (n, d) -> f[begin]()(3 * n + 1, d),
    ]

    evenodd = [f() for f in Y(even_odd_fix)]
    collatz = Y(collatz_fix)[begin]()

    for i = 1:10
        e = evenodd[begin](i)
        o = evenodd[begin+1](i)
        c = collatz(i, 0)
        println(lpad(i, 2), ": Even: $e  Odd: $o  Collatz: $c")
    end
end

Output:

 1: Even: false  Odd: true  Collatz: 0
 2: Even: true  Odd: false  Collatz: 1
 3: Even: false  Odd: true  Collatz: 7
 4: Even: true  Odd: false  Collatz: 2
 5: Even: false  Odd: true  Collatz: 5
 6: Even: true  Odd: false  Collatz: 8
 7: Even: false  Odd: true  Collatz: 16
 8: Even: true  Odd: false  Collatz: 3
 9: Even: false  Odd: true  Collatz: 19
10: Even: true  Odd: false  Collatz: 6

Phix

Translation of Wren/Julia/JavaScript/Python... The file closures.e was added for 1.0.5 [not yet shipped], with the somewhat non-standard requirement of needing captures explicitly stated [and returned if updated], and invokable only via call_lambda(), not direct or [implicit] call_func().
Disclaimer: Don't ask me if this is a proper Y combinator, all I know for sure is it converts a set of functions into a set of closures, without recursion.

include builtins/closures.e  -- auto-include in 1.0.5+ (needs to be manually installed and included prior to that)

function Y(sequence a)
    for i,ai in a do
--      a[i] = define_lambda(ai,{a})
        a[i] = define_lambda(ai,{0})
    end for
    -- using {a} above would stash partially-updated copies,
    --  so instead use a dummy {0} and blat all at the end
    set_captures(a, {a})
    return a
end function

function e(sequence f, integer n)
    return n==0 or call_lambda(f[2],n-1)
end function

function o(sequence f, integer n)
    return n!=0 and call_lambda(f[1],n-1)
end function

function c1(sequence f, integer n, d)
    if n=1 then return d end if
    return call_lambda(f[2+odd(n)],{n,d+1})
end function

function c2(sequence f, integer n, d)
    return call_lambda(f[1],{floor(n/2),d})
end function

function c3(sequence f, integer n, d)
    return call_lambda(f[1],{3*n+1,d})
end function

sequence f2 = Y({e,o}),
         f3 = Y({c1,c2,c3})

object even_func = f2[1],
        odd_func = f2[2],
         collatz = f3[1]

for x=1 to 10 do
    bool bE = call_lambda(even_func,x),
         bO = call_lambda(odd_func,x)
    integer c = call_lambda(collatz,{x,0})
    printf(1,"%2d: even:%t, odd:%t, collatz:%d\n",{x,bE,bO,c})
end for

Output:

 1: even:false, odd:true, collatz:0
 2: even:true, odd:false, collatz:1
 3: even:false, odd:true, collatz:7
 4: even:true, odd:false, collatz:2
 5: even:false, odd:true, collatz:5
 6: even:true, odd:false, collatz:8
 7: even:false, odd:true, collatz:16
 8: even:true, odd:false, collatz:3
 9: even:false, odd:true, collatz:19
10: even:true, odd:false, collatz:6

Python

A re-translation of the Wren version.

Y = lambda a: [(lambda x: lambda: x(Y(a)))(f) for f in a]

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: d if n == 1 else f[(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]()

for i in range(1, 11):
    e = even_odd[0](i)
    o = even_odd[1](i)
    c = collatz(i, 0)
    print(f'{i :2d}: Even: {e}  Odd: {o}  Collatz: {c}')

Wren

Library: Wren-fmt

This is a translation of the Python code here.

import "./fmt" for Fmt

var Y = Fn.new { |a|
    var ly = []
    for (x in a) {
        ly.add(Fn.new { |x| Fn.new { x.call(Y.call(a)) } }.call(x))
    }
    return ly
}

var evenOddFix = [
    Fn.new { |f| Fn.new { |n|
        if (n == 0) return true
        return f[1].call().call(n-1)
    }},

    Fn.new { |f| Fn.new { |n|
        if (n == 0) return false
        return f[0].call().call(n-1)
    }}
]

var collatzFix = [
    Fn.new { |f| Fn.new { |n, d|
        if (n == 1) return d
        return f[n%2 + 1].call().call(n, d+1)
    } },

    Fn.new { |f| Fn.new { |n, d| f[0].call().call((n/2).floor, d) } },

    Fn.new { |f| Fn.new { |n, d| f[0].call().call(3*n+1, d) } }
]

var evenOdd = Y.call(evenOddFix).map { |f| f.call() }.toList

var collatz = Y.call(collatzFix)[0].call()

for (x in 1..10) {
    var e = evenOdd[0].call(x)
    var o = evenOdd[1].call(x)
    var c = collatz.call(x, 0)
    Fmt.print("$2d: Even: $5s  Odd: $5s  Collatz: $n", x, e, o, c)
}

Output:

 1: Even: false  Odd:  true  Collatz: 0
 2: Even:  true  Odd: false  Collatz: 1
 3: Even: false  Odd:  true  Collatz: 7
 4: Even:  true  Odd: false  Collatz: 2
 5: Even: false  Odd:  true  Collatz: 5
 6: Even:  true  Odd: false  Collatz: 8
 7: Even: false  Odd:  true  Collatz: 16
 8: Even:  true  Odd: false  Collatz: 3
 9: Even: false  Odd:  true  Collatz: 19
10: Even:  true  Odd: false  Collatz: 6