Variadic fixed-point combinator

A fixed-point combinator is a higher order function ${\displaystyle \operatorname {fix} }$ that returns the fixed point of its argument function. If the function ${\displaystyle f}$ has one or more fixed points, then ${\displaystyle \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: ${\displaystyle \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 ${\displaystyle \operatorname {fix} ^{*}}$ that finds and returns the fixed points of all given functions: ${\displaystyle \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 ${\displaystyle \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]])

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, which has not yet shipped, and has the somewhat non-standard requirement of needing any captures explicitly stated [and returned if updated], and invokable only via the [new] call_lambda() function, rather than directly or the usual call_func() or the implicit invocation of that. Not yet properly documented, or for that matter fully tested...

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

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