I want to exhaustively generate sidon sets, but my haskell code seems slow. Are there any improvements I could make to run this faster?



Previous Attempts: presorting sequences and choosing the head, using Data.Set, using a count variable instead of using size (all these attempts were slower)

 $ ghc -O2 sidon.hs
 $ time ./sidon
[5,10,12,18,21,22]

real    0m3.880s
user    0m3.836s
sys     0m0.041s


import           Data.IntSet (IntSet, empty, insert, notMember, size)
import           Data.List   (sortOn, subsequences)

isCollision' :: [Int] -> IntSet -> IntSet
isCollision' currL set = case currL of
  []     -> set
  (x:xs) -> if notMember x set
               then isCollision' xs (insert x set)
               else set

isCollision :: [Int] -> Bool
isCollision xs = length xs /= size (isCollision' xs empty)

isSidon :: [Int] -> Bool
isSidon xs = not $ isCollision [ x+y | x <- xs, y <-xs, x <= y]

sidon :: Int -> [[Int]]
sidon x = filter isSidon (subsequences [1..x])

maxSidon :: Int -> [Int]
maxSidon sz = snd $ maximum $ [(length x, x) | x <- sidon sz]

main = putStrLn $ show $ maxSidon 22
Thank you :)