标签: undecidable-instances

在使用UndecidableInstances之前编写的代码时,我遇到了一些我发现很奇怪的东西.我设法无意中创建了一些代码,当我认为不应该这样做时:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UndecidableInstances #-}

data Foo = Foo

class ConvertFoo a b where
  convertFoo :: a -> b

instance (ConvertFoo a Foo, ConvertFoo Foo b) => ConvertFoo a b where
  convertFoo = convertFoo . (convertFoo :: a -> Foo)

evil :: Int -> String
evil = convertFoo

具体来说,convertFoo函数类型检查在给出任何输入以产生任何输出时,如evil函数所示.起初,我认为也许我设法意外地实现了unsafeCoerce,但事实并非如此:实际上尝试调用我的convertFoo函数(evil 3例如通过执行某些操作)只是进入无限循环.

我有点 …

当我第一次阅读严肃的批评时-XUndecidableInstances,我已经完全习惯了它,将其视为仅仅删除了令人讨厌的限制Haskell98必须使编译器更容易实现.

事实上,我遇到了大量需要不可判定实例的应用程序,但没有一处它们实际上导致任何与不可判定性相关的问题.卢克的例子存在问题,原因完全不同

class Group g where
  (%) :: g -> g -> g
  ...
instance Num g => Group g where
  ...

- 好吧,这显然会被任何适当的实例重叠Group,所以不可判断性是我们最不担心的事情:这实际上是不确定的!

但公平地说,我自己保留了"不可判断的实例可能会让编译器挂起".

当我在CodeGolf.SE上阅读这个挑战时获得它,请求代码无限地挂起编译器.嗯,听起来像是不可判断的实例的工作,对吧？

事实证明我无法让他们这样做.以下编译,至少从GHC-7.10开始:

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
class C y
instance C y => C y
main = return ()

我甚至可以使用类方法,它们只会在运行时引起循环:

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
class C y where y::y
instance C y => C y …

我正在尝试将二叉树实现为类型类：

class BinaryTree bt where\n    empty :: bt a -> Bool\n    empty = isNothing . root\n    emptyTree :: bt a\n    branch :: a -> bt a -> bt a -> bt a \n    root :: bt a -> Maybe a\n    lbranch :: bt a -> bt a \n    rbranch :: bt a -> bt a \n

我想用这个定义来说明二叉树是数据容器：

instance BinaryTree bt => Functor bt where\n    fmap f bt = case root bt of\n        Nothing -> emptyTree\n        Just a …

以下片段使GHC(在8.6.2和8.4.4中检查)在编译期间卡住:

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE UndecidableSuperClasses #-}

import GHC.Exts (Constraint)

data T = T

type family F t (c :: * -> Constraint) :: Constraint
type instance F T c = c T

class F t C => C t where

t :: C T => t
t = undefined

我认为它会被卡住,因为tGHC试图找到C T,这会导致F T C通过类型族扩展F回来C T,这就是它所寻求的(无限循环).

我认为从理论上说,GHC可以告诉它它自己的追求C T,任何依赖自身的东西都可以递归地工作,或者我误解了什么？

附注:在我偶然发现了这种行为,我能够实现我想要的东西,而不通过更换堵塞在编译器的真实的例子 …