0

Haskell Bag（マルチセット）を実装しようとしています。

これまでのところ私はこれを持っています

data Bag a = EmptyBag | ListBag [(a, Integer)] deriving (Eq, Show)

emptyBag :: Bag a
emptyBag = EmptyBag

add :: a -> (Bag a) -> (Bag a)
add element EmptyBag = ListBag [(element,1)]
add element (ListBag bag)
  | element `elem` map fst bag = ListBag bag -- will actually increment the count, and return the new bag.

エラーが発生します

No instance for (Eq a)
      arising from a use of `elem'
    In the expression: element `elem` map fst bag

コンパイルするとき。これは、2つの異なるタイプで同等性を判断できないためですか？バッグ内のアイテムの最初の要素がすでにバッグ内にあるかどうかを確認するにはどうすればよいですか？

また、特定のアイテムのカウントをインクリメントし、新しい（element、count）タプルでバッグを戻す方法に関するヒントはありますか？

4

2 に答える 2

6

問題の直接の原因は、すべてのタイプが同等であるとは限らないことです。型シグネチャを変更することにより、等価比較を提供する型でのみ機能するように型を制限できます。

add :: Eq a => a -> Bag a -> Bag a

実装のヒントについては、Hackageのmultiset-combおよびdata-ordlistパッケージを確認することをお勧めします。

最後に、EmptyBagコンストラクターは少し疑わしいと思います。たとえば、コンストラクターはどのように違うのListBag []でしょうか。

于 2012-06-24T06:39:12.927 に答える
5

はい、問題は、Haskellが任意の要素を比較して等しいかどうかを比較できないことです。つまり、型クラスの一部である型しか比較できませEqん。これは理にかなっています。関数などの特定のものを比較することは決定できません。他の言語には「参照の平等」の概念がありますが、これはHaskellでは意味がありません。したがって、基本的に値が等しいかどうかを比較できないタイプがあります。2つの値が等しいかどうかを比較する方法がない限り、何かがすでにリストにあるかどうかを確認することはできませんEq。

Eqこれは、セット（またはマルチセット）の実装が（または他の明示的な比較関数）に依存することを意味します。実際には、セットはパフォーマンス上の理由からも依存する傾向がありOrdますが、リストを使用しているだけなので、心配する必要はありません。これはまた、マルチセットをファンクターまたはモナドにすることはできませんが、c'estlavieにすることはできないことを意味します。

つまり、タイプをに制限する必要がありますEq。したがって、に変更a -> Bag a -> Bag gしEq a => a -> Bag a -> Bag aます。

あなたは言語を学ぶためにいくつかの練習をしているように見えるので（これが見下すようなものにならないことを願っています）、2番目の質問のヒントをいくつか示します。

再帰的に考えます。まず、基本的なケースを考えてみましょう。空のマルチセットに要素を追加するにはどうすればよいですか？別の基本ケース：リストの先頭に要素を含むマルチセットがある場合、新しい増分マルチセットをどのように作成しますか？最後に、再帰的な場合：ヘッドがインクリメントしたい要素ではないリストがある場合はどうしますか？これらすべての質問に答えたら、リストのパターンマッチングによってそれぞれを単一のケースとして記述し、それらを組み合わせてadd関数を取得できます。

もう1つの注意：コンストラクターを持つことEmptyBagは冗長です。リストはすでに空にすることができます！とどうListBag []違うのEmptyBag？この場合、コンストラクターは1つだけです。

したがって、add関数は次のようになります。

add :: Eq a => a -> Bag a -> Bag a
add x (ListBag []) = ...
add x (ListBag [(x', n)]) = ...

適切なケースを入力するだけで、...準備は完了です。

あなたのコメントによると、これはあなたがそれを繰り返している間リストを保持する方法についてのいくつかのサンプルコードです。

基本的に、主な考え方は単純です。再帰的な場合、関数に渡されたリストの残りの部分を返すのではなく、現在の要素の後にリストの残りの部分を返します。基本ケースはまだ単純なままです：

add :: Eq a => a -> Bag a -> Bag a
add x (ListBag []) = ListBag [(x, 1)] -- first base case
add x (ListBag (x', n):xs)
  | x == x'   = ListBag $ (x', n + 1) : xs -- second base case
  | otherwise = let ListBag rest = add x (ListBag xs) in ListBag $ (x', n) : rest

letステートメントを使用してリストListBagを削除し、タッチしなかったタプルをリストの前に戻す必要があります。

このように再帰を考えるとき、私はそれを一連のステップのように考えるのではなく、それぞれのケースを別々に考えることを好みます。いずれの場合も、与えられたもの全体 を返却したいと思います。ListBagしたがって、作業中のタプルをリストの残りの部分と比較する必要があります。再帰的な場合、リストの残りの部分は再帰的な呼び出しから取得します。2番目の基本ケースでは、関数を再度呼び出す必要はありません。

したがって、各ステップでバッグ全体を返すことにより、すべての再帰の最後にリスト全体を維持します。

これがより明確になることを願っています。

于 2012-06-24T06:41:37.573 に答える