Fp-ts: Add `memoize`

[vicrac]

🚀 Feature request

Add helper for memoization:

const f = arg => {
    console.log("some costly computations")
    return result
}

const memoized = memoize(f)

// logs "Some costly computation"
memoized(1)

// logs "Some costly computation"
memoized(2)

// Cache hit, element returned without computation
memoized(1)

Desired Behavior

It would be nice if memoization was included in fp-ts. It's such a fundamental concept in functional programming I nearly regret it's not shipped with the language itself ;) I would also appreciate fp-ts being self-contained, battery included package for functional programming, without need to install Ramda/lodash or writing own helpers for such a basic feature.

Suggested Solution

If this is approved, I can open a PR on that

Who does this impact? Who is this for?

All users of pure but costly functions ;)

Your environment

| Software | Version(s) |
| ---------- | ---------- |
| fp-ts | 2.4 |
| TypeScript | 3.7.3 |

[raveclassic]

Again - what bounds do we define for fp-ts to include such helpers? IMO this is definitely smth for an external library.

[vicrac]

@raveclassic I agree - a consistent guide/standard for placing new features/shaping API is very desirable.

On the other hand, I am pretty sure memoization should live in the very core of any functional library - as I said, I would welcome including it in the language itself ;) (yeah, it's not gonna happen, but imagine e.g. pure function f(n: number) { ... } - of course it has its own limitations, but still... ;))

[raveclassic]

When we introduce memoization we should always think of the following questions:

• what is the size of our cache?
• if cache is infinite, then how do we deal with non-primitive arguments? how do we create the key? Do we have any way to clear the memory?
• if cache is finite then what is its size, 1-level or greater?
• what is the underlying implementation of the cache? Is it possible to reuse an existing library that's already in the project?
• and in the end - should we memoize the core itself?

All these question are too specific for such an abstract library like fp-ts.

[vicrac]

@raveclassic Fair point, let's see what @gcanti thinks about it.

Just for transparency, I usually implement cache as simple Map (which allows using any values as keys, including objects) with limited size (and invalidating oldest elements). I limit memoization to single-argument functions for simplicity.

[gkamperis]

Personally I see fp-ts as a lib that implements the theories (category, abstract algebra, etc). with some common usage implementations.

Caching is a huge subject onto its own - notoriously difficult.
memoization is a practical consequence of functional purity.

Personally I see little reason why it should be tied into fp-ts itself.

Another example would be immutability.
It would be great if we can also get it baked in but it is not a FP concern.

So maybe an ecosystem lib that provides this functionality as a configurable opt-in (like @ngrx does re immutability) would be the best solution.

[gcanti]

Ideally an (fp-ts) API should have a single, obvious implementation.
Otherwise, i.e. if we must make an opinionated choice, it would be better a dedicated library.