| 73 | |
| 74 | |
| 75 | === Further Examples === |
| 76 | |
| 77 | Here'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 |
| 79 | GM approach we cannot override generic with specific (ad-hoc) behavior |
| 80 | in a modular fashion. |
| 81 | |
| 82 | The main idea behind the GM approach is to provide |
| 83 | a uniform representation of data types in terms of |
| 84 | unit, sum and product types. |
| 85 | Generic functions are defined in terms of this uniform |
| 86 | rather than the concrete structural representation of a data type. |
| 87 | The programmer only needs to maintain a type isomorphism between |
| 88 | the uniform and concrete representation. |
| 89 | Thus, there is no need to extend |
| 90 | the (now generic) definition of functions in case we include new data types. |
| 91 | |
| 92 | Here is a (over-simplified) presentation of the GM approach |
| 93 | We only consider the uniform representations "literals" and "plus". |
| 94 | |
| 95 | {{{ |
| 96 | data Lit = Lit Int |
| 97 | data Plus a b = Plus a b |
| 98 | class Generic g where |
| 99 | lit :: g Lit |
| 100 | plus :: g a -> g b -> g (Plus a b) |
| 101 | }}} |
| 102 | |
| 103 | Below is a generic definition of some evaluation function. |
| 104 | |
| 105 | {{{ |
| 106 | newtype Ev a = Ev{eval' :: a -> Int} |
| 107 | instance Generic Ev where |
| 108 | lit = Ev (\x -> case x of Lit i -> i) |
| 109 | plus a b = |
| 110 | Ev (\p -> case p of |
| 111 | (Plus x y) -> eval' a x + eval' b y) |
| 112 | }}} |
| 113 | |
| 114 | |
| 115 | In order to use the evaluator on its familiar type, |
| 116 | we need a ``dispatcher'' function to select the appropriate case of |
| 117 | a generic function. |
| 118 | The most straightforward approach is to use an ad-hoc polymorphic |
| 119 | (therefore extensible) function. |
| 120 | {{{ |
| 121 | class Rep a where |
| 122 | rep :: Generic g => g a |
| 123 | instance Rep Lit where |
| 124 | rep = lit |
| 125 | instance (Rep a,Rep b) => Rep (Plus a b) where |
| 126 | rep = plus rep rep |
| 127 | eval :: Rep t => t -> Int |
| 128 | eval = eval' rep |
| 129 | }}} |
| 130 | The dispatcher function rep will select the |
| 131 | appropriate generic case depending on the concrete type context. |
| 132 | We can straightforwardly introduce new generic functions (omitted here). |
| 133 | |
| 134 | Suppose we introduce a new ad-hoc case "minus" which has the |
| 135 | same structural representation as "plus". |
| 136 | |
| 137 | {{{ |
| 138 | data Minus a b = Minus a b |
| 139 | class Generic g => GMinus g where |
| 140 | minus :: g a -> g b -> g (Minus a b) |
| 141 | instance GMinus Ev where |
| 142 | minus a b = |
| 143 | Ev (\p -> case p of |
| 144 | (Minus x y) -> eval' a x - eval' b y) |
| 145 | instance (Rep a,Rep b) => Rep (Minus a b) where |
| 146 | rep = minus rep rep |
| 147 | }}} |
| 148 | |
| 149 | The problem is that we cannot access this new case, unless |
| 150 | we update the type of the dispatcher function rep. We must |
| 151 | change rep's declaration as follows. |
| 152 | |
| 153 | {{{ |
| 154 | class Rep a where |
| 155 | rep :: GMinus g => g a |
| 156 | -- original code: rep :: Generic g => g a |
| 157 | }}} |
| 158 | |
| 159 | But changing rep's class declaration requires to recompile the entire |
| 160 | program. Hence, extending generic definitions with ad-hoc cases |
| 161 | cannot be modularly. |
| 162 | |
| 163 | Such problems go away if we use indexed classes. |
| 164 | More precisely, we use a type indexed class in rep's class declaration. |
| 165 | |
| 166 | The generic cases. |
| 167 | {{{ |
| 168 | class Rep a where |
| 169 | class Generic' g a |
| 170 | -- or class Generic' g :: * -> Class using Tom's suggestion |
| 171 | rep :: Generic' g a => g a |
| 172 | instance Rep Lit where |
| 173 | class Generic g => Generic' g Lit |
| 174 | -- better written as? Generic' g Lit = Generic g |
| 175 | rep = lit |
| 176 | instance (Rep a,Rep b) => Rep (Plus a b) where |
| 177 | class Generic g => Generic' g (Plus a b) |
| 178 | rep = plus rep rep |
| 179 | eval :: Rep t => t -> Int |
| 180 | eval = eval' rep |
| 181 | }}} |
| 182 | |
| 183 | The ad-hoc case. |
| 184 | {{{ |
| 185 | class GMinus g where |
| 186 | minus :: g a -> g b -> g (Minus a b) |
| 187 | instance GMinus Ev where |
| 188 | minus a b = |
| 189 | Ev (\p -> case p of |
| 190 | (Minus x y) -> eval' a x - eval' b y) |
| 191 | |
| 192 | instance (Rep a,Rep b) => Rep (Minus a b) where |
| 193 | class GMinus g => Generic' g (Minus a b) |
| 194 | rep = minus rep rep |
| 195 | }}} |
| 196 | |
| 197 | Notice the use of indexed classes to select appropriate classes |
| 198 | for each instance. |
| 199 | |
| 200 | |
| 201 | General insight: It seems that via indexed classes we can encode |
| 202 | a type-passing type-class translation scheme. |
| 203 | |