Why am I getting an exponential number of calls into my sub-function?

Question

I have a problem with the following Haskell function:

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

If I call this function with maxIter = 1 and run with profiling then I see function entry counts, which make sense to me:

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

The function entry count numbers, above, make sense to me, as follows:

1. evalPol is entered twice:

   1. once, when called from outside, and
   2. once, recursively. (Only one recursive call is allowed, due to: maxIter = 1.)

2. evalPol.delta is called only once, because when evalPol is called the second time (recursively) the test: nIter >= maxIter succeeds, and there is no need to evaluate delta.

3. It makes sense that I get 441 entries into evalPol.vofs', because I'm mapping that function over the list, ss, and there are 441 items in that list.

Now, if I make only one change: calling evalPol with maxIter = 2, I find that my program doesn't terminate in a reasonable amount of time. Allowing it to run for several hours before interupting it, I get the following instead:

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

The change in the number of entries to evalPol.delta from 1 to 2 (See #2, above.) makes sense to me, since I've set maxIter = 2. However, I was not expecting such a blow up in the number of entries into evalPol.vofs'. (I was expecting to see 882 entries, 441 for each allowed recursion.) It looks like the number of entries into evalPol.vofs' is exponential in maxIter. (I don't know this, since I didn't let the program finish.)

If I "unroll" this 2 recursion case, looking for an exponential dependency upon maxIter, I get:

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

I see the recursion developing, as expected, but I don't see any nested calling into evalPol.vofs', which might explain the (supposedly) exponential dependency upon maxIter that I'm observing. Furthermore, I've looked at both the actVal function, as well as the gen function, and there are no calls into evalPol.vofs' hiding in either of them. So, I'm at a loss to explain this very large number of entries into evalPol.vofs' that I'm observing in the maxIter = 2 case.

Answer 1

I solved this by using a vector representation of the vofs' function. Doing so has eliminated the redundant calculations that were being performed previously. I now see 882 calls into the new equivalent of vofs', for the 2 recursions case, which is what I expect. That is, I expect the execution time of evalPol to be linear in maxIter and, using a vector representation of vofs', that's what I'm seeing.