如何在Haskell中优化此功能

Question

作为代码挑战的一部分，我在Haskell中编写了以下函数：

simulateUntilRepeat_int a b i = if (a /= b) then (simulateUntilRepeat_int a (updateCycle b) (i+1)) else i

simulateUntilRepeat a = simulateUntilRepeat_int a (updateCycle a) 1

这样做的目的是获取卫星列表并模拟它们的运动，直到它们恢复其原始位置，并返回它们到达该位置所花费的周期数。 （函数updateCycle进行一次仿真迭代）。但是，当我尝试运行它时，它将使用所有可用内存，然后被操作系统杀死。该问题确实承认这可能需要大量的周期。

围绕这个问题，我发现通常的解决方法是使某些参数严格，但是我想我已经对参数的严格性的所有可能排列进行了试验，但无济于事。从该函数的外观来看，我已经预料到编译器将能够使用尾部递归优化并将其转换为循环，但这似乎并没有发生。

我的一个在haskell方面很博学的朋友建议将函数的形式更改为以下形式：

f a b0 = length (takeWhile (/= a) (iterate updateCycle b0))

但是这样做也不能解决问题，使我无所适从。

Answer 1

这些评论无疑是正确的，因为您的方法不是预期的解决方法。

但是，您发布的功能本身不会导致内存泄漏，无法尾随递归或导致性能下降。给定上面的代码以及定义：

updateCycle 4686774942 = 0
updateCycle n = n+1

main = do
  print $ simulateUntilRepeat (0 :: Int)

并使用-O2进行编译，该程序在笔记本电脑中的恒定内存中运行约30秒。添加显式类型签名以使用Int代替Integer进行迭代计数：

simulateUntilRepeat_int :: Int -> Int -> Int -> Int
simulateUntilRepeat :: Int -> Int

大约运行2.4秒。

因此，要了解为什么您的程序会吞噬所有可用内存或为什么严格性注释不能起作用，可能有必要查看整个工作程序（或者最好是一个说明性能问题的最小示例）。如果程序简短，问题是“为什么该程序的性能完全不合理？”而不是“我如何优化程序以使其尽可能快地运行？”，这可能仍然是一个很好的SO问题。否则，Code Review网站可能会更好-您可以在此处发布更大的程序，并寻求一般的性能建议，这被认为是该网站的主题。