haskell - haskell初学者-递归递归

刚从Haskell开始，我整理了这个丑陋的部分，以确定列表中的数字可被数字整除，所有数字均小于该数字。

divis :: (Integral a) => a -> [a] -> [a]
divis _ [] = []
divis n (x:xs)
    | x `mod` n == 0 && n == 2 = x : divis n xs
    | x `mod` n == 0 = divis (n-1) [x] ++ divis n xs
    | otherwise = divis n xs

我可以这样称呼它...

head (divis 10 [1..])

以获得列表中的第一个数字，在这种情况下为2520。但是，这似乎不足以有效地解决使用20这样的更高数字。

如何解决haskell的问题？

最佳答案

这可以通过使用不同的算法得到显着改善:可以用一组数字除以的最小数(在这种情况下，该数为[1..10])是这些数字的最小公倍数。

Haskell甚至具有内置的最不常用的多功能(lcm)，您可以使用:

Prelude> foldl lcm 1 [1..10]
2520

如果您不想使用内置的lcm函数(因为这几乎是作弊的:))，则可以使用Euclid's algorithm计算GCD，然后使用:

lcm a b = a * b `div` gcd a b

如果需要找到给定列表中所有可被[1..n]整除的数字，则可以使用以下事实:任何此类数字也可被[1..n]的最小公倍数整除:

divis n xs = filter (\x -> x `mod` mult == 0) xs
    where mult = foldl lcm 1 [1..n]