Overlapping subproblems in immutable languages

Question

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?

• Robert Harvey: Have a look at Okasaki's book, or his thesis.
• Erik Eidt: I have not played with these, but LENSes sound interesting: "... you can think of lenses as Haskell's "getters" and "setters", but we shall see that they are far more powerful." (not sure if they are in Okasaki's book; didn't see lenses in his thesis.)

Answer 1

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.

• Jörg W Mittag: As Clojure's Rich Hickey once said, Clojure's data structures are O(log_32 n), and the 32 is pretty darn important, even if technically O(log_32 n) = O(log n).

Answer 2

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.