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でそのような比較を行うことは可能ですか？

編集：私の場合、検査/デバッグの目的で2つを比較しようとしています。しかし、これを行うもう1つの理由は、単体テストのためである可能性があります。

4

2 に答える 2

12

まず第一に、aとbは等しくありませんが、aとcは概念的にだけでなく、実際には同じものです。

あなたの質問に答えるには、あなたの問題に対するドロップインの解決策はありません。同一性の比較が必要な場合は、まず同一性の概念を確立する必要があります。これを行う 1 つの方法は、Mapfrom キーをノードにすることです。

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

アイデアは、タイプkMapのキーとは別のものをノードに持つということです。ただし、そのインスタンスのインスタンスを作成することはできません。これを解決するややエレガントな方法は、リフレクションを使用することです。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)

最近注目を集めたもう 1 つのオプションは、観察可能な共有の概念です。

于 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 に答える