2

通过共同递归，我的意思是展开一棵树，例如使用anaEd Kmett递归方案中的态射

通过重新组合树，我的意思是共享结构的图。例如，二项式期权定价树或帕斯卡三角形。这两者都有一些对称性，所以为了效率，我们希望避免重新计算树的一部分，而是重新使用已经计算过的分支。

注意这个问题不是关于计算上述示例中的值的一些聪明方法；这是关于递归的一般问题。

例如，对于期权定价，可以像这样生成树：

data Tree x = Leaf x | Branch x (Tree x) (Tree x)
ana \(x, depth) ->
  if depth == maxDepth
    then LeafF x
    else BranchF x (p * x, depth + 1) ( (1.0 - p) * x, depth + 1)     -- p < 1.0

因此，“向上”分支中p * x的值为 ，“向下”分支中的值为(1-p) * x。由于这种对称性，“up”后跟“down”节点将具有与“down”后跟“up”分支相同的值。它也是整个子树。

我认为有可能以State某种方式传递包含已计算节点的哈希图。

或者，如果我能以某种方式访问​​已经计算过的子树，我可以将它作为态射中的 aLeft传入apo。

是否有一些现有的态射允许这样做？或者我可以自己编码吗？

4

1 回答 1

1

ana定义一个递归函数x -> Tree a（给定一个 colgebra alg :: x -> TreeF a x）。您可以ana使用专门的固定点运算符定义记忆化版本（而通常的定义或多或少等同于 using fix），例如，在MemoTrie 库中找到。

memoFix :: (...) => ((a -> b) -> (a -> b)) -> (a -> b)
-- for some constraints "(...)" depending on the implementation.

-- ana': Memoized version of ana

type Memo a b = ((a -> b) -> (a -> b)) -> a -> b

memoAna :: Memo x (Tree a) -> (x -> TreeF a x) -> x -> Tree a
memoAna memo alg = memo $ \ana_ x ->
  case alg x of
    LeafF a -> Leaf a
    BranchF a x1 x2 -> Branch a (ana_ x1) (ana_ x2)

ana' :: HasTrie x => (x -> TreeF a x) -> x -> Tree a
ana' = memoAna memoFix

这确保了从同一种子生成的所有树x实际上都是同一棵树。

您还必须注意种子的类型。在您的示例中，操作(Double, Int)的不精确性Double使记忆变得不可靠。所以你还需要修改代数。例如，由于价格始终为 形式p^i (1-p)^(depth-i)，因此您可以记住索引i。

optionsAlg' :: Num a => a -> (Int, Int) -> TreeF a (Int, Int)
optionsAlg' p (ups, depth) =
  if depth >= maxDepth then
    LeafF price
  else
    BranchF price (ups+1, depth+1) (ups, depth+1)
  where
    price = p ^ ups * (1 - p) ^ (depth - ups)

记忆化的实现有各种权衡。根据您的特定用例，可能需要进一步优化和更多适应。

于 2020-12-27T20:00:49.227 回答