Неизменная мемоизация — возможно ли это?

avatar
Shanon Jackson
7 апреля 2018 в 23:14
756
2
4

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

Говорят, что все алгоритмы, которые могут быть реализованы изменчиво, могут быть реализованы неизменно, поэтому в javascript, как бы я реализовал неизменяемую функцию запоминания? Потому что для возврата по другому пути в функции какое-то состояние внутри или вне функции должно измениться.

С помощью следующей функции, как вы можете иметь неизменяемую память в javascript?

function once(fn){
  let returnValue;
  let canRun = true;
  return function runOnce(){
      if(canRun) {
          returnValue = fn.apply(this, arguments);
          canRun = false;
      }
      return returnValue;
  }
}
var processonce = once(process);
processonce(); //process
processonce(); //
Источник
zch
7 апреля 2018 в 23:28
2

Мемоизация по своей сути зависит от состояния, ее нельзя удалить. В лучшем случае вы могли бы сделать его «чисто функциональным», явно передав состояние. Состояние будет неизменной структурой данных, но новой после каждого вызова.

Ответы (2)

avatar
Black Akula
9 апреля 2018 в 22:38
6

Меня также интересовал этот вопрос. Я согласен с @zch - передача неизменного состояния будет работать (первоначальный вызов инициализирует рекурсию с пустым состоянием).

Итак, я сделал домашнее задание по реализации функции Фибоначчи: помните, она нам понадобится как минимум дважды для n-1 и для n-2. Когда звоним fib(n-2) - он уже запоминается.

Вот моя реализация:

const resultCombination = cache => result => (getResult = true) => getResult ? result : cache
const cacheResult = ({resultCombination}) => result => n => resultCombination({...result(false), [n]: result()})(result())

const memoize = ({resultCombination, cacheResult}) => cache => f => n => cache.hasOwnProperty(n)
    ? resultCombination(cache)(cache[n])
    : cacheResult({resultCombination})(f(cache)(n))(n)

const fib2 = ({resultCombination, cacheResult, memoize}) => f1Result => f => n => resultCombination(f1Result(false))(f1Result() + memoize({resultCombination, cacheResult})(f1Result(false))(f)(n - 2)())

const fib = ({resultCombination, cacheResult, memoize, fib2}) => cache => n => n === 1 || n === 2
    ? resultCombination(cache)(1)
    : fib2({resultCombination, cacheResult, memoize})(memoize({resultCombination, cacheResult})(cache)(fib({resultCombination, cacheResult, memoize, fib2}))(n - 1))(fib({resultCombination, cacheResult, memoize, fib2}))(n)


console.log('THE RESULT: ' + fib({
    resultCombination,
    cacheResult: ({resultCombination}) => result => n => {
        console.log(`Caching result: f(${n})=${result()}`)
        return cacheResult({resultCombination})(result)(n)
    },
    memoize: ({resultCombination, cacheResult}) => cache => f => n => {
        console.log(cache.hasOwnProperty(n) ? `Cache hit for n=${n}` : `Calculating value for f(${n})`)
        return memoize({resultCombination, cacheResult})(cache)(f)(n)
    },
    fib2
})({})(8)(true))

// Calculating value for f(7)
// Calculating value for f(6)
// Calculating value for f(5)
// Calculating value for f(4)
// Calculating value for f(3)
// Calculating value for f(2)
// Caching result: f(2)=1
// Calculating value for f(1)
// Caching result: f(1)=1
// Caching result: f(3)=2
// Cache hit for n=2
// Caching result: f(4)=3
// Cache hit for n=3
// Caching result: f(5)=5
// Cache hit for n=4
// Caching result: f(6)=8
// Cache hit for n=5
// Caching result: f(7)=13
// Cache hit for n=6
// THE RESULT: 21

Для лучшего понимания того, что происходит, в функции cacheResult и memoize вводятся обертки протоколирования. Как видите, все функции чистые, принимающие только один параметр (кроме внедрения зависимостей).

Убедитесь, что resultCombination(cache)(result) - это просто замена структуры данных {cache, result}.

P.S. Я не фанат Haskell (даже совсем не знаю синтаксиса Haskell или Lisp), но я увлечен функциональным программированием

Shanon Jackson
10 апреля 2018 в 01:02
0

Очень интересно, посмотрю подробнее, когда буду дома после работы. Выглядит солидно, однако я стараюсь не передавать что-то, что означает «кэш» или «не кеш», и чтобы функция изначально знала, была ли она вызвана или не вызвана раньше. Очевидно, что это требует в некоторой степени изменчивости, но если эта изменчивость может существовать где-то за пределами моей кодовой базы (например, в самом движке javascript), то это то, с чем я бы согласился.

Black Akula
10 апреля 2018 в 18:05
0

Затем я предлагаю использовать некоторые библиотеки или фреймворки, которые имеют эту реализацию. Например, Redux указывает мутацию, но, согласно идеологии Redux, все мутации неизменяемы, и у вас должно быть одно глобальное хранилище. Например, у меня есть моя библиотека, реализующая мемоизацию, согласованную с интерфейсом Redux (но не обязательно Redux — вы можете написать адаптер, совместимый с интерфейсом Redux и моей библиотекой). github.com/blackakula/redux-composite/blob/master/… — библиотека позволяет мне быть гибким и модульным и при этом иметь единое глобальное состояние.

avatar
Sceat
6 июня 2019 в 21:09
0

Я предлагаю другой подход к вводу-выводу, можно ли с помощью генераторов сказать, что он чистый?

function* _cache() {
    const value = yield null
    while (true) yield value
}

const cache = _cache()

const heavyComputation = i => {
        console.log(`uh oh that's some heavy computations here`)
        return i++
}

cache.next().value
cache.next(heavyComputation(1))
cache.next().value
cache.next().value

затем вы можете использовать его для кэширования значения во время выполнения

function* _cache() {
    const value = yield null
    while (true) yield value
}

const cache = _cache()
const loadMongo = uri => void console.log(`fully loaded ${uri}`)

function end(loadedMongo) {
    console.log('handler called')
}

function handler() {
    const mongoUri = 'salutos speculos'
    const loaded = cache.next().value
    if (loaded === null) {
        cache.next(loadMongo(mongoUri))
        end(cache.next().value)
    } else end(loaded)
}

handler()
handler()
handler()
handler()
handler()

enter image description here