Brandon Michael Moore wondered: | I'm wondering if there are any libraries out there | for creating parsers that lazily build up their | result. Joe English answered: | type Parser sym result = [sym] -> Maybe (result, [sym]) However, a parser for a particular type T might actually just return T directly, without any Maybe in the way, if T has a failure constructor built-in. Something like: data T = Plus T T | ... | Fail Error Now, a parser for T can already start building its result without having to wait for the whole thing to succeed. This gets a bit ugly, especially when dealing with many types that are being parsed, or with the extra failure constructor always being part of the datatype. One way of adding such a constructor to any type would be: data Result a = Val a | forall b c . Apply2 (b -> c -> Result a) (Result b) (Result c) | Fail Error This gives you a way of creating an 'a' not only lazily, but one can decide oneself what to do with failure and when to do it. Example: When parsing the following faulty expression "(1+2)+blurp" And expecting an Int as a result, the parser would build the following expression: Apply2 (\x y -> Val (x+y)) (Apply2 (\x y -> Val (x+y)) (Val 1) (Val 2)) (Fail "unrecognized `blurp'") None of this is type checked and surely contains bugs, but I hope you get the idea. The hope is that a value of type `Result a' gives you more information and better space behavior than just a value of type `Maybe a'. /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen Chalmers University, Gothenburg, Sweden.