Haskell, кэширующий результаты функции

См. мемоизация

Вы можете написать медленную функцию как функцию более высокого порядка, возвращающую саму функцию. Таким образом, вы можете выполнять всю предварительную обработку внутри медленной функции и той части, которая отличается в каждом вычислении в возвращаемой (надеюсь, быстрой) функции. Пример может выглядеть так: (код SML, но идея должна быть ясной)

fun computeComplicatedThing (x:float) (y:float) = (* ... some very complicated computation *)
fun computeComplicatedThingFast = computeComplicatedThing 3.14 (* provide x, do computation that needs only x *)
val result1 = computeComplicatedThingFast 2.71 (* provide y, do computation that needs x and y *)
val result2 = computeComplicatedThingFast 2.81
val result3 = computeComplicatedThingFast 2.91

Я добавлю собственное решение, которое тоже кажется довольно медленным. Первый параметр - это функция, которая возвращает Int32 - уникальный идентификатор параметра. Если вы хотите однозначно идентифицировать его разными способами (например, по 'id'), вам нужно изменить второй параметр в H.new на другую хеш-функцию. Я постараюсь узнать, как использовать Data.Составьте карту и проверьте, получу ли я более быстрые результаты.

import qualified Data.HashTable as H
import Data.Int
import System.IO.Unsafe

cache :: (a -> Int32) -> (a -> b) -> (a -> b)
cache ident f = unsafePerformIO $ createfunc
    where 
        createfunc = do
            storage <- H.new (==) id
            return (doit storage)

        doit storage = unsafePerformIO . comp
            where 
                comp x = do
                    look <- H.lookup storage (ident x)

                    case look of
                        Just res -> return res
                        Nothing -> do
                            result <- return (f x)
                            H.insert storage (ident x) result
                            return result

У меня есть несколько десятков тысяч возможных входов, а на самом деле я использую только горстку. Мне бы потребовалось инициализировать массив ... с помощью функции вместо списка.

Я бы использовал listArray (start, end) (map func [start..end])

• func на самом деле не вызывалась выше. Haskell ленив и создает thunks, которые будут вычисляться, когда значение будет действительно необходимо.
• При использовании обычного массива всегда нужно инициализировать его значения. Так что работа, необходимая для создания этих элементов, все равно необходима.
• Несколько десятков тысяч - это далеко не много. Если бы у Вас были триллионы, то я бы предложил использовать хэш-таблицу yada yada

Я не знаю конкретно haskell, но как насчет сохранения существующих ответов в некотором хешированном виде? структура данных (можно было бы назвать словарем или хэш-картой)? Вы можете заключить свою медленную функцию в другую функцию, которая сначала проверяет карту и вызывает медленную функцию только в том случае, если она не нашла ответа.

Вы можете сделать это необычным, ограничив размер карты определенным размером и, когда он достигнет этого размера, выкинув наименее использовавшуюся запись. Для этого вам дополнительно потребуется сохранить карту сопоставлений ключей и отметок времени.

В системе времени выполнения GHC есть ряд инструментов, специально предназначенных для поддержки мемоизации.

К сожалению, мемоизация не является универсальной задачей, поэтому существует несколько различных подходов, которые нам необходимо поддерживать, чтобы справиться с различными потребностями пользователей.

Вы можете найти оригинальную запись 1999 года полезной, поскольку она включает в себя несколько реализаций в качестве примеров:

Расширение диспетчера хранилища: слабые указатели и стабильные имена в Haskell Саймона Пейтона Джонса, Саймона Марлоу и Конала Эллиотта