[编辑]
这是How to implement a stack-safe chainRec operator for the continuation monad? 的后续问题
给定的是 chainRec
的类型
chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b
通常,chainRec
与 trampoline 一起实现,以允许在 monad 中进行堆栈安全递归。然而,如果我们放下蹦床,我们可以实现 chainRec
的普通函数类型,如下所示:
const chainRec = f => x => join(f(chainRec(f), of, x));
接下来,我想将它应用于递归操作:
const map = f => g => x => f(g(x));
const join = f => x => f(x) (x);
const of = x => y => x;
const chainRec = f => x => join(f(chainRec(f), of, x));
const repeat = n => f => x =>
chainRec((loop, done, args) =>
args[0] === 0
? done(args[1])
: loop([args[0] - 1, map(f) (args[1])])) ([n, of(x)]);
const inc = x => of(x + 1);
repeat(10) (inc) (0) (); // error
我想既然在chainRec
的定义中有一个join
,那么在的实现中肯定有一个
,这样就有两个嵌套的函数上下文要折叠了。但它不起作用,我不知道如何修复它。map
重复
最佳答案
不知道你的 repeat
函数做了什么,我猜你的调用 repeat(10)(inc)(0)
应该扩展到
map(inc)(
map(inc)(
map(inc)(
map(inc)(
map(inc)(
map(inc)(
map(inc)(
map(inc)(
map(inc)(
map(inc)(
of(0)
)
)
)
)
)
)
)
)
)
)
因为你的 inc
由于某种原因确实返回一个函数 _ => Int
而不是普通的 Int
,这将调用 x + 1
在函数 x
上导致该函数的字符串化(y => x
变成 "y => x1"
), 尝试调用时会抛出异常。
修复 const inc = x => x + 1;
后,您的 repeat
函数仍然不起作用。它需要是简单的递归,用
const id = x => x
// rec :: ((a -> c, b -> c, a) -> c) -> a -> b
// here with c == b, no trampoline
const rec = f => x => f(rec(f), id, x) // a bit like the y combinator
const repeat = n => f => x =>
rec((loop, done, [m, g]) =>
m === 0
? done(g)
: loop([m - 1, map(f)(g)])
)([n, of(x)]);
repeat(10)(inc)(0)() // 10 - works!
根本不涉及单子(monad)!
如果我们想使用 chainRec
,我们需要引入一些任意的 monad(这里:函数 monad),以及 f
回调到 chainRec
需要返回该 monad 类型的实例,而不仅仅是 loop
/done
:
chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b
// ^
我们可以通过简单地将返回值包装在 of
中来实现:
const repeat = n => f => x =>
chainRec((loop, done, [m, g]) =>
of(m === 0
// ^^
? done(g)
: loop([m - 1, map(f)(g)])
)
)([n, of(x)]);
当然现在得到一个 m b
,即所有内容都包含在另一个函数中:
repeat(10)(inc)(0)()() // 10
// ^^
// repeat(1)(inc)(0) expands to `of(map(inc)(of(0)))
但我怀疑这是你想要的。
关于javascript - chainRec 的基本思想是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50551725/