# How to view Graph Reduction/Graph Representation for a Haskell program?

I know that under the hood, for a Haskell program, the GHC compiler uses graph reduction for optimization. Is there any way to view this graphical representation of the program? I haven't been able to find an existing plugin that, given a Haskell program, produces its graphical representation. I am relatively new to Haskell.

Are there research tools available to study and manipulate such graphs?

• Great question! Welcome to the site. I don't know the answer, but maybe someone else does.
– 6005
Jul 10 '20 at 16:10

Welcome to CS.SE!

I cannot present the underlying algorithms themselves, just the concepts they use.

The normal form (NF) of some expression is basically its result, like 42, Just 1, \ x -> 1 + x.

The weak head normal form (WHNF) is some expression which is one of three:

1. A lambda: \ x -> x + 5 * 6. The NF is \ x -> x + 30.
2. Data constructor: (3, 2 + 5). The NF is (3, 7). It could be partially applied: (,) (2 * 5). The NF is \ x -> (10, x).
3. Partially applied built-in function: (+) (2 * 8). The NF is \ x -> 16 + x.

As one can see, WHNF generalizes NF.

So, what have graphs got to do with this? Well, one can understand f e1 e2 ... en as a graph with a node f which is connected with n other nodes: e1, e2, ..., en. Evaluation is the reduction of the nodes1. To show why this is actually very cool I am going to use a picture which I stumbled upon on Wikipedia and HaskellWiki not so long ago:

So, what is going on in this picture? The idea is simple: when working with lists, we have a binary operation (:) and some initial value []. When we are folding, we have a binary operation f and some initial value z. The data structure does not change - only the nodes of our graph. To get the complete result (NF, that is), we reduce the graph.

(Please note that the initial 1 : 2 : 3 : 4 : 5 : [] could not have been reduced any further; in (pseudo-)haskell the lists are: data [a] = a : [a] | [].)

1Some technical details on evaluation (the basic tools to manipulate graphs, just as you have asked). The programmer might force the reduction. seq x y forces its first argument to the WHNF and returns the second (being basically flip const magically strict in the first argument). More formally:

...seq x y means that whenever y is evaluated to weak head normal form, x is also evaluated to weak head normal form.

If the programmer wants to do the same for the NF, they should take a look at Control.DeepSeq.deepseq.