1. 14

  2. 7

    I would guess that GHC generates these data structures at runtime to prevent a combinatorial explosion of pregenerated typeclass dictionaries when using more advanced typeclass rules.

    It’s not just that. Haskell, unlike C++, has polymorphic recursion, which makes full specialization outright impossible. Here is a stupid example:

    data Tree a = Leaf a | Node [Tree [a]]
    instance Show a => Show (Tree a) where
      show (Leaf x) = "Leaf " ++ show x
      show (Node xs) = "Node " ++ show xs

    There is no way to fully specialize the code for, say, show :: Tree Int -> String, because a Tree Int may contain nested Tree [Int]s, which in turn may contain nested Tree [[Int]]s, and so on.