Haskell 中的两个无限数据结构之间是否可以进行相等性测试？
Is equality testing possible between two infinite data structure in Haskell?
在我正在进行的一个项目中，某种类型的数据有时可能包含在其中。例如，
data Example = Apple Int
| Pear Int Example
a = Pear 10 a
b = Pear 10 b
作为一名程序员，我知道 a 和 b 是相等的，但是当我实际测试它们之间的相等性时，它会无限循环，因为需要评估它们的值以进行比较。
有没有其他方法可以在这些数据之间进行相等性测试？或者有什么办法可以避免这样的问题？
总的来说：没有。这种相等性测试减少了停机问题。一种看待这一点的方法是，我们可以将图灵机对某些输入的执行表示为这样的无限数据结构。另一种看待它的方式是惰性数据结构可以表示任意暂停的计算。
避免此类问题的唯一真正方法是对您的数据结构设置一些额外的限制，或者检查比相等性更受限制的内容。
第一种方法的一个示例是使用某种引用使数据类型中的循环显式化，让您在进行时检测到它们。这将准确地限制您可以用数据结构表达的内容，但也会让您的相等谓词可靠地检测循环。我想你可以用 observable sharing;看一下 data-reify 的包，可以做到这一点。这种方法应该使检查像您的示例一样非常直接的递归结构变得容易。
对于第二种方法，你可以有一个returns一个Maybe Bool的函数：如果它在X步中不能确定两个结构是否相等，它returns Nothing。根据您的数据类型的创建方式，您可以确保任何超过一定大小且具有相同前缀的类型 几乎总是 相等并且仅依赖于此。
我想谈谈如何真正正确地做到这一点，如果这是你想做的事情。它比您一开始可能猜到的要难——但比您第二次可能猜到的要容易！为了好玩，我打算把问题稍微难一点；我们最终将代表价值观
a = Pear 10 a
b = Pear 10 (Pear 10 b)
c = Apple 10
并计算 a 和 b 是 "equal"——为了精确的平等意义，我们将在下面讨论。这可不是observable分享一定会免费给你的东西。
我们将在 sequel 中使用的精确平等意义是双相似性。通常，双相似性——及其近亲，双模拟——被表示为两个标记图之间的关系。出于我们的目的，您应该在此处描绘图中的节点，其中包含我们数据类型的当前构造函数中的一些数据，以及指向子项的边。因此，对于值 Pear 10 (Pear 20 (Apple 30))，我们可能有图 Pear 10 -> Pear 20 -> Apple 30；而上面的值b就是循环图
Pear 10 -> Pear 10
^ |
\_______/
Observable 共享会让你走到这一步，但不会让你明白如何确定这两个图是等价的：
Pear 10 -. Pear 10 -> Pear 10
^ | ~= ^ |
\____/ \_______/
如果您熟悉用于最小化 DFA 的算法，您可能会到此为止；此类算法很容易用于测试常规语言的相等性，而这正是我们下面要做的。
关键的见解是上面两个图中的所有三个节点的行为基本相同——从左图中的节点开始的任何路径在右图中都有一条 "identical" 路径。也就是说，假设我们在左右图中的节点之间有一个关系 R 满足 属性:
if nl R nr
and there is an edge (nl, e, nl') in the graph,
then there is an edge (nr, e, nr') in the graph
and nl' R nr'
我们称 R 为互模拟。最大的关系 R 将被称为双相似性。如果两个图中的 "root" 个节点是双相似的，那么对应的 Haskell 个值是相等的！在这一点上，我希望你已经到了这个问题似乎比你最初猜测的更难的地步；也许不可能。毕竟，我们应该如何获得最大的此类关系？
一个答案是从完整的关系开始，剪掉任何违反上述约束的节点对。不断迭代该过程，直到没有任何变化，然后看看我们还剩下什么。事实证明你可以证明这个过程实际上产生了 双相似性！我们将在下面以一种非常天真的方式实现它；如果你想要更快的速度，你可以 google 关于高效的双相似算法。
首先是序言。我们将使用 fgl 包来表示图形。
import Control.Monad.Reader
import Data.Graph.Inductive hiding (ap)
import Data.Map (Map)
import Data.Set (Set)
import qualified Data.Map as M
import qualified Data.Set as S
fgl 包为节点的身份定义了一个类型 Node。我们将简单地表示我们的关系为
type Relation = Set (Node, Node)
首先，我们需要一对图的完整关系。当我们这样做时，我们还不如立即删除节点标签不匹配的任何对。 （关于我选择的命名约定的注意事项：在 fgl 中，每个节点和边缘都有一个标签——可以是您喜欢的任何类型——和一个标识——必须是 Node 或 [=30 类型=]. 我们的名字将尽可能反映这一点：n 前缀代表节点，e 代表边，i 代表身份，v 代表 label/value。我们将使用 l 和 r 作为我们左图和右图的后缀。）
labeledPairs :: (Eq n, Graph gr) => gr n e -> gr n e' -> Relation
labeledPairs l r = S.fromList
[ (nil, nir)
| (nil, nvl) <- labNodes l
, (nir, nvr) <- labNodes r
, nvl == nvr
]
现在，下一步是检查两个节点是否满足我们上面描述的 "single-step relatedness" 条件。也就是说，对于其中一个节点的每条边，我们正在寻找具有相同标签的另一条边，并通向我们当前声称相关的另一个节点。将此搜索音译为 Haskell:
-- assumption: nil and nir are actual nodes in graphs l and r, respectively
ssRelated :: (Ord e, Graph gr) => gr n e -> gr n e -> Relation -> Node -> Node -> Bool
ssRelated l r rel nil nir = rell && relr where
el = out l nil
er = out r nil
mel = M.fromListWith (++) [(evl, [nil]) | (_, nil, evl) <- el]
mer = M.fromListWith (++) [(evr, [nir]) | (_, nir, evr) <- er]
rell = and
[ or [(nil, nir) `S.member` rel | nir <- M.findWithDefault [] evl mer]
| (_, nil, evl) <- el
]
relr = and
[ or [(nil, nir) `S.member` rel | nil <- M.findWithDefault [] evr mel]
| (_, nir, evr) <- er
]
我们现在可以编写一个函数来检查每对节点的单步适用性：
prune :: (Ord e, Graph gr) => gr n e -> gr n e -> Relation -> Relation
prune l r rel = S.filter (uncurry (ssRelated l r rel)) rel
为了计算双相似度，如上所述，我们将从完整的关系开始，并反复修剪掉不符合标准的节点。
bisimilarity :: (Eq n, Ord e, Graph gr) => gr n e -> gr n e -> Relation
bisimilarity l r
= fst . head
. dropWhile (uncurry (/=))
. ap zip tail
. iterate (prune l r)
$ labeledPairs l r
现在我们可以通过选取每个图中的根节点并检查它们的双相似性来检查两个图是否具有相同的无限展开：
-- assumption: the root of the graph is node 0
bisimilar :: (Eq n, Ord e, Graph gr) => gr n e -> gr n e -> Bool
bisimilar l r = (0, 0) `S.member` bisimilarity l r
现在让我们看看它的实际效果！我们将在图形表示的答案中模拟 a、b 和 c。由于我们的数据类型只有一种可能的递归出现，因此我们不需要有趣的边缘标签。 mkGraph 函数获取标记节点列表和标记边列表，并根据它们构建图形。
data NodeLabel = Apple Int | Pear Int
deriving (Eq, Ord, Read, Show)
type EdgeLabel = ()
a, b, c :: Gr NodeLabel EdgeLabel
a = mkGraph [(0, Pear 10)] [(0, 0, ())]
b = mkGraph [(0, Pear 10), (1, Pear 10)] [(0, 1, ()), (1, 0, ())]
c = mkGraph [(0, Apple 10)] []
在 ghci 中：
*Main> bisimilar a b
True
*Main> bisimilar a c
False
*Main> bisimilar b c
False
*Main> bisimilar a a
True
*Main> bisimilar b b
True
*Main> bisimilar c c
True
看起来不错！使其快速并将其连接到可观察共享库作为 reader 的练习。请记住，虽然这种方法可以处理具有无限展开的图，但用这种方式处理无限图当然可能会遇到麻烦！
在我正在进行的一个项目中，某种类型的数据有时可能包含在其中。例如，
data Example = Apple Int
| Pear Int Example
a = Pear 10 a
b = Pear 10 b
作为一名程序员，我知道 a 和 b 是相等的，但是当我实际测试它们之间的相等性时，它会无限循环，因为需要评估它们的值以进行比较。
有没有其他方法可以在这些数据之间进行相等性测试？或者有什么办法可以避免这样的问题？
总的来说：没有。这种相等性测试减少了停机问题。一种看待这一点的方法是，我们可以将图灵机对某些输入的执行表示为这样的无限数据结构。另一种看待它的方式是惰性数据结构可以表示任意暂停的计算。
避免此类问题的唯一真正方法是对您的数据结构设置一些额外的限制，或者检查比相等性更受限制的内容。
第一种方法的一个示例是使用某种引用使数据类型中的循环显式化，让您在进行时检测到它们。这将准确地限制您可以用数据结构表达的内容，但也会让您的相等谓词可靠地检测循环。我想你可以用 observable sharing;看一下 data-reify 的包，可以做到这一点。这种方法应该使检查像您的示例一样非常直接的递归结构变得容易。
对于第二种方法，你可以有一个returns一个Maybe Bool的函数：如果它在X步中不能确定两个结构是否相等，它returns Nothing。根据您的数据类型的创建方式，您可以确保任何超过一定大小且具有相同前缀的类型 几乎总是 相等并且仅依赖于此。
我想谈谈如何真正正确地做到这一点，如果这是你想做的事情。它比您一开始可能猜到的要难——但比您第二次可能猜到的要容易！为了好玩，我打算把问题稍微难一点；我们最终将代表价值观
a = Pear 10 a
b = Pear 10 (Pear 10 b)
c = Apple 10
并计算 a 和 b 是 "equal"——为了精确的平等意义，我们将在下面讨论。这可不是observable分享一定会免费给你的东西。
我们将在 sequel 中使用的精确平等意义是双相似性。通常，双相似性——及其近亲，双模拟——被表示为两个标记图之间的关系。出于我们的目的，您应该在此处描绘图中的节点，其中包含我们数据类型的当前构造函数中的一些数据，以及指向子项的边。因此，对于值 Pear 10 (Pear 20 (Apple 30))，我们可能有图 Pear 10 -> Pear 20 -> Apple 30；而上面的值b就是循环图
Pear 10 -> Pear 10
^ |
\_______/
Observable 共享会让你走到这一步，但不会让你明白如何确定这两个图是等价的：
Pear 10 -. Pear 10 -> Pear 10
^ | ~= ^ |
\____/ \_______/
如果您熟悉用于最小化 DFA 的算法，您可能会到此为止；此类算法很容易用于测试常规语言的相等性，而这正是我们下面要做的。
关键的见解是上面两个图中的所有三个节点的行为基本相同——从左图中的节点开始的任何路径在右图中都有一条 "identical" 路径。也就是说，假设我们在左右图中的节点之间有一个关系 R 满足 属性:
if nl R nr
and there is an edge (nl, e, nl') in the graph,
then there is an edge (nr, e, nr') in the graph
and nl' R nr'
我们称 R 为互模拟。最大的关系 R 将被称为双相似性。如果两个图中的 "root" 个节点是双相似的，那么对应的 Haskell 个值是相等的！在这一点上，我希望你已经到了这个问题似乎比你最初猜测的更难的地步；也许不可能。毕竟，我们应该如何获得最大的此类关系？
一个答案是从完整的关系开始，剪掉任何违反上述约束的节点对。不断迭代该过程，直到没有任何变化，然后看看我们还剩下什么。事实证明你可以证明这个过程实际上产生了 双相似性！我们将在下面以一种非常天真的方式实现它；如果你想要更快的速度，你可以 google 关于高效的双相似算法。
首先是序言。我们将使用 fgl 包来表示图形。
import Control.Monad.Reader
import Data.Graph.Inductive hiding (ap)
import Data.Map (Map)
import Data.Set (Set)
import qualified Data.Map as M
import qualified Data.Set as S
fgl 包为节点的身份定义了一个类型 Node。我们将简单地表示我们的关系为
type Relation = Set (Node, Node)
首先，我们需要一对图的完整关系。当我们这样做时，我们还不如立即删除节点标签不匹配的任何对。 （关于我选择的命名约定的注意事项：在 fgl 中，每个节点和边缘都有一个标签——可以是您喜欢的任何类型——和一个标识——必须是 Node 或 [=30 类型=]. 我们的名字将尽可能反映这一点：n 前缀代表节点，e 代表边，i 代表身份，v 代表 label/value。我们将使用 l 和 r 作为我们左图和右图的后缀。）
labeledPairs :: (Eq n, Graph gr) => gr n e -> gr n e' -> Relation
labeledPairs l r = S.fromList
[ (nil, nir)
| (nil, nvl) <- labNodes l
, (nir, nvr) <- labNodes r
, nvl == nvr
]
现在，下一步是检查两个节点是否满足我们上面描述的 "single-step relatedness" 条件。也就是说，对于其中一个节点的每条边，我们正在寻找具有相同标签的另一条边，并通向我们当前声称相关的另一个节点。将此搜索音译为 Haskell:
-- assumption: nil and nir are actual nodes in graphs l and r, respectively
ssRelated :: (Ord e, Graph gr) => gr n e -> gr n e -> Relation -> Node -> Node -> Bool
ssRelated l r rel nil nir = rell && relr where
el = out l nil
er = out r nil
mel = M.fromListWith (++) [(evl, [nil]) | (_, nil, evl) <- el]
mer = M.fromListWith (++) [(evr, [nir]) | (_, nir, evr) <- er]
rell = and
[ or [(nil, nir) `S.member` rel | nir <- M.findWithDefault [] evl mer]
| (_, nil, evl) <- el
]
relr = and
[ or [(nil, nir) `S.member` rel | nil <- M.findWithDefault [] evr mel]
| (_, nir, evr) <- er
]
我们现在可以编写一个函数来检查每对节点的单步适用性：
prune :: (Ord e, Graph gr) => gr n e -> gr n e -> Relation -> Relation
prune l r rel = S.filter (uncurry (ssRelated l r rel)) rel
为了计算双相似度，如上所述，我们将从完整的关系开始，并反复修剪掉不符合标准的节点。
bisimilarity :: (Eq n, Ord e, Graph gr) => gr n e -> gr n e -> Relation
bisimilarity l r
= fst . head
. dropWhile (uncurry (/=))
. ap zip tail
. iterate (prune l r)
$ labeledPairs l r
现在我们可以通过选取每个图中的根节点并检查它们的双相似性来检查两个图是否具有相同的无限展开：
-- assumption: the root of the graph is node 0
bisimilar :: (Eq n, Ord e, Graph gr) => gr n e -> gr n e -> Bool
bisimilar l r = (0, 0) `S.member` bisimilarity l r
现在让我们看看它的实际效果！我们将在图形表示的答案中模拟 a、b 和 c。由于我们的数据类型只有一种可能的递归出现，因此我们不需要有趣的边缘标签。 mkGraph 函数获取标记节点列表和标记边列表，并根据它们构建图形。
data NodeLabel = Apple Int | Pear Int
deriving (Eq, Ord, Read, Show)
type EdgeLabel = ()
a, b, c :: Gr NodeLabel EdgeLabel
a = mkGraph [(0, Pear 10)] [(0, 0, ())]
b = mkGraph [(0, Pear 10), (1, Pear 10)] [(0, 1, ()), (1, 0, ())]
c = mkGraph [(0, Apple 10)] []
在 ghci 中：
*Main> bisimilar a b
True
*Main> bisimilar a c
False
*Main> bisimilar b c
False
*Main> bisimilar a a
True
*Main> bisimilar b b
True
*Main> bisimilar c c
True
看起来不错！使其快速并将其连接到可观察共享库作为 reader 的练习。请记住，虽然这种方法可以处理具有无限展开的图，但用这种方式处理无限图当然可能会遇到麻烦！