chainRec 的基本思想是什么？

Question

[编辑]

这是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 与蹦床一起实现，以允许在 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，那么在repeat的实现中一定有一个map参与进来，所以有两个嵌套的函数上下文崩溃。但是它不起作用，我不知道如何修复它。

Answer 1

不知道你的 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 由于某种原因 return 函数 _ => 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!

根本不涉及单子！

如果我们想使用 chainRec，我们需要引入一些任意的 monad（这里：函数 monad），f 到 chainRec 的回调需要 return 该 monad 类型的实例，而不仅仅是 loop/done:

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b
//                                                ^

我们可以通过简单地将 return 值包装在 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)))

但我怀疑这是你想要的。

chainRec 的基本思想是什么？

What is the underlying idea of chainRec?

javascript

monads

recursion

functional-programming