javascript - 如何更有效地使用 Trampoline 类型作为变压器的基本单子?
问题描述
我有一个数组转换器类型,它展示交错的效果层,以确保合法的效果实现。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
解决方案
首先,你的数组单子变换器的定义是错误的。
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 转换器类型在m = Identity
.
of([1, of([2, of([3, of([])])])]) === [1, [2, [3, []]]]
但是,没有办法创建一个合法的数组 monad 转换器类型,当底层 monad 是Identity
. 这是因为 monad 转换器本质上是代数数据结构,而数组不是代数的。
您可以获得的最接近的是通过定义ArrayT m a = Array (m a)
. 然而,这只会在底层单子是可交换的时满足单子定律。
请记住,在定义 monad 转换器数据类型时。
- 底层 monad 一次最多只能包装一个值。
- 底层的 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
推荐阅读
- database - 坚持从 docker 运行的 Elastic/Kibana db/config?
- ruby-on-rails - 仅包含特定属性作为 Ruby on Rails 中脚手架生成的表单的输入选项
- tfs - Team Foundation Server 集合中的总代码行数?
- bash - 如何用 shell 脚本的参数替换文件中的特定行?
- rust - 为什么 &str 从函数返回时没有“寿命不够长”的问题?
- azure - Azure 政府何时提供托管容器服务 (AKS)?
- vba - 替换句子中的单词
- html - 对于两种类型的列(固定宽度和流体宽度),对于 flex-nowrap (bootstrap 4),overflow-x:auto 不能按预期工作
- php - 从递归函数php获取数据
- r - 在 R 中导入原始图像