Idiomatic Haskell code to simplify recursion

Question

I need to compute foo n = maximumBy (comparing p) [1..n], where p :: Int -> Int is slow. But I know that p n < n for all n > 0 and want to use this fact to speed up this computation the following way: I compute p x for x beginning with n down to 1, memorizing the current maximum. Once I reach an x less or equal to the current maximum, I know that this maximum must be the global one and I am done.

So my attempt looks like this:

foo n = go (0, 0) n where
    go (c, _) 1 = c
    go (c, c') !x = if c' >= x then c else go (c2, c'2) (x-1) where
        x' = p x
        (c2, c'2) = if c' >= x' then (c, c') else (x, x')

This works, but does not look very idiomatic. So I am looking for a more elegant solution. Do you have suggestions?

Answer 1

You can use pattern matching to reduce the use of if ... then ... else
Another trick is to give a number to your variable, it allow you to remember the starting case var0 and for the other recursive call you can then use a nicer var
Last note, you have some if returning the same value after a predicate of the same form and sharing the same environment then may be you can group them together.

foo n0 = go (0, 0) n0
  where
    go (x, y) n
        | (n  == 1) || (y >= n) = x
        | y < (p n) = go (n, (p n)) (n-1)
        | otherwise = go (x, y) (n-1)

---

Rewriting taking into account comment,

foo n0 = go 0 0 n0
  where
    go x y n
        | (n  == 1) || (y >= n) = x
        | pn > y                = go n pn (n-1)
        | otherwise             = go x y (n-1)
          where
            pn = p n

Answer 2

OK, so let me see if I wrapped my brain around this correctly... You're saying that p n < n for all interesting n. And you want to compute p x for x = n to 1, until x becomes less than the largest p x seen so far?

Well, it looks like you could compute all the p x as a lazy list. Now the problem is reduced to scanning this list until you find what you're looking for. I would suggest takeWhile, except we also need to fold the list to find the current maximum. Hmm, perhaps we can pair each value with the running maximum?

Something like

foo n =
  let
    ps = [ p x | x <- [n, n-1 .. 1] ]
    qs = fold (\ px' (px, maxPX) -> (px', maxPX `max` px') ) ps
  in last . takeWhile (\ (px, maxPX) -> px >= maxPX) qs

or similar?