GHC能否警告类实例是否存在循环？

Question

《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

所以，您必须至少实现其中一种方法，否则它将会循环。而且您可以灵活选择哪种方法，这很方便。

我的问题是，如果没有覆盖足够的默认值并且默认值形成了循环，是否有一种方法可以得到警告或其他东西？对我来说，编译器非常聪明，但这个例子似乎没问题。

- Adam Gordon Bell

Answer 1

我认为，在出现“未破环”的循环依赖的情况下，GHC发出警告是完全可以接受的。甚至已经有一个相关的票据：http://hackage.haskell.org/trac/ghc/ticket/6028

仅仅因为某件事是“不可判定的”，并不意味着问题的解决方案就不能有效地解决。GHC（或任何其他Haskell编译器）已经拥有了相当多所需的信息，如果用户实例化一个类而没有“打破”循环依赖，则它完全可以发出警告。如果编译器在之前帖子中所示的罕见情况下出现错误，那么用户可以使用-nowarnundefinedcyclicmethods 或类似机制来告诉 GHC 保持安静。在几乎所有其他情况下，这个警告将会非常受欢迎，并且可以提高程序员的生产力，避免几乎总是愚蠢的错误。

- alias

---

是的！在停机问题的情况下，Agda等全面语言证明一般无法解决的问题可以有大而有趣的可解子集。 - Ben Millwood

“‘只是纯粹的不可判定’并不足以作为驳回编译器技术的充分标准。大多数在一般情况下不可判定的问题，在特定情况下是可以判定的。” http://c2.com/cgi/wiki?SufficientlySmartCompiler - Adam Gordon Bell

Trac 票据因为无意义的理由而被关闭：有人可能会定义一个 Num 实例，没有 - 或者 negate，但是其中的 + 却不会评估它的第二个参数，因此它显然的循环定义将正常终止。这种总是丢弃第二个参数的方法是脱离非终止状态而不定义 - 或者 negate 的唯一方法。我认为这些是奇怪的用例，如果您想通过使用 _ 来避免循环定义，则需要指定 -noarnundefinedcyclicmethods。但是我不知道如何在 Trac 上引发这个问题。 - AndrewC

Answer 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

- opqdonut

---

有趣，我从未想过。 - Adam Gordon Bell

事实上，许多标准类都这样做（例如Ord）。这就是“最小完整定义”的来源。 - Cat Plus Plus

你是不是想说互递归？Corecursive 是不同的。 - nponeccop

Answer 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

当然，这并不是实现科拉兹猜想最自然的方法，但它说明了相互递归函数的实现方式。

collatzEven和collatzOdd现在相互依赖，但是科拉兹猜想指出调用collatz对于所有正整数n都会终止。如果GHC能够确定一个类是否具有完整的定义，其中包括collatzOdd和collatzEven作为默认定义，那么GHC将能够解决科拉兹猜想！（当然，这并不是停机问题不可判定性的证明，但它应该说明确定相互递归函数集合是否良好定义并不像看起来那么简单。）

通常情况下，由于GHC无法自动确定这一点，因此Haskell类的文档将给出创建类实例所需的“最小完整定义”。

- ajd

---

如果有一种方式可以指定最小完整定义，并且编译器可以检查它，那将是很好的。 - hammar

这是一个很好的观点 - 或许可以在类定义中使用编译器指示语。 - AndrewC

Answer 4

我不这么认为。我担心你期望编译器解决停机问题！仅仅因为两个函数是相互定义的，并不意味着它是一个糟糕的默认类。此外，我过去曾经使用过类，在那里我只需要写 instance MyClass MyType 就可以添加有用的功能。因此，要求编译器警告你该类是在要求它抱怨其他有效的代码。

[当然，在开发过程中使用ghci，并在编写每个函数后测试它！使用 HUnit 和/或 QuickCheck，只是为了确保没有这些东西出现在最终代码中。]

- AndrewC

Answer 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 实例可以选择实现任何比较运算符。

- Ben Millwood