haskell初学者 - 递归递归

Question

刚刚开始使用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.

我如何修复这个哈斯克尔的raskell？

Answer 1

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

Haskell甚至还有一个最常见的多功能(lcm)内置你可以使用:

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

如果您不想使用内置lcm函数(因为这几乎是作弊:)),您可以使用Euclid的算法来计算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]