[Haskell-cafe] Analysing Haskell with Graph Theory

Ivan Miljenovic ivan.miljenovic at gmail.com
Thu Mar 6 20:45:12 EST 2008

Back in December, I posted that I was thinking about doing a project
for my honours year on using graph theory for analysis on Haskell
source code, amongst others:


Well, I've officially started this project, and my supervisor and I
have come up with the following functions that would probably be
relevant to analysing _any_ piece of source code (the actual code will
be tentatively stored as a directed graph with the nodes being
functions and the edges being function calls, i.e. if f calls g, there
is a directed edge from f to g):

* root finding -> find nodes with no incoming edges (in a program,
you'd ideally want only main to be such a node)

* cycle detection -> find a possibly recursive cycle in your code: if
the cycle is too big, then you may wish to consider refactoring

* depth analysis -> find leaves that have a depth from the root node
that is extremely large compared to the others (if a function is 50
calls down from main compared to an average of 15, you may wish to

* chain detection -> find connected functions that have only one
incoming and one outgoing edge, e.g. : f -> g -> h : if g isn't used
anywhere else, you may wish to combine it inside either f or g

* node popularity -> get a count of how many functions use a
particular function and how many other functions it calls (related to
chain detection above)

* clique detection -> probably not as relevant to source code, but if
you have a large number of functions that are all pairwise
co-recursive than you may wish to refactor

Can anyone think of any other kind of functions that would be useful
in this kind of source code analysis?

Also, I'm going to be using haskell-src for for the parsing of the
Haskell code so that I don't waste my time writing a parser, when my
project is technically on the graph-theory side of things.  I know
that it focuses mainly on H98 with only a few extensions... is this
likely to be a problem if I want to try running my eventual program on
say ghc or xmonad as test examples?

Ivan Lazar Miljenovic

More information about the Haskell-Cafe mailing list