Changes between Version 10 and Version 11 of TypeFunctions/ClassFamilies

May 23, 2007 3:51:42 AM (8 years ago)



  • TypeFunctions/ClassFamilies

    v10 v11  
    7575=== Further Examples === 
     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 
     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. 
     86==== Generics for the masses ==== 
    8288The main idea behind the GM approach is to provide 
     211==== SYB3 ==== 
     213The SYB3 approach faces similar challenges when it comes 
     214to modularity.  
     216The generic cases. 
     218class Typable a => Data a where 
     219 gmapQ :: (forall b. Data b => b -> r) -> a -> [r] 
     221instance Data Char where 
     222  gmapQ f c = [] 
     223instance Data a => Data [a] where   
     224  gmapQ f (x:xs) = [f x, f xs] 
     227A new generic "size" function. 
     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) 
     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 
     243forall a. Data a => a -> Int 
     245and the actual argument gsize has type 
     247forall a. Size a => a -> Int 
     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). 
     258'''MS note''': How to fix the (modularity) problem via indexed classes? 
    205260=== Type checking ===