Resolution of function call in existential type

Question

After reading this page in existential languages ​​in Haskell, I was forced to check the limits of this behavior, so I wrote the following code fragment:

{-# LANGUAGE ExistentialQuantification #-} data Showable = forall a. Show a => MkShowable a pack :: Show a => a -> Showable pack = MkShowable instance Show Showable where show (MkShowable x) = show x 

The Showable type Showable very similar to the ShowBox type created in the above link. Then I created this contrived example to illustrate my question.

 showSomething :: Bool -> Showable showSomething True = pack 1 showSomething False = pack "ABC" main :: IO () main = do x <- getLine let y = read x print $ showSomething y 

This code (which works fine) asks the user for input (which should be “True” or “False”), and then outputs 1 if it is True or "ABC" if it is False.

But I can’t fully understand how the system does this. Mathematically this makes sense. But I do not see how the computer can solve it. For me, it seems that at runtime, the system decides whether to call the Int show or String show function, but that would mean the existence of something like C ++ vtables, I believe that Haskell has a concept.

My question is: how does he resolve this? The system cannot know in advance whether I will enter true or false, so it cannot know which show call at compile time, but it clearly works in both cases.

Answer 1

One way to implement type classes is to transfer a dictionary of functions that implement a type class under the hood. For example, a function with a signature

 f :: Show a => T 

will be transferred to

 f' :: (a -> String) -> T 

by the compiler and whenever show used inside f , it is replaced with an additional argument (in reality there would be more functions, all of which are declared in show ).

Similarly, the data type

 forall a . Show a => MkShowable a 

will be transferred to

 forall a . MkShowable' (a -> String) a 

Thus, the converted code may look like this:

 {-# LANGUAGE ExistentialQuantification #-} data Showable' = forall a . MkShowable' (a -> String) a pack' :: Show a => a -> Showable' pack' = MkShowable' show instance Show Showable' where show (MkShowable' fx) = fx showSomething :: Bool -> Showable' showSomething True = pack' 1 showSomething False = pack' "ABC" 

When pack is called, the show implementation is also passed to the constructor so that it is available when needed.

Answer 2

Yeah. Many language functions (most of them extensions) in Haskell can be considered as basically implementing many concepts that are combined into a complex monolith of a “class” in OO programming, but individually as separate functions. Existential types with class type restrictions are mostly vtables!

For show (MkShowable x) work without any other restrictions, MkShowable x must contain enough information to know how show x . So that is exactly what he does; although it contains only one field, it contains additional information.

This is essentially the same as the function foo :: Show a => a; foo x = show x foo :: Show a => a; foo x = show x seems to have only one parameter, but really needs to get enough additional information to know how show x ; it cannot be “hard bound” because foo is probably used in several different types. But where foo requires the caller to pass this information from the outside (and the type system applies it), the Showable value contains exactly the same information to be able to retrieve it to go to functions like foo .

So now with this tool, unlike ExistentialQuantification , the problem of determining which instance of show is being called is simply the choice between two values ​​of the same type (which contains the show instance for an unknown type along with a value of the same type) that easy to do; no knowledge of the compilation time at which it is needed is required.