How should I recursively process a file in Haskell?

Question

Basically I'm expanding a literate program in Haskell. There are two things I need to look for to expand. Here's an example file:

program.c.lit:
==============
Some comments in the source file that I can ignore
    <main>=
    code.. code ...
    code..
    <a> 

Some comments in the source file that I can ignore
    <a>=
    code... code...
    code..

In a file, I need to look at each <some var> and substitute it with its matching definition defined below <some var>=. All the lines which are indented with 4 spaces below a <some defn>= are included in that chunk. In the end i should have a file consisting of only code ... lines.

How should I approach this problem in terms of file processing, what's a good approach? I'm comfortable with recursion, less comfortable with monads.

Answer 1

I will make a few assumptions in my answer. Feel free to correct me if one of them is incorrect:

• you are doing this as an exercise
• you only want to inline the top level definitions
• there is at most only one definition for a given variable name
• you want to simplify a given definition by inlining all known variables

If you are doing this for a "real" project, or want to make more complex transformations, I recommend that you look at existing packages such as haskell-src-exts.

Now if you want a robust solution, you will need those functions:

parse 
    :: String        -- the input text
    -> [Declaration] -- a datastructure representing the expression
inline
    :: Declaration   -- the definition to inline
    -> Declaration   -- the definition to modify
    -> Declaration   -- the result definition
showDecl :: Declaration -> String
simplify 
    :: String        -- the input text
    -> String        -- the variable name to simplify
    -> String        -- the result

Declaration can be as simple as (String, String) (the variable name and its definition). Note that I am using loosely typed definitions. I am also using String, which may not be the most efficient solution. You may consider using Text to speed things up.

The parse function can be tricky. I recommend using the parsec library. It uses a monad, but don't feel intimidated by it. Using monads does not require understanding them at a fundamental level. Actually the opposite is true. See here for an introduction. You can view the parsec type as a statement which consume a piece of text and maybe return some result.

parse input = /case analysis of / runParser (many parseBlock) () "source name" input

parseBlock = do
    skipComment
    parseDef

parseDef = do
    varName <- parseVar
    string " = "
    definition <- parseExpr
    return $ Declaration varName defintion

parseExpr = ...

Here, unit tests are your best friends. Be sure that all your smaller parsers are working well before combining them. Pay attention to the backtracking semantics (ie the try combinator) because you can easily shoot yourself in the foot with that.

The inline function is easier. It will just be a well thought out search and replace. The simplify function is just a matter of calling parse, extracting the declaration to simplify, and calling inline with all the other ones on it. No recursion needed.

Alternatively, your inline function can be of type Declaration -> String -> String, and edit directly the input string. This way you won't have to write the showDecl function.