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

Question

I am attempting to translate the following Haskell code to Javascript:

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

I have trouble understanding ($ self) though. Here is what I've achieved so far:

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

The error is Uncaught TypeError: f.runDefer(...)[1] is not a function.

Here is the source.

score 1 · Answer 1 · answered Apr 05 '19 at 12:32

1

($ self) is just \f -> f $ self; it's a function that applies its argument to self. You could rewrite the Haskell version using a list comprehension:

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

answered Apr 05 '19 at 12:32

chepner

497,756
71
530
681

4castle · Accepted Answer · 2019-04-05T13:39:01.777

The definition of defFixPoly has an extra layer of Defer than it should. Since self is already a Defer value, you can just pass it directly to f rather than wrapping it again.

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

This now defines mutually recursive isEven and isOdd functions.

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

This kind of mistakes happen a lot to me, because I tend to focus on patterns (like passing a `Defer` to `f`) rather than actually visualizing the algorithm. This works frequently with the declarative code of FP, but not always. — , Apr 05 '19 at 13:38
@bob, very circular code like this is hard to visualize. Types help a lot. You can use them in your mind. — luqui, Apr 06 '19 at 00:50

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

2 Answers2