Запомните функцию типа() → 'a

Ответ 1

Причина сбоя функции заключается в том, что F # представляет unit (), используя null типа unit. Словарь не позволяет принимать значения null в качестве ключей, и поэтому он терпит неудачу.

В вашем конкретном случае в memoizing функции типа unit -> 'a не так много смысла (потому что для этого лучше использовать lazy), но есть и другие случаи, когда это было бы проблемой - например None также представлен null, поэтому это тоже не удается:

let f : int option -> int = memoize (fun a -> defaultArg a 42)
f None

Самый простой способ исправить это - обернуть ключ в другой тип данных, чтобы он никогда не был null:

type Key<'K> = K of 'K

Затем вы можете просто обернуть ключ конструктором K, и все будет хорошо работать:

let memoize f =
    let cache = System.Collections.Generic.Dictionary()
    fun x ->
        if cache.ContainsKey(K x) then 
            cache.[K x]
        else 
            let res = f x
            cache.[K x] <- res
            res

Ответ 2

Я только что обнаружил, что последняя функция memoize на том же веб-сайте, используя Map вместо Dictionary работает для 'a Option -> 'b и () -> 'a тоже:

let memoize1 f =
    let cache = ref Map.empty
    fun x ->
        match (!cache).TryFind(x) with
        | Some res -> res
        | None ->
            let res = f x
            cache := (!cache).Add(x,res)
            res

Ответ 3

Запоминание, имеющее чистую функцию (а не только тип unit -> 'a, но любой другой) в качестве ключевого ключа невозможно, потому что функции вообще не имеют сопоставления равенства для причины.

Может показаться, что для этого конкретного типа функции unit -> 'a можно было бы создать собственный сопоставитель сравнений. Но единственный подход для реализации такого компаратора за пределами экстремумов (отражение, IL и т.д.) Вызывал бы функцию поиска как f1 = f2 iff f1() = f2(), что, по-видимому, сводит на нет любое улучшение производительности, ожидаемое от memoization.

Итак, возможно, как уже отмечалось, для этого случая оптимизация должна строиться вокруг шаблона lazy, но не memoization one.

UPDATE: действительно, после второго взгляда на вопрос, который все говорит выше о функциях, отсутствующих в сравнении с равным сравнением, правильно, но неприменимо, потому что memoization происходит внутри каждой функции индивидуально cache от замыкания. С другой стороны, для этого специфического вида функций с сигнатурой unit->'a, то есть не более одного значения аргумента, использование Dictionary с большей частью одной записи является излишним. Следующая аналогичная, но более простая реализация с одним сохраненным значением будет делать:

let memoize2 f =
    let notFilled = ref true
    let cache = ref Unchecked.defaultof<'a>
    fun () ->
        if !notFilled then
            cache := f ()
            notFilled := false
        !cache

используется как let foo = memoize2(fun () -> ...heavy on time and/or space calculation...) с первым использованием foo() выполнением и сохранением результата вычисления и всего последующего foo() просто повторного использования сохраненного значения.

Ответ 4

Решение с измененным словарем и одним словарным поиском: let memoize1 f = // printfn "Dictionary" let cache = System.Collections.Generic.Dictionary() fun x -> let result, value = cache.TryGetValue(x) match result with | true -> value | false -> // printfn "f x" let res = f x cache.Add(x, res) res