Calculating recurrence relationships in Haskell

Question

Greetings, StackOverflow.

Say I have the following two recurrence relations for computing S (i, j)

I would like to calculate the values ​​of S (0,0), S (0,1), S (1,0), S (2,0), etc. asymptotically optimal way. A few minutes with a pencil and paper show that it unfolds into a tree structure, which can be transformed in several ways. Now this unlikely tree will be useful later, so now I am looking to create a nested list such as [[S(00)],[S(10),S(01)],[S(20),S(21),S(12),S(02)],...] . I created a function to create a flat list S (i, 0) (or S (0, j), depending on the first argument):

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

However, I am losing how I move on.

Answer 1

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

 import qualified Data.MemoCombinators as Memo osrr p = memoed where memoed = Memo.memo2 Memo.integral Memo.integral osrr' osrr' ab = ... -- recursive calls to memoed (not osrr or osrr') 

The library will create an endless table for storing already calculated values. Since memo constructors are under the p parameter, a table exists for the p region; that is, osrr 1 2 3 will create a table to compute A (2,3), and then clear it. You can reuse the table for a specific p by partially applying:

 osrr1 = osrr p 

Now osrr1 will share the table between all its calls (which, depending on your situation, may or may not be what you want).

Answer 2

First, there must be some boundary conditions that you did not tell us about.

Once you have this, try specifying the solution as a recursively defined array. This works as long as you know the upper bound on i and j. Otherwise, use note combinators.