Haskell 缓存函数结果

Question

我有一个函数，它接受一个参数并产生一个结果。不幸的是，该函数需要很长时间才能产生结果。使用相同的输入经常调用该函数，这就是为什么如果我可以缓存结果会很方便。就像

let cachedFunction = createCache slowFunction
in (cachedFunction 3.1) + (cachedFunction 4.2) + (cachedFunction 3.1)

我正在研究 Data.Array 一样，虽然该数组是惰性的，但我需要用一个对列表（使用 listArray）来初始化它 - 这是不切实际的。如果“键”是“Double”类型，我根本无法初始化它，即使理论上我可以为每个可能的输入分配一个整数，我也有数万个可能的输入，但实际上我只使用了少数。我需要使用函数而不是列表来初始化数组（或者最好是哈希表，因为只会使用少数结果）。

更新：我正在阅读记忆文章，据我了解，MemoTrie 可以按照我想要的方式工作。或许。有人可以尝试生成“cachedFunction”吗？更适合需要 2 个 Double 参数的慢速函数？或者，另一种方法是，在 ~ [0.1 亿] 的域中采用一个 Int 参数，而不会耗尽所有内存？

Answer 1

嗯，有Data.HashTable。不过，哈希表往往不能很好地处理不可变数据和引用透明性，因此我认为它没有太多用途。

对于少量值，将它们存储在搜索树（例如 Data.Map）中可能足够快。如果您可以忍受对 Double 进行一些修改，更可靠的解决方案是使用类似 trie 的结构，例如 Data.IntMap；它们的查找时间主要与密钥长度成正比，并且集合大小大致恒定。如果 Int 限制太多，您可以在 Hackage 上深入研究，找到使用密钥类型更灵活的 trie 库。

至于如何缓存结果，我认为你想要的通常称为“memoization”。如果您想按需计算和记忆结果，该技术的要点是定义一个包含所有可能结果的索引数据结构，这样当您请求特定结果时，它只强制获得您想要的答案所需的计算。常见的示例通常涉及对列表进行索引，但相同的原则应该适用于任何非严格的数据结构。根据经验，非函数值（包括无限递归数据结构）通常会被运行时缓存，但函数结果不会被缓存，因此技巧是将所有计算包装在一个顶级定义中，该定义不会取决于任何参数。

编辑： MemoTrie 示例啊嘿！

这是一个快速而肮脏的概念证明；可能存在更好的方法。

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
import Data.MemoTrie
import Data.Binary
import Data.ByteString.Lazy hiding (map)

mangle :: Double -> [Int]
mangle = map fromIntegral . unpack . encode

unmangle :: [Int] -> Double
unmangle = decode . pack . map fromIntegral

instance HasTrie Double where
    data Double :->: a = DoubleTrie ([Int] :->: a)
    trie f = DoubleTrie $ trie $ f . unmangle
    untrie (DoubleTrie t) = untrie t . mangle

slow x 
    | x < 1 = 1
    | otherwise = slow (x / 2) + slow (x / 3)

memoSlow :: Double -> Integer
memoSlow = memo slow

请注意 MemoTrie 包使用的 GHC 扩展；希望这不是问题。将其加载到 GHCi 中，然后尝试使用 (10^6) 或 (10^7) 之类的内容调用 slow 与 memoSlow 来查看它的实际情况。

将其推广到采用多个参数或其他参数的函数应该相当简单。有关使用 MemoTrie 的更多详细信息，您可以找到 这篇博客文章它的作者很有帮助。

Answer 2

请参阅记忆

Answer 3

GHC 的运行时系统中有许多工具明确支持记忆化。

不幸的是，记忆化并不是真正的一刀切，因此我们需要支持几种不同的方法来满足不同的用户需求。

您可能会发现 1999 年的原始文章很有用，因为它包含多个实现作为示例：

扩展存储管理器：Haskell 中的弱指针和稳定名称 作者：Simon Peyton Jones、Simon Marlow 和 Conal Elliott

Answer 4

我将添加我自己的解决方案，这似乎也很慢。第一个参数是一个返回 Int32 的函数 - 这是参数的唯一标识符。如果您想通过不同的方式（例如通过“id”）唯一地标识它，则必须将 H.new 中的第二个参数更改为不同的哈希函数。我将尝试找出如何使用 Data.Map 并测试是否能获得更快的结果。

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

Answer 5

您可以将慢速函数编写为高阶函数，返回函数本身。因此，您可以在慢速函数内进行所有预处理，并在返回的（希望是快速的）函数中进行每次计算中不同的部分。一个例子可能是这样的：
（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

Answer 6

我有数万个可能的输入，但实际上我只使用了少数。我需要使用函数而不是列表来初始化数组......

我会选择 listArray (start, end) (map func [start..end])

• func 上面并没有真正被调用。 Haskell 很懒，会创建 thunk，当实际需要该值时才会对其进行求值。
• 使用普通数组时，您始终需要初始化其值。所以无论如何，创建这些 thunk 所需的工作是必要的。
• 几万远不是很多。如果你有数万亿，那么我建议使用哈希表 yada yada

Answer 7

我具体不了解 haskell，但是如何将现有答案保留在某些散列数据结构（可能称为字典或散列图）中？您可以将慢速函数包装在另一个函数中，该函数首先检查映射，并且仅在未找到答案时才调用慢速函数。

您可以通过将地图的大小限制为一定大小来使其变得更奇特，当达到该大小时，丢弃最近最少使用的条目。为此，您还需要保留键到时间戳映射的映射。