GHC currently does not have proper support support recursive programs and instead users to write .hs-boot files to break cycles in the module graph. This is finding a feedback arc set for your import graph. This process isn’t complete however.
Consider this set of modules:
module A where
import B
import C
data A
a :: A -> B -> C
a = b `seq` c `seq` undefined
module B where
import A
import C
data B
b :: A -> B -> C
b = a `seq` c `seq` undefined
module C where
import A
import B
data C
c :: A -> B -> C
c = a `seq` b `seq` undefined
This forms a complete directed graph for the definitions with this edge set: { (a, b), (a, c), (b, a), (b, c), (c, a), (c, b) }. A minimal feedback arc set for this would be { (b, a), (c, a), (c, b) }. This translate this Haskell would mean that b needs a {-# SOURCE #-} import of a and c needs a {-# SOURCE #-} import of both a and b. Here is what the hs-boot files defining aand b would look like:
-- hs-boot files
module A where
data A
a :: A -> B -> C
module B where
data B
b :: A -> B -> C
There’s a problem however. These type signatures contain types that aren’t defined. Here, the A and B .hs-boot files both need to import each other and .hs-boot files can’t contain cycles, so this program is impossible for GHC to compile.
Just for completeness, the .hs-boot files would form a graph with this edge set { (A, B), (A, C), (B, A), (B, C) } and a minimal feedback arc set for this would be { (B, A) }. This means that B needs a secondary .hs-boot file for A.
To give some context. I’m currently writing my own Haskell compiler that has very cyclical modules. I’ve run into this on occasion and I’ve had to work around it. Lastly, just to brag my compiler can currently compile this perfectly
, no .hs-boot files needed.