Graph generator for undirected graphs
-- for a given y = (y_1,...,y_n) and a bound m, find all vectors
-- x = (x_1,...,x_n) such that |x| = m and x_i &lt;= y_i
boundSequences :: (Num a, Ord a, Enum a) =&gt; a -&gt; [a] -&gt; [[a]]
boundSequences m x | m &lt;= sum x = (fByM . sequence . ranges) x
                   | otherwise = [[]]
    where fByM = filter (\x -&gt; sum x == m)
          ranges = map (\x -&gt; [0..x])


Excepting some fortunate cases, you are wasting a lot of work here. sequence . ranges produces (y_1+1) * ... * (y_n+1) lists you have to check. If you write a function to produce only the successful lists, you can gain a lot of performance for larger input (it won't do too much for short lists with small elements, but it will help for those too).
Shouldn't the case sum x &lt; m return [] rather than [[]]?

-- return all the possible arc combinations  to an equivalence
-- class for a given number of arcs
connectionCombinations :: Int -&gt; EquivClass -&gt; [NodeSelection]
connectionCombinations arcs = map groupOcc . prune arcs . sequence . orderRep
    where orderRep (EC o v) = replicate (length v) [0..o]
          prune a = nub . map (reverse . sort) . filter ((== a) . sum)
          groupOcc = filter ((/= 0) . fst) . occurences


Instead of reverse . sort, use sortBy (flip compare). That won't make much difference for short lists, but it's cleaner, IMO. prune arcs . sequence contains another occurrence of the boundSequences problem, creating a lot of lists and filtering out most of them immediately. nub is not good, it is quadratic (worst case, O(total*distinct) in general). The things you're nubbing have an Ord instance, if the order doesn't matter, map head . group . sort is a much faster nub than nub (still better Data.Set.toList . Data.Set.fromList), if order matters, keep a Set of seen elements and for each new, output that and add it to the set of seen.

I've not yet profiled, but it may be that the profile is misleading because it attributes costs to the functions where results are forced rather than where they are calculated, that needs some investigation, check back later.

Okay, the given data doesn't run long enough to produce a meaningful profile, so I changed it to

let cons = connections [EC 4 [1 .. 6], EC 6 [2 .. 9]] 5


That runs long enough to collect a handful of samples. Unfortunately, the profile wasn't very informative:

    total time  =        7.90 secs   (395 ticks @ 20 ms)
    total alloc = 8,098,386,128 bytes  (excludes profiling overheads)
COST CENTRE                    MODULE               %time %alloc
connectionCombinations         Main                 100.0  100.0


So I inserted a couple of {-# SCC #-} pragmas. The biggo in that programme is the sequence . orderRep, unsurprisingly. A rewrite along the lines mentioned above,

boundSequences :: (Num a, Ord a, Enum a) =&gt; a -&gt; [a] -&gt; [[a]]
boundSequences m xs
    | sm &lt; m    = []
    | sm == m   = [xs]
    | otherwise = go sm m xs
      where
        sm = sum xs
        go _ r []
            | r == 0 = [[]]
            | otherwise = []
        go _ r [y]
            | y &lt; r     = []
            | otherwise = [[r]]
        go s r (y:ys) = do
            let mny | s &lt; r+y   = r+y-s
                    | otherwise = 0
                mxy = min y r
            c &lt;- [mny .. mxy]
            map (c:) (go (s-y) (r-c) ys)


and using that in connectionCombinations instead of prune arcs . sequence (requires a small change in orderRep),

connectionCombinations :: Int -&gt; EquivClass -&gt; [NodeSelection]
connectionCombinations arcs = map groupOcc . nub . map (sortBy (flip compare)) . 
                                     boundSequences arcs . orderRep
    where orderRep (EC o v) = replicate (length v) o
          groupOcc = filter ((/= 0) . fst) . occurences


brought the running time (ghc -O2, no profiling) down significantly:

dafis@schwartz:~/Cairo&gt; time ./orArcs &gt; /dev/null

real    0m5.836s
user    0m5.593s
sys     0m0.231s
dafis@schwartz:~/Cairo&gt; time ./arcs &gt; /dev/null

real    0m0.008s
user    0m0.005s
sys     0m0.003s


Whether any further optimisations (e.g. the abovementioned nub) are necessary, and where most of the time in the actual programme is spent, so that one could identify the most important points, I cannot tell without more realistic data.