Graph generator for undirected graphs

Question

I am still pretty new to Haskell and am working on a graph generator for undirected unlabeled graphs containing loops and I have a bottleneck in the following functions. So far, I have not given any thought to performance and just looked for correctness.

I know this kind of question is not really popular, but I'd be interested in general guidelines for improving performance given some naive but correct implementation like the following.

For instance:

1. Where to enforce strictness?
2. Should I use vector/array instead of lists? When, where and why?
3. Should I improve single functions by replacing recursion using folds/maps/etc. or similar?

Additional info:

1. I'm using -O2 with ghc
2. profiling shows (when normalizing runtime of connections to 100%)
   • arqSeq 40% (with almost all time spend in boundsequences)
   • connectionCombinations 60% with a quarter of the time spend in occurences

I don't think you need to understand all the details. I'm looking more for micro-improvements (the following determines arcs from a given node to equivalence classes of vertices grouped by their degree).

import Data.List
import Control.Monad

type Arcs = Int
type Count = Int
type Vertex = Int    
type MSequence = [Int]
data EquivClass = EC { order :: Int, verts :: [Vertex] } deriving (Eq, Show)
type ECPartition = [EquivClass]
type NodeSelection = [(Arcs,Count)]
type ECNodeSelection = (EquivClass, NodeSelection)

-- number of occurences of unique elements in a list
occurences :: (Ord a) => [a] -> [(a, Int)]
occurences = map (\xs@(x:_) -> (x, length xs)) . group . reverse . sort

-- number of vertices in an equivalence class
ecLength :: EquivClass -> Int
ecLength = length . verts

-- 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 <= y_i
boundSequences :: (Num a, Ord a, Enum a) => a -> [a] -> [[a]]
boundSequences m x | m <= sum x = (fByM . sequence . ranges) x
                   | otherwise = [[]]
    where fByM = filter (\x -> sum x == m)
          ranges = map (\x -> [0..x])

-- return m-sequences (combinations of number of arcs) for the given
-- order to an ECPartition
arcSeq :: Int -> ECPartition -> [MSequence]
arcSeq m x = boundSequences m (map ecProd x)
    where ecProd e = ecLength e * order e

-- return all the possible arc combinations  to an equivalence
-- class for a given number of arcs
connectionCombinations :: Int -> EquivClass -> [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

-- return all the possible lists of equivalence class node selections
-- from a Partition and a givne number of arcs
connections :: ECPartition -> Int -> [[ECNodeSelection]]
connections p order = concatMap (con p) $ arcSeq order p
     where con p arcs = map (zip p) $ zipWithM connectionCombinations arcs p

main = do
    -- small example. In the complete app this is called 10,000's of
    -- times in case of high degrees or vertex counts
    let cons = connections [EC 4 [1], EC 1 [2,3,4]] 5
    mapM_ (print) cons

Answer 1

-- 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 <= y_i
boundSequences :: (Num a, Ord a, Enum a) => a -> [a] -> [[a]]
boundSequences m x | m <= sum x = (fByM . sequence . ranges) x
                   | otherwise = [[]]
    where fByM = filter (\x -> sum x == m)
          ranges = map (\x -> [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 < m return [] rather than [[]]?

-- return all the possible arc combinations  to an equivalence
-- class for a given number of arcs
connectionCombinations :: Int -> EquivClass -> [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) => a -> [a] -> [[a]]
boundSequences m xs
    | sm < m    = []
    | sm == m   = [xs]
    | otherwise = go sm m xs
      where
        sm = sum xs
        go _ r []
            | r == 0 = [[]]
            | otherwise = []
        go _ r [y]
            | y < r     = []
            | otherwise = [[r]]
        go s r (y:ys) = do
            let mny | s < r+y   = r+y-s
                    | otherwise = 0
                mxy = min y r
            c <- [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 -> EquivClass -> [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> time ./orArcs > /dev/null

real    0m5.836s
user    0m5.593s
sys     0m0.231s
dafis@schwartz:~/Cairo> time ./arcs > /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.