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.

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.