Caching function result f#

Question

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.

See this answer about memoization: http://stackoverflow.com/questions/833180/handy-f-snippets/851449#851449 — Benjol, Jan 04 '10 at 12:53

Sedat Kapanoglu · Accepted Answer · 2021-05-07T01:38:12.433

3

Here is the Internet Archive link.

edited May 07 '21 at 01:38

answered Dec 29 '09 at 20:17

Sedat Kapanoglu

46,641
25
114
148

oh, lazy initialization. thank you! it's not a function, it's data, that's the point – Valentin Golev Dec 29 '09 at 20:20
@ebb it's a shame :( deleting the answer now. – Sedat Kapanoglu Aug 20 '13 at 09:25
1

@SedatKapanoglu the first link to cs.hubfs.net appears to redirect to a web page with questionable intentions as of 2021. You may want to remove it and leave only the archive link. – GrumpyRodriguez May 06 '21 at 14:35
1

@GrumpyRodriguez thank you for reporting it, removed the link. – Sedat Kapanoglu May 07 '21 at 01:38

score 2 · Answer 2 · answered Dec 30 '09 at 14:39

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.

thanks! actually I created a Sequence and put it into |> Seq.cache. Your function is also great, thank you, I'll use it for something else — Valentin Golev, Dec 31 '09 at 07:01

Caching function result f#

2 Answers2