Whenever I solve a problem with overlapping subproblems, I reach for memoization because it’s so simple to implement. However, memoizing in an immutable language that doesn’t have built-in support for memoizing without copying the memory on every insert isn’t that efficient.
What techniques are common in immutable languages to solve the overlapping subproblems problem in dynamic programming?
2
You use memoization. Inserts and lookups on an immutable persistent hash table are effectively constant. While technically that constant value is a little bit longer than a mutable data structure, in practice you won’t usually care. Here’s an example from one of my previous answers where I memoized overlapping collatz sequences to get a result that returned pretty much instantaneously in my REPL.
1
Most so-called immutable languages provide a back door that allows you to escape from the immutability amd use mutable data structures. For example, Haskell provides the ST monad and the ability to store mutable data with the IO monad. It also has a function “unsafePerformIO” which you can use to execute IO operations in a context that is not declared to use the IO monad. You can use these basic building blocks to perform memoization (and as such an implementation should be provably referentially transparent, it is not unsafe to do so (despite the stern-sounding warning in the function name)).
I can therefore see there possible signatures for a memoize function:
mwmoizeST :: (a -> b) -> a -> ST s b
memoizeIO :: (a -> b) -> a -> IO b
memoizeUmsafeIO :: (a -> b) -> a -> b
All could be useful in different circumstances.
Other similar languages provide similar escape hatches – they have to, as sometimes a mutable structure is the only way to achieve satisfactory performance.
0