Changes between Version 10 and Version 11 of TypeFunctions/ClassFamilies


Ignore:
Timestamp:
May 23, 2007 3:51:42 AM (8 years ago)
Author:
sulzmann
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • TypeFunctions/ClassFamilies

    v10 v11  
    7575=== Further Examples ===
    7676
     77Indexed classes appear to be highly useful to achieve
     78modularity for type-class based generic programming approaches.
    7779Here's a sketch of a "modular" extension of Hinze's "Generics for the masses" (GM)
    78 approach using indexed classes.  We first explain why in the original
     80approach
     81and Laemmel's and Peyton Jones' "Scrap your boilerplate" (SYB3) approach using indexed classes.  We first explain why in the original
    7982GM approach we cannot override generic with specific (ad-hoc) behavior
    80 in a modular fashion.
     83in a modular fashion. Then, we show how indexed classes
     84come to the rescue. Finally, we consider the SYB3 approach.
     85
     86==== Generics for the masses ====
    8187
    8288The main idea behind the GM approach is to provide
     
    203209
    204210
     211==== SYB3 ====
     212
     213The SYB3 approach faces similar challenges when it comes
     214to modularity.
     215
     216The generic cases.
     217{{{
     218class Typable a => Data a where
     219 gmapQ :: (forall b. Data b => b -> r) -> a -> [r]
     220
     221instance Data Char where
     222  gmapQ f c = []
     223instance Data a => Data [a] where 
     224  gmapQ f (x:xs) = [f x, f xs]
     225}}}
     226
     227A new generic "size" function.
     228{{{
     229class Size a where
     230  gsize :: a -> Int
     231-- specific instance
     232instance Size Name where ...
     233-- generic instance,
     234-- we use overlapping instances to cover all remaining cases
     235instance Data t => Size t where         -- (S)
     236  gsize t = 1 + sum (gmapQ gsize t)
     237}}}
     238The problem is that the instance (S) will not type check.
     239The program text gmapQ size is the trouble maker.
     240In this specific context, the combinator gmapQ expects as
     241its first argument a function of type
     242{{{
     243forall a. Data a => a -> Int
     244}}}
     245and the actual argument gsize has type
     246{{{
     247forall a. Size a => a -> Int
     248}}}
     249But the second type is not a subtype of the second.
     250For this subtype relation to hold, if we can satisfy
     251the condition
     252that from 'Data a' we can derive 'Size a' for any 'a'.
     253This condition is satisfied
     254if we make 'Sizes' a superclass of 'Data'.
     255But this will break modularity (we have to change
     256'Data's class declaration for each new generic function).
     257
     258'''MS note''': How to fix the (modularity) problem via indexed classes?
     259
    205260=== Type checking ===
    206261