在 Haskell 中的异构列表中键入安全查找

Question

我想为以下数据类型开发一个类型安全的查找函数：

data Attr (xs :: [(Symbol,*)]) where
   Nil  :: Attr '[]
   (:*) :: KnownSymbol s => (Proxy s, t) -> Attr xs -> Attr ('(s , t) ': xs)

明显的查找函数如下：

 lookupAttr :: (KnownSymbol s, Lookup s env ~ 'Just t) => Proxy s -> Attr env -> t
 lookupAttr s ((s',t) :* env')
       = case sameSymbol s s' of
            Just Refl -> t
            Nothing   -> lookupAttr s env'

其中 Lookup 类型族在单例库中定义。此定义无法在 GHC 7.10.3 上进行类型检查，并显示以下错误消息：

 Could not deduce (Lookup s xs ~ 'Just t)
   from the context (KnownSymbol s, Lookup s env ~ 'Just t)
      bound by the type signature for
             lookupAttr :: (KnownSymbol s, Lookup s env ~ 'Just t) =>
                           Proxy s -> Attr env -> t

此消息是为递归调用 lookupAttr s env' 生成的。这是合理的，因为我们有 if

Lookup s ('(s',t') ': env) ~ 'Just t

持有，

s :~: s'

无法证明，那么

Lookup s env ~ 'Just t

必须持有。我的问题是，我怎样才能说服 Haskell 类型检查器这是真的？

Answer 1

Lookup is defined in terms of :== equality, which comes from here。大致上，Lookup是这样实现的：

type family Lookup (x :: k) (xs :: [(k, v)]) :: Maybe v where
  Lookup x '[] = Nothing
  Lookup x ('(x' , v) ': xs) = If (x :== x') (Just v) (Lookup x xs)

sameSymbol s s' 上的模式匹配不会向我们提供有关 Lookup s env 的任何信息，并且不会让 GHC 减少它。我们需要了解 s :== s'，为此我们需要使用 :== 的 singleton version。

data Attr (xs :: [(Symbol,*)]) where
   Nil  :: Attr '[]
   (:*) :: (Sing s, t) -> Attr xs -> Attr ('(s , t) ': xs)

lookupAttr :: (Lookup s env ~ 'Just t) => Sing s -> Attr env -> t
lookupAttr s ((s', t) :* env') = case s %:== s' of
  STrue  -> t
  SFalse -> lookupAttr s env'

通常，您不应该使用 KnownSymbol、sameSymbol 或 GHC.TypeLits 中的任何东西，因为它们太 "low-level" 并且不玩默认情况下连同 singletons。

当然你可以自己写Lookup等函数，不需要使用singletons导入；重要的是同步术语级别和类型级别，以便术语级别模式匹配为类型级别生成相关信息。

在 Haskell 中的异构列表中键入安全查找

Type safe lookup on heterogeneous lists in Haskell

haskell

dependent-type

type-level-computation