Understanding type-directed resolution in Haskell with existential types

Question

I've been learning Haskell and encountered a point of confusion. When defining an existential type with a custom type class, it seems that other algebraic data types, which are instances of the same custom type class, share the same structure from the type class.

Here's an example:

{-# LANGUAGE ExistentialQuantification #-}

class MyShow a where
    myShow :: a -> String

data Showable = forall a. MyShow a => Showable a

instance MyShow Showable where
    myShow (Showable a) = myShow a

data CustomType = CustomInt Int | CustomString String

instance MyShow CustomType where
    myShow (CustomInt i) = "CustomInt " ++ show i
    myShow (CustomString s) = "CustomString " ++ s

main :: IO ()
main = do
    let intShowable = Showable (CustomInt 5)
        stringShowable = Showable (CustomString "Hello, Haskell!")

    putStrLn $ myShow intShowable
    putStrLn $ myShow stringShowable

In the above code, my concern is with the following part:

instance MyShow Showable where
    myShow (Showable a) = myShow a

I believe myShow a is not a recursive function; instead, it acts as a placeholder for myShow functions that are instances implemented in the MyShow type class.

I think myShow a is a placeholder that will be replaced with the appropriate function based on the relevant types when the compiler compiles the program, and it operates as type-directed resolution.

Is my understanding correct, or is there a different interpretation of this behavior?

I hope the clear explanation. Thanks for your patient.

Answer 1

Your intuition is correct. A common implementation of typeclass constraints uses hidden dictionary arguments to pass around the relevant typeclass methods implementations.

Your code is roughly compiled as the one below. Note how the code below has no typeclasses.

data Showable = forall a. Showable (a -> String) a
                                   ------------- hidden "dictionary" field

-- no longer an instance, now a plain function
myShow_Showable (Showable otherMyShow a) = otherMyShow a
                          ----------- we call the hidden field, no recursion

data CustomType = CustomInt Int | CustomString String

-- no longer an instance, now a plain function    
myShow_CustomType (CustomInt i) = "CustomInt " ++ show i
myShow_CustomType (CustomString s) = "CustomString " ++ s

main :: IO ()
main = do
    let intShowable = Showable myShow_CustomType (CustomInt 5)
                               ----------------- added by the compiler
        stringShowable = Showable myShow_CustomType (CustomString "Hello, Haskell!")
                                  -----------------

    putStrLn $ myShow_Showable intShowable
               --------------- the compiler chose the right instance
    putStrLn $ myShow_Showable stringShowable
               ---------------

The compiler uses type-directed reasoning to infer the values of the hidden dictionary arguments/fields. You can directly observe this if you compile a program asking GHC to "dump the Core" with the -ddump-simpl flag (warning: a lot of low-level code will be printed. Core is somehow Haskell-like but not so easy to understand at first).