On 2002-08-22T17:04:02+0930, Dr Mark H Phillips wrote:
But for the "Trie" type you have above, I am not aware of any way of converting this to an "essential type". What I am thinking, is something like [(a, *)] where '*' means to recursively refer to yourself.
I guess this depends on what you mean by "essential type". If you are willing to grant me a few additional types as essential ones: data Fix f = Fix (f (Fix f)) newtype Pair f g a = Pair (f a, g a) newtype Compose f a = Compose (f a) newtype Self a = Self a newtype Const t a = Const t then I can build a type roughly isomorphic to what you call "[(a,*)]": type T a = Fix (Compose [] (Pair (Const a) Self)) For example, the value "[('a', [])]" would be written Fix (Compose [Pair (Const 'a', Self (Fix (Compose [])))]) :: Fix (Compose [] (Pair (Const Char) Self)) One place to learn more about these things is section 4 of Mark P. Jones. Functional programming with overloading and higher-order polymorphism. In Johan Jeuring and Erik Meijer, editors, Advanced Functional Programming: First International Spring School on Advanced Functional Programming Techniques, number 925 in Lecture Notes in Computer Science, pages 97-136. Springer-Verlag, Berlin, 1995. http://www.cse.ogi.edu/~mpj/pubs/springschool.html The paper is also a great read otherwise! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig http://oxford.freeexchange.co.uk/pages/6001.html