Ken, Thanks for the references! Have two-level types been applied to parser generation? Best wishes, --greg Greg Meredith <lgreg.meredith@biosimilarity.com> wrote in article <5de3f5ca0712111100l79ec280fl1d828b12125abbdc@mail.gmail.com
in gmane.comp.lang.haskell.cafe: Here is an idea so obvious that someone else must have already thought of it and worked it all out. Consider the following grammar.
Hello!
If I understand your basic idea correctly, it is to split a recursive data type into two parts, a non-recursive type constructor and a knot-tying recursive type. This idea has been christened "two-level types" by
Tim Sheard and Emir Pasalic. 2004. Two-level types and parameterized modules. Journal of Functional Programming 14(5):547-587.
The idea dates earlier, to initial-algebra semantics and "functional programming with bananas and lenses":
Mark P. Jones. 1995. Functional programming with overloading and higher-order polymorphism. In Advanced functional programming: 1st international spring school on advanced functional programming techniques, ed. Johan Jeuring and Erik Meijer, 97-136. Lecture Notes in Computer Science 925. http://web.cecs.pdx.edu/~mpj/pubs/springschool.html<http://web.cecs.pdx.edu/%7Empj/pubs/springschool.html>
Erik Meijer, Maarten Fokkinga, and Ross Paterson. 1991. Functional programming with bananas, lenses, envelopes and barbed wire. In Functional programming languages and computer architecture: 5th conference, ed. John Hughes, 124-144. Lecture Notes in Computer Science 523. http://research.microsoft.com/~emeijer/Papers/fpca91.pdf<http://research.microsoft.com/%7Eemeijer/Papers/fpca91.pdf>
Cheers, Ken
Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com