haskell - 我可以根据特定类别的可用性来过滤类型级别列表吗？

Question

我可以使用如下类型系列将函数与空值分开:

type family Funs (ts :: [*]) :: [*]
  where
    Funs '[ ] = '[ ]
    Funs ((a -> b): ts) = (a -> b): Funs ts
    Funs (k: ts) = Funs ts

我想要的是分离满足约束的类型，例如Show。类比尝试:

type family Showable (ts :: [*]) :: [*]
  where
    Showable '[ ] = '[ ]
    Showable ((Show a => a): ts) = a: Showable ts
    Showable (k: ts) = Showable ts

— 导致错误:

    • Illegal qualified type: Show a => a
    • In the equations for closed type family ‘Showable’
      In the type family declaration for ‘Showable’
   |
35 |     Showable ((Show a => a): ts) = a: Showable ts
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

可以做什么？我对使用 Template Haskell 或任何类型的低级黑客技术的解决方案感到满意。

Answer 1

我不认为可以轻松地做到这一点(没有 TH)，因为开放世界的假设:GHC 基本上永远不会解决类约束的负面问题，因为某个地方可能有更多实例可以实现它true(并且不能很好地使用 GHC/Haskell 使用的单独编译策略)。因此，通常不可能从纯“常规”Haskell 代码决定类型是否具有类实例，以及是否将其包含在列表中。

如果您愿意稍微破坏单独的编译，只需考虑您正在处理的模块编译时范围内的实例(即在该模块源文件的范围内) ，您可以使用 Template Haskell 或 GHC 类型检查器插件来获得与此行为非常相似的东西。我知道有几个实现在值(value)级别上做了类似的事情，包括 ifcxt和 constraints-emerge 。我相信这些库，尤其是 ifcxt(我稍微熟悉一点)非常简单:您可以使用 TH 函数 reify 来获取 ClassI Info 对于特定类型类，并使用其 [InstanceDec] 字段来获取编译期间范围内的所有实例的列表。然后，您基本上可以为每个具体类型实例创建一个分支，将实例头添加到列表中，并在其后面添加一个不会添加实例头的包罗万象的分支。您可能还需要递归地执行此操作以处理本身具有约束的实例。

请注意，如果您选择使用此方法，这将以可能令人困惑的方式打破开放世界假设:如果模块导入类型级过滤器模块，然后定义数据类型/实例，则类型级过滤器将不知道新实例，并将继续将该类型视为没有实例。当您使用 TH 生成过滤器类型系列时，您需要确保您关心的所有实例都在范围内。

如果您想稍微改进这一点，您可以使用一种更像 IfCxt 的方法，其中您可以执行以下操作，而不是直接创建类型系列实例:

class IsShow (a :: Type) (b :: Bool) where
instance {-# OVERLAPPABLE #-} (b ~ 'False) => IsShow a b where

您的 TH 生成实例如下:

instance IsShow Int 'True where

这样做的优点是，如果另一个模块定义了重要的类型/实例，您应该能够使用(大致)相同的 TH 来使用这些新实例和您的类型来扩展 IsShow 的实例使用 IsShow 的家庭应该没问题。上面链接的 ifcxt 包基本上做同样的事情，但它没有做必要的技巧来获取类型级别的信息，而是生成函数来获取值级别的信息。

此解决方案使用具有功能依赖性的类而不是类型族，因为 OverlappingInstances 可以为基于类的解决方案提供“默认情况”。我不确定是否有任何合理的方法可以为 open 类型系列提供默认情况，因此您可能无法在到处使用类型系列时获得这种“可扩展性”(而不是fundep'd)实例)。

理查德·艾森伯格 says

With separate compilation, the lack of ordering and the overlap check are necessary for type soundness.

所以我认为这可能是不可能的。这里还有一些关于类型族与fundeps的有趣讨论:https://typesandkinds.wordpress.com/2015/09/09/what-are-type-families/