Changes between Version 10 and Version 11 of TypeFunctions/ClassFamilies


Ignore:
Timestamp:
May 23, 2007 3:51:42 AM (7 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