CODEWITHSUNDEEP
javascriptimmutability
Shanon Jackson
Shanon Jackson

Reputation: 6531

Immutable Memoization - is it possible?

I'm trying to keep my front-end stack as functionally pure and immutable as possible and its done wonders for this project.

It is said all algorithms that can be implemented mutably can be implemented immutably, so in javascript how would I implement an immutable function memoizer? Because in order to return through a different path in the function some state inside or outside the function would have to change.

With the following function, how you can have an immutable memoization in 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(); //

Upvotes: 4

Views: 952

Answers (2)

Sceat
Sceat

Reputation: 1579

I propose a different io aproach, using generators can we say it's pure ?

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

you can then use it to cache a value at runtime

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

Upvotes: 0

Black Akula
Black Akula

Reputation: 626

I was also curious about this question. I agree with @zch - passing the immutable state around would work (the initial call will initialize recursion with empty state).

So, I did my homework with implementing Fibonacci function: remember, we need it at least twice for n-1 and for n-2. When we call fib(n-2) - it is already memoized.

Here is my implementation:

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

For better understanding, what's going on - the cacheResult and memoize functions are injected with logging wrappers. As you can see, all functions are pure, taking only one parameter (except dependency injection).

Be sure, that resultCombination(cache)(result) - is just replacement of {cache, result} data structure.

P.S. I'm not a Haskell nerd (even don't know the Haskell or Lisp syntax at all), but I'm passionate about functional programming

Upvotes: 6

Related Questions