我有一个数组转换器类型，它展示了交错的效果层，以确保合法的效果实现。您可以很容易地从类型的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首先，数组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]
另一方面，递归数组monad transformer类型在m = Identity时返回链表。
of([1, of([2, of([3, of([])])])]) === [1, [2, [3, []]]]
然而，没有办法创建合法的数组monad transformer类型，当底层monad是Identity时，它也会返回实际的数组。这是因为monad变换器本质上是代数数据结构，而数组不是代数数据结构。
最接近的方法是定义ArrayT m a = Array (m a)。然而，这只会满足monad定律，当基础的monad是交换的。
请记住，在定义monad转换器数据类型时。
- 底层monad一次最多只能包装一个值
- 底层monad必须嵌套，才能正确排列和交错效果
回到过去，Trampolinemonad就是Freemonad。我们可以将其定义如下。
// 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