Data structures with cyclic dependencies in haskell

Question

I'm trying to implement simple parser in haskell using parsec library (for learning purposes). So I wrote bunch of data structutes and related functions like this:

data SourceElement 
    = StatementSourceElement Statement
    | FunctionSourceElement FunctionName FunctionBody

data Statement 
    = IfStatement Expr Statement Statement
    | WhileStatement Expr Statement

data FunctionBody = FunctionBody [SourceElement]

parseSourceElement :: Parser SourceElement
parseSourceElement = ...

parseFunctionBody :: Parser FunctionBody
parseFunctionBody = ...

It works fine. Now I want to split this stuff into two modules to separate FunctionBody and Statement data structures (because of readability issues). But I can't! The reason is cyclic dependency between SourceElement and FunctionBody.

So, is there any way to solve this problem ?

Answer 1

The typical way I break dependency cycles is by parameterizing something out. In this case, your Function module might do function parsers for your language, but expressed in such a way that it can do so no matter what the rest of the language is like. Thus:

module Function where 

data FunctionBody e = FunctionBody [e]

parseFunctionBody :: Parser e -> Parser (FunctionBody e)

And

module AST where

data SourceElement
    = StatementSourceElement Statement
    | FunctionSourceElement FunctionName (FunctionBody SourceElement)

Thus the mutual recursion is abstracted into a simple recursion + parameterization. I think parameterization is at least as important as separating different things into different files, so it's kind of nice (and kind of annoying) that one forces the other.

Answer 2

Haskell actually allows recursive modules, and GHC supports them (with a minor inconvenience of writing .hs-boot files). See How to compile mutually recursive modules.

I don't see anything wrong with using this feature here.