不知道怎么表达fix
作为尾递归算法。或者它已经是尾递归了?大概是我想多了……
const fix = f => x => f(fix(f)) (x); // redundant eta abstraction due to eager eval
const sum = fix(go => acc => ([x, ...xs]) =>
x === undefined
? acc
: go(acc + x) (xs)) (0);
const main = sum([1,2,3,4,5]);
console.log(main); // 15
我尝试了很多,但还没有想出任何远程有用的东西。尾递归算法可以很容易地转换为堆栈安全循环。这才是真正的目标。
最佳答案
I can't figure out how to express
fix
as a tail recursive algorithm.
一、转换
fix
的定义进入 A-normal form .// fix :: ((a -> b) -> a -> b) -> a -> b
const fix = f => x => {
const g = fix(f);
const h = f(g);
const y = h(x);
return y;
};
接下来,将生成的程序转换为 continuation-passing style .
// type Cont r a = (a -> r) -> r
// fix :: ((a -> Cont r b) -> Cont r (a -> Cont r b)) -> Cont r (a -> Cont r b)
const fix = f => k => k(x => k =>
fix(f) (g =>
f(g) (h =>
h(x) (y =>
k(y)))));
现在,
fix
是尾递归的。但是,这可能不是您想要的。A tail recursive algorithm could be easily transformed to a stack safe loop. That is the actual goal.
如果您想要的只是堆栈安全,那么您可以使用
Trampoline
单子(monad)。// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });
// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });
// trampoline :: Trampoline a -> a
const trampoline = result => {
while (result.bounce) result = result.func(...result.args);
return result.value;
};
// fix :: ((a -> Trampoline b) -> a -> Trampoline b) -> a -> Trampoline b
const fix = f => Bounce(x => f(fix(f))(x));
// id :: a -> a
const id = x => x;
// reachable code
console.log("begin"); // open the console in your browser
// infinite loop
trampoline(fix(id)(0));
// unreachable code
console.log("end");
但是,这需要您更改
sum
的定义。也是。// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });
// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });
// trampoline :: Trampoline a -> a
const trampoline = result => {
while (result.bounce) result = result.func(...result.args);
return result.value;
};
// fix :: ((a -> Trampoline b) -> a -> Trampoline b) -> a -> Trampoline b
const fix = f => Bounce((...args) => f(fix(f))(...args));
// _sum :: (Number, [Number]) -> Trampoline Number
const _sum = fix(recur => (acc, xxs) => {
if (xxs.length === 0) return Return(acc);
const [x, ...xs] = xxs;
return recur(acc + x, xs);
});
// sum :: [Number] -> Trampoline Number
const sum = xxs => _sum(0, xxs);
// result :: Number
const result = trampoline(sum([1,2,3,4,5]));
// 15
console.log(result);
希望有帮助。
关于javascript - fix 可以是尾递归的,因此可以表示为一个简单的循环?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59886494/