[Haskell-cafe] How to define Show [MyType] ?

[Ryan Ingram]

On Sun, Dec 7, 2008 at 1:51 AM, Fraser Wilson <blancolioni at gmail.com> wrote:
> (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