I have some F# code that caches results for future lookup. My understanding is that dictionaries and other data structures that you add to require side effects. (i.e. changing the state of the dictionary) Is this correct? Is this considered impure or is this still in the model of side effect free computation.
let rec fib =
let dict = new System.Collections.Generic.Dictionary<_,_>()
fun n ->
match dict.TryGetValue(n) with
| true, v -> v
| false, _ ->
let fibN =
match n with
| 0 | 1 -> n
| _ -> fib (n - 1) + fib(n - 2)
dict.Add(n, fibN)
fibN
To restate what was mentioned in the comments, you can extract memoization into a higher order function that would return a memoized version of the function passed in as an argument:
let memoize f =
let dict = new System.Collections.Generic.Dictionary<_,_>()
fun x ->
match dict.TryGetValue(n) with
| true, v -> v
| false, _ ->
let v = f x
dict.Add(x, v)
v
By doing that, you actually can make the memoized function pure, and memoization an implementation detail. The code you posted, where those two concerns are tangled together, is not as simple to reason about as it could be.
Note that memoizing a recursive function is a little tricky - you need to structure the function to memoize in a way that lends itself to memoization.
A separate issue here are the concurrency problems you can run into. To combat those, you could either have a lock around the dict.Add:
...
let v = f x
lock dict <| fun () ->
if not <| dict.ContainsKey(x) then
dict.Add(x, v)
v
or instead of Dictionary have a ref cell holding a Map (in which case any concurrency issues you might have are still there, but are no longer catastrophic in nature).