Clever Geek Handbook

Is memory possible without side effects

I have F # code that caches results for future searches. I understand that dictionaries and other data structures you add require side effects. (i.e. changing the state of the dictionary). Is it correct? It is considered impure or is it still in the free side-effect computation model.

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
+3


source to share


2 answers


To echo what was mentioned in the comments, you can extract the memoization into a higher-order function, which will return the memoized version of the function passed 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

This way you can actually make memoized a function clean and memoization an implementation detail. The code you posted where these two problems get confused is not as straightforward to reason as possible.

Note that the imaginary recursive function is a little tricky - you need to structure the memoize function in such a way that it is faked for memoization.



A separate issue here is the concurrency issues you may encounter. To combat them, you can either block around dict.Add

:

...
let v = f x
lock dict <| fun () ->
    if not <| dict.ContainsKey(x) then
       dict.Add(x, v)
v

or instead Dictionary

have a cell ref

containing Map

(in this case, any concurrency issues you might still have but are not catastrophic in nature).

+5


source


A memo function stores the result, so it doesn't need to compute the result on subsequent calls with the same arguments. The fact that the result is saved is a side effect and also a defining property of the memoized function. So I conclude that the answer to your question is no.

To answer your comment about storing the wrong value in a dict; yes, you are correct, but there is another problem that does not include incorrect results. The Dictionary class is not thread safe. If two threads are trying to read and / or write to the dictionary at the same time, you will most likely get an exception. For example:

let data = [| 1 .. 20 |]
let fibs = data |> Array.Parallel.map fib

I didn't get any exceptions when I ran this multiple times in F # interactively, but with some modifications I got a System.ArgumentException:



An item with the same key has already been added.

The changes were like this; in each case I got an exception on the first or second try:

  • The tool performs the function of printing diagnostic information using printfn

  • Change the numeric type to uint64

    (remove printfn

    diagnostics)
  • Change the numeric type to float

    (i.e. System.Double)
  • Change the numeric type to bigint

+1


source






More articles:


All Articles