6

我有一个复杂且递归的数据结构，我已将其简化为以下内容：

data Node = Node { value :: Integer, next :: Node } deriving (Show,Eq)

给定以下表达式：

--Create a circular structure
a = Node 1 b
b = Node 0 a --Tie the knot
c = Node 1 b --Another structure which points to b

表达式a和c在概念上是相等的：它们都表示一个节点，该节点保存值 1 并指向表达式 b。我的问题是：如何检查它们在 Haskell 表达式中是否确实相等？如果我评估a == c，它将永远评估循环结构中的子元素。

是否可以在 Haskell 中进行这样的比较？

编辑：就我而言，我试图比较两者以进行检查/调试。但这样做的另一个原因可能是单元测试。

4

2 回答 2

12

首先，a和b不相等，但是a和c相等，不仅在概念上，而且它们实际上是相同的东西。

回答您的问题：您的问题没有直接解决方案。如果你需要身份比较，你首先要建立一个身份的概念。一种方法是使用Map从键到节点：

data Node k =
    Node {
      nodeValue :: Integer,
      nodeNext  :: k
    }

这个想法是你有一个单独Map的从类型k到节点的键。但是，您不能Eq为该实例编写实例。解决这个问题的一种优雅的方法是使用反射：

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Reflection

data Node n k =
    Node {
      nodeValue :: Integer,
      nodeNext  :: k
    }

instance (n `Reifies` Map k (Node n k)) => Eq (Node n k) where
    (==) = {- ... -}
        where
        nodeMap :: Map k (Node n k)
        nodeMap = reflect (Proxy :: Proxy n)

最近引起关注的另一个选项是可观察共享的概念。

于 2013-01-22T00:16:55.100 回答
-1

如果您承诺仅将其用于测试和调试，而不用于应用程序代码，您还可以使用我的ghc-heap-view库，它为您提供 Haskell 堆的低级视图，并使您能够实现比较：

Prelude> :script /home/jojo/.cabal/share/ghc-heap-view-0.4.0.0/ghci 
Prelude> data Node = Node { value :: Integer, next :: Node } deriving (Show,Eq)
Prelude> let { a = Node 1 b; b = Node 0 a ; c = Node 1 b}
Prelude> take 100 (show a) -- make sure it is evaluated, we are not interested in thunks here
"Node {value = 1, next = Node {value = 0, next = Node {value = 1, next = Node {value = 0, next = Node"
Prelude> take 100 (show c) -- dito
"Node {value = 1, next = Node {value = 0, next = Node {value = 1, next = Node {value = 0, next = Node"
Prelude> System.Mem.performGC
Prelude> :printHeap a
let x0 = Node (S# 1) (Node (S# 0) x0)
in x0
Prelude> :printHeap c
let x2 = Node (S# 0) (Node (S# 1) x2)
in Node (S# 1) x2

但是现在这对你来说肯定不是正确的事情，因为你正在“做这个项目作为学习 Haskell 的练习”。

于 2013-01-22T08:55:40.223 回答