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

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