在 Haskell 中计算递归关系

发布于 2024-10-26 04:58:12 字数 795 浏览 1 评论 0原文

你好，StackOverflow。

假设我有两个用于计算的递归关系 S(i,j)

$S_{i,j +1} = X_{PA}S_{i,j} + \frac{1}{2p}(iS_{i-1,j}+jS_{i,j-1}) \\ S_{i+1, j} = X_{PB}S_{i,j} + \frac{1}{2p}(iS_{i-1,j}+jS_{i,j-1})$

我想计算值 < em>S(0,0)、S(0,1)、S(1,0)、S(2,0) 等等......以渐近最优的方式。用铅笔和纸几分钟就可以发现它展开成树状结构，可以通过多种方式横向移动。现在，树以后不太可能有用，所以现在我希望生成像 [[S(00)],[S(10),S(01)],[S(20) 这样的嵌套列表),S(21),S(12),S(02)],...]。我创建了一个函数来生成 S(i,0) （或 S(0,j)，取决于第一个参数）的平面列表：

osrr xpa p predexp = os00 : os00 * (xpa + rp) : zipWith3 osrr' [1..] (tail osrr) osrr
  where
    osrr' n a b = xpa * a + rp * n * b
    os00  = sqrt (pi/p) * predexp
    rp    = recip (2*p)

但是，我是，不知道如何进一步进行。

原文

Greetings, StackOverflow.

Let's say I have two following recurrence relations for computing S(i,j)

$S_{i,j+1} = X_{PA}S_{i,j} + \frac{1}{2p}(iS_{i-1,j}+jS_{i,j-1}) \\ S_{i+1,j} = X_{PB}S_{i,j} + \frac{1}{2p}(iS_{i-1,j}+jS_{i,j-1})$

I would like to compute values S(0,0), S(0,1), S(1,0), S(2,0), etc... in asymptotically optimal way. Few minutes with pencil and paper reveal that it unfolds into treelike structure which can be transversed in several ways. Now, it's unlikely tree will be useful later on, so for now I'm looking to produce nested list like [[S(00)],[S(10),S(01)],[S(20),S(21),S(12),S(02)],...]. I have created a function to produce a flat list of S(i,0) (or S(0,j), depending on first argument):

osrr xpa p predexp = os00 : os00 * (xpa + rp) : zipWith3 osrr' [1..] (tail osrr) osrr
  where
    osrr' n a b = xpa * a + rp * n * b
    os00  = sqrt (pi/p) * predexp
    rp    = recip (2*p)

I am, however, at loss as how to proceed further.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

冬天旳寂寞 2024-11-02 04:58:12

我建议以直接递归风格编写它并使用记忆来创建遍历：

import qualified Data.MemoCombinators as Memo

osrr p = memoed
    where
    memoed = Memo.memo2 Memo.integral Memo.integral osrr'
    osrr' a b = ...  -- recursive calls to memoed (not osrr or osrr')

该库将创建一个无限表来存储您已经计算的值。由于备忘录构造函数位于 p 参数下，因此该表在 p 范围内存在；即 osrr 1 2 3 将创建一个表用于计算 A(2,3)，然后清理它。您可以通过部分应用来重用特定p的表：

osrr1 = osrr p

现在osrr1将在其所有调用之间共享该表（根据您的情况，可能会也可能不会）你想要什么）。

I would suggest writing it in a direct recursive style and using memoization to create your traversal:

import qualified Data.MemoCombinators as Memo

osrr p = memoed
    where
    memoed = Memo.memo2 Memo.integral Memo.integral osrr'
    osrr' a b = ...  -- recursive calls to memoed (not osrr or osrr')

The library will create an infinite table to store values you have already computed. Because the memo constructors are under the p parameter, the table exists for the scope of p; i.e. osrr 1 2 3 will create a table for the purpose of computing A(2,3), and then clean it up. You can reuse the table for a specific p by partially applying: