替代版本编号方法的 Eq 定义

Question

我正在尝试为替代版本编号方法定义 Eq 运算符。

type VersionCompound = Maybe Int -- x, 0, 1, 2, ...
type VersionNumber = [VersionCompound] -- x.x, x.0, x.1, x.2, ... , 1.0, 1.1, 1.2, ... 1.x.x, 2.x.x, 3.x.x, ...
instance Eq VersionNumber where
[] == [] = True
(x:[]) == (y:[]) = x == y
(Nothing:xs) == ys = (xs == ys)
xs == (Nothing:ys) = (xs == ys)

对于以下情况，预计它会返回True：x.x.x == x、1.x.x == x.1.x.x、x.1 == 1等。但相反，它返回一个错误：

VersionNumber.hs:58:34:
Overlapping instances for Eq [VersionCompound]
arising from a use of ‘==’
Matching instances:
instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
instance Eq VersionNumber -- Defined at VersionNumber.hs:55:10
In the expression: (xs == ys)
In an equation for ‘==’: (Nothing : xs) == ys = (xs == ys)
In the instance declaration for ‘Eq VersionNumber’

有什么想法可以解决吗？

编辑：我通过列表上的模式匹配来解决这个问题的方法被证明是不完整的。我想忽略给定版本左侧的任何任意x(或Nothing(列表。因此，例如，x.x.x.x.x将等于x.x.x和x.同样，x.x.x.1等于x.x.1和1。如果中间有x，它不会被扔掉。因此，对于这种情况，x.x.1.x.0等于x.1.x.0和1.x.0.再举一个例子：x.1.x.x.0.x等于1.x.x.0.x，x.1.x.0.x等于1.x.0.x(你只需删除左侧的x(。

修复错误后，我正在努力解决Overlapping instances for Eq [VersionCompound]是如何通过模式匹配获得x.x.x == x->True。但是，正如@WillemVanOnsem出色地指出的那样，它不应该通过模式匹配来实现，而应该通过函数组合来实现。

我个人鼓励你通过@WillemVanOnsem对答案投赞成票，因为他的解决方案真的很优雅，需要一些努力才能想出，并且代表了Haskell力量的本质。

Answer 1

使用类型别名。这意味着您尚未定义单独的类型VersionNumber或VersionCompound;你只是构造了一个别名。在幕后，哈斯克尔认为VersionNumber只是[Maybe Int]。

现在，如果我们看一下 Haskell 的图书馆，我们会看到：

instance Eq Int where
-- ...
instance Eq a => Eq (Maybe a) where
-- ...
instance Eq a => Eq [a] where
-- ...

这意味着Eq Int被定义，Eq (Maybe Int)也被定义，因此Eq [Maybe Int]也由Haskell库定义。所以你实际上已经构建了一个Eq VersionNumber，没有写一个。现在你尝试编写一个额外的，当然，编译器会混淆选择哪一个。

有一些方法可以解决重叠的实例，但这可能只会产生更多的麻烦。

因此，最好使用单个构造函数构造data类型。例如：

type VersionCompound = Maybe Int
dataVersionNumber =VersionNumber[VersionCompound]

现在，由于只有一个构造函数，因此最好使用newtype：

type VersionCompound = Maybe Int
newtypeVersionNumber = VersionNumber [VersionCompound]

现在我们可以定义我们的特殊实例，例如：

instance Eq VersionNumber where
(VersionNumbera) == (VersionNumberb) = a=*=b
where [] =*= [] = True
(x:[]) =*= (y:[]) = x == y
(Nothing:xs) =*= ys = (xs =*= ys)
xs =*= (Nothing:ys) = (xs =*= ys)

因此，我们解开构造函数的包装，然后使用另一个本地定义的函数=*=，其工作原理与您在问题中定义的那样。

但是请注意，您忘记了程序中的一些模式，例如左侧和右侧的Just x : xs。因此，您最好先解决这些问题。如果我通过编译器运行您的代码，则会收到以下警告：

Pattern match(es) are non-exhaustive
In an equation for ‘=*=’:
Patterns not matched:
[] (Just _:_)
[Just _] []
[Just _] (Just _:_:_)
(Just _:_:_) []

你想如何处理这些情况当然取决于你。 @DanielWagner建议使用：

import Data.Function(on)
import Data.Maybe(catMaybes)
instance Eq VersionNumber where
(VersionNumber a) == (VersionNumber b) = on (==) catMaybes a b

这将过滤掉两个VersionNumber的Nothing值，然后检查Just中的值是否生成相同的列表。所以3.x.2.x.x.1等于3.2.1和x.x.x.x.x.3.2.1.

编辑：根据您在评论中的规范，您可能正在寻找：

import Data.Function(on)
instance Eq VersionNumber where
(VersionNumber a) == (VersionNumber b) = on (==) (dropWhile (Nothing ==)) a b