1

私は、Haskellを学び、優れたプレーヤーアルゴリズムを見つけようとする演習として、SpiderSolitaireプレーヤーのHaskell実装に取り​​組んでいます。

私は、タブローの効率的な表現を探しています。これは、アンディールデッキ、スタック、およびファンデーションで構成されています。

デッキの場合、最も明白な表現は、代数的データ型が[Card]どこにあるかです。Card

data Rank = Ace
          | Two
          | Three
          | Four
          | Five
          | Six
          | Seven
          | Eight
          | Nine
          | Ten
          | Jack
          | Queen
          | King
          deriving (Bounded, Enum, Eq, Ord)

data Suit = Clubs
          | Diamonds
          | Hearts
          | Spades
          deriving (Bounded, Enum, Eq, Ord)

data Card = Card
  { rank   :: Rank
  , suit   :: Suit
  , faceUp :: Bool
  } deriving (Bounded, Eq, Ord)

-- I omitted the instance Show ... implementations

ファンデーション（完成したスーツ）は、ファンデーションのサイズが8であることを確認するだけで勝つゲームを決定する必要があるため、完成したスーツの数[(Card King suit True)]または単にカウントとして表すことができます。Int

スタック（場にあるカード）の最良の表現は、私が苦労している部分です。これをScalaまたはClojureで書いている場合、おそらくの不変（永続的）Vectorを使用し[Card]ます。ベクトルを使用すると、リスト内包表記を使用して、合法的な移動計算のためにカードリストをすばやくインデックスで検索できます。カードリストは、一番上のカード（上向き）をリストの先頭として保存されます。あるリストから別のリストへのカードの移動は、ドロップとプリペンドまたは短所を組み合わせて行うことができます。

Haskellでは、これがカードリストのリストまたはカードリストの配列、あるいは私がまだ見つけていない他のデータ構造として最もよく表されているかどうかはわかりません。

考え？

4

2 に答える 2

4

Vectorパッケージはあなたのセットに適しているよう[Card]です。ただし、パイルの数は少ないので問題ありません。長さ8のリストをナビゲートする必要がある場合でも、アプリケーションが応答しなくなることはないので、適切と思われるものを選択してください。数が少ないことを考えると、あなたが何を選ぶかがそれほど重要かどうかはわかりません。

オプション：

  • ベクトル-一番の選択ですが、やり過ぎだと思うかもしれません
  • リスト-使用!!など。この目的のために手に負えないほど遅くはなく、なじみがありますが、CAMcCannの回答を読んでください。私はあなたを悪い習慣に導くべきではありません！
  • 配列の直接使用
  • 抽象データ型data Piles = Piles [Card] [Card] [Card] [Card] [Card] [Card] [Card] [Card]-あまり便利ではありません
  • タプル([Card],[Card],[Card],[Card],[Card],[Card],[Card],[Card])-あまり便利ではありません
于 2012-10-07T12:53:18.297 に答える
4

AndrewCは、このサイズではほとんど何でも使用でき、十分に機能するというのは正しいことです。多くの場合、どこでもリストを使用することが妥当な出発点であり、妥当なデフォルトです。しかし、Haskellでの慣用的なアプローチが何であるかを知りたいと思っているのではないかと思います。リストへのインデックス作成が慣用的なものになることはめったにありません（またはまったく良い考えではありません）。

スタックのコレクションには、インデックス付きアクセスが必要です。ちなみに、これらは単なるシーケンスです。ここでの適切なデフォルトData.IntMapは、です。これは、トライで表されるキー値コレクションです。これは、ルックアップ時間がキーのサイズによって制限されることを意味します（ハッシュ関数の計算もキーサイズに比例するため、ハッシュテーブルにも同様の特性があります） ）。

ここで考えられる多くの構造に関する小さな問題は、インデックスが有効なスタックであるかどうかを確認する必要があることです。そのため、別のオプションは、列挙型を作成し、data Stack = Stack1 | Stack2 | ...代わりに、キーとして、カードのコレクションを値としてData.Map持つ、バイナリ検索ツリーであるを使用することです。Stackそうすれば、可能なすべてのキーが有効なスタックであり、最初に初期化した限り、Map必要な値が存在すると安全に想定できます。

スタックのリスト、大きなタプル、またはそれらの線に沿ったものを使用するよりも、またはが非常に望ましいですIntMap。Map

個々のスタックについては、リストの最後の要素として表向きのカードを使用して保存することを実際に検討します。有効なカードのシーケンスを一緒に移動できるため、カードをこの順序で保存すると、テールを簡単に入れ替えることができます。リストを常にトラバースして再構築するのではなく、リスト。

もう1つのオプションは、カードシーケンスを単一の値（スーツ、最低のカード、最高のカード）として表すことです。この値は、後で移動したり分割したりできます。

リストの方向の選択を完全に回避する、より汎用的なアプローチは、代わりにを使用するData.Sequenceことです。これは、両端で効率的な操作を行うシーケンシャル（明らかに）データ構造です。

私が提案した3つのタイプはすべて、標準ライブラリである同じパッケージからのものであり、リストがニーズに合わない場合は、通常、最初に純粋なデータ構造を探す必要があることに注意してください。

編集：「ベクトル」タイプに関する補遺： Haskellで頻繁に使用されるパッケージはvector、1次元配列であるという通常の意味でのベクトルデータ構造であり、一定時間のインデックス付け、不変のオールオアナッシング更新を備えています。Vectors、および順次生成および消費されるベクトルのいくつかの優れた最適化。

しかし、私が見つけることができることから、ScalaとClojureで使用される「永続的なベクトル」は、通常の意味での単純な不変のベクトルではありません。むしろ、それらは実際の使用で可変ベクトルの期待されるパフォーマンスに可能な限り近づくように設計された、より洗練されたデータ構造です。実際の実装は、各ノードに小さな配列があるトライのようです。これはに似てData.IntMapいますが、Key-Valueスタイルの使用（任意のインデックスに格納されたスパースデータ）ではなく、配列のような使用（限られた範囲の多くの値）用に最適化されています。

于 2012-10-07T16:34:55.397 に答える