In Monad.Reader 8, Conrad Parker shows how to solve the Instant Insanity puzzle in the "Haskell" type system. Along the way he demonstrates very clearly something that was implicit in Mark Jones' "Type Classes with Functional Dependencies" paper if you read it very very carefully (which I hadn't, but on re-reading it is there). That is, Haskell types plus multiparameter type classes plus functional dependencies is a logic programming language. In fact it is a sufficiently powerful language to emulate any Turing machine calculation as a type checking problem.
So we have C++ : imperative language whose type system is a Turing-complete functional language (with rather twisted syntax) Haskell: functional language whose type system is a Turing- complete logic programming language (with rather twisted syntax) Since not all Turing machines halt, and since the halting problem is undecidable, this means not only that some Haskell programs will make the type checker loop forever, but that there is no possible meta- checker that could warn us when that would happen. I've been told that functional dependencies are old hat and there is now something better. I suspect that "better" here means "worse". _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe