I'm writing a function in Haskell that takes in two integers a and b and computes the length of the largest subset(s) of [a,b] such that all the elements are mutually coprime. Now, the reason for this is because I believe investigating such values might yield means of producing trivial lesser bounds (possibly one's large enough to imply actual primes in various per conjectured ranges such as consecutive squares). So naturally I'm trying to run this for some pretty large numbers.
Unfortunately the below code is not running fast enough for it to be even practical for me to use. I think the flaw is Haskell's laziness policy causing issues, but I neither know the syntax nor the place where I need to force execution to prevent the operations from accumulating.
subsets [] = [[]]
subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)
divides a b = (mod a b == 0)
coprime a b = ((gcd a b) == 1)
mutually_coprime [] = True
mutually_coprime (x:xs) | (coprime_list x xs) = mutually_coprime xs
| otherwise = False
coprime_list _ [] = True
coprime_list a (x:xs) | (coprime a x) = coprime_list a xs
| otherwise = False
coprime_subsets a b = coprime_subsets_helper (subsets [a..b])
coprime_subsets_helper [] = []
coprime_subsets_helper (x:xs) | (mutually_coprime x) = [x] ++ (coprime_subsets_helper xs)
| otherwise = coprime_subsets_helper xs
coprime_subset_length a b = max_element (map list_length (coprime_subsets a b))
list_length [] = 0
list_length (x:xs) = 1 + list_length xs
max_element a = max_element_helper a 0
max_element_helper [] a = a
max_element_helper (x:xs) a | (x > a) = max_element_helper xs x
| otherwise = max_element_helper xs a
Just to make it clear what sort of input this is hanging upon, "coprime_subsets 100 120" never seems to even halt for me. I actually left it running, got up, did some other stuff and came back to it later. It was still running. I suspect that a large bottleneck is computing all the subsets immediately. However, I don't want to put an artificial lower bound on the subsets generated. That might sieve out all of the coprime sets leaving me with nothing.
What I have tried so far:
I replaced the original coprime function I had with gcd. Originally this used modulo and iterative checking for all integers. I presume gcd used something like Euclid's Algorithm which should run faster, in theory.
I've been trying to think of a way to build the generation of the subsets into the coprime set generator. So far I haven't been able to come up with anything. I'm also not sure if that would actually help with anything.
I've been looking for anywhere that Haskell's laziness policy might be hurting me. Nothing stands out, but I'm sure.
I'm also aware that this could be an efficiency issue with the environment I use (winhugs). I'd say that is the issue; however, when I asked how to determine the largest subset (for general n sized ranges) on Math Stack Exchange the answers I received indicated that computationally speaking this is a very slow thing to calculate. If so, that's fine. I was just hoping to maybe be able to run through some of the ranges I was interested in without it taking almost forever.
I know efficiency is generally not allowed on this site; however, I have tried quite a bit and I'm not just trying to be lazy here. I know Haskell has quite a few weird quirks that can force it into being deceptively inefficient. It's been a while since I've coded in it, and I suspect I've landed in one of those quirks.