“Pair”是“MonadRec”的有效实例吗？

Question

在论文 Stack Safety for Free 中，Phil Freeman 定义了

MonadRec

类型类，如下。

class (Monad m) <= MonadRec m where
  tailRecM :: forall a b. (a -> m (Either a b)) -> a -> m b

MonadRec

类的实例必须满足以下定律。

1. tailRecM f a

   必须等于

   f a >>= go

   ，其中

   go (Left a) = f a >>= go

   和

   go (Right b) = pure b

   。

2. tailRecM f

   的堆栈使用量最多只能是

   f

   本身的堆栈使用量的常数倍。

现在，考虑 TypeScript 中的以下

Pair

类。

class Pair<out A> {
  public constructor(
    public readonly fst: A,
    public readonly snd: A,
  ) {}

  public chain<A, B>(this: Pair<A>, arrow: (value: A) => Pair<B>): Pair<B> {
    return new Pair(arrow(this.fst).fst, arrow(this.snd).snd);
  }

  public static of<A>(value: A): Pair<A> {
    return new Pair(value, value);
  }
}

如您所见，

Pair

是一个有效的 monad。现在，我想为

chainRec

定义

Pair

函数，它相当于 Phil Freeman 定义的 tailRecM 函数的

Fantasy Land

。为简单起见，我首先定义自己的

Either

类型。

class Left<out A> {
  public readonly isLeft = true;

  public constructor(public readonly value: A) {}
}

class Right<out B> {
  public readonly isLeft = false;

  public constructor(public readonly value: B) {}
}

type Either<A, B> = Left<A> | Right<B>;

然后，我在

chainRec

类中定义了

Pair

函数，如下所示。

public static chainRec<A, B>(
  arrow: (value: A) => Pair<Either<A, B>>,
  value: A,
): Pair<B> {
  const rec = (either: Either<A, B>): Pair<B> => {
    const stack: Either<B, Either<A, B>>[] = [];

    let cursor: Either<Either<A, B>, Pair<B>> = new Left(either);

    while (stack.length > 0 || cursor.isLeft) {
      if (cursor.isLeft) {
        const either: Either<A, B> = cursor.value;
        if (either.isLeft) {
          const pair = arrow(either.value);
          cursor = new Left(pair.fst);
          stack.push(new Right(pair.snd));
        } else cursor = new Right(Pair.of(either.value));
      } else {
        const pair: Pair<B> = cursor.value;
        const frame = stack.pop()!;
        if (frame.isLeft) cursor = new Right(new Pair(frame.value, pair.snd));
        else {
          cursor = new Left(frame.value);
          stack.push(new Left(pair.fst));
        }
      }
    }

    return cursor.value;
  };

  return arrow(value).chain(rec);
}

游乐场链接

很容易证明

chainRec

的实现满足第一定律。

Pair.chainRec(f, a)

相当于

f(a).chain(function go(either) {
  return either.isLeft ? f(either.value).chain(go) : Pair.of(either.value);
});

但是，我不确定它是否满足第二定律。

• Pair.chainRec(f, a)

  的堆栈使用量最多只能是

  f

  本身的堆栈使用量的常数倍。

我不确定，因为

rec

函数有一个局部

stack

变量，它可以增长任意大。当然，

stack

存在于堆中，并且只有对

stack

的引用存在于堆栈中。所以，从这个意义上说，它确实满足第二定律。但是，如果我们允许

chainRec

函数使用任意大的 local 堆栈，那么我们是否能够为每个可能的 monad 创建一个有效的

MonadRec

实例？如果答案是否定的，那么哪些示例类型是

Monad

的有效实例，但不是

MonadRec

的有效实例？也就是说，有哪些非尾递归的 monad 示例？

Answer 1

是的，我希望

Pair

monad 是堆栈安全的，并且有正确的

tailRecM

方法。

一个简单的说法是，

Pair

monad 实际上是

Reader

monad 的一个特例：

 type Reader r a = r -> a

我们设置

r = Bool

的地方。类型

Bool -> a

相当于对

(a, a)

。所以，

Pair a

与

Reader Bool a

相同。

Reader r

monad 对于任何类型

r

始终都是堆栈安全的，并且具有其标准函数

tailRecM

。

Reader

的函数可以专门化，通过设置

r = Bool

，然后您将获得

tailRecM

的

Pair

。