Debugging infinite loops in Haskell programs with GHCi

Question

For the first time I've encountered an infinite loop in a Haskell program I'm writing. I've narrowed it down to a quite specific section of code, but I cannot seem to pinpoint exactly where I have a non-terminating recursive definition. I'm vaguely familiar with :trace and :history in GHCi, but the problem is that some branches of my code involve quite a bit of recursive modifications of a Data.Map.Map in the sense that the map x is obtained by adjusting something in the map x' based on values in another map depending on x'. The specifics don't matter here, but as you can probably tell, if this happens in an intertwined recursive way, my call history gets completely bogged down in all the various comparisons involved in map lookups, adjustments and insertions.

Can anyone recommend a more efficient way to locate infinite loops? It would, for example, help a lot to restrict the call history to calls from a single source file.

Answer 1

I'm surprised no one has mentioned the ubiquitous response that all Haskell performance issues get (infinite runtime being a rather extreme example of a "performance issue"): profiling!

I was just able to quickly identify an infinite loop using profiling. For completeness, compile with -prof -fprof-auto, then run the program for enough time that the offending function should be apparent in the profiling stats. For example, I expected my program to complete in <1 second, so I let the profiler run for about 30 seconds, then killed my program with Ctrl+C. (Note: Profiling saves incremental results, so you can still get meaningful data even if you kill the program before it runs to completion. EDIT: Except when it doesn't.)

In the .prof file, I found the following block:

                                                 individual      inherited COST CENTRE         MODULE     no.    entries   %time  %alloc   %time %alloc ... primroot.\          Zq         764          3    10.3    13.8    99.5  100.0  primroot.isGen     Zq         1080   50116042    5.3     6.9    89.2   86.2   primroot.isGen.\  Zq         1087   50116042   43.4    51.7    83.8   79.3    fromInteger      ZqBasic    1088          0   40.4    27.6    40.4   27.6 

So there are 50 million entries to primroot.isGen, and the next most-called function had only 1024 calls. Additionally, 99.5% of runtime was spent computing primroot, which seems highly suspicious. I checked out that function and quickly found the error, a simple typo in my case: (`div` foo) instead of (div foo).

I think it's worth noting that GHC warnings wouldn't have caught this problem, nor -fbreak-on-exceptions. The code base is huge; trying to track down the problem by inserting debugging statements (of any sort) didn't get me anywhere. I was also unsuccessful using the GHCi debugger because the history was essentially non-existent, and HPC didn't reveal anything useful.