interpreter - How can one parse a function of unknown type in Haskell? -

i'm haskell novice, , i'm trying write parser evaluates set of simple haskell expressions. however, i'm running difficulty functions when don't know in advance type are.

suppose, example, know string want parse evaluates integer. here few possibilities string might be.

"succ 4"

"head [5,6,7]"

"sum [1,3,1]"

"length [a,b,c,d,e]"

"pred $ sum $ take 3 $ iterate succ 1"

naively i'd last example process this.

1. parse out function pred, deduce fact has type (enum a) => -> a , string represents integer rest of string (after dollar) still represents integer.

2. parse out function sum , deduce i'm trying evaluate list of integers.

3. parse out function take , deduce i'm looking integer , list of integers.

4. parse out 3 , deduce rest of string should list of integers.

5. parse out iterate , deduce i'm looking function of type int -> int , integer.

6. parse out succ , 1.

7. perform evaluation.

the problem @ each stage of process, there many possible types next object come across, examples illustrate. can't write general-purpose parser pulls out function , leaves string represents argument (or arguments). if have write separate parsers every conceivable kind of function, rapidly become nightmare, when have @ functions of more 1 variable.

i realize it's not quite bad that, since many functions defined several different types. if, example, "if string begins "succ" pull out , apply succ evaluation of rest of string", complains should have specified dealing type in enum class. have trouble when i'm dealing type that's not in class.

full disclosure: i'm using simple parser in graham hutton's book build want build. maybe answer there more advanced parsers out there cope kind of problem , should using instead.

as pointed out in comment, compilers , interpreters work in several passes, , don't try work in each pass.

typically parsing 1 pass, perhaps preceded lexing. next type-checking, , either compiler translation target language (generally in several more passes), or interpreter, evaluation. quick , dirty experiment, or dynamic language, can omit type-checking.

you should first define abstract syntax tree represent parsed expressions - haskell algebraic datatypes ideal this. example "succ 4" might parse term apply (symbol "succ") (int 4). need local information generate this, rather types of surrounding values - e.g. 4 translates int 4 because it's number , not symbol.

you can define type-checker work on syntax tree, or jump directly evaluating , check types make sense dynamically. type-checking language haskell not simple - classic paper "typing haskell in haskell" best starting point if want that.