Определение уравнения для альтернативного подхода нумерации версий

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х (или Nothings) в левой части данной версии. Так, например, 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, это должно быть достигнуто не с помощью сопоставления с образцом, а с помощью композиции функций.

PS. Я лично призываю вас поддержать ответ @WillemVanOnsem, потому что его решение действительно изящно, требует определенных усилий и представляет суть силы Хаскелла.

Answer 1

Вы используете псевдонимы типа. Это означает, что вы не определили отдельный тип VersionNumber или же VersionCompound; Вы просто создали псевдоним. За шторами Хаскелл видит VersionNumber так же просто [Maybe Int],

Теперь, если мы посмотрим на библиотеку Хаскелла, мы увидим, что:

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
data VersionNumber = VersionNumber [VersionCompound]

Теперь, поскольку есть только один конструктор, лучше использовать newtype:

type VersionCompound = Maybe Int
newtype VersionNumber = VersionNumber [VersionCompound]

и теперь мы можем определить наш специальный экземпляр как:

instance Eq VersionNumber where
    (VersionNumber a) == (VersionNumber b) = 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

Это отфильтрует Nothing значения обоих VersionNumbers, а затем проверьте, являются ли значения в 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