Variadic fixed-point combinator
You are encouraged to solve this task according to the task description, using any language you may know.
A fixed-point combinator is a higher order function that returns the fixed point of its argument function. If the function has one or more fixed points, then .
You can extend a fixed-point combinator to find the fixed point of the i-th function out of n given functions:
- Task
Your task is to implement a variadic fixed-point combinator that finds and returns the fixed points of all given functions:
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 could actually be somewhat useful.
- Related tasks
- See also
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]