这是一个关于Haskell LCM函数的更符合习惯的写法。

Question

我刚开始学Haskell，写了一个简单的递归算法来找到列表中每个数字的LCM。它能够工作，但是代码有些凌乱，希望有人能够对其进行审查，提出更加优雅、易读和符合Haskell编程风格的改进意见。

lcms list 
  | length list > 1 = lcms (lcm (head list) (head (tail list)):(tail (tail list)))
  | otherwise = list

该函数接受一个列表并计算前两个元素的最小公倍数，然后将其插入到剩余元素之前。伪代码如下：

lcms [a,b,c] = lcm (a, (lcm (b, c))

任何建议都可以吗？我渴望提高Haskell技能，写出易读的代码。如果有提升效率的技巧也欢迎分享！感谢大家！

- catleeball

Answer 1

这是一个折叠：

import Data.List

lcms :: [Int] -> Int
lcms xs = foldl' lcm 1 xs

其中lcm计算仅两个数字的最小公倍数：

lcm :: Int -> Int -> Int

- ErikR

---

你也可以使用 foldr，例如 lcms = foldr lcm 1。 - amar47shah

@clball foldl 几乎永远不是你想要的。 - Daniel Wagner

本文深入探讨了这三个函数，并在结尾提供了一些经验法则。https://wiki.haskell.org/Foldr_Foldl_Foldl%27 - amar47shah

@user5402 foldr和foldl'都可以是合理的选择，具体取决于用途。考虑到这种特定用法被类型限制为Int--一种本质上严格的类型--我认为foldl'是自然的选择。 - Daniel Wagner

@PyRulez，我热切期待您对于惰性自然数列表的首选LCM算法的性能分析。 - dfeuer

Answer 2

您可以几乎按照您建议的语法来编写它，如下：

lcms (a:b:c) = lcms (lcm a b:c)
lcms list = list

我觉得第二个从句有点奇怪，但并不是很糟糕：它优雅地处理了空列表，但当你知道最多只会返回一个项目时，返回列表可能被一些 Haskeller 视为在类型方面不够精确。你也可以考虑使用 Maybe，这是经典的 0 或 1 元素类型：

lcms (a:b:c)  = lcms (lcm a b:c)
lcms [answer] = Just answer
lcms []       = Nothing

另一个不错的选择是确定一个明智的基本情况。对于二进制操作，该操作的单位通常是一个不错的选择，因此对于 lcm，我会选择1，即：

lcms (a:b:c)  = lcms (lcm a b:c)
lcms [answer] = answer
lcms []       = 1

通常情况下，尽可能避免显式递归；其他答案展示了如何采取这一步骤。在这种情况下，有一个中间转换使得基本情况稍微更加美观：不要将累加器保留在列表的头部 - 这仅仅是因为你的累加器与列表元素具有相同的类型而偶然起作用 - 可以使累积更加明确或不那么明确。因此，其中之一：

lcms (x:xs) = lcm x (lcm xs)
lcms []     = 1

-- OR

lcms = go 1 where
    go acc (x:xs) = go (lcm acc x) xs
    go acc []     = acc

这两个实现对应于选择foldr或foldl来消除显式递归; foldl'类似于第二种实现，但增加了一个seq：

lcms = go 1 where
    go acc (x:xs) = let acc' = lcm acc x in acc' `seq` go acc' xs
    go acc []     = acc

- Daniel Wagner

---

感谢您提供如此详细的解释！为什么通常避免使用显式递归？只是一般来说不是最好的方法吗？另外，您能够实现几乎完全符合伪代码的解决方案真的很酷。那真是太棒了。 - catleeball

通常，使用像map、filter以及类似的函数（还有在一定程度上的foldr）要优于一般递归，因为这样可以减少出现错误的可能性，而且读者可以更轻松地一眼看懂代码。如果我看到递归，我总是会寻找使其不符合标准模式的特殊情况。 - Daniel Wagner

请注意此解决方案如何避免使用 head 和 tail 函数。这些函数很危险，因为如果您在空列表上调用它们，程序将崩溃。相反，使用上述的模式匹配不会使程序崩溃，除非您没有覆盖所有可能的情况。幸运的是，-Wall 会警告您定义是否不全面。我发现这非常有帮助。此外，模式匹配可以使代码更易读。 - chi