帮助使用功能依赖关系 [英] help with use of functional dependencies

问题描述

我有一个关于函数依赖的问题。我的理解是，例如，如果我写类Graph g a b | g - > a，g - > b ，那么任何特定的 g 只能与一个类型的 a 和 b 。的确，试图用相同的 g 和不同的 a 和 b 不起作用。



然而，编译器（ghc）在下列情况下似乎无法使用依赖项。

  class（Eq a，Eq b）=>图g a b | g  - > a，g  - > b其中
 edges :: g  - > [b] 
 src :: g  - > b  - > a 
 dst :: g  - > b  - > a 
 
 vertices :: g  - > [a] 
 vertices g = List.nub $ map（src g）（edges g）++ map（dst g）（edges g）
 
 class图g a b =>子图g a b | g  - > a，g  - > b其中
 extVertices :: g  - > [b] 
 
数据子图1 g其中
子图1 ::图g a b => g  - > [b]  - >子图1 g 
 
实例图g a b =>图（Subgraph1 g）ab其中
顶点（Subgraph1 g _）=顶点g 
边（Subgraph1 g _）=边g 
 src（Subgraph1 g _）= src g 
如果我修改 Subgraph1 ，那么dst（Subgraph1 g _）= dst g 
  



通过将 a 和 b 参数添加到类型签名中， p>



  data subgraph1 gab where 
 Subgraph1 :: Graph gab => g  - > [b]  - > Subgraph1 gab 
  




解决方案

不要使用fundeps，它们也是很痛苦。使用相关的类型。



  class（Eq（Vertex g），Eq（Edge g））=>图g其中
类型边缘g :: * 
类型顶点g :: * 
 
边缘:: g  - > [Edge g] 
 src :: g  - >边缘g  - >顶点g 
 dst :: g  - >边缘g  - >顶点g 
 
顶点:: g  - > [顶点g] 
顶点g = nub $ map（src g）（边缘g）++映射（dst g）（边缘g）
 
 class图g =>子图g其中
 extVertices :: g  - > [边缘g] 
 
数据子图1 g其中
 Subgraph1 :: Graph g => g  - > [边缘g]  - >子图1 g 
 
实例图g =>图（Subgraph1 g）其中
类型Edge（Subgraph1 g）= Edge g 
类型Vertex（Subgraph1 g）= Vertex g 
 vertices（Subgraph1 g _）= vertices g 
 edges （Subgraph1 g _）= edges g 
 src（Subgraph1 g _）= src g 
 dst（Subgraph1 g _）= dst g 
  

这看起来更具可读性。 Edge g 是 g 的边缘等的类型。

请注意，我机械地翻译了您的代码，但未理解Subgraph1的功能。为什么你需要一个GADT，以及数据构造函数的第二个参数是什么意思？它不在任何地方使用。

I have a question about functional dependencies. My understanding was that, for example, if I write class Graph g a b | g -> a, g -> b, then any specific g can be associated with only one type of a and b. Indeed, trying to declare two instance with the same g and different a and b does not work.

However, the compiler (ghc) seems unable to use the dependency in the following case,

class (Eq a, Eq b) => Graph g a b | g -> a, g -> b where
    edges :: g -> [b]
    src :: g -> b -> a
    dst :: g -> b -> a

    vertices :: g -> [a]
    vertices g = List.nub $ map (src g) (edges g) ++ map (dst g) (edges g)

class Graph g a b => Subgraph g a b | g -> a, g -> b where
    extVertices :: g -> [b]

data Subgraph1 g where
    Subgraph1 :: Graph g a b => g -> [b] -> Subgraph1 g

instance Graph g a b => Graph (Subgraph1 g) a b where
    vertices (Subgraph1 g _) = vertices g
    edges (Subgraph1 g _) = edges g
    src (Subgraph1 g _) = src g
    dst (Subgraph1 g _) = dst g

If I revise Subgraph1 by adding the parameters a and b to the type signature, then everything works out.

data Subgraph1 g a b where
    Subgraph1 :: Graph g a b => g -> [b] -> Subgraph1 g a b

解决方案

Don't use fundeps, they are too much pain. Use associated types.

class (Eq (Vertex g), Eq (Edge g)) => Graph g where
  type Edge   g :: *
  type Vertex g :: *

  edges :: g -> [Edge g]
  src   :: g -> Edge g -> Vertex g
  dst   :: g -> Edge g -> Vertex g

  vertices :: g -> [Vertex g]
  vertices g = nub $ map (src g) (edges g) ++ map (dst g) (edges g)

class Graph g => Subgraph g where
  extVertices :: g -> [Edge g]

data Subgraph1 g where
    Subgraph1 :: Graph g => g -> [Edge g] -> Subgraph1 g

instance Graph g => Graph (Subgraph1 g) where
    type Edge (Subgraph1 g) = Edge g
    type Vertex (Subgraph1 g) = Vertex g
    vertices (Subgraph1 g _) = vertices g
    edges (Subgraph1 g _) = edges g
    src (Subgraph1 g _) = src g
    dst (Subgraph1 g _) = dst g

This looks somewhat more readable. Edge g is the type of g's edges, etc.

Note that I translated your code mechanically, without understanding what Subgraph1 does. Why do you need a GADT here, and what the second argument of the data constructor means? It is not used anywhere.

这篇关于帮助使用功能依赖关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！