亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

如何折疊來自非尾遞歸算法的數據結構?

如何折疊來自非尾遞歸算法的數據結構?

慕的地6264312 2021-06-17 17:05:35
我有一個可變參數提升函數,它允許沒有深度嵌套的函數組合的扁平 monadic 鏈: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為每次迭代返回 a ,而不是部分應用的函數。如何用折疊替換非尾遞歸?這是當前遞歸實現的一個工作示例:const TYPE = Symbol.toStringTag;const struct = type => cons => {  const f = x => ({    ["run" + type]: x,    [TYPE]: type,  });  return cons(f);};// variadic argument transformerconst 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 functionconst 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 Taskconst 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 functionconst delay = (ms, x) =>  Task(r => setTimeout(r, ms, x));// test dataconst tw = delay(100, 1),  tx = delay(200, 2),  ty = delay(300, 3),  tz = delay(400, 4);
查看完整描述

2 回答

?
縹緲止盈

TA貢獻2041條經驗 獲得超4個贊

那個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)))))

根據 monad 定律,它們的評估結果應該相同,但在實踐中,一個可能比另一個更有效率。


查看完整回答
反對 回復 2021-06-18
  • 2 回答
  • 0 關注
  • 151 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號