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?

Accepted Answer

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

Idiomatic Haskell code to simplify recursion

Solution

Problem