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 ?

Accepted Answer

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.

Data structures with cyclic dependencies in haskell

Solution

Problem