计算Haskell中的递归关系

Question

问候,StackOverflow.

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

我想以渐近最优的方式计算值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)

但是,我不知道如何继续前进.

Answer 1

我建议用直接递归样式编写它并使用memoization来创建遍历:

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')

该库将创建一个无限表来存储您已计算的值.因为memo构造函数在p参数下,所以表存在于范围内p; 即osrr 1 2 3将创建一个表用于计算A(2,3),然后清理它.您可以p通过部分应用将表重用于特定表:

osrr1 = osrr p

现在osrr1将在所有呼叫之间共享该表(根据您的情况,可能或可能不是您想要的).