haskell - 确保两个 (G) ADT 在 (GHC) Haskell 中具有相同的底层表示

Question

在 Haskell 中，有时为了性能人们会使用 unsafeCoerce (或更安全的 coerce )在具有相同内部表示的类型之间进行转换。我所知道的最常见的例子是新类型列表:

newtype Identity a = Identity a

f :: [Identity a] -> [a]
f = coerce

现在，我正在处理的代码库中有两个 GADT，看起来像这样精简:

data Typ where
    PredT :: Typ
    ProcT :: [Typ] -> Typ
    IntT :: Typ
    ListT :: Typ -> Typ


data HKTyp v (f :: * -> * -> *) where
    HKPredT :: HKTyp v f
    HKProcT :: [HKTyp v f] -> HKTyp v f
    HKIntT :: HKTyp v f
    HKListT :: f v (HKTyp v f) -> HKTyp v f  

我需要这些类型不同(而不是使用后者作为前者的概括)，因为单例库(或至少模板 haskell 函数)不喜欢更高种类的数据。现在，因为我必须将这些类型分开，所以我希望它们之间有一些转换函数:

newtype Id v a = Id a

promoteHK :: Typ -> HKTyp v Id
promoteHK PredT = HKPredT
promoteHK (ProcT ts) = HKProcT (fmap promoteHK ts)
promoteHK IntT = HKIntT
promoteHK (ListT x) = HKListT (Id $ promoteHK x)

demoteHK :: HKTyp v Id -> Typ
demoteHK HKPredT = PredT
demoteHK (HKProcT (Id ts)) = ProcT (fmap demoteHK ts)
demoteHK HKIntT = IntT
demoteHK (HKListT (Id x)) = HKListT x

这些写起来很机械，但这不是问题。
虽然我确信在许多情况下，GHC 可以内联并减少 demoteHK 的应用程序。和 promoteHK在编译时，因此不会导致进行这些转换的任何运行时成本，我真的希望能够编写

f :: [Typ] -> [HKTyp v Id]
f = coerce

避免遍历数据结构，因为这些类型非常相似，因此(我假设)应该在内存中具有相同的底层表示。
我的问题有两个。

这些类型实际上在 GHC 中具有相同的内存表示吗？

GHC 中是否对 (G)ADT 在内存中的布局有强有力的保证，让您通常可以做这样的事情？

Answer 1

下面的性能我没有测试过，可能是够复杂的，GHC其实也无法优化，但它会让我们构建一个更好的工具。这个想法是使用 Generics .
计划是定义一个类型类来强制具有相同 Generic 的两种类型。结构以及使用该类的函数。考虑以下:

{-# LANGUAGE DeriveGeneric #-}
import GHC.Generics

class GenericCoerce a b where
  genericCoerce' :: a x -> b x

genericCoerce :: (Generic x, Generic y, GenericCoerce (Rep x) (Rep y)) => x -> y
genericCoerce = to . genericCoerce' . from

当然，我们仍然需要定义是什么使两个 Rep是强制的，但就像你的 promoteHK和 demoteHK定义，这有点机械:

{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE EmptyCase #-}

instance GenericCoerce V1 V1 where
  genericCoerce' = \case

instance GenericCoerce U1 U1 where
  genericCoerce' = id

instance (GenericCoerce f f', GenericCoerce g g') => GenericCoerce (f :+: g) (f' :+: g') where
  genericCoerce' (L1 x) = L1 (genericCoerce' x)
  genericCoerce' (R1 x) = R1 (genericCoerce' x)

instance (GenericCoerce f f', GenericCoerce g g') => GenericCoerce (f :*: g) (f' :*: g') where
  genericCoerce' (x :*: y) = genericCoerce' x :*: genericCoerce' y

instance GenericCoerce cs1 cs2 => GenericCoerce (M1 t m cs1) (M1 t m' cs2) where
  genericCoerce' (M1 x) = M1 (genericCoerce' x)

instance (Generic x, Generic y, GenericCoerce (Rep x) (Rep y)) => GenericCoerce (K1 t x) (K1 t y) where
  genericCoerce' (K1 x) = K1 (genericCoerce x)

这实际上适用于非常基本的情况!考虑如下数据类型:

data Foo = Bar | Baz
  deriving (Generic, Show)

我们得到了我们想要的行为:

> genericCoerce @Bool @Foo True
Baz

> genericCoerce @Foo @Bool Bar
False

然而，这个 Generic 的问题进行强制的方式是它不能很好地与强制数据类型的正常方式配合使用。具体来说，给定类型的类型 rep 和包装在 newtype 包装器中的该类型的类型 rep 是不一样的。
一种可能的解决方案是使用(喘气)不连贯的实例。这对你来说可能有点太远了，但如果你对它们没意见，请考虑以下两个额外的例子:

-- instances to handle newtype constructor
instance {-# INCOHERENT #-} (Generic x, Rep x ~ D1 m x', GenericCoerce x' y) => GenericCoerce (C1 m2 (S1 m3 (Rec0 x))) y where
  genericCoerce' = genericCoerce' . unM1 . from . unK1 . unM1 . unM1

instance {-# INCOHERENT #-} (Generic y, Rep y ~ D1 m y', GenericCoerce x y') => GenericCoerce x (C1 m2 (S1 m3 (Rec0 y))) where
  genericCoerce' = M1 . M1 . K1 . to . M1 . genericCoerce'

这两个实例专门针对其中一种类型具有新类型包装器的情况。不连贯的实例被认为是危险的，如果你的强制中有很多嵌套类型/新类型，那么可能会出现问题。也就是说，有了这两个实例，您可以使用您给出的示例:

promoteHK :: Typ -> HKTyp v Id
promoteHK = genericCoerce

demoteHK :: HKTyp v Id -> Typ
demoteHK = genericCoerce

在行动:

> promoteHK PredT
HKPredT

> promoteHK (ListT PredT)
HKListT (Id HKPredT)

> promoteHK (ListT (ListT (ListT PredT)))
HKListT (Id (HKListT (Id (HKListT (Id HKPredT)))))

> demoteHK (HKProcT [HKIntT, HKPredT])
ProcT [IntT,PredT]

到目前为止，我还没有完全回答你的问题。您问两种看似同构的类型是否真的在 GHC 中具有相同的内存表示，以及 GHC 中是否有任何保证可以让您通常做这样的事情(我假设“像这样的事情”，你的意思是同构数据类型之间的强制)。
据我所知，GHC 不提供任何保证，但 genericCoerce给了我们一个稍微坚实的基础来继续前进。排除不连贯的实例 hack，genericCoerce 的原始版本将具有幻像类型参数的数据类型转换为具有不同幻像参数的相同数据类型。从技术上讲，我不能保证 GHC 会以相同的方式存储相同运行时数据的多个实例，但在我看来，这似乎是一个很容易做出的假设。
一旦我们添加了不连贯的实例和新类型的包装器恶作剧，我们就站在不那么坚实的基础上，但是这一切都有效的事实是一些安慰。
确实，现在我们看到 genericCoerce 的核心确实是一个强制(我们在每种情况下都从刚刚破坏的数据构建相同的数据类型)，如果我们相信 newtype-wrapper 不连贯的实例也可以作为强制，那么我们可以这样写:

genericCoerceProbablySafe :: (Generic x, Generic y, GenericCoerce (Rep x) (Rep y)) => x -> y
genericCoerceProbablySafe = unsafeCoerce

我们得到比 genericCoerce 更好的性能并且比 unsafeCoerce 更安全，我们已将您的问题简化为:“Generic Rep 是 GHC 如何存储内存的准确代理(直到新类型包装器)？”