Более хекельский способ написать эту рекурсию?

Question

Я написал код для вычисления коэффициентов частного от деления двух бесконечных серий, используя сокращение, следующий образом:

main :: Int -> PInt 
main 0 = 0 
main n = cancel x3 
    where 
    x1 = someOtherFunction 
    x2 = expression involving x1 
    x3 = x2 - (foldr 
     (\y z -> z + (someOtherFunction y) * (main (n - y))) 0 [1..(n - 1)]) 

(Я определил данные под названием PInt, который является экземпляром Num и дробным, и есть вспомогательная функция «отменить» для выполнения сокращения.) Моя проблема заключается в выражении в сгибе в x3: она кажется не очень эффективной, так как она должна вычислять каждую основную k для более низких значений k.

Я имею в виду, может быть, я могу использовать реализацию таких как

fib = 1 : 1 : zipWith (+) fib (tail fib) 

для чисел Фибоначчи вычислить рекурсию выше, что является более эффективным. К сожалению, я не знаю, с чего начать.

Благодарим за любую помощь заранее.

P.S. Код занимает значительное количество времени, чтобы вычислить значение в 20, какое поведение, по-видимому, подразумевает экспоненциальный рост времени?

Answer 1

Мясо функции выглядит следующим образом:

main 0 = 0 
main n = f [main n' | n' <- [0..n-1]] 

Вы рассказали нам немного о f, но не на самом деле достаточно, чтобы сделать много с самого f. Тем не менее, как вы говорите, мы можем memoize некоторых вещей, нападая на рекурсивные вызовы:

mains = 0 : map f (inits mains) 
main = (mains!!) 

В самом деле, в вашем коде, ваша специализация f бывает никогда не смотреть на голове списка это при условии (и вы интернализуйте это, вычислив [1..n-1] вместо [0..n-1]). Мы можем выдвинуть эту проблему через в mains, если нам нравится, по:

mains = 0 : map (f' . drop 1) (inits mains) 
-- corresponds to the specification: 
-- main 0 = 0 
-- main n = f' [main n' | n' <- [1..n-1]] 

Хотя я думаю, что это на самом деле может быть чище, чтобы оставить это f.