用于简化递归的惯用Haskell代码

Question

我需要计算foo n = maximumBy (comparing p) [1..n],哪里p :: Int -> Int慢.但我知道,p n < n所有的n > 0,想利用这一点来此计算加速方式如下:我计算p x了x年初n到1,记忆当前最大.一旦达到x小于或等于当前最大值,我知道这个最大值必须是全局值,我就完成了.

所以我的尝试看起来像这样:

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

这有效,但看起来不是很惯用.所以我正在寻找更优雅的解决方案.你有什么建议吗？

Answer 1

您可以使用模式匹配来减少if ... then ... else的使用
另一个技巧是为您的变量赋一个数字,它允许您记住起始情况var0,而对于另一个递归调用,您可以使用nicer var
最后请注意,如果在相同表单的谓词之后返回相同的值并共享相同的环境,那么您可以将它们组合在一起.

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)

重写考虑到评论,

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