Как ускорить (или запомнить) ряд взаимно рекурсивных функций

У меня есть программа, которая производит ряд функций f а также g который выглядит следующим образом:

step (f,g) = (newF f g, newG f g)

newF f g x = r (f x) (g x)
newG f g x = s (f x) (g x)

foo = iterate step (f0,g0)

Где r и s - некоторые неинтересные функции f x а также g x, Я наивно надеялся, что имея foo быть списком будет означать, что, когда я называю N f он не будет пересчитывать (n-1) -й f если он уже вычислил его (как это случилось бы, если f а также g не были функции). Есть ли способ запомнить это, не разрывая всю программу на части (например, оценивая f0 а также g0 на все уместные аргументы, а потом работает наверх)?

Источник

2 ответа

Решение

Может оказаться полезным Data.MemoCombinators (в пакете data-memocombinators).

Вы не говорите, какой аргумент вводит ваш f а также g взять --- если они оба принимают целочисленные значения, то вы бы использовали это так:

import qualified Data.MemoCombinators as Memo

foo = iterate step (Memo.integral f0, Memo.integral g0)

При необходимости вы также можете запомнить результат каждого шага

step (f,g) = (Memo.integral (newF f g), Memo.integral (newG f g))

Я надеюсь, что вы не видите, что это разрывает всю программу на части.

В ответ на ваш комментарий:

Это лучшее, что я могу придумать. Это не проверено, но должно работать в правильном направлении.

Я беспокоюсь, что преобразование между Double а также Rational излишне неэффективно --- если бы был Bits экземпляр для Double мы могли бы использовать Memo.bits вместо. Так что это может в конечном итоге не иметь никакого практического применения для вас.

import Control.Arrow ((&&&))
import Data.Ratio (numerator, denominator, (%))

memoV :: Memo.Memo a -> Memo.Memo (V a)
memoV m f = \(V x y z) -> table x y z
  where g x y z = f (V x y z)
        table = Memo.memo3 m m m g

memoRealFrac :: RealFrac a => Memo.Memo a
memoRealFrac f = Memo.wrap (fromRational . uncurry (%))
                           ((numerator &&& denominator) . toRational)
                           Memo.integral

Другой подход.

У тебя есть

step :: (V Double -> V Double, V Double -> V Double)
     -> (V Double -> V Double, V Double -> V Double)

Как насчет того, чтобы изменить это на

step :: (V Double -> (V Double, V Double))
     -> (V Double -> (V Double, V Double))
step h x = (r fx gx, s fx gx)
  where (fx, gx) = h x

А также изменить

foo = (fst . bar, snd . bar)
  where bar = iterate step (f0 &&& g0)

Надеюсь, что общий fx а также gx должно привести к небольшому ускорению.

Источник

Есть ли способ запомнить это, не разрывая всю программу на части (например, вычисляя f0 и g0 по всем соответствующим аргументам и затем работая вверх)?

Это может быть то, что вы подразумеваете под "разрывом всей программы", но вот решение, в котором (я считаю, но не могу проверить банкомат) fooX можно поделиться.

nthFooOnX :: Integer -> Int -> (Integer, Integer)
nthFooOnX x = 
    let fooX = iterate step' (f0 x, g0 x)
     in \n-> fooX !! n

step' (fx,gx) = (r fx gx, s fx gx)

-- testing definitions:
r = (+)
s = (*)
f0 = (+1)
g0 = (+1)

Я не знаю, сохраняет ли это дух вашей первоначальной реализации.

Источник
Другие вопросы по тегам