haskell beginner - recursive recursion

Question

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?

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... — Andrzej Doyle
– Andrzej Doyle, Commented Mar 9, 2011 at 17:58
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. — Brandon Frohbieter
– Brandon Frohbieter, Commented Mar 9, 2011 at 18:04

interjay · Accepted Answer · 2011-03-09 18:16:32Z

13

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]

edited Mar 9, 2011 at 18:16

answered Mar 9, 2011 at 18:02

interjay

111k22 gold badges278 silver badges264 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Brandon Frohbieter Over a year ago

instantaneous vs several long minutes, thank you, still have so much to learn

ephemient Over a year ago

Prefer foldr (when you can lazily stream structures) or foldl' (when the best strategy is strict evaluation) over foldl.

Collectives™ on Stack Overflow

haskell beginner - recursive recursion

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related