如果类实例是一个循环,GHC可以发出警告吗？

Question

真实世界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

因此,您必须实现两种方法中的至少一种,否则它将循环.而且你可以灵活地选择哪一个很整洁.

我的问题是,有没有办法得到一个警告或什么,如果没有覆盖足够的默认值和默认值形成一个循环？我觉得奇怪的是,这个例子对于那么疯狂的编译器来说很好.

Answer 1

不,我担心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

Answer 2

我认为GHC在"不间断"循环依赖的情况下发出警告是完全没问题的.甚至还有这样的票:http://hackage.haskell.org/trac/ghc/ticket/6028

仅仅因为某些东西是"不可判定的"并不意味着没有问题的实例能够得到有效解决.GHC(或任何其他Haskell编译器)已经拥有它需要的相当多的信息,并且如果用户在没有"破坏"循环依赖性的情况下实例化类,它就完全有可能发出警告.如果编译器在极少数情况下错误,如前面的帖子所示,那么用户可以有一个-nowarnundefinedcyclicmethods或类似的机制来告诉GHC安静.在几乎所有其他情况下,警告将是最受欢迎的,并将增加程序员的工作效率; 避免什么几乎总是一个愚蠢的错误.

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

(这当然不是实现Collat​​z猜想的最自然的方式,但它说明了相互递归的函数.)

现在collatzEven,collatzOdd彼此依赖,但Collat​​z猜想说,呼叫collatz终止所有积极的n.如果GHC可以确定具有collatzOdd和collatzEven作为默认定义的类是否具有完整的定义,那么GHC将能够解决Collat​​z猜想!(这当然不是停止问题不可判定性的证明,但它应该说明为什么确定一个相互递归的函数集是否定义良好并不像它看起来那么微不足道.)

通常,由于GHC无法自动确定,因此Haskell类的文档将提供创建类实例所需的"最小完整定义".