Personal tools

Mutually recursive modules

From HaskellWiki

Revision as of 14:23, 6 February 2009 by Lemming (Talk | contribs)

Jump to: navigation, search

Mutually recursive modules are modules that import each other. This way it is not possible to find a sequence to compile them one after another. This is a typical problem of languages with a strong module system, in contrast to languages like C, where all parts of a program are merged textually by the preprocessor before compiling them.

Simple example:

module A where
 
import B
 
 
module B where
 
import A

If possible, mutually recursive modules should be avoided, since they complicate module dependencies. Once you have mutually recursive modules in a package, you will no longer be able to put modules of an import cycle into different packages, because mutually recursive packages are not supported.


Contents

1 Compiler support

The Haskell 98 report says, that Haskell 98 allows mutually recursive modules, but not all compilers support them completely or even in a simple way.

1.1 GHC

GHC supports mutually recursive modules in a limited way and requires additional information. You must break the data dependency cycles manually by creating .hiboot files. Up to version 6.10 it is not possible to create mutually recursive class definitions across modules, e.g.

module A where
 
import B
 
class B t => A t where
   ...
 
 
module B where
 
import A
 
class B t where
   f :: A t => t -> t


1.2 Hugs

Hugs until September 2006 does not support mutual recursive modules.


2 Resolve mutual recursion

There are some ways to avoid mutually recursive imports, which we will describe below.

2.1 Use type parameters

If you have the definitions

module A where
 
import B
 
data A = A B
 
 
module B where
 
import A
 
data B = B A

you can break the cycle by adding a type parameter to one of these data declarations. By thinking about that possibility you might find that you want to generalize one of the data structures anyway. This yields:

module A where
 
data A b = A b
 
 
module B where
 
import A
 
data B = B (A B)

This way you only generalize the data structure.

All functions that use
A
may use it with the fixed type argument
B
.


2.2 Global type definitions

Some packages use to define all data types and classes in one module of the package. These types are then imported by all other modules of the package. This may however conflict with the use of qualified names, since in this style clashes of unqualified type identifiers in the type definition module are more likely.