новичок в Haskell - рекурсивная рекурсия

Question

Просто начав с Хаскелла, я собрал этот уродливый кусочек, чтобы определить числа в списке, делимые на число, и все числа, меньшие его.

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.

Как я могу исправить этот раскел Хаскелла?

Answer 1

Это можно существенно улучшить, используя другой алгоритм: наименьшее число, которое можно разделить на набор чисел (в данном случае набор равен [1..10]), является наименьшим общим кратным из этих чисел.

Haskell даже имеет встроенную функцию наименьшего общего числа (lcm), которую вы можете использовать:

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

Если вы предпочитаете не использовать встроенную функцию lcm (поскольку это почти обманывает :)), вы можете сделать это с помощью алгоритма Евклида для вычисления 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]