3

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
    Have a look at Okasaki's book, or his thesis. – Robert Harvey Jul 19 '16 at 18:30
  • 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.) – Erik Eidt Jul 19 '16 at 19:28
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.

  • 1
    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). – Jörg W Mittag Jul 19 '16 at 23:25
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.