如何更有效地使用 Trampoline 类型作为 transformer 的基础 monad？

Question

我有一个阵列转换器类型，它展示了交错的效果层以确保合法的效果实现。您可以轻松地从类型的 of 操作 const arrOfT = of => x => of([of(x)]).

中读取结构

该类型将有效的折叠作为其基本操作。我使用左折叠，因为底层数组类型本质上是严格的：

const arrFoldT = chain => f => init => mmx =>
  chain(mmx) (mx => {
    const go = (acc, i) =>
      i === mx.length
        ? acc
        : chain(mx[i]) (x =>
            go(f(acc) (x), i + 1))
//          ^^^^^^^^^^^^^^^^^^^^^ non-tail call position
    return go(init, 0);
  });

如您所见，实现不是堆栈安全的。然而，堆栈安全只是另一种可以通过 monad 编码的计算效果。我为 Trampoline 类型实现了一个：

const monadRec = o => {
  while (o.tag === "Chain")
    o = o.f(o.x);

  return o.tag === "Of"
    ? o.x
    : _throw(new TypeError("unknown case"));
};

const recChain = mx => fm =>
  mx.tag === "Chain" ? Chain(mx.x) (x => recChain(mx.f(x)) (fm))
    : mx.tag === "Of" ? fm(mx.x)
    : _throw(new TypeError("unknown case"));

const Chain = x => f =>
  ({tag: "Chain", f, x});

const Of = x =>
  ({tag: "Of", x});

虽然实现很简单，但应用程序却并非如此。我很确定我应用错了：

const mmx = Of(
  Array(1e5)
    .fill(Chain(1) (x => Of(x))));
//                  ^^^^^^^^^^^^ redundant continuation

const main = arrFoldT(recChain)
  (acc => y => recMap(x => x + y) (acc))
    (Of(0))
      (mmx);

monadRec(main); // 100000

我需要在创建大型有效数组时使用 Chain，因为 Of 发出控制流跳出蹦床的信号。另一方面，对于 Chain，我必须指定一个冗余延续。

我的第一个想法是翻转 Chain 的论点并依赖于部分应用，但这不适用于当前的实现。

有没有办法更有效地使用类型？

这是一个工作示例：

// ARRAYT

const arrFoldT = chain => f => init => mmx =>
  chain(mmx) (mx => {
    const go = (acc, i) =>
      i === mx.length
        ? acc
        : chain(mx[i]) (x =>
            go(f(acc) (x), i + 1))

    return go(init, 0);
  });

// TRAMPOLINE

const monadRec = o => {
  while (o.tag === "Chain")
    o = o.f(o.x);

  return o.tag === "Of"
    ? o.x
    : _throw(new TypeError("unknown case"));
};

const Chain = x => f =>
  ({tag: "Chain", f, x});

const Of = x =>
  ({tag: "Of", x});

// Functor

const recMap = f => tx =>
  Of(f(tx.x));

// Monad

const recChain = mx => fm =>
  mx.tag === "Chain" ? Chain(mx.x) (x => recChain(mx.f(x)) (fm))
    : mx.tag === "Of" ? fm(mx.x)
    : _throw(new TypeError("unknown case"));

const recOf = Of;

// MAIN

const mmx = Of(
  Array(1e5)
    .fill(Chain(1) (x => Of(x))));

const main = arrFoldT(recChain)
  (acc => y => recMap(x => x + y) (acc))
    (Of(0))
      (mmx);

console.log(
  monadRec(main)); // 100000

Answer 1

首先，你的数组monad转换器的定义是错误的。

ArrayT m a = m (Array (m a))

上面的类型定义没有正确交错底层的 monad。

以下是上述数据类型的示例值。

of([of(1), of(2), of(3)])

这种数据类型有几个问题。

数组末尾没有影响。
效果未排序。因此，它们可以按任何顺序执行。
底层的 monad 包装了单个元素以及整个数组。这是错误的。

以下是正确的数组 monad 转换器类型的示例值。

of([1, of([2, of([3, of([])])])])

请注意。

数组末尾有效果
效果是有序的。这是因为数据类型是递归定义的。
底层 monad 包装了数组的各个步骤。它不会再次包装整个数组。

现在，我明白你为什么要定义ArrayT m a = m (Array (m a))了。如果 m = Identity 那么你会得到一个实际的 Array a，它支持元素的随机访问。

of([of(1), of(2), of(3)]) === [1, 2, 3]

另一方面，当 m = Identity.

时，递归数组 monad 转换器类型 returns 一个链表

of([1, of([2, of([3, of([])])])]) === [1, [2, [3, []]]]

但是，当底层 monad 是 Identity 时，无法创建合法的数组 monad 转换器类型，它也是 returns 实际数组。这是因为 monad 转换器本质上是代数数据结构，而数组不是代数的。

最接近的是定义 ArrayT m a = Array (m a)。然而，这只会满足单子法则，当基础单子是可交换的。

请记住，在定义 monad 转换器数据类型时。

底层 monad 一次最多只能包装一个值。
底层 monad 必须嵌套，才能正确排序和交错效果。

回来，Trampoline monad 就是 Free monad。我们可以定义如下。

// pure : a -> Free a
const pure = value => ({ constructor: pure, value });

// bind : Free a -> (a -> Free b) -> Free b
const bind = monad => arrow => ({ constructor: bind, monad, arrow });

// thunk : (() -> Free a) -> Free a
const thunk = eval => ({ constructor: thunk, eval });

// MonadFree : Monad Free
const MonadFree = { pure, bind };

// evaluate : Free a -> a
const evaluate = expression => {
    let expr = expression;
    let stack = null;

    while (true) {
        switch (expr.constructor) {
            case pure:
                if (stack === null) return expr.value;
                expr = stack.arrow(expr.value);
                stack = stack.stack;
                break;
            case bind:
                stack = { arrow: expr.arrow, stack };
                expr = expr.monad;
                break;
            case thunk:
                expr = expr.eval();
        }
    }
};

我还将从我的 .

中复制数组 monad 转换器的实现

// Step m a = null | { head : a, tail : ListT m a }
// ListT m a = m (Step m a)

// nil : Monad m -> ListT m a
const nil = M => M.pure(null);

// cons : Monad m -> a -> ListT m a -> ListT m a
const cons = M => head => tail => M.pure({ head, tail });

// foldr : Monad m -> (a -> m b -> m b) -> m b -> ListT m a -> m b
const foldr = M => f => a => m => M.bind(m)(step =>
    step ? f(step.head)(foldr(M)(f)(a)(step.tail)) : a);

因此，当底层 monad 是 Free 时，操作是堆栈安全的。

// replicate :: Number -> a -> ListT Free a
const replicate = n => x => n ?
    cons(MonadFree)(x)(thunk(() => replicate(n - 1)(x))) :
    nil(MonadFree);

// map : (a -> b) -> Free a -> Free b
const map = f => m => bind(m)(x => pure(f(x)));

// add : Number -> Free Number -> Free Number
const add = x => map(y => x + y);

// result : Free Number
const result = foldr(MonadFree)(add)(pure(0))(replicate(1000000)(1));

console.log(evaluate(result)); // 1000000

把它们放在一起。

// pure : a -> Free a
const pure = value => ({ constructor: pure, value });

// bind : Free a -> (a -> Free b) -> Free b
const bind = monad => arrow => ({ constructor: bind, monad, arrow });

// thunk : (() -> Free a) -> Free a
const thunk = eval => ({ constructor: thunk, eval });

// MonadFree : Monad Free
const MonadFree = { pure, bind };

// evaluate : Free a -> a
const evaluate = expression => {
    let expr = expression;
    let stack = null;

    while (true) {
        switch (expr.constructor) {
            case pure:
                if (stack === null) return expr.value;
                expr = stack.arrow(expr.value);
                stack = stack.stack;
                break;
            case bind:
                stack = { arrow: expr.arrow, stack };
                expr = expr.monad;
                break;
            case thunk:
                expr = expr.eval();
        }
    }
};

// Step m a = null | { head : a, tail : ListT m a }
// ListT m a = m (Step m a)

// nil : Monad m -> ListT m a
const nil = M => M.pure(null);

// cons : Monad m -> a -> ListT m a -> ListT m a
const cons = M => head => tail => M.pure({ head, tail });

// foldr : Monad m -> (a -> m b -> m b) -> m b -> ListT m a -> m b
const foldr = M => f => a => m => M.bind(m)(step =>
    step ? f(step.head)(foldr(M)(f)(a)(step.tail)) : a);

// replicate :: Number -> a -> ListT Free a
const replicate = n => x => n ?
    cons(MonadFree)(x)(thunk(() => replicate(n - 1)(x))) :
    nil(MonadFree);

// map : (a -> b) -> Free a -> Free b
const map = f => m => bind(m)(x => pure(f(x)));

// add : Number -> Free Number -> Free Number
const add = x => map(y => x + y);

// result : Free Number
const result = foldr(MonadFree)(add)(pure(0))(replicate(1000000)(1));

console.log(evaluate(result)); // 1000000

如何更有效地使用 Trampoline 类型作为 transformer 的基础 monad？

How to use the Trampoline type as the base monad of a transformer more efficiently?

javascript

functional-programming

monads

monad-transformers

trampolines