Tentando criar um algoritmo eficiente para uma função no Haskell
Estou procurando uma solução eficiente em tempo polinomial para o seguinte problema:
Implemente um nó de função recursiva x y para calcular o (x, y) -ésimo número em um triângulo numérico definido como
g(x,y) = 0 if |x| > y
= 1 if (x,y) = (0,0)
= sum of all incoming paths otherwise
A soma de todos os caminhos de entrada para um nó é definida como a soma dos valores de todos os caminhos possíveis do nó raiz (x, y) = (0, 0) para o nó em consideração, onde em cada nó (x, y ) um caminho pode continuar na diagonal para baixo e para a esquerda (x − 1, y + 1), para baixo (x, y + 1) ou na diagonal para baixo e para a direita (x + 1, y + 1). O valor de um caminho para um nó é definido como a soma de todos os nós ao longo desse caminho até o nó em consideração, mas não incluindo o mesmo.
As primeiras entradas no triângulo numérico são fornecidas na tabela:
\ x -3 -2 -1 0 1 2 3
\
y \ _________________________
|
0 | 0 0 0 1 0 0 0
|
1 | 0 0 1 1 1 0 0
|
2 | 0 2 4 6 4 2 0
|
3 | 4 16 40 48 40 16 4
Estou tentando descobrir uma solução ingênua primeiro, eis o que tenho:
node x y | y < 0 = error "number cannot be negative"
| (abs x) > y = 0
| (x == 0) && (y == 0) = 1
| otherwise = node (x+1) (y-1) + node x (y-1) + node (x-1) (y-1)
Sempre que executo isso, recebo:
"* Exceção: estouro de pilha "?