Computación de relaciones de recurrencia en Haskell

Question

Saludos, Stackoverflow.

Digamos que tengo dos después de las relaciones de recurrencia para la computación S (I, J)

Me gustaría calcular los valores S (0,0), S (0,1), S (1,0), S (2,0), etc ... de manera asintóticamente óptima. Pocos minutos con lápiz y papel revelan que se desarrolla en una estructura de árboles que se puede transversar de varias maneras. Ahora, es poco probable que el árbol sea útil más adelante, así que por ahora estoy buscando producir una lista anidada como [[S(00)],[S(10),S(01)],[S(20),S(21),S(12),S(02)],...]. He creado una función para producir una lista plana de S (i, 0) (o S (0, J), dependiendo del primer argumento):

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)

Sin embargo, estoy en pérdida como cómo continuar.

Answer 1

Sugeriría escribirlo en un estilo recursivo directo y usar memoización para crear su recorrido:

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

La biblioteca creará una tabla infinita para almacenar valores que ya ha calculado. Porque los constructores de memo están bajo el p Parámetro, la tabla existe para el alcance de p; es decir, OSRR 1 2 3 creará una tabla con el propósito de calcular un (2,3), y luego limpiarla. Puedes reutilizar la tabla para un p aplicando parcialmente:

osrr1 = osrr p

Ahora osrr1 Compartirá la tabla entre todas sus llamadas (que, dependiendo de su situación, puede o no ser lo que desee).

Answer 2

Primero, debe haber algunas condiciones de contorno de las que no nos ha contado.

Una vez que los tenga, intente declarar la solución como una matriz definida recursivamente. Esto funciona siempre que conozca un límite superior en I y J. De lo contrario, use combinadores de memo.