logo标签列表

记忆化递归方案

haskelltypesrecursion-schemescatamorphismanamorphism
5

能否对递归方案进行记忆化？如果可以，应该如何实现？

例如，以下代码使用了anamorphism和catamorphism。

newtype Fix f = In (f (Fix f))

deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Ord (f (Fix f))) => Ord (Fix f)
deriving instance (Show (f (Fix f))) => Show (Fix f)

out :: Fix f -> f (Fix f)
out (In f) = f

-- Catamorphism
type Algebra f a = f a -> a

cata :: (Functor f) => Algebra f a -> Fix f -> a                                                                                                                                
cata f = f . fmap (cata f) . out                                                                                                                                                
                                                                                                                                                                                
-- Anamorphism                                                                                                                                                                  
type Coalgebra f a = a -> f a                                                                                                                                                   
                                                                                                                                                                                
ana :: (Functor f) => Coalgebra f a -> a -> Fix f                                                                                                                               
ana f = In . fmap (ana f) . f

解决格子路径问题：

latticePaths m n = cata countPathsAlgNoMemo (ana buildLattice (m, n))                                                                           
 
-- recursive solution without dynamic programming                                                                                                    
buildLattice :: (Int, Int) -> LeafBTreeF Int (Int, Int)                                                                                              
buildLattice (m, n)                                                                                                                                  
        | m == 0 && n == 0 = LeafBTreeLeafF 1                                                                                                        
        | m < 0 || n < 0 = LeafBTreeLeafF 0                                                                                                          
        | otherwise = LeafBTreeNodeF (m - 1, n) (m, n - 1)
                                                                                                                                                     
countPathsAlgNoMemo :: LeafBTreeF Int Int -> Int                                                                                                
countPathsAlgNoMemo (LeafBTreeLeafF n) = n
countPathsAlgNoMemo (LeafBTreeNodeF a b) = a + b

这种方法效率低下，因为子问题没有被存储和重复使用而是重新计算。我想知道是否有一种方法可以存储（或让Haskell编译器存储）先前计算过的子问题。

我查看了一些与记忆化多态函数相关的资源（http://blog.sigfpe.com/2009/11/memoizing-polymorphic-functions-with.html，http://conal.net/blog/posts/memoizing-polymorphic-functions-part-two），但是还没有能够理解它们如何适用于此处。

注意：我特别关注apomorphism/paramorphism和anamorphism/catamorphism是否可以进行记忆化（或者是否有其他解决方案可以使用这些递归方案来存储子问题）。我知道histomorphism和dynamorphism适合解决动态规划问题，但出于我的目的，我想将重点限制在apo/para或ana/cata上。

我的paramorphism和apomorphism：

-- Paramorphism
type RAlgebra f a = f (Fix f, a) -> a                                                                                          
        
para :: (Functor f) => RAlgebra f a -> Fix f -> a
para rAlg = rAlg . fmap fanout . out
        where fanout t = (t, para rAlg t)
                                                                                                                                                                                
-- Apomorphism
type RCoalgebra f a = a -> f (Either (Fix f) a)                                        
                                                                                       
apo :: Functor f => RCoalgebra f a -> a -> Fix f                                       
apo rCoalg = In . fmap fanin . rCoalg                                                                                                                                           
        where fanin = either id (apo rCoalg)
1个回答
2

更新：请参见下面有关参数形态/去参形态组合的内容。

请注意，单独对和进行记忆化是没有意义的。问题在于从头开始构建新的格子：

ana buildLattice (20,20)

实际上，这比从预生成的内存副本中读取该结构要容易得多。这就像记忆化replicate 1000000000 'x'一样。这毫无意义。

cata countPathsAlg也是如此。计算路径数很容易。难点在于遍历结构（无论是执行计算还是将其作为键查找到备忘录表中）。如果您想有效地进行记忆化catamorphism，则需要使用简单的键表示大型结构。但是我们已经有了用于生成这些结构的anamorphism的简单键值！

换句话说，为了使此计算适合记忆化，您需要通过融合catamorphism和anamorphism来消除中间数据结构。

这并不太困难。假设我们有：

h = cata f . ana g

因此，它遵循：

h
= cata f . ana g
= f . fmap (cata f) . out . In . fmap (ana g) . g
= f . fmap (cata f . ana g) . g
= f . fmap h . g

请注意，这是来自“recursion-schemes”包的“refold”（又名“hylo”）代码块：
hylo f g = h where h = f . fmap h . g

针对您的示例，我们有融合递归：

latticePaths :: (Int, Int) -> Int
latticePaths = countPathsAlg . fmap latticePaths . buildLattice

可以很容易地使用诸如memoize包进行记忆：

import Data.Function.Memoize

latticePaths :: (Int, Int) -> Int
latticePaths = h where h = memoize (countPathsAlg . fmap h . buildLattice)

main = print $ latticePaths (100,100)

更一般地说，任何一个 hylomorphism 都可以使用以下方式进行记忆化：

hylo_memo f g = h where h = memoize (f . fmap h . g)

无法对参数形式和自然形式的组合进行完全记忆化。存在两个问题。

首先，当一个自然形式产生一个Left时，它可以产生任意复杂的结构。即使您可以记忆化该结构的根（因为它由a值键入），也没有有效的方法来记忆化该结构中相同的子问题。例如，假设一个自然形式产生一个由1000个相同分支组成的Left玫瑰树，每个分支都有一百万个节点。发现所有1000个分支都是相同的并且可以共享相同的解决方案的唯一方法是遍历每个分支中的一百万个节点以进行比较。

其次，参数形式计算通常取决于当前节点的完整结构，而不仅仅是代数定义的本地结构之前计算的参数形式结果的“小”组合。例如，考虑在玫瑰树上进行参数形式计算，该计算将子树中节点值出现的次数相加，并将这些计数加起来，假设它的实现如下：

data Rose a t = Rose a [t]
refCount :: (Eq a) => RAlgebra (Rose a) Int
refCount (Rose a bs)
    -- reference counts from subnodes
  = sum (map snd bs)
    -- occurrences of "a" in the branches
  + sum (map (countValues a . fst) bs)

-- count number of "a"s in the tree
countValues :: (Eq a) => a -> Fix (Rose a) -> Int
countValues a = ...

请注意，一旦我们得到了“子问题”的结果，我们所拥有的只是该树中的总引用计数。如果这棵树出现在五个不同的父节点下，我们可以重复使用这个结果，但我们仍然需要搜索整个树来构建它们的计数，以满足五个不同的父节点值。
这并不意味着记忆化是无用的。我们可以记忆化apomorphism的Right部分，并且即使需要完整的结构遍历（例如上面的refCount），paramorphism结果的记忆化仍然可能是有用的（部分记忆化将复杂度从立方降至二次）。
因此，如果您继续扩展：
h
= para f . apo g
= f . fmap ((\t -> (t, para f t)) . either id (apo g)) . g
= f . fmap k . g
  where k = \case Left t -> (t, para f t)
                  Right a -> (apo g, h a)

我们可以实现部分记忆化：

paraApo :: (Ord a, Functor f) => RAlgebra f b -> RCoalgebra f a -> a -> b
paraApo f g = h
  where h = memo $
          f . fmap k . g
          where k = \case Left t -> (t, para f t)
                          Right a -> (apo g a, h a)

这可能是有用的。未记忆化的部分将是当apo产生一个Left时的para f t和由apo g a在Right分支中产生的第一个参数的para的潜在昂贵操作。

catamorphism/apomorphism组合也是部分可记忆化的。我们仍然面临着apo可以产生具有任意不可记忆结构的Left的问题，但apo的Right可以完全记忆化。

h
= cata f . apo g
= f . fmap (cata f . either id (apo g)) . g
= f . fmap k . g
  where k = \case Left t  -> cata f t      -- non-memoizable
                  Right a -> h a           -- memoizable
这对于 anamorphism 之后的 catamorphism 很有效，但是同样的想法能否用于 apomorphism 之后的 paramorphism 呢？我已经在问题中添加了两者的定义。目前我在 h = rAlg.fmap (fanout.fanin).rCoalg 处卡住了。 - cocorudeboy
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接