Caching function result f#

Question

Hi there!

I have a function which is constant to its argument, for example

let is_prime x = (test)

But it's pretty large and slow. So I want the result of it to be calculated only once while I'm calling it as often as I want.

I've tried to do it in a way I did it in not functional languages:

let _is_prime x = (test)

let mutable _is_prime_primes = []
let mutable _is_prime_tested = []

let is_prime x =
    if List.exists (fun el -> el = x) _is_prime_primes then
        true
    else
        if List.exists (fun el -> el = x) _is_prime_tested then
        false
    else 
        let result = _is_prime x
        if result then _is_prime_primes <- x :: _is_prime_primes
        _is_prime_tested <- x :: _is_prime_tested
        result

But I think I'm deeply wrong. Caching such result must be something very common and simple for functional languages.

Answer 1

Here is a thorough thread on the subject.

Answer 2

I'm having trouble testing this in FSI, but it should be fine in a normal F# project.

let cache f =
    let dict = new Dictionary<_,_>()
    fun n ->
        if dict.ContainsKey(n) then dict.[n]
        else
            let r = f n
            dict.[n] <- r
            r

Its signature is ('a->'b) -> ('a->'b) when 'a : equality. It takes non-curried function and returns another with an identical signature. The function given is only called once for each unique argument that is passed to it. This makes it good for expensive pure functions. This cache function however is not pure, and not thread-safe. Here's an example of its usage:

let slow n = // 'a -> 'a
    System.Threading.Thread.Sleep(1000)
    n

let fast = cache slow // 'a -> 'a

Calling fast 1 will cause a second of sleep the first time you call it. Each successive call with the same parameter will return the value instantly.