如何将多元定点组合器翻译成严格的语言？

Question

我正在尝试将以下 Haskell 代码翻译成 Javascript:

fix_poly :: [[a] -> a] -> [a]
fix_poly fl = fix (\self -> map ($ self) fl)
  where fix f = f (fix f)

虽然我无法理解 ($ self)。这是我到目前为止取得的成就：

const structure = type => cons => {
  const f = (f, args) => ({
    ["run" + type]: f,
    [Symbol.toStringTag]: type,
    [Symbol("args")]: args
  });

  return cons(f);
};

const Defer = structure("Defer") (Defer => thunk => Defer(thunk));

const defFix = f => f(Defer(() => defFix(f)));

const defFixPoly = (...fs) =>
  defFix(self => fs.map(f => f(Defer(() => self))));

const pair = defFixPoly(
  f => n => n === 0
    ? true
    : f.runDefer() [1] (n - 1),
  f => n => n === 0
    ? false
    : f.runDefer() [0] (n - 1));

pair[0] (2); // true expected but error is thrown

错误是Uncaught TypeError: f.runDefer(...)[1] is not a function。

这里是 source.

Answer 1

($ self) 就是 \f -> f $ self；它是一个将其参数应用于 self 的函数。您可以使用列表理解重写 Haskell 版本：

fix_poly fl = fix (\self -> [f self | f <- fl])
    where fix f = f (fix f)

Answer 2

defFixPoly 的定义多了一层 Defer。由于 self 已经是一个 Defer 值，您可以直接将它传递给 f 而不是再次包装它。

const defFixPoly = (...fs) =>
  defFix(self => fs.map(f => f(self)));

const structure = type => cons => {
  const f = (f, args) => ({
    ["run" + type]: f,
    [Symbol.toStringTag]: type,
    [Symbol("args")]: args
  });

  return cons(f);
};

const Defer = structure("Defer") (Defer => thunk => Defer(thunk));

const defFix = f => f(Defer(() => defFix(f)));

const defFixPoly = (...fs) =>
  defFix(self => fs.map(f => f(self)));

const pair = defFixPoly(
  f => n => n === 0
    ? true
    : f.runDefer() [1] (n - 1),
  f => n => n === 0
    ? false
    : f.runDefer() [0] (n - 1));

console.log(pair[0] (2)); // true expected

这现在定义了相互递归的 isEven 和 isOdd 函数。

const isEven = pair[0];
const isOdd = pair[1];

如何将多元定点组合器翻译成严格的语言？

How to translate the poly-variadic fix-point combinator to a strict language?

javascript

recursion

haskell

functional-programming

mutual-recursion