memoizeAsync.fsx

let lockObj = obj()
let printLock s = lock lockObj (fun () -> printfn "%s" s)

let memoizeAsyncAsTask f =
    let cache = System.Collections.Concurrent.ConcurrentDictionary()
    let f' x = Async.StartAsTask (f x)
    fun x -> async { return cache.GetOrAdd(x, lazy f' x).Value.Result }

[<Struct>]
type MemoizeAsyncState<'a> = | Running of sem:System.Threading.SemaphoreSlim | Completed of 'a

let memoizeAsync f =
    let cache = System.Collections.Concurrent.ConcurrentDictionary()
    fun x -> async {
        match cache.GetOrAdd(x, valueFactory = fun _ -> Running(new System.Threading.SemaphoreSlim 1)) with
        | Running sem as r ->
            if sem.Wait(0) then
                printLock (sprintf "computing %A" x)
                let! y = f x
                cache.TryUpdate(x, Completed y, r) |> ignore
                sem.Release() |> ignore
                return y
            else
                printLock (sprintf "waiting for %A" x)
                sem.Wait()
                sem.Release() |> ignore
                let (_, Completed y) = cache.TryGetValue x
                return y
        | Completed y -> return y
    }

let a = memoizeAsync (fun x -> async {printLock (sprintf "Run %i" x); return x})
[1..10] |> List.map (fun x -> a (x % 2)) |> Async.Parallel |> Async.RunSynchronously

I think there may be a scenario where we come in line 17 but by then the value is already computed and available in the cache. The scenario is similar to the double-lock singleton pattern. Also, the locks dictionary may grow unbounded (as may the cache dictionary but I would replace it with IMemoryCache instead).

I think there may be a scenario where we come in line 17 but by then the value is already computed and available in the cache. The scenario is similar to the double-lock singleton pattern.

This is just my attempt how to do manual locking and definitely there could be bugs.

You are right about the problem. I didn't want to create the lock for every read, but maybe it is better to be on safe side and put locks.GetOrAdd on top of async.

Another idea I had is to use MailboxProcessor. It seems heavy-weight for this use case, but something like this can be written fail-proof in it.

Also, the locks dictionary may grow unbounded (as may the cache dictionary but I would replace it with IMemoryCache instead).

Yes, I didn't attempt to solve this. Maybe some way to use one dict instead two would be better?

Updated with fixed version that use only one Dictionary. Multiple eval shouldn't be possible here.