使用 Scala、OCaml 和 Haskell 中的类型捕获图的规则
Capturing rules of graph using types in Scala, OCaml and Haskell
我正在尝试描述一个复杂的图形，其中包含许多不同类型的节点和边，这些节点和边只能根据一组规则相互连接。我希望在编译时使用语言的类型系统检查这些规则。我的实际应用中有很多不同的节点和边类型。
我已经在 Scala 中轻松创建了一个简单的示例：
sealed trait Node {
val name: String
}
case class NodeType1(override val name: String) extends Node
case class NodeType2(override val name: String) extends Node
case class NodeType3(override val name: String) extends Node
sealed trait Edge
case class EdgeType1(source: NodeType1, target: NodeType2) extends Edge
case class EdgeType2(source: NodeType2, target: NodeType1) extends Edge
object Edge {
def edgeSource(edge: Edge): Node = edge match {
case EdgeType1(src, _) => src
case EdgeType2(src, _) => src
}
}
object Main {
def main(args: Array[String]) {
val n1 = NodeType1("Node1")
val n2 = NodeType2("Node2")
val edge = EdgeType1(n1, n2)
val source = Edge.edgeSource(edge)
println(source == n1) // true
}
}
有效图只能连接给定类型节点之间的给定边类型，如上面的 Scala 示例所示。函数"edgeSource"从边中提取源节点，就这么简单
这是一个我想用 OCaml 编写的非工作示例：
type node =
NodeType1 of string
| NodeType2 of string
type edge =
EdgeType1 of NodeType1 * NodeType2
| EdgeType2 of NodeType2 * NodeType1
let link_source (e : edge) : node =
match e with
| EdgeType1 (src, _) -> src
| EdgeType2 (src, _) -> src
这里的问题是 "NodeTypeX" 是构造函数而不是类型。因此，当我用定义了边的源和目标描述元组时，我无法使用它们。 "link_source" 函数只能 return 一种类型，而 "node" 是可以 return 某些东西的变体。
我一直在尝试如何在 OCaml 和 Haskell 中解决这个问题，这里是 OCaml 中的一个示例，其中节点类型包装 node_type_X:
type node_type_1 = NodeType1 of string
type node_type_2 = NodeType2 of string
type node =
NodeType1Node of node_type_1
| NodeType2Node of node_type_2
type edge =
EdgeType1 of node_type_1 * node_type_2
| EdgeType2 of node_type_2 * node_type_1
let link_source (e : edge) : node =
match e with
| EdgeType1 (src, _) -> NodeType1Node src
| EdgeType2 (src, _) -> NodeType2Node src
但问题是我在复制类型信息。我在edge的定义中指定了源节点类型，匹配link_source中的edge时也给定为NodeTypeXNode.
显然我不明白如何解决这个问题。我一直在思考 class 层次结构。在 OCaml 或 Haskell 中表达我在上面的 Scala 代码中实现的目标的正确方法是什么？
编辑： GADT 的答案更直接。
这是一个 Haskell 版本（没有 unsafeCoerce），这是您的 Scala 代码的一种可能翻译。然而，我无法提供 OCaml 解决方案。
请注意，在 Haskell 中，== 不能用于不同类型的值（在 Scala 中这样做的能力经常不受欢迎，并且是烦恼和错误的来源）。但是，如果您真的需要，我在下面提供了一个比较不同节点类型的解决方案。如果您 确实 不需要它，我建议您避免使用它，因为它依赖于 GHC features/extensions，这会使您的代码的可移植性降低，甚至可能导致问题类型检查器。
没有多态节点比较：
{-# LANGUAGE TypeFamilies, FlexibleContexts #-}
-- the FlexibleContexts extension can be eliminated
-- by removing the constraint on edgeSource.
-- let's start with just the data types
data NodeType1 = NodeType1 { name1 :: String } deriving Eq
data NodeType2 = NodeType2 { name2 :: String } deriving Eq
data NodeType3 = NodeType3 { name3 :: String } deriving Eq
data EdgeType1 = EdgeType1 { source1 :: NodeType1, target1 :: NodeType2 }
data EdgeType2 = EdgeType2 { source2 :: NodeType2, target2 :: NodeType1 }
-- you tell the compiler that the node types
-- somehow "belong together" by using a type class
class Node a where name :: a -> String
instance Node NodeType1 where name = name1
instance Node NodeType2 where name = name2
instance Node NodeType3 where name = name3
-- same about the edges, however in order to
-- map each Edge type to a different Node type,
-- you need to use TypeFamilies; see
-- https://wiki.haskell.org/GHC/Type_families
class Edge a where
type SourceType a
-- the constraint here isn't necessary to make
-- the code compile, but it ensures you can't
-- map Edge types to non-Node types.
edgeSource :: Node (SourceType a) => a -> SourceType a
instance Edge EdgeType1 where
type SourceType EdgeType1 = NodeType1
edgeSource = source1
instance Edge EdgeType2 where
type SourceType EdgeType2 = NodeType2
edgeSource = source2
main = do
let n1 = NodeType1 "Node1"
n2 = NodeType2 "Node2"
edge = EdgeType1 n1 n2
source = edgeSource edge
print (source == n1) -- True
-- print (source == n2) -- False -- DOESN'T COMPILE
WITH多态节点比较：
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
-- again, constraint not required but makes sure you can't
-- define node equality for non-Node types.
class (Node a, Node b) => NodeEq a b where
nodeEq :: a -> b -> Bool
-- I wasn't able to avoid OVERLAPPING/OVERLAPS here.
-- Also, if you forget `deriving Eq` for a node type N,
-- `nodeEq` justs yield False for any a, b :: N, without warning.
instance {-# OVERLAPPING #-} (Node a, Eq a) => NodeEq a a where
nodeEq = (==)
instance {-# OVERLAPPING #-} (Node a, Node b) => NodeEq a b where
nodeEq _ _ = False
main = do
let n1 = NodeType1 "Node1"
n2 = NodeType2 "Node2"
edge = EdgeType1 n1 n2
source = edgeSource edge
print (source `nodeEq` n1) -- True
print (source `nodeEq` n2) -- False
以上并不是告诉 Haskell 类型系统您的约束的唯一方法，例如函数依赖似乎适用，以及 GADT。
解释：
值得理解为什么在 Scala 中解决方案似乎更直接。
Scala 是 subtype polymorphism based OO such as the one found in C++, Java/C#, Python/Ruby, and (often Haskell-like) functional programming, which typically avoids subtyping a.k.a. datatype inheritance, and resorts to other, arguably better, forms of polymorphism.
的混合体
在 Scala 中，定义 ADT 的方式是将它们编码为 sealed trait + 多个（可能密封的）case 类 and/or case 对象。但是，这只是一个纯 ADT，前提是您从不引用案例对象和案例 类 的类型，以便假装它们类似于 Haskell 或 ML ADT。但是，您的 Scala 解决方案确实使用了这些类型，即它指向 "into" ADT。
在 Haskell 中无法做到这一点，因为 ADT 的各个构造函数没有不同的类型。相反，如果您需要在 ADT 的各个构造函数之间进行类型区分，则需要将原始 ADT 拆分为单独的 ADT，每个原始 ADT 的构造函数一个。然后 "group" 这些 ADT 放在一起，以便能够在您的类型签名中引用它们，方法是将它们放在 type class 中，这是一种特殊的多态性形式。
您对 Ocaml 类型系统的要求过高。在您第二次尝试的这一点上：
let link_source (e : edge) : node =
match e with
| EdgeType1 (src, _) ->
你说的是：应该清楚src是node_type_1的，而我给的是return类型的node，所以编译器应该可以从src的类型中找出正确的构造函数来使用。然而，这通常是不可能的：在给定的变体中，不存在从 'member types' 到构造函数的唯一映射；例如：type a = A of int | B of int。所以你必须指定构造函数（你可以将其命名更短）。
如果您不想这样，则必须使用多态性。一种选择是使 src_link 函数多态。一种尝试是
type e12 = node_type_1 * node_type_2
type e21 = node_type_2 * node_type_1
let link_source = fst
但随后您必须将 link 类型单独公开为元组。另一种选择是使用多态变体。
type node1 = [`N1 of string]
type node2 = [`N2 of string]
type node3 = [`N3 of string]
type node = [node1 | node2 | node3]
type edge = E12 of node1 * node2 | E21 of node2 * node1
然后可以写
let link_source (e:edge) : [<node] = match e with
| E12 (`N1 s, _) -> `N1 s
| E21 (`N2 s, _) -> `N2 s
这会自动统一 return 类型并检查它是否是现有节点。最后一个模式匹配也可以通过类型强制来处理：
let link_source (e:edge) : node = match e with
| E12 (n1, _) -> (n1:>node)
| E21 (n2, _) -> (n2:>node)
GADTs 也有帮助。使用与上面 node{,1,2,3} 相同的定义，可以定义
type ('a, 'b) edge =
| E12 : node1 * node2 -> (node1, node2) edge
| E21 : node2 * node1 -> (node2, node1) edge
然后是多态
let link_source : type a b . (a, b) edge -> a = function
| E12 (n1, _) -> n1
| E21 (n2, _) -> n2
附录：使用 GADT 时，没有必要使用多态变体。所以，一个人可以拥有
type node1 = N1 of string
type node2 = N2 of string
type node3 = N3 of string
并且 edge 和 link_source 的相同定义将起作用。
我认为对您的 Scala 版本最直接的翻译是使用幻像类型来标记节点和边缘类型，并使用 GADT 将它们绑定到特定的构造函数。
{-# LANGUAGE GADTs #-}
{-# LANGUAGE DataKinds #-}
data Type = Type1 | Type2
data Edge t where
EdgeType1 :: Node Type1 -> Node Type2 -> Edge Type1
EdgeType2 :: Node Type2 -> Node Type1 -> Edge Type2
data Node t where
NodeType1 :: String -> Node Type1
NodeType2 :: String -> Node Type2
instance Eq (Node t) where
NodeType1 a == NodeType1 b = a == b
NodeType2 a == NodeType2 b = a == b
edgeSource :: Edge t -> Node t
edgeSource (EdgeType1 src _) = src
edgeSource (EdgeType2 src _) = src
main :: IO ()
main = do
let n1 = NodeType1 "Node1"
n2 = NodeType2 "Node2"
edge = EdgeType1 n1 n2
src = edgeSource edge
print $ src == n1
现在这实际上比 Scala 版本更安全，因为我们知道从 edgeSource 静态地 returned 的确切类型，而不是仅仅获得我们需要的抽象基础 class类型转换或模式匹配。
如果你想完全模仿 Scala 版本，你可以将存在包装器中的幻像类型隐藏到 return 一个通用的 "unknown" 来自 edgeSource.[=14 的节点=]
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE FlexibleInstances #-}
data Some t where
Some :: t x -> Some t
edgeSource :: Edge t -> Some Node
edgeSource (EdgeType1 src _) = Some src
edgeSource (EdgeType2 src _) = Some src
label :: Node t -> String
label (NodeType1 l) = l
label (NodeType2 l) = l
instance Eq (Some Node) where
Some n1 == Some n2 = label n1 == label n2
我正在尝试描述一个复杂的图形，其中包含许多不同类型的节点和边，这些节点和边只能根据一组规则相互连接。我希望在编译时使用语言的类型系统检查这些规则。我的实际应用中有很多不同的节点和边类型。
我已经在 Scala 中轻松创建了一个简单的示例：
sealed trait Node {
val name: String
}
case class NodeType1(override val name: String) extends Node
case class NodeType2(override val name: String) extends Node
case class NodeType3(override val name: String) extends Node
sealed trait Edge
case class EdgeType1(source: NodeType1, target: NodeType2) extends Edge
case class EdgeType2(source: NodeType2, target: NodeType1) extends Edge
object Edge {
def edgeSource(edge: Edge): Node = edge match {
case EdgeType1(src, _) => src
case EdgeType2(src, _) => src
}
}
object Main {
def main(args: Array[String]) {
val n1 = NodeType1("Node1")
val n2 = NodeType2("Node2")
val edge = EdgeType1(n1, n2)
val source = Edge.edgeSource(edge)
println(source == n1) // true
}
}
有效图只能连接给定类型节点之间的给定边类型，如上面的 Scala 示例所示。函数"edgeSource"从边中提取源节点，就这么简单
这是一个我想用 OCaml 编写的非工作示例：
type node =
NodeType1 of string
| NodeType2 of string
type edge =
EdgeType1 of NodeType1 * NodeType2
| EdgeType2 of NodeType2 * NodeType1
let link_source (e : edge) : node =
match e with
| EdgeType1 (src, _) -> src
| EdgeType2 (src, _) -> src
这里的问题是 "NodeTypeX" 是构造函数而不是类型。因此，当我用定义了边的源和目标描述元组时，我无法使用它们。 "link_source" 函数只能 return 一种类型，而 "node" 是可以 return 某些东西的变体。
我一直在尝试如何在 OCaml 和 Haskell 中解决这个问题，这里是 OCaml 中的一个示例，其中节点类型包装 node_type_X:
type node_type_1 = NodeType1 of string
type node_type_2 = NodeType2 of string
type node =
NodeType1Node of node_type_1
| NodeType2Node of node_type_2
type edge =
EdgeType1 of node_type_1 * node_type_2
| EdgeType2 of node_type_2 * node_type_1
let link_source (e : edge) : node =
match e with
| EdgeType1 (src, _) -> NodeType1Node src
| EdgeType2 (src, _) -> NodeType2Node src
但问题是我在复制类型信息。我在edge的定义中指定了源节点类型，匹配link_source中的edge时也给定为NodeTypeXNode.
显然我不明白如何解决这个问题。我一直在思考 class 层次结构。在 OCaml 或 Haskell 中表达我在上面的 Scala 代码中实现的目标的正确方法是什么？
编辑： GADT 的答案更直接。
这是一个 Haskell 版本（没有 unsafeCoerce），这是您的 Scala 代码的一种可能翻译。然而，我无法提供 OCaml 解决方案。
请注意，在 Haskell 中，== 不能用于不同类型的值（在 Scala 中这样做的能力经常不受欢迎，并且是烦恼和错误的来源）。但是，如果您真的需要，我在下面提供了一个比较不同节点类型的解决方案。如果您 确实 不需要它，我建议您避免使用它，因为它依赖于 GHC features/extensions，这会使您的代码的可移植性降低，甚至可能导致问题类型检查器。
没有多态节点比较：
{-# LANGUAGE TypeFamilies, FlexibleContexts #-}
-- the FlexibleContexts extension can be eliminated
-- by removing the constraint on edgeSource.
-- let's start with just the data types
data NodeType1 = NodeType1 { name1 :: String } deriving Eq
data NodeType2 = NodeType2 { name2 :: String } deriving Eq
data NodeType3 = NodeType3 { name3 :: String } deriving Eq
data EdgeType1 = EdgeType1 { source1 :: NodeType1, target1 :: NodeType2 }
data EdgeType2 = EdgeType2 { source2 :: NodeType2, target2 :: NodeType1 }
-- you tell the compiler that the node types
-- somehow "belong together" by using a type class
class Node a where name :: a -> String
instance Node NodeType1 where name = name1
instance Node NodeType2 where name = name2
instance Node NodeType3 where name = name3
-- same about the edges, however in order to
-- map each Edge type to a different Node type,
-- you need to use TypeFamilies; see
-- https://wiki.haskell.org/GHC/Type_families
class Edge a where
type SourceType a
-- the constraint here isn't necessary to make
-- the code compile, but it ensures you can't
-- map Edge types to non-Node types.
edgeSource :: Node (SourceType a) => a -> SourceType a
instance Edge EdgeType1 where
type SourceType EdgeType1 = NodeType1
edgeSource = source1
instance Edge EdgeType2 where
type SourceType EdgeType2 = NodeType2
edgeSource = source2
main = do
let n1 = NodeType1 "Node1"
n2 = NodeType2 "Node2"
edge = EdgeType1 n1 n2
source = edgeSource edge
print (source == n1) -- True
-- print (source == n2) -- False -- DOESN'T COMPILE
WITH多态节点比较：
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
-- again, constraint not required but makes sure you can't
-- define node equality for non-Node types.
class (Node a, Node b) => NodeEq a b where
nodeEq :: a -> b -> Bool
-- I wasn't able to avoid OVERLAPPING/OVERLAPS here.
-- Also, if you forget `deriving Eq` for a node type N,
-- `nodeEq` justs yield False for any a, b :: N, without warning.
instance {-# OVERLAPPING #-} (Node a, Eq a) => NodeEq a a where
nodeEq = (==)
instance {-# OVERLAPPING #-} (Node a, Node b) => NodeEq a b where
nodeEq _ _ = False
main = do
let n1 = NodeType1 "Node1"
n2 = NodeType2 "Node2"
edge = EdgeType1 n1 n2
source = edgeSource edge
print (source `nodeEq` n1) -- True
print (source `nodeEq` n2) -- False
以上并不是告诉 Haskell 类型系统您的约束的唯一方法，例如函数依赖似乎适用，以及 GADT。
解释：
值得理解为什么在 Scala 中解决方案似乎更直接。
Scala 是 subtype polymorphism based OO such as the one found in C++, Java/C#, Python/Ruby, and (often Haskell-like) functional programming, which typically avoids subtyping a.k.a. datatype inheritance, and resorts to other, arguably better, forms of polymorphism.
的混合体在 Scala 中，定义 ADT 的方式是将它们编码为 sealed trait + 多个（可能密封的）case 类 and/or case 对象。但是，这只是一个纯 ADT，前提是您从不引用案例对象和案例 类 的类型，以便假装它们类似于 Haskell 或 ML ADT。但是，您的 Scala 解决方案确实使用了这些类型，即它指向 "into" ADT。
在 Haskell 中无法做到这一点，因为 ADT 的各个构造函数没有不同的类型。相反，如果您需要在 ADT 的各个构造函数之间进行类型区分，则需要将原始 ADT 拆分为单独的 ADT，每个原始 ADT 的构造函数一个。然后 "group" 这些 ADT 放在一起，以便能够在您的类型签名中引用它们，方法是将它们放在 type class 中，这是一种特殊的多态性形式。
您对 Ocaml 类型系统的要求过高。在您第二次尝试的这一点上：
let link_source (e : edge) : node =
match e with
| EdgeType1 (src, _) ->
你说的是：应该清楚src是node_type_1的，而我给的是return类型的node，所以编译器应该可以从src的类型中找出正确的构造函数来使用。然而，这通常是不可能的：在给定的变体中，不存在从 'member types' 到构造函数的唯一映射；例如：type a = A of int | B of int。所以你必须指定构造函数（你可以将其命名更短）。
如果您不想这样，则必须使用多态性。一种选择是使 src_link 函数多态。一种尝试是
type e12 = node_type_1 * node_type_2
type e21 = node_type_2 * node_type_1
let link_source = fst
但随后您必须将 link 类型单独公开为元组。另一种选择是使用多态变体。
type node1 = [`N1 of string]
type node2 = [`N2 of string]
type node3 = [`N3 of string]
type node = [node1 | node2 | node3]
type edge = E12 of node1 * node2 | E21 of node2 * node1
然后可以写
let link_source (e:edge) : [<node] = match e with
| E12 (`N1 s, _) -> `N1 s
| E21 (`N2 s, _) -> `N2 s
这会自动统一 return 类型并检查它是否是现有节点。最后一个模式匹配也可以通过类型强制来处理：
let link_source (e:edge) : node = match e with
| E12 (n1, _) -> (n1:>node)
| E21 (n2, _) -> (n2:>node)
GADTs 也有帮助。使用与上面 node{,1,2,3} 相同的定义，可以定义
type ('a, 'b) edge =
| E12 : node1 * node2 -> (node1, node2) edge
| E21 : node2 * node1 -> (node2, node1) edge
然后是多态
let link_source : type a b . (a, b) edge -> a = function
| E12 (n1, _) -> n1
| E21 (n2, _) -> n2
附录：使用 GADT 时，没有必要使用多态变体。所以，一个人可以拥有
type node1 = N1 of string
type node2 = N2 of string
type node3 = N3 of string
并且 edge 和 link_source 的相同定义将起作用。
我认为对您的 Scala 版本最直接的翻译是使用幻像类型来标记节点和边缘类型，并使用 GADT 将它们绑定到特定的构造函数。
{-# LANGUAGE GADTs #-}
{-# LANGUAGE DataKinds #-}
data Type = Type1 | Type2
data Edge t where
EdgeType1 :: Node Type1 -> Node Type2 -> Edge Type1
EdgeType2 :: Node Type2 -> Node Type1 -> Edge Type2
data Node t where
NodeType1 :: String -> Node Type1
NodeType2 :: String -> Node Type2
instance Eq (Node t) where
NodeType1 a == NodeType1 b = a == b
NodeType2 a == NodeType2 b = a == b
edgeSource :: Edge t -> Node t
edgeSource (EdgeType1 src _) = src
edgeSource (EdgeType2 src _) = src
main :: IO ()
main = do
let n1 = NodeType1 "Node1"
n2 = NodeType2 "Node2"
edge = EdgeType1 n1 n2
src = edgeSource edge
print $ src == n1
现在这实际上比 Scala 版本更安全，因为我们知道从 edgeSource 静态地 returned 的确切类型，而不是仅仅获得我们需要的抽象基础 class类型转换或模式匹配。
如果你想完全模仿 Scala 版本，你可以将存在包装器中的幻像类型隐藏到 return 一个通用的 "unknown" 来自 edgeSource.[=14 的节点=]
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE FlexibleInstances #-}
data Some t where
Some :: t x -> Some t
edgeSource :: Edge t -> Some Node
edgeSource (EdgeType1 src _) = Some src
edgeSource (EdgeType2 src _) = Some src
label :: Node t -> String
label (NodeType1 l) = l
label (NodeType2 l) = l
instance Eq (Some Node) where
Some n1 == Some n2 = label n1 == label n2