[ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
Representing Chomsky hierarchy in the `natural' for functional programmers way (as a type-restricted linear lambda-calculus) is one of the attractions of the so-called Abstract Categorial Grammar (ACG) formalism. It is being developed by Philippe de Groote and collaborators. One can find many pointers on the ACG home page http://www.loria.fr/equipes/calligramme/acg/ The specific question about Chomsky hierarchy and the orders of types in ACG is answered on slide 44 (PDF page 44) of the following course http://www.loria.fr/equipes/calligramme/acg/publications/esslli-09/2009-esslli-acg-week-1-day-3.pdf (Of course one have to read previous slides to understand the L(n,m) notation). Slide 56 talks about the hierarchy of tree languages (rather than string languages) and the open problems. Incidentally, ACG turns out to closely related to the Tagless-Final approach (as Philippe de Groote himself told me).
