将专门针对列表的未来主义表达式转化为命令式循环。

Question

将专门针对列表的未来主义表达式转化为命令式循环。

javascriptloopshaskellrecursion-schemescorecursion

4

我一直在尝试翻译这个递归的Haskell实现，它是专门针对List的futumorphism。

futuL :: (a -> Maybe (b, ([b], Maybe a))) -> a -> [b]
futuL f x = case f x of
  Nothing -> []
  Just (y, (ys, mz)) -> y : (ys ++ fz)
    where fz = case mz of
      Nothing -> []
      Just z -> futuL f z

将其转换为JavaScript命令式循环非常困难（至少对于我来说）。

const None = ({type: "Option", tag: "None"});
const Some = x => ({type: "Option", tag: "Some", runOption: x});

const arrFutu = coalg => x => { // futuL f x
  const acc = []; // ~ fz

  while (true) {
    let optX = coalg(x); // f x

    switch (optX.tag) { // case
      case "None": return acc; // Nothing -> []

      case "Some": {
        let [y, [ys, optX_]] = optX.runOption; // Just (y, (ys, mz))

        switch(optX_.tag) {
          case "None": {
            arrPushFlat(acc) ((ys.unshift(y), ys)); // y : (ys ++ [])
            return acc;
          }

          case "Some": { // y : (ys ++ futuL f z)
            arrPushFlat(acc) ((ys.unshift(y), ys)); 
            x = optX_.runOption;
            break;
          }

          default: throw new UnionError("invalid tag");
        }

        break;
      }

      default: throw new UnionError("invalid tag");
    }
  }
};

我很难在心里解析Haskell代码，特别是包含递归调用的where部分。我猜想这个调用不是尾部位置，因此我需要为我的JS循环使用显式堆栈(acc)。

我的翻译正确吗？

- user5536315

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- danidiaz · Accepted Answer

由于Haskell是惰性的，因此可以在其余部分计算完成之前开始消耗“futu”返回的列表开头。用JavaScript术语来说，这最好用生成器来建模。

例如（为简单起见，我使用了null值来表示None）：

const arrFutu = coalg => function*(seed) {
    while (true) {
        const next = coalg(seed);
        if (next) {
            // Maybe (b, ([b], Maybe a)), using null for None & flattening nested tuple   
            const [item, items, nextseed] = next; 
            yield item;
            yield* items;
            // Maybe a, using null for None 
            if (nextseed) { 
                seed = nextseed;
                continue; // Continue iterating if the seed isn't null.
            }
        } 
        return;
    }
}

使用一个类似以下的余代数示例：

const coalg1 = seed => {
    if (seed < 5) {
        return ['a', ['a','a'], seed + 1];
    } else if (seed < 10) {
        return ['b', ['b','b'], seed + 1];
    } else if (seed == 10) {
        return ['c', ['c'], null];
    }
    return null;
}

for (const x of arrFutu(coalg1)(0)) {
    console.log(x);
}

for (const x of arrFutu(coalg1)(20)) {
    console.log(x);
}

将futu改为递归而不是迭代会更好，但似乎JavaScript尾调用优化在生成器中无法工作。

顺便说一下，即使Haskell代码不是尾递归的，递归也是"受保护的"：递归调用发生在一个或多个数据构造函数（这里是列表构造函数）内部，当客户端消耗返回的列表时，调用可以被延迟直到构造函数被“剥离”。