0

我有一个数组转换器类型，它展示交错的效果层，以确保合法的效果实现。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

4

1 回答 1

2

首先，你的数组单子变换器的定义是错误的。

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

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

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

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

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

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

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

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

注意。

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

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

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

另一方面，递归数组 monad 转换器类型在m = Identity.

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

但是，没有办法创建一个合法的数组 monad 转换器类型，当底层 monad 是Identity. 这是因为 monad 转换器本质上是代数数据结构，而数组不是代数的。

您可以获得的最接近的是通过定义ArrayT m a = Array (m a). 然而，这只会在底层单子是可交换的时满足单子定律。

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

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

回来，Trampoline单子只是Free单子。我们可以定义如下。

// 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

于 2020-11-16T07:48:31.923 回答