Recursion issues in Haskell

Question

I have this compile function that is supposed to take a String and then yield an Expression.

This is how Expression was defined:

data Expression = Name Char | Lambda Char Expression | Apply Expression Expression 
        deriving Show

Let's say that the String that the 'compile' function takes is:

"\\x.\\y.yx"

So, at the end the compile function is supposed to yield this as the final Expression:

Lambda 'x' (Lambda 'y' (Name 'y') (Name 'x'))

This is the compile function:

compile :: [Char] -> Expression
compile (x:xs) = if [x] == "\\" then Lambda (head xs) (compile (tail xs))
                    else if [x] == "." then compile xs
                    else if null xs then Name x
                    else Name x

Currently this function obviates the last part of the Expression ((Name 'x')). My question is:

How this function can keep going further with more Names if once I yield a Name I can't keep going calling the same function with the rest of the Expression? Since Expression was defined like that, if Expression is a Name it just has a Name and no more, there is no expression left on it.

I mean, how can I take every single Name that is in Expression, 'telling' Haskell that I want to keep looking for Names and not just stop when a single Name is found.

I thought that maybe creating another function was a good idea, but I can't figure out how to call that function multiple times. Truth is that I am not really used to recursion in Haskell and I really need some help.

How can I do this?

chi · Accepted Answer · 2014-04-12 22:03:26Z

3

Directly using recursion on String for parsing, while doable, is tricky. In your lambda calculus language, handling (nested) parentheses for instance require some care.

If you want to attempt that, at the very least you should look into how LL parsers work: how to write an LL grammar, how to handle a lookahead symbol, and the basics of formal language theory in general.

If you'd rather learn these "by doing", try playing around with a parser library such as Parsec.

As a minor suggestion: while most papers about the lambda calculus use only single-letter variables and write e.g. "xy" for application, in an implementation you really want longer names for variables, even if it comes at the cost of requiring spaces between applied terms (e.g. "x y"). This makes the parser slightly harder to write but is worth the effort.

answered Apr 12, 2014 at 22:03

chi

117k4 gold badges143 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Cubic Over a year ago

Actually, writing an LL parser with direct recursion isn't hard at all. It's just tedious (Ok there are some corner cases that are tricky, but nothing that would come up when parsing lambda calculus expressions)

chi Over a year ago

@Cubic It is indeed easy to program (even in imperative languages!) if you understand what a LL grammar is, and a bit of the theory underlying. Yet, it is not something I would expect an average programmer to rediscover on their own without any previous exposure to formal languages. One needs to understand that (for the language at hand) you can write the grammar so that one lookahead token is enough to resolve non-determinism in the productions for each nonterminal.

Cubic Over a year ago

Well, you can often get away with one token lookahead. LL(1) doesn't cover all context free grammars after all.

Collectives™ on Stack Overflow

Recursion issues in Haskell

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related