使用DataKinds的類型級別映射

Question

我有一個常見模式，其中有一個類型級別列表[*]，我想將類型* -> *的構造函數應用於列表中的每個元素。例如，我想將'[Int, Double, Integer]的類型更改爲'[Maybe Int, Maybe Double, Maybe Integer]。

這裏是我嘗試實現類型級別map。

{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, TypeOperators, DataKinds, ScopedTypeVariables, GADTs #-} 

-- turns a type list '[b1, b2, b3] 
-- into the type list '[a b1, a b2, a b3] 
class TypeMap (a :: * -> *) (bs :: [*]) where 
    type Map a bs :: [*] 

instance TypeMap a '[b] where 
    type Map a '[b] = '[a b] 

instance TypeMap a (b1 ': b2 ': bs) where 
    type Map a (b1 ': b2 ': bs) = ((a b1) ': (Map a (b2 ': bs))) 


data HList :: [*] -> * where 
       HNil :: HList '[] 
       HCons :: a -> HList as -> HList (a ': as) 

class Foo as where 
    toLists :: HList as -> HList (Map [] as) 

instance Foo '[a] where 
    toLists (HCons a HNil) = HCons [a] HNil 

instance (Foo (a2 ': as)) => Foo (a1 ': a2 ': as) where 
    toLists (HCons a as) = 
     let as' = case (toLists as) of 
        (HCons a2 as'') -> HCons [head a2] as'' -- ERROR 
     in HCons [a] as' 

這將導致錯誤

Could not deduce (a3 ~ [t0]) 
    from the context (Foo ((':) * a2 as)) 
     bound by the instance declaration at Test.hs:35:10-50 
    or from ((':) * a1 ((':) * a2 as) ~ (':) * a as1) 
     bound by a pattern with constructor 
       HCons :: forall a (as :: [*]). 
          a -> HList as -> HList ((':) * a as), 
       in an equation for `toLists' 
     at Test.hs:36:14-23 
    or from (Map [] as1 ~ (':) * a3 as2) 
     bound by a pattern with constructor 
       HCons :: forall a (as :: [*]). 
          a -> HList as -> HList ((':) * a as), 
       in a case alternative 
     at Test.hs:38:22-34 
     `a3' is a rigid type variable bound by 
      a pattern with constructor 
      HCons :: forall a (as :: [*]). 
         a -> HList as -> HList ((':) * a as), 
      in a case alternative 
      at Test.hs:38:22 
    Expected type: HList (Map [] ((':) * a2 as)) 
     Actual type: HList ((':) * [t0] as2) 
    In the return type of a call of `HCons' 
    In the expression: HCons [head a2] as'' 
    In a case alternative: (HCons a2 as'') -> HCons [head a2] as'' 

我已經嘗試添加豐富的類型註釋，但錯誤或多或少出來的一樣：GHC甚至不能推斷出的第一個元素HList是一個（正常）列表。我在這裏做些傻事嗎？非法的東西？或者有什麼辦法嗎？

Answer 1

當您編寫TypeMap a (b1 ': b2 ': bs)時，與您定義的Map ...所做的遞歸不一致，當您嘗試使用不是1或2個元素的TypeMap列表時，這隻會導致錯誤。此外，在你的情況下，只需要一個類型家庭就更清潔了。

type family TypeMap (a :: * -> *) (xs :: [*]) :: [*] 
type instance TypeMap t '[] = '[] 
type instance TypeMap t (x ': xs) = t x ': TypeMap t xs 

注意這是相當多的直接翻譯：

map f [] = [] 
map f (x:xs) = f x : map f xs 

Answer 2

的最小變化，使你的代碼的編譯是改變你的情況爲[a]和b1:b2:bs爲實例爲[]和b:bs。

instance TypeMap a '[] where 
    type Map a '[] = '[] 

instance TypeMap a (b ': bs) where 
    type Map a (b ': bs) = a b ': Map a bs