haskell beginner - recursive recursion

Tag: haskell , recursion , functional-programming Author: mobilebilly Date: 2011-02-21

Just starting with Haskell, and I put together this ugly piece to determine the numbers in a list divisible by a number and all numbers less than it.

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 

and I can call it like...

head (divis 10 [1..])

to get the first number in the list, in this case 2520. However, it seems that this is not good enough to efficently solve using a higher number like 20.

How can I fix this raskell of a haskell?

+1 for "raskell of a haskell"
My first impression is that the algorithm may not be possible to make efficient - each of the k numbers in the list up to the first result has to be tested against all of the n-1 integers between 2 and n, so this is looking like a quadratic solution at least. And when you consider that the relationship of k to n is superlinear, this is looking like O(n^3) or so...
Thanks much for taking a look, the question started out with me not recursing through [x] or knowing how to accomplish it, but after I had typed out my question, I was able to sort of put it together, but then running it to solve the problem was taking forever, so I thought I would ask anyway, in case I had implemented a poor algorithm.

Best Answer

This can be improved substantially by using a different algorithm: The smallest number which can be divided by a set of numbers (in this case, the set is [1..10]) is the least common multiple of those numbers.

Haskell even has a least common multiple function (lcm) built-in which you can use:

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

If you prefer not to use the build-in lcm function (as that's almost cheating :) ), you can do it by using Euclid's algorithm to calculate the GCD, and then using:

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

If you need to find all the numbers in a given list which are divisible by [1..n], you can use the fact that any such number will also be divisible by the least common multiple of [1..n]:

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

comments:

instantaneous vs several long minutes, thank you, still have so much to learn
Prefer foldr (when you can lazily stream structures) or foldl' (when the best strategy is strict evaluation) over foldl.