是否可以使用（协同）递归创建高效的重组树？

Question

通过共同递归，我的意思是展开一棵树，例如使用来自 Ed Kmett 的 recursion-schemes

的 ana 态射

我所说的重新组合树是指共享结构的图。例如，二项式 option pricing tree, or Pascal's triangle。这两者都有一定的对称性，所以为了效率，我们希望避免重新计算树的一部分，而是重新使用已经计算过的分支。

n.b。这个问题不是关于计算上述示例中的值的一些巧妙方法；这是一个关于递归的一般问题。

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

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

所以 'up' 分支中的值是 p * x 而 'down' 分支中的值是 (1-p) * x。由于这种对称性，'up' 后跟 'down' 节点将与 'down' 后跟 'up' 分支具有相同的值。它将是整个子树。

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

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

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

Answer 1

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

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)

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

是否可以使用（协同）递归创建高效的重组树？

Is it possible to create efficient recombining trees using (co)recursion?

recursion

binary-tree

haskell

recursion-schemes