3

我刚从 Haskell 开始，并敲定了这个简单的递归算法来找到列表中每个数字的 LCM。它可以工作，但很混乱，我希望能得到一些同行评议，看看如何使它更优雅、更易读和更符合 Haskell 风格。

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

因此，它需要一个列表并对前两项进行 LCM，然后将其添加到列表中减去这两个元素。基本上，我要使用的伪代码是这样的：

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

任何建议，有人吗？我渴望在 Haskell 上有所改进，写出人们可以真正阅读的东西。也欢迎效率提示！

谢谢大家！

4

2 回答 2

9

这是一个折叠：

import Data.List

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

lcm计算两个数字的 lcm ：

lcm :: Int -> Int -> Int
于 2015-08-23T02:36:53.080 回答
3

您几乎可以使用您建议的语法编写它，因此：

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

我发现第二个子句有点奇怪，但并不可怕：它优雅地处理空列表，尽管当你知道你最多会返回一个项目时返回一个列表可能会被一些 hasochists 认为对你的类型有点不精确。您还可以考虑使用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
于 2015-08-23T03:03:05.683 回答