1

我正在尝试制作一个简单的图形结构,并编写了以下内容。但是 GHG 会引发错误,我就堆在那里。这是我第一次制作自己的类型类,所以也许我做错了什么。有人可以解释什么是错的吗?

我发现了一个类似的问题,但我认为它不适用于我的情况。: Error binding type variables in instance of typeclass

class Link l where
  node :: (Node n) => l -> n

class Node n where
  links :: (Link l) => n -> [l]

data (Node n) => SimpleLink n =
  SimpleLink
  { simpleLinkNode :: n
  } deriving (Show, Read, Eq)

instance (Node n) => Link (SimpleLink n) where
  node = simpleLinkNode

data (Link l) => SimpleNode l =
  SimpleNode
  { simpleNodeLinks :: [l]
  } deriving (Show, Read, Eq)

instance (Link l) => Node (SimpleNode l) where
  links = simpleNodeLinks

这是我收到的错误消息:

***.hs:13:10:Could not deduce (n ~ n1)
from the context (Node n)
  bound by the instance declaration
  at ***.hs:12:10-40
or from (Node n1)
  bound by the type signature for
             node :: Node n1 => SimpleLink n -> n1
  at ***.hs:13:3-23
  `n' is a rigid type variable bound by
      the instance declaration
      at ***.hs:12:16
  `n1' is a rigid type variable bound by
       the type signature for node :: Node n1 => SimpleLink n -> n1
       at ***.hs:13:3
Expected type: SimpleLink n -> n1
  Actual type: SimpleLink n -> n
In the expression: simpleLinkNode
In an equation for `node': node = simpleLinkNode

***.hs:21:11:Could not deduce (l ~ l1)
from the context (Link l)
  bound by the instance declaration
  at ***.hs:20:10-40
or from (Link l1)
  bound by the type signature for
             links :: Link l1 => SimpleNode l -> [l1]
  at ***.hs:21:3-25
  `l' is a rigid type variable bound by
      the instance declaration
      at ***.hs:20:16
  `l1' is a rigid type variable bound by
       the type signature for links :: Link l1 => SimpleNode l -> [l1]
       at ***.hs:21:3
Expected type: SimpleNode l -> [l1]
  Actual type: SimpleNode l -> [l]
In the expression: simpleNodeLinks
In an equation for `links': links = simpleNodeLinks

编辑 1

我尝试了丹尼尔的一些建议。但我无法让它们工作。

构造函数类

得到:“`n' 没有应用于足够的类型参数”

class Link l n where
  node :: Node n l => l n -> n l
class Node n l where
  links :: Link l n => n l -> [l n]

多参数类型类(MPTC)

得到:“在类声明中循环(通过超类)”

class (Node n) => Link l n where
  node :: l -> n
class (Link l) => Node n l where
  links :: n -> [l]

具有函数依赖关系的 MPTC

得到:“在类声明中循环(通过超类)”

class (Node n) => Link l n | l -> n where
  node :: l -> n
class (Link l) => Node n l | n -> l where
  links :: n -> [l]

目标(编辑 2)

我想要实现的是一个有向无环图结构,如下所示(更具体地说,是因子图)。

PRML 图 8.51
(来源:microsoft.com

有两种节点(白色圆圈和红色正方形),它们只连接到不同类型的节点,这意味着有两种链接。

我想要不同版本的节点和链接,它们附加了数据(数组)。我还想要只有一种类型的节点和链接的“香草”DAG。但是为了遍历它们,我只想要一个接口来做到这一点。

4

4 回答 4

6

类方法的签名

class Link l where
  node :: (Node n) => l -> n

class Node n where
  links :: (Link l) => n -> [l]

说“调用者想要的任何类型,只要它是 resp. 的成员,就可以产生它node。” ,但实现说只能产生一种特定类型的值。linksLinkNode

它与 OOP 中的接口根本不同,其中实现决定类型,调用者必须接受它,这里由调用者决定。


您在尝试构造函数时遇到了一些问题。你的类有两个参数,lkindklnof kind kn。参数的种类(->)必须都是*,类型的种类。因此,l n要成为 , 的良好参数(->)l必须是一个类型构造函数,采用 kind 的参数kn并创建 kind 的结果*,即

l :: kn -> *

现在您尝试将结果类型node设为 be n l,这意味着

n :: kl -> *

但在上面我们看到kl = kn -> *

n :: (kn -> *) -> *

分别 kn = (kn -> *) -> *, 是无限种。无限类型,如无限类型,是不允许的。但是种类推断只实现了非常基本的,因此编译器假定参数l有 kind *,但从中看到n lnkind kl -> *,因此作为 的参数ln有错误的种类,它没有应用于足够的类型参数。

构造函数类的正常使用是单参数类

class Link l where
    node :: l nod -> nod

class Node n where
    links :: n lin -> [lin]

-- note that we don't have constraints here, because the kinds don't fit

instance Link SimpleLink where
    node = simpleLinkNode

instance Node SimpleNode where
    links = simpleNodeLinks

您必须DatatypeContexts从数据声明中删除

  1. 它们已从语言中删除(可通过扩展获得)
  2. 无论如何,它们从来没有用过

然后上面的编译。不过,我认为这对你没有帮助。正如 Chris Kuklewicz 所观察到的,你的类型追逐自己的尾巴,你会把它们当作

SimpleLink (SimpleNode (SimpleLink (SimpleNode ... {- ad infinitum -})))

对于多参数类,正如编译器所说,您不能互相要求,这会导致依赖循环(此外,在您的约束中,您只使用一个参数,

class Node n => Link l n where ...

这是格式错误的,如果循环被破坏,编译器会拒绝)。

您可以通过合并类来解决循环,

class NodeLinks l n | l -> n, n -> l where
    node :: l -> n
    links :: n -> l

但是您仍然会遇到您的类型对此无用的问题。

抱歉,我不太了解您的目标,无法提出可行的解决方案。

于 2012-07-10T20:55:55.550 回答
4

有人可以解释什么是错的吗?

在我解释错误消息之前的一个初始问题:多态数据类型很好,但最终必须使用具体类型。

对于种类的 SimpleNode 和种类的* -> *SimpleLinks,* -> *没有具体的类型:

SimpleNode (SimpleLink (SimpleNode (SimpleLink (SimpleNode (...

你不能在 Haskell 中拥有无限类型,尽管 newtype 和 data 让你更接近:

type G0 = SimpleNode (SimpleLink G0)  -- illegal
newtype G1 = G1 (SimpleNode (SimpleLink G1))   -- legal
data G2 = G2 (SimpleNode (SimpleLink G2))   -- legal

也许您需要在创建类型类之前重新考虑您的数据类型。

现在来解释错误消息:您的类型类Link定义了一个函数node

class Link l where
  node :: (Node n) => l -> n

是一个神奇的nodeOOP 工厂,给定 的类型和值l,然后可以使任何类型n(以 为界Node n)成为愿望的调用者node这与您的实例n无关:n

instance (Node n) => Link (SimpleLink n) where
  node = simpleLinkNode

重复我自己:n上面实例中的与定义n中的node :: (Node n) => l -> n不同。编译器创建一个相关但新鲜的名称n1,并给您错误:

  `n' is a rigid type variable bound by
      the instance declaration
      at ***.hs:12:16
  `n1' is a rigid type variable bound by
       the type signature for node :: Node n1 => SimpleLink n -> n1
       at ***.hs:13:3

实例中的n取自node函数输入的类型 (SimpleLink n)。n1是召唤者node要求这个魔法工厂生产的那种。如果 n 和 n1 相同,那么编译器会很高兴......但是您对类型类和实例的定义不限制这一点,因此代码片段被拒绝。

SimpleLink 中的错误重复了类似的故事。对此没有灵丹妙药。我希望您需要重新考虑和重新设计它,可能是在阅读其他人的代码之后,以便学习实现目标的方法。

你的目标是什么?图形数据结构可以是多种多样的,细节很重要。

于 2012-07-10T22:16:39.340 回答
1

我正在打破堆栈溢出礼仪并添加第二个答案以保持独立。这是带有未标记边的二分无向图的简单代码示例,它可能对建模因子图有用:

-- Bipartite graph representation, unlabeled edges

-- Data types to hold information about nodes, e.g. ID number
data VariableVertex = VV { vvID :: Int }  deriving (Show)
data FactorVertex = FV { fvID :: Int }  deriving (Show)

-- Node holds itself and a list of neighbors of the oppostite type
data Node selfType adjacentType =
  N { self :: selfType
    , adj :: [Node adjacentType selfType] }

-- A custom Show for Node to prevent infinite output
instance (Show a, Show b) => Show (Node a b) where
  show (N x ys) = "Node "++ show x ++ " near " ++ show (map self ys)

-- Type aliases for the two node types that will be used
type VariableNode = Node VariableVertex FactorVertex
type FactorNode = Node FactorVertex VariableVertex

data FactorGraph = FG [VariableNode] [FactorNode]  deriving (Show)

v1 = N (VV 1) [f1,f2]
v2 = N (VV 2) [f2]
v3 = N (VV 3) [f1,f3]
f1 = N (FV 1) [v1,v3]
f2 = N (FV 2) [v1,v2]
f3 = N (FV 3) [v3]

g = FG [v1,v2,v3] [f1,f2,f3]
于 2012-07-12T11:19:49.327 回答
0

在 Chris Kuklewicz (http://stackoverflow.com/a/11450715/727827) 的提示下,我首先得到了我想要的代码。

但是,我认为 Crhis 的答案(*Vertex用于保存数据)简单且更好。我把它留在这里是为了澄清我想要什么。

class NodeClass n where
  adjacent :: n a b -> [n b a]

data Node selfType adjacentType =
  N
  { selfNode :: selfType
  , adjNode :: [Node adjacentType selfType] }

data NodeWithData selfType adjacentType =
  NWD
  { selfNodeWithData :: selfType
  , adjNodeWithData :: [NodeWithData adjacentType selfType]
  , getDataWithData :: [Double]
  }

instance NodeClass Node where
  adjacent = adjNode

instance NodeClass NodeWithData where
  adjacent = adjNodeWithData

data VariableVertex = VV { vvID :: Int }  deriving (Show)
data FactorVertex = FV { fvID :: Int }  deriving (Show)

type VariableNode = Node VariableVertex FactorVertex
type FactorNode = Node FactorVertex VariableVertex

type VariableNodeWithData = NodeWithData VariableVertex FactorVertex
type FactorNodeWithData = NodeWithData FactorVertex VariableVertex
于 2012-07-12T16:40:14.223 回答