Может ли GHC предупредить, если экземпляр класса является циклом?

В Real World Haskell есть этот пример:

class BasicEq3 a where
    isEqual3 :: a -> a -> Bool
    isEqual3 x y = not (isNotEqual3 x y)

    isNotEqual3 :: a -> a -> Bool
    isNotEqual3 x y = not (isEqual3 x y) 

instance BasicEq3 Bool

И когда я запускаю его в GHCI:

#> isEqual3 False False
out of memory

Итак, вы должны реализовать хотя бы один из 2-х методов или зациклиться. И вы получаете гибкость в выборе того, который является опрятным.

Вопрос, который у меня есть, есть способ получить предупреждение или что-то, если не переопределить достаточное количество значений по умолчанию, а значения по умолчанию составляют цикл? Мне кажется странным, что компилятор, который настолько сумасшедший, умен в этом примере.

Ответ 1

Я думаю, что GHC отлично подходит для выдачи предупреждения в случае "неразрывной" циклической зависимости. Там даже билет по этим строкам: http://hackage.haskell.org/trac/ghc/ticket/6028

Просто потому, что что-то "неразрешимо" не означает, что ни один экземпляр проблемы не может быть эффективно разрешен. GHC (или любой другой компилятор Haskell) уже имеет совсем немного информации, которая ему нужна, и было бы вполне возможно, чтобы он выдал предупреждение, если пользователь создает экземпляр класса без "нарушения" циклической зависимости. И если компилятор ошибается в редких случаях, как показано в предыдущих сообщениях, пользователь может иметь -nowarnundefinedcyclicmethods или аналогичный механизм, чтобы сказать, что GHC является тихим. Почти в каждом другом случае предупреждение будет наиболее желанным и добавит к производительности программиста; избегая почти всегда глупых ошибок.

Ответ 2

Нет, я боюсь, что GHC не делает ничего подобного. Также это невозможно вообще.

Вы видите, что методы класса типа могут быть взаимно рекурсивными. Здесь надуманный пример такого типа. Совершенно нормально не определять sumOdds или sumEvens, хотя их реализации по умолчанию находятся в терминах друг друга.

class Weird a where
    measure :: a -> Int

    sumOdds :: [a] -> Int
    sumOdds [] = 0
    sumOdds (_:xs) = sumEvens xs

    sumEvens :: [a] -> Int
    sumEvens [] = 0
    sumEvens (x:xs) = measure x + sumOdds xs

Ответ 3

Нет, нет, поскольку, если компилятор мог бы сделать это определение, это было бы эквивалентно решению проблемы остановки. В общем, тот факт, что две функции называют друг друга в "петлевом" шаблоне, недостаточно для того, чтобы сделать вывод, что на самом деле вызов одной из функций приведет к циклу.

Чтобы использовать (надуманный) пример,

collatzOdd :: Int -> Int
collatzOdd 1 = 1
collatzOdd n = let n' = 3*n+1 in if n' `mod` 2 == 0 then collatzEven n'
                                   else collatzOdd n'

collatzEven :: Int -> Int
collatzEven n = let n' = n `div` 2 in if n' `mod` 2 == 0 then collatzEven n'
                                        else collatzOdd n'

collatz :: Int -> Int
collatz n = if n `mod` 2 == 0 then collatzEven n else collatzOdd n

(Это, конечно, не самый естественный способ реализации гипотезы Collatz, но он иллюстрирует взаимно рекурсивные функции.)

Теперь collatzEven и collatzOdd зависят друг от друга, но гипотеза Collatz утверждает, что вызов collatz завершается для всех положительных n. Если GHC может определить, имел ли класс, имеющий collatzOdd и collatzEven определения по умолчанию, полное определение или нет, тогда GHC сможет решить гипотезу Collatz! (Это, конечно, не является доказательством неразрешимости проблемы остановки, но это должно проиллюстрировать, почему определение того, правильно ли определен взаимно-рекурсивный набор функций, вовсе не так тривиален, как может показаться.)

В общем, поскольку GHC не может определить это автоматически, документация для классов Haskell даст "минимальное полное определение", необходимое для создания экземпляра класса.

Ответ 4

Я так не думаю. Я беспокоюсь, что вы ожидаете, что компилятор решит проблему остановки! Просто потому, что две функции определены в терминах друг друга, не означает, что это плохой класс по умолчанию. Кроме того, я использовал классы в прошлом, где мне просто нужно было написать instance MyClass MyType для добавления полезных функций. Поэтому, прося компилятор предупредить вас о том, что класс просит его жаловаться на другой, действительный код.

[Конечно, используйте ghci во время разработки и проверяйте каждую функцию после того, как вы ее написали! Используйте HUnit и/или QuickCheck, просто чтобы убедиться, что ни один из этих материалов не попадает в окончательный код.]

Ответ 5

По моему личному мнению, механизм по умолчанию не нужен и неразумен. Автору класса было бы просто предоставить стандартные значения как обычные функции:

notEq3FromEq3 :: (a -> a -> Bool) -> (a -> a -> Bool)
notEq3FromEq3 eq3 = (\x y -> not (eq3 x y))

eq3FromNotEq3 :: (a -> a -> Bool) -> (a -> a -> Bool)
eq3FromNotEq3 ne3 = (\x y -> not (ne3 x y))

(На самом деле эти два определения равны, но в целом это было бы неверно). Затем экземпляр выглядит так:

 instance BasicEq3 Bool where
   isEqual3 True True = True
   isEqual3 False False = True
   isEqual3 _ _ = False

   isNotEqual3 = notEq3FromEq3 isEqual3

и не требуются значения по умолчанию. Затем GHC может предупредить вас, если вы не предоставите определение, и любые неприятные циклы должны быть явно написаны вами в вашем коде.

Это устраняет опрятную способность добавлять новые методы в класс с определениями по умолчанию, не затрагивая существующие экземпляры, но это не так сильно выгодно для меня. Вышеупомянутый подход также в принципе более гибкий: вы можете, например, предоставляют функции, позволяющие экземпляру Ord выбирать любой оператор сравнения для реализации.