简化递归的原地Haskell代码

我需要计算foo n = maximumBy (comparing p) [1..n]，其中p :: Int -> Int很慢。但是我知道p n < n对于所有的n > 0并且想用这个事实来加速这个计算的方式如下：我计算p x为x为n降到1，记住当前的最大值。一旦我达到x小于或等于当前最大值，我知道这个最大值必须是全局值，而且我已经完成了。简化递归的原地Haskell代码

所以我尝试看起来像这样：

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

这工作，但看起来不是很习惯。所以我正在寻找更优雅的解决方案。你有什么建议吗？

来源

2013-03-26 ipsec

您可以使用模式匹配，以减少使用的，如果......那么......否则
另一个技巧是给一个号码给您的变量，它让你记住起始情况var0，为你可以使用更好的递归调用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

来源

2013-03-26 12:26:12 zurgl

摆脱对，使它'去XYN ...'，我会pn'绑定'到一个名称（唐甚至不给编译器一个重新计算它的机会），否则这就是我所要做的。简单，清晰，高效。 – 2013-03-26 14:18:27

谢谢，取而代之的是你建议它绝对更好。无论如何，我必须承认，我对于使用let ...在绑定时犹豫不决，因为我真的不知道在我的第二个模式匹配中，（p n）是否会计算两次。如果我必须证明我的代码是正确的，那么我会认为Haskell本质上是懒惰的，这意味着它的评估策略是按需呼叫，并且定义为“按需呼叫是名称呼叫的备忘录版本”，那么它应该没问题，不是。诚然，按照您的建议使用允许绑定不会让任何疑问的地方，我已经在我的下面添加了您的建议。 – zurgl 2013-03-26 16:00:53

我会用'where'。 'go x y n | n == 1 || n <= y = x | pn> y = go n pn（n-1）|否则=去x y（n-1）其中pn = p n'。 – 2013-03-26 16:03:56

好吧，让我看看我是否正确地把我的大脑包裹起来......你说的p n < 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

或类似的？

来源

2013-03-26 11:55:03 MathematicalOrchid

简化递归的原地Haskell代码

回答

相关问题