用惯用的 Haskell 代码简化递归

Question

我需要计算 foo n = maximumBy (comparing p) [1..n]，其中 p :: Int -> Int 运行缓慢。但我知道对于所有的 n > 0，p n < n，并想要利用这个事实加速计算过程：从 n 开始递减计算 x 的 p x，同时记忆当前最大值。一旦我到达一个小于或等于当前最大值的 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')

这个方法可以工作，但不够优雅。因此，我正在寻找更加优美的解决方案。您有什么建议吗？

- ipsec

Answer 1

使用模式匹配可以减少if ... then ... else的使用量
另一个技巧是给变量编号，这样您就可以记住起始情况var0，对于其他递归调用，您可以使用更好的var
最后注意，如果有一些if在相同形式的谓词之后返回相同的值并共享相同的环境，则可以将它们分组在一起。

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

- zurgl

---

去掉成对的参数，改为 go x y n ...，然后我会将 p n 绑定到一个名称上（甚至不给编译器重新计算的机会），否则这就是我要做的。简单、清晰、高效。 - Daniel Fischer

谢谢，按照你建议的更换了一对，肯定更好。不过，我必须承认，我对使用 let ... in 绑定有些犹豫，因为我真的不知道在我的第二个模式匹配中，(p n) 是否会被计算两次。如果我必须证明我的代码，我会说 Haskell 本质上是惰性的，这意味着它的求值策略是按需调用，并且根据定义，“按需调用是按名称调用的记忆化版本”，那么应该没问题，对吧？虽然使用像你建议的 let ... in 绑定确实没有任何疑问，但我已经在我的下面添加了你的建议。 - zurgl

我会使用 where。go x y n | n == 1 || n <= y = x | pn > y = go n pn (n-1) | otherwise = go x y (n-1) where pn = p n。 - Daniel Fischer

绝对不，就去做吧。 - zurgl

关于问题，即使p n没有绑定到名称，是否会重新计算；通过优化，可能不会。但是要确保，需要查看核心代码。然而，我已经学会了永远不要盲目地信任编译器，并且引入本地绑定比查看核心代码更少的工作量，并且只要编译器甚至四分之一理智，就可以做到预期的事情，因此在这种情况下我会这样做。 - Daniel Fischer

Answer 2

好的，让我看看是否正确理解了... 你是说对于所有有趣的n，p n < n。并且你想计算x = n to 1的p x，直到x变成比迄今为止最大的p x小？

那么，看起来您可以将所有p x计算为一个惰性列表。现在问题已经缩减为扫描此列表，直到找到所需内容。我建议使用takeWhile，除非我们还需要折叠列表以查找当前的最大值。嗯，也许我们可以将每个值与运行时最大值配对？

像这样

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

或类似的吗？

- MathematicalOrchid