Почему я получаю экспоненциальное количество вызовов в мою подфункцию?

Question

У меня проблема со следующей функцией Haskell:

evalPol :: Float
        -> Float
        -> Integer
        -> Integer
        -> (s -> a -> [(s, [(Float, Float)])])
        -> (s -> a)
        -> [s]
        -> [((s -> Float), Float)]
        -> [((s -> Float), Float)]
evalPol eps gamma maxIter nIter gen pol ss vofss =
  if nIter >= maxIter || delta < eps
    then reverse ((vofs', delta) : vofss)
    else evalPol eps gamma maxIter (nIter + 1) gen pol ss ((vofs', delta) : vofss)
 where delta   = maximum [abs (vofs s - vofs' s) | s <- ss]
       vofs' s = actVal gamma gen vofs s (pol s)
       vofs    = (fst . P.head) vofss

Если я вызываю эту функцию с помощью maxIter = 1 и запускаю с профилированием, то вижу количество записей функций, которые имеют смысл для меня:

evalPol..............2
  evalPol.delta......1
    evalPol.vofs'..441

Числа записей функций, приведенные выше, имеют для меня смысл:

1. evalPol вводится дважды:

   1. один раз, когда вызывается извне, и
   2. один раз, рекурсивно. (Допускается только один рекурсивный вызов из-за: maxIter = 1.)

2. evalPol.delta вызывается только один раз, потому что когда evalPol вызывается во второй раз (рекурсивно), тест: nIter >= maxIter успешен, и нет необходимости оценивать delta.

3. Имеет смысл, что я получаю 441 запись в evalPol.vofs', потому что я сопоставляю эту функцию со списком, ss, и в этом списке 441 элемент.

Теперь, если я сделаю только одно изменение: вызову evalPol с maxIter = 2, я обнаружу, что моя программа не завершает свою работу в разумные сроки. Позволяя ему работать в течение нескольких часов, прежде чем перезапустить его, я получаю следующее:

evalPol................2
  evalPol.delta........2
    evalPol.vofs'..60366

Изменение количества записей с evalPol.delta с 1 на 2 (см. № 2 выше) имеет смысл для меня, так как я установил maxIter = 2. Тем не менее, я не ожидал такого увеличения количества записей в evalPol.vofs'. (Я ожидал увидеть 882 записи, 441 для каждой разрешенной рекурсии.) Похоже, что количество записей в evalPol.vofs' равно экспоненциально в maxIter. (Я не знаю этого, так как я не дал программе завершиться.)

Если я «разверну» этот случай 2 рекурсии, ища экспоненциальную зависимость от maxIter, я получу:

-- This is how I call it from outside:
evalPol eps gamma 2 0 gen pol ss [((const 0), 0)] =                  -- Assume delta >= eps and recurse.
evalPol eps gamma 2 1 gen pol ss [(vofs', delta), ((const 0), 0)]

-- Now, expand delta
delta = maximum $ map (abs . uncurry (-) . (vofs &&& vofs')) ss      -- Substitute for vofs, vofs', and pol, using previous iteration's definitions.
      = maximum $ map ( abs
                      . uncurry (-)
                      . ( vofs' &&&
                          \s -> actVal gamma gen vofs' s 0
                        )
                      ) ss
      = maximum $ map ( abs
                      . uncurry (-)
                      . ( \s -> actVal gamma gen (const 0) s 0 &&&
                          \s -> actVal gamma gen (\s' -> actVal gamma gen (const 0) s' 0) s 0
                        )
                      ) ss

Я вижу, что рекурсия развивается, как и ожидалось, но я не вижу вложенных вызовов в evalPol.vofs', которые могли бы объяснить (предположительно) экспоненциальную зависимость от maxIter, которую я наблюдаю. Кроме того, я рассмотрел как функцию actVal, так и функцию gen, и нет вызовов в evalPol.vofs', скрывающихся ни в одной из них. Итак, я затрудняюсь объяснить это очень большое количество записей в evalPol.vofs', которые я наблюдаю в случае maxIter = 2.

Answer 1

Я решил это, используя векторное представление функции vofs'. Это исключило избыточные вычисления, которые выполнялись ранее. Теперь я вижу 882 вызова в новый эквивалент vofs' для случая 2 рекурсии , что я и ожидаю. То есть я ожидаю, что время выполнения evalPol будет линейным в maxIter, и, используя векторное представление vofs', это то, что я вижу.