记忆一个以集合为参数的函数

Question

我正在使用 Data.MemoCombinators (https://hackage.haskell.org/package/data-memocombinators-0.3/docs/Data-MemoCombinators.html) 来记忆一个函数，该函数将一个集合作为其参数并 returns 一个集合（这是一个人为的例子，除了接受很长时间才完成）：

test s = case Set.toList s of
         []     -> Set.singleton 0
         [x]    -> Set.singleton 1
         (x:xs) -> test (Set.singleton x) `Set.union` test (Set.fromList xs)

由于 Data.MemoCombinators 没有为集合实现 table，我想自己写一个：

{-# LANGUAGE RankNTypes #-}

import Data.MemoCombinators (Memo)
import qualified Data.MemoCombinators as Memo
import Data.Set (Set)
import qualified Data.Set as Set

set :: Ord a => Memo a -> ((Set a) -> r) -> (Set a) -> r
set m f = Memo.list m (f . Set.fromList) . Set.toList

这里是我的 test 应该被记录的：

test s = set Memo.integral test' s
    where
      test' s = case Set.toList s of
                []     -> Set.singleton 0
                [x]    -> Set.singleton 1
                (x:xs) -> test (Set.singleton x) `Set.union` test (Set.fromList xs)

Data.MemoCombinators 没有我清楚的文档，所以基本上我不知道我在做什么。

我的问题是：

Memo.list 函数的第二个参数是什么？它是列表元素的记忆器吗？
如何在不使用 Memo.list 的情况下直接为集合实现 table？这里想弄清楚如何在不使用某人的库的情况下手动实现记忆。例如，使用 Map。我见过使用无限列表记忆整数的示例，但在地图的情况下，我不知道如何初始化地图以及如何插入地图。

感谢您的帮助。

Answer 1

您对 test 的定义很好，尽管通常您会使用 Set 操作将 test 定义为集合上的函数。这是我正在谈论的示例：

-- memoize a function on Set Int
foo = set M.integral foo'
  where foo' s | Set.null s = 0
        foo' s = let a = Set.findMin s
                     b = Set.findMax s
                     m = (a+b) `div` 2
                     (lo,found,hi) = Set.splitMember m s
                 in if a >= b
                      then 1
                      else (if found then 1 else 0) + foo lo + foo hi

这是计算集合中元素数量的一种非常低效的方法，但请注意 foo' 是如何根据集合操作定义的。

关于你的其他问题：

what is the second parameter to the Memo.list function? Is it a memoizer for the elements of the list?

Memo.list 具有签名 Memo a -> Memo [a]，因此在表达式 Memo.list m f 中我们有：

m :: Memo a
f :: [a] -> r    -- some type r
Memo.list m f :: [a] -> r

所以 f 是您正在记忆的 [a] 上的函数，而 m 是接受类型 a.[=31 参数的函数的记忆器=]

how to implement a table for a set directly?

这取决于你所说的 "directly" 是什么意思。以这种方式记忆将涉及创建一个（可能是无限的）惰性数据结构。 string、integral 和 list 记忆器都使用某种形式的惰性特里树。这与命令式语言中的记忆非常不同，在命令式语言中，您显式检查哈希映射以查看您是否已经计算了某些内容并使用函数的值更新该哈希映射等。（顺便说一句 - 您可以在 ST 中进行这种记忆或 IO monads，它可能比 Data.Memocombinators 方法更好 - 需要考虑的事情。）

你通过传递给列表来记忆 Set a -> r 函数的想法是个好主意，但我会使用 to/from AscList:

set m f = Memo.list m (f . Set.fromAscList) . Set.toAscList

这样集合 Set.fromList [3,4,5] 将重新使用为记住 Set.fromList [3,4].

的值而创建的相同部分的 trie

Answer 2

what is the second parameter to the Memo.list function? Is it a memoizer for the elements of the list?

第一个参数m是列表元素的记忆器。第二个参数 f 是您要应用到列表的函数（也将被记忆）。

how to implement a table for a set directly, without using Memo.list? Here is would like to figure out how to implement memoization manually without using someone's library. For example, using a Map. I have seen examples that memoize integers using an infinite list but in case of a map I cannot figure out how to initialize the map and how to insert into it.

使用与 Data.MemoCombinators 相同的策略，您可以做一些类似于希望他们为列表做的事情。这种方法不为此使用显式数据结构，而是探索 Haskell 将内容保存在内存中和惰性求值的方式。

set :: Ord a => Memo a -> Memo (Set a)
set m f = table (f Set.empty) (m (\x -> set m (f . (x `Set.insert`))))
  where
  table nil cons set | Set.null set = nil
                     | otherwise    = uncurry cons (Set.deleteFindMin set)

您还可以使用显式数据结构（如 Map）在 Haskell 中使用记忆。我将使用 Fibonacci 示例来证明这一点，因为它更容易进行基准测试，但对于其他函数来说也是类似的。

让我们从简单的实现开始：

fib0 :: Integer -> Integer
fib0 0 = 0
fib0 1 = 1
fib0 x = fib0 (x-1) + fib0 (x-2)

然后Data.MemoCombinators提出这个实现：

import qualified Data.MemoCombinators as Memo

fib1 :: Integer -> Integer
fib1 = Memo.integral fib'
  where
  fib' 0 = 0
  fib' 1 = 1
  fib' x = fib1 (x-1) + fib1 (x-2)

最后，我的版本使用 Map:

import Data.Map (Map)
import qualified Data.Map as Map

fib2 :: Integer -> Integer
fib2 = fst . fib' (Map.fromList [(0, 0),(1, 1)])
  where
  fib' m0 x | x `Map.member` m0 = (Map.findWithDefault 0 x m0, m0)
            | otherwise         = let (v1, m1) = fib' m0 (x-1)
                                      (v2, m2) = fib' m1 (x-2)
                                      y = v1 + v2
                                  in (y, Map.insert x y m2)

现在，让我们看看他们的表现：

fib0 40: 13.529371s
fib1 40: 0.000121s
fib2 40: 0.000048s

fib0 已经太慢了。让我们对其他两个进行适当的测试：

fib1 400000: 6.234243s
fib2 400000: 4.022798s

fib1 500000: 8.683649s
fib2 500000: 5.781104s

对于我执行的所有测试，Map 解决方案实际上似乎优于 Memo 解决方案。但我认为 Data.MemoCombinators 的最大优势实际上是拥有如此出色的性能，而无需编写比天真的解决方案更多的代码。

更新：我改变了结论，因为我没有正确地进行基准测试。我在同一执行中进行了多次调用，在 500000 的情况下，无论第二次调用是什么（fib1 或 fib2），都花费了太长时间。

记忆一个以集合为参数的函数

memoizing a function that takes a set as parameter

haskell

memoization