我有一个可变参数提升函数,它允许没有深度嵌套函数组合的扁平一元链:
const varArgs = f => {
const go = args =>
Object.defineProperties(
arg => go(args.concat(arg)), {
"runVarArgs": {get: function() {return f(args)}, enumerable: true},
[TYPE]: {value: "VarArgs", enumerable: true}
});
return go([]);
};
const varLiftM = (chain, of) => f => { // TODO: replace recursion with a fold
const go = (ms, g, i) =>
i === ms.length
? of(g)
: chain(ms[i]) (x => go(ms, g(x), i + 1));
return varArgs(ms => go(ms, f, 0));
};
它有效,但我想用折叠从递归中抽象出来。正常的折叠似乎不起作用,至少与Task
类型一起不起作用,
const varLiftM = (chain, of) => f =>
varArgs(ms => of(arrFold(g => mx => chain(mx) (g)) (f) (ms))); // A
因为第 A
行中的代数将为每个迭代返回一个Task
,而不是部分应用的函数。
如何将非尾递归替换为折叠?
下面是当前递归实现的工作示例:
const TYPE = Symbol.toStringTag;
const struct = type => cons => {
const f = x => ({
["run" + type]: x,
[TYPE]: type,
});
return cons(f);
};
// variadic argument transformer
const varArgs = f => {
const go = args =>
Object.defineProperties(
arg => go(args.concat(arg)), {
"runVarArgs": {get: function() {return f(args)}, enumerable: true},
[TYPE]: {value: "VarArgs", enumerable: true}
});
return go([]);
};
// variadic monadic lifting function
const varLiftM = (chain, of) => f => { // TODO: replace recursion with a fold
const go = (ms, g, i) =>
i === ms.length
? of(g)
: chain(ms[i]) (x => go(ms, g(x), i + 1));
return varArgs(ms => go(ms, f, 0));
};
// asynchronous Task
const Task = struct("Task") (Task => k => Task((res, rej) => k(res, rej)));
const tOf = x => Task((res, rej) => res(x));
const tMap = f => tx =>
Task((res, rej) => tx.runTask(x => res(f(x)), rej));
const tChain = mx => fm =>
Task((res, rej) => mx.runTask(x => fm(x).runTask(res, rej), rej));
// mock function
const delay = (ms, x) =>
Task(r => setTimeout(r, ms, x));
// test data
const tw = delay(100, 1),
tx = delay(200, 2),
ty = delay(300, 3),
tz = delay(400, 4);
// specialization through partial application
const varAsyncSum =
varLiftM(tChain, tOf) (w => x => y => z => w + x + y + z);
// MAIN
varAsyncSum(tw) (tx) (ty) (tz)
.runVarArgs
.runTask(console.log, console.error);
console.log("1 sec later...");
[编辑] 正如评论中所希望的那样,我的折叠实现:
const arrFold = alg => zero => xs => {
let acc = zero;
for (let i = 0; i < xs.length; i++)
acc = alg(acc) (xs[i], i);
return acc;
};
of
arrFold
周围打电话似乎有点不合适。
我不确定您的arrFold
是右折叠还是左折叠,但假设它是右折叠,您将需要使用带有闭包的延续传递样式,就像您在递归实现中所做的那样:
varArgs(ms => of(arrFold(g => mx => chain(mx) (g)) (f) (ms)))
成为
varArgs(ms => arrFold(go => mx => g => chain(mx) (x => go(g(x)))) (of) (ms) (f))
用左折,你可以写
varArgs(arrFold(mg => mx => chain(g => map(g) (mx)) (mg)) (of(f)))
但你需要注意,这构建了一个与右折叠不同的调用树:
of(f)
chain(of(f))(g0 => map(m0)(g0))
chain(chain(of(f))(g0 => map(m0)(g0)))(g1 => map(m1)(g1))
chain(chain(chain(of(f))(g0 => map(m0)(g0)))(g1 => map(m1)(g1)))(g2 => map(m2)(g2))
vs(已应用续集(
of(f)
chain(m0)(x0 => of(f(x0)))
chain(m0)(x0 => chain(m1)(x1 => of(f(x0)(x1))))
chain(m0)(x0 => chain(m1)(x1 => chain(m2)(x2) => of(f(x0)(x1)(x2)))))
根据单子法,它们应该评估相同,但在实践中,一个可能比另一个更有效率。
对于这个特定的用例,你不需要monads的全部功能。应用函子是你所需要的:
// type Cont r a = (a -> r) -> r
// type Async a = Cont (IO ()) a
// pure :: a -> Async a
const pure = a => k => k(a);
// ap :: Async (a -> b) -> Async a -> Async b
const ap = asyncF => asyncA => k => asyncF(f => asyncA(a => k(f(a))));
// delay :: (Number, a) -> Async a
const delay = (ms, a) => k => setTimeout(k, ms, a);
// async1, async2, async3, async4 :: Async Number
const async1 = delay(100, 1);
const async2 = delay(200, 2);
const async3 = delay(300, 3);
const async4 = delay(400, 4);
// sum :: Number -> Number -> Number -> Number -> Number
const sum = a => b => c => d => a + b + c + d;
// uncurry :: (a -> b -> c) -> (a, b) -> c
const uncurry = f => (a, b) => f(a)(b);
// result :: Async Number
const result = [async1, async2, async3, async4].reduce(uncurry(ap), pure(sum));
// main :: IO ()
result(console.log);
console.log("1 second later...");
如果需要,您可以定义一个应用上下文函数(即 apply
( 如下:
const apply = (asyncF, ...asyncArgs) => asyncArgs.reduce(uncurry(ap), asyncF);
const result = apply(pure(sum), async1, async2, async3, async4);
如果你把这个函数,那么你可以创建一个lift
函数:
const apply = asyncF => (...asyncArgs) => asyncArgs.reduce(uncurry(ap), asyncF);
const lift = f => apply(pure(f));
const asyncSum = lift(sum);
const result = asyncSum(async1, async2, async3, async4);
请注意,reduce
等效于 arrFold
。因此,lift
等同于varLiftM
.