具有 Haskell 约束的不安全蕴含

Question

我正在使用 constraints 包（用于 GHC Haskell）。我有一个类型族来确定类型级列表是否包含元素：

type family HasElem (x :: k) (xs :: [k]) where
  HasElem x '[] = False                                                                               
  HasElem x (x ': xs) = True                                                                          
  HasElem x (y ': xs) = HasElem x xs

这行得通，但它没有告诉我的一件事是

HasElem x xs   entails   HasElem x (y ': xs)

因为类型族不是 "is element of" 语句的归纳定义（就像你在 agda 中那样）。我很确定，在 GADT 可以提升到类型级别之前，没有办法用数据类型来表达列表成员资格。

所以，我用 constraints 包写了这个：

containerEntailsLarger :: Proxy x -> Proxy xs -> Proxy b -> (HasElem x xs ~ True) :- (HasElem x (b ': xs) ~ True)
containerEntailsLarger _ _ _ = unsafeCoerceConstraint

怪异，但它有效。我可以对蕴含进行模式匹配以获得我需要的东西。我想知道它是否会导致程序崩溃。似乎不能，因为 unsafeCoerceConstraint 被定义为：

unsafeCoerceConstraint = unsafeCoerce refl

并且在 GHC 中，类型级别在运行时被省略。我想我会检查一下，只是为了确保这样做没问题。

--- 编辑 ---

既然还没有人给出解释，我想我会稍微扩展一下这个问题。在我正在创建的不安全蕴涵中，我只需要一个类型族。如果我做了一些涉及类型类字典的事情，而不是像这样：

badEntailment :: Proxy a -> (Show a) :- (Ord a)
badEntailment _ = unsafeCoerceConstraint

我认为这几乎肯定会导致段错误。这是真的？如果是这样，它与原来的有什么不同？

--- 编辑 2 ---

我只是想提供一点背景来说明我为什么对此感兴趣。我的兴趣之一是在 Haskell 中对关系代数进行可用编码。我认为无论您如何定义函数以在类型级列表上工作，都会有一些明显的事情没有被正确证明。例如，我以前的一个约束（对于半连接）看起来像这样（这是来自记忆，所以它可能不准确）：

semijoin :: ( GetOverlap as bs ~ Overlap inAs inBoth inBs
            , HasElem x as, HasElem x (inAs ++ inBoth ++ inBs)) => ...

所以，很明显（对一个人来说）如果我采用两个集合的并集，它包含 as 中的元素 x，但我不确定有可能合法地说服约束求解器。所以，这就是我做这个技巧的动机。我创建了 entailments 来欺骗约束求解器，但我不知道它是否真的安全。

Answer 1

我不知道这是否满足您的其他需求，但它实现了这个特定目的。我自己不太擅长类型族，所以我不清楚你的类型族实际上可以用来做什么。

{-# LANGUAGE ...., UndecidableInstances #-}
type family Or (x :: Bool) (y :: Bool) :: Bool where
  Or 'True x = 'True
  Or x 'True = 'True
  Or x y = 'False

type family Is (x :: k) (y :: k) where
  Is x x = 'True
  Is x y = 'False

type family HasElem (x :: k) (xs :: [k]) :: Bool where
  HasElem x '[] = 'False
  HasElem x (y ': z) = Or (Is x y) (HasElem x z)

containerEntailsLarger :: proxy1 x -> proxy2 xs -> proxy3 b ->
                          (HasElem x xs ~ 'True) :- (HasElem x (b ': xs) ~ 'True)
containerEntailsLarger _p1 _p2 _p3 = Sub Dict

一种使用 GADT 的方法

我一直无法摆脱这个问题。这是使用 GADT 获得良好证据同时使用类型族和类获得良好接口的方法。

-- Lots of extensions; I don't think I use ScopedTypeVariables,
-- but I include it as a matter of principle to avoid getting
-- confused.
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, UndecidableInstances #-}
{-# LANGUAGE TypeFamilies, TypeOperators #-}
{-# LANGUAGE DataKinds, PolyKinds #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE GADTs #-}

-- Some natural numbers
data Nat = Z | S Nat deriving (Eq, Ord, Show)

-- Evidence that a type is in a list of types
data ElemG :: k -> [k] -> * where
  Here :: ElemG x (x ': xs)
  There :: ElemG x xs -> ElemG x (y ': xs)
deriving instance Show (ElemG x xs)

-- Take `ElemG` to the class level.
class ElemGC (x :: k) (xs :: [k]) where
  elemG :: proxy1 x -> proxy2 xs -> ElemG x xs

-- There doesn't seem to be a way to instantiate ElemGC
-- directly without overlap, but we can do it via another class.
instance ElemGC' n x xs => ElemGC x xs where
  elemG = elemG'

type family First (x :: k) (xs :: [k]) :: Nat where
  First x (x ': xs) = 'Z
  First x (y ': ys) = 'S (First x ys)

class First x xs ~ n => ElemGC' (n :: Nat) (x :: k) (xs :: [k]) where
  elemG' :: proxy1 x -> proxy2 xs -> ElemG x xs

instance ElemGC' 'Z x (x ': xs) where
  elemG' _p1 _p2 = Here

instance (ElemGC' n x ys, First x (y ': ys) ~ 'S n) => ElemGC' ('S n) x (y ': ys) where
  elemG' p1 _p2 = There (elemG' p1 Proxy)

这似乎确实有效，至少在简单的情况下是这样：

*Hello> elemG (Proxy :: Proxy Int) (Proxy :: Proxy '[Int, Char])
Here

*Hello> elemG (Proxy :: Proxy Int) (Proxy :: Proxy '[Char, Int, Int])
There Here

*Hello> elemG (Proxy :: Proxy Int) (Proxy :: Proxy '[Char, Integer, Int])
There (There Here)

这不支持您想要的精确蕴含，但我相信 ElemGC' 递归情况可能是您可以获得的最接近这种信息约束的情况，至少在 GHC 7.10 中是这样。

具有 Haskell 约束的不安全蕴含

Unsafe entailment with Haskell constraints

haskell

ghc

一种使用 GADT 的方法