haskell - 在计算嵌套深度的方法中使用可重叠的捕获所有实例是否安全？

Question

考虑方法g:

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

 

λ g [[[]:: [Void]],[]]
3

它可以转换为适用于任何固定类型的嵌套列表，但我在使其多态时遇到困难。

如果我像这样定义一个包罗万象的实例:

instance G a where
    g _ = 0

− 它将与 G a => G [a] 重叠。我可以使用“重叠”和“可重叠”编译指示来允许这样做:

class G a where
    g :: a -> Int

instance {-# OVERLAPPABLE #-} G a => G [a] where
    g [ ] = 1
    g xs = maximum (g <$> xs) + 1

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

我尝试过一次类似的事情，got burned ，但我还是没有吸取教训。

我的问题:

1. 如何确定此代码是否安全？
2. 是否有更合适的方法来计算嵌套深度？

P.S. 我刚刚注意到我不小心为 G 的两个实例指定了“overlappable”。我一开始并没有注意到，因为它实际上似乎是这样工作的。如果说有什么不同的话，那就是让这个案子更加令人震惊。

Answer 1

我建议您使用数据而不是类。所以:

data FixedDepthTree a = Zero a | Succ (FixedDepthTree [a])

depth :: FixedDepthTree a -> Integer
depth (Zero _) = 0
depth (Succ t) = succ (depth t)