On Sat, 2009-10-10 at 20:12 +0200, Ben Franksen wrote: > Since 'some' is defined recursively, this creates an infinite production for > numbers that you can neither print nor otherwise analyse in finite time.
Yes, sorry, I should have been more careful there. One has to be careful to handle EDSLs that have potentially infinite syntax properly. > I can see at least two solutions: One is to parameterize everything over the > type of terminals, too. > The second solution (which I followed) is to break the recursion by adding > another nonterminal to the NT type: A third solution is to add the Kleene star to the grammar DSL, so the representation of productions becomes: > data Production nt a > = Stop a > | Terminal Char (Production nt a) > | forall b. NonTerminal (nt b) (Production nt (b -> a)) > | forall b. Star (Production nt b) (Production nt ([b] -> a)) You also need to add the necessary parts for Alternative to the Production type too, because they may be nested inside Star constructors: > | Zero > | Choose (Production nt a) (Production nt a) The type Production nt is now directly an Applicative and an Alternative and also has the combinator: > star :: Production nt a -> Production nt [a] > star p = Star p $ Stop id The type of grammars is changed to (with the additional of the starting nonterminal, as you point out): > type Grammar nt = forall a. nt a -> Production nt a It is probably also possible to write a function that converts grammars with “Star”s in to ones without by introducing new non-terminals in the way you did. Bob -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
