Haskell中计算嵌套深度时使用可重叠通配实例是否安全？

好问题！咱们来仔细聊聊这个Haskell重叠实例在嵌套深度计算场景下的安全性问题。

首先先回顾你给出的原始实现：

class G a where g :: a -> Int
instance G a => G [a] where
  g [] = 1
  g xs = maximum (g <$> xs) + 1
instance G Void where g = absurd

这个实现对固定类型的嵌套列表（比如[[[]::[Void]]]）工作完全正常，测试表达式g [[[]:: [Void]],[]]返回3，符合预期——它递归计算每个元素的深度，取最大值加1，空列表的深度定义为1。

现在你的问题是：如果添加一个通配实例

instance {-# OVERLAPPABLE #-} G a where g _ = 0

同时利用Haskell的overlapping/overlappable编译指令允许实例重叠，这样的做法是否安全？

结论：在这个特定场景下，合理使用重叠实例是安全的，但需要抓住几个关键前提： #

1. 实例优先级规则是可靠的 #

Haskell的重叠实例遵循「更具体的实例优先匹配」的规则：

• G [a]实例比通配G a更具体，所以所有列表类型都会优先匹配列表实例，绝对不会触发通配实例的g _=0逻辑。
• G Void是具体类型实例，同样比通配实例更具体，所以Void类型会正确使用absurd的实现，不会被通配实例覆盖。

这意味着你原本关心的嵌套列表场景（比如[[Int]]、[[Void]]等），行为和之前完全一致，不会出现意外的0值。

2. 通配实例的语义符合预期 #

通配实例g _=0的语义是：所有没有专门定义G实例的类型，其「嵌套深度」为0。这个逻辑在嵌套深度计算的场景下是合理的：

• 对于Int、Bool这类基础类型，它们本身不是嵌套结构，深度为0完全符合直觉——比如g (5::Int)返回0，没问题。
• 如果你后续给自定义类型（比如树形结构data Tree a = Leaf a | Node (Tree a) (Tree a)）添加G实例，只要定义专门的实例，它就会优先于通配实例，不会影响现有逻辑。

3. 需要避开的潜在坑 #

虽然当前场景安全，但有几个细节要注意：

• 不要搞反实例的编译指令：只能给通配实例加OVERLAPPABLE，列表和Void实例要么加OVERLAPPING，要么依赖它们天然的具体性。如果反过来给通配实例加OVERLAPPING，会直接覆盖所有更具体的实例，彻底破坏逻辑。
• 保持语义一致性：确保g _=0的逻辑在你的代码库中是统一的。比如如果某个类型你认为它的深度不是0，但忘记定义实例，就会得到0——这是编码失误，不是重叠实例本身的问题。
• 注意无约束多态的情况：如果有一个无约束的多态值（比如x :: a，没有G a约束），调用g x会匹配通配实例返回0。你需要确认这个行为是你想要的。

验证示例 #

我们可以测试几个场景，确认行为符合预期：

• g [[[]::[Void]],[]] → 3（和原始实现结果一致）
• g (5::Int) → 0（基础类型深度为0，符合预期）
• g (Left 'a' :: Either Char Void) → 0（因为Either Char Void没有专门的G实例，匹配通配）

如果我们给Either添加专门的实例：

instance (G a, G b) => G (Either a b) where
  g (Left x) = g x
  g (Right x) = g x

那么g (Left [[[]::[Void]]] :: Either [[[Void]]] Void) → 4，完全符合递归计算的预期，不会触发通配实例。

总的来说，在这个嵌套深度计算的场景下，使用OVERLAPPABLE通配实例是安全的——它既解决了多态场景下的实例缺失问题，又不会破坏原有嵌套列表的计算逻辑。

内容的提问来源于stack exchange，提问作者Ignat Insarov