Variadic fixed-point combinator: Difference between revisions
(Create page) |
(→{{header|Haskell}}: Added Wren) |
||
Line 68: | Line 68: | ||
{{out}} |
{{out}} |
||
<code>[0,1,2,0,1,2,0,1,2,0,1]</code> |
<code>[0,1,2,0,1,2,0,1,2,0,1]</code> |
||
=={{header|Wren}}== |
|||
{{libheader|Wren-fmt}} |
|||
This is a translation of the Python code [https://codegolf.stackexchange.com/questions/266083/write-a-variadic-fixed-point-combinator here]. |
|||
<syntaxhighlight lang="wren">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) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
Revision as of 23:52, 3 March 2024
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]
Wren
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