On Sun, Dec 7, 2008 at 1:51 AM, Fraser Wilson
(I know you know this, I just have this weird fascination with the showList wart, although for the life of me I can't think of a better way of doing it)
Well, if you extend the compiler's core language with "typecase", you can solve a lot of these problems. Then the implementation of typeclasses changes from "dictionary-passing" to "type-passing", and overlapping instances can be resolved by dynamic dispatch. For example, the following program: class C a where view :: a -> String instance C Char where view x = viewChar x -- primitive instance C String where view x = viewString x -- primitive instance C a => C [a] where view [] = "[]" view (x:xs) = concat $ [ "[", view x ] ++ concatMap (\y -> [ ", ", view y ]) xs ++ [ "]" ] would compile to this "core": view :: Type a -> a -> String view t = typecase t of Char -> viewInstanceChar [t'] -> typecase t' of Char -> viewInstanceString _ -> viewInstanceList t' _ -> error ("no instance for View " ++ show t) viewInstanceChar x = viewChar x viewInstanceString x = viewString x viewInstanceList t x = concat $ [ "[", view t x ] ++ concatMap (\y -> [ ", ", view t y ]) xs ++ [ "]" ] I think at least one Haskell compiler implements typeclasses this way. One nice property of this solution is that you retain parametricity, at least unless you also include "typeof"; any function with a typeclass constraint takes an additional type argument. Passing "Type a" around in this way is like using Typeable in current Haskell except it would have to be supported at the compiler level. And of course all of the standard optimizations apply, so if you statically know that the type is [Char] you inline "view" and get the correct answer. If you statically know that the type is [x] but you don't know x, you can still specialize the case down to just the typecase on the inside of the list. The biggest wart is that "view" is not a total function; the compiler needs to be extra careful to only call it on types that are instances of "View". I wonder if there is a good way to solve this problem? -- ryan