Variadic fixed-point combinator: Difference between revisions

Content added Content deleted

Inline

Revision as of 04:06, 4 March 2024

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]

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

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