1

我正在研究一个蜘蛛纸牌玩家的 Haskell 实现，既作为学习 Haskell 的练习，又试图找到一个好的玩家算法。

我正在寻找由未处理的甲板、堆栈和基础组成的画面的有效表示。

对于卡片组，最明显的表示是[Card]whereCard是代数数据类型：

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

基础（已完成的花色）可以表示为一个[(Card King suit True)]或简单的Int已完成花色的计数，因为确定获胜游戏只需要确认基础大小为 8。

堆栈（游戏中的牌）的最佳表示是我正在努力解决的部分。如果我在 Scala 或 Clojure 中编写此代码，我可能会使用不可变（持久）Vector的[Card]. 向量允许使用列表推导快速索引查找卡片列表以进行合法移动计算。卡片列表以最上面的卡片（面朝上）作为列表的头部存储。将卡片从一个列表移动到另一个列表可以通过 drop 和 prepend 或 cons 的组合来完成。

在 Haskell 中，我不确定这是否最好表示为卡片列表列表或卡片列表数组，或者我尚未找到的其他一些数据结构。

想法？

4

2 回答 2

4

听起来该Vector软件包适合您的[Card]s 集。但是，只有少数堆，所以没关系 - 如果您必须浏览长度为 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，它是一个由 trie 表示的键值集合，这意味着查找时间受键大小的限制（哈希表具有相似的特征，因为计算哈希函数也与键大小成正比）。

这里有许多可能的结构的一个小烦恼是您必须检查索引是否是有效堆栈。因此，另一种选择是创建一个枚举类型data Stack = Stack1 | Stack2 | ...，而不是使用Data.Map，它是一个二叉搜索树，使用Stackas 键和卡片集合作为值。这样，每个可能的键都是一个有效的堆栈，只要你初始化第Map一个，你就可以安全地假设你需要的任何值都存在。

要么 要么IntMap比Map使用堆栈列表、大型元组或任何类似的东西都更可取。

对于单个堆栈，我实际上会考虑将它们与正面卡片一起存储为列表中的最后一个元素 - 因为您可以将有效的卡片序列移动在一起，按该顺序存储卡片意味着您可以简单地在列表，而不是不断地遍历和重建列表。

另一种选择是将牌序列表示为单个值（花色、最低牌、最高牌），然后可以在以后移动或拆分。

一种更通用的方法，它完全避免选择列表方向，是使用Data.Sequenceinstead，它是一种顺序（显然）数据结构，两端都有高效的操作。

请注意，我建议的所有三种类型都来自同一个包，这是一个标准库，如果列表不适合您的需要，通常应该首先寻找纯数据结构。

编辑：关于“向量”类型主题的附录：Haskell 中经常使用的vector包是通常意义上的向量数据结构，即一维数组，具有恒定时间索引，不可变的全或全更新Vectors，以及对按顺序生成和使用的向量的一些很好的优化。

然而，据我所知，Scala 和 Clojure 中使用的“持久向量”并不是通常意义上的简单不可变向量。相反，它们是一种更复杂的数据结构，旨在尽可能接近实际使用中可变向量的预期性能。实际的实现似乎是一个在每个节点上都有小数组的 trie；这类似于Data.IntMap，但针对类似数组的使用（有限范围内的许多值）而不是键值样式的使用（存储在任意索引处的稀疏数据）进行了优化。

于 2012-10-07T16:34:55.397 回答