Реализация отложенной оценки для функции `reduRight ()` в JavaScript - PullRequest
Новая
       12

Реализация отложенной оценки для функции `reduRight ()` в JavaScript

0 голосов
/ 05 июля 2019

Проблема в codewars.com: https://www.codewars.com/kata/foldr/train/javascript

Определить функцию свёртки для массива, которая реализует ту же функцию, что и встроенная функция reduRight (). Проблема очень абстрактная, потому что я мало знал о функциональном программировании.

Я считаю, что наиболее важным является реализация отложенной оценки в JavaScript. Но я не знаю, как с этим справиться.

Например, у нас есть две функции: indexOf и logging, indexOf(x) - это функция, которая будет вызываться в качестве аргументов в методе foldr, logging - это функция-обертка, которая сообщает нам, сколько раз indexOf(x) можно назвать. 

const indexOf = y => function (cur, acc) {
  if (cur === y) {
    return 0
  } else {
    return acc + 1 || -1
  }
};

const logging = fn => function logging(...a) {
  i++;
  return fn(...a);
};

Если мы реализуем это без лени и используем рекурсию: 

Object.defineProperty(Array.prototype, "foldr", {
  value: function foldr(fn, z) {
    return function _foldr(a) {
      if (a.length === 0) {
        return z
      }
      return fn(a[0], _foldr(a.slice(1)))
    }(this);
  }
});
let i = 0
let x = [1, 2, 3].foldr(logging(indexOf(1)), -1)
console.log(`x: ${x}`) // x: 0
console.log(`i: ${i}`) // i: 3

Переменная i показывает, что функция была вызвана 3 раза, весь массив был повторен. Однако, если мы наблюдаем функцию indexOf, мы обнаружим, что нам не нужно итерировать весь массив, если мы используем ленивую оценку.

На первом уровне рекурсии indexOf(1)(a[0], _foldr(a.slice(1))) равно indexOf(1)(1, _foldr([2,3])), потому что cur === y, он должен немедленно возвратить 0 и не нужно оценивать второй аргумент _foldr([2,3]). Таким образом, в тестовом примере codewars.com, i должно быть 1.

Как я мог справиться с этим?

Ответы [ 2 ]

0 голосов
/ 06 июля 2019

Я нахожу решение. Используйте Object.prototype.valueOf()

Метод valueOf () возвращает примитивное значение указанного объекта.

Поскольку мы хотели бы вызывать функцию, когда выполняем некоторые алгоритмы, такие как return acc + 1 || -1.

Мы могли бы использовать: 

Object.defineProperty(Array.prototype, 'foldr', {
  value(fn, z) {
      let _foldr = (a) => {
          if (!a.length) return z;
          let r = fn(a[0], { valueOf: () => _foldr(a.slice(1)) });
          return (r.valueOf) ? r.valueOf() : r;
      };
      return _foldr(this);
  },
});
0 голосов
/ 05 июля 2019

Вы близки ...: 

  fn(a[0], () => _foldr(a.slice(1)))

Если вы передадите функцию вместо значения acc umulator, функция может решить, оценивать аккумулятор или нет: 

  const indexOf = y => function (cur, acc) {
    if (cur === y) {
      return 0; // acc() was not called, ends here
    } else {
      return acc() + 1 || -1; // acc() gets called, traversal goes on
    }
 };
...