哈斯克爾代表蜘蛛紙牌畫面

我正在研究一個蜘蛛紙牌遊戲的哈斯克爾實現，既作爲學習哈斯克爾的練習，也試圖找到一個好的球員算法。哈斯克爾代表蜘蛛紙牌畫面

我正在尋找一個高效的代表畫面，其中包括低價甲板，堆棧和基礎。

對於甲板，最明顯的表示是作爲[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

基礎（已完成的套）可以表示爲任一一個[(Card King suit True)]或簡稱爲Int計數因爲確定獲勝遊戲只需要確認基礎大小爲8.

堆棧（玩牌）的最佳表示形式是我正在努力的部分。如果我在Scala或Clojure中編寫它，我可能會使用[Card]的不可變（持續）Vector。使用列表理解，矢量可以快速索引卡列表查找合法移動計算。卡片列表以頂部卡片（朝上）作爲列表的頭部存儲。將卡從一個列表移動到另一個列表可以通過drop和prepend或cons的組合來完成。

在Haskell中，我不確定這是否最適合用作卡列表或卡列表陣列，還是其他尚未找到的數據結構。

想法？

來源

2012-10-07 Ralph

AndrewC是正確的，在這個尺寸可以使用幾乎任何東西，它會工作得不錯。在任何地方使用列表往往是一個合理的起點，也是一個合理的默認值但是我懷疑你也想知道Haskell會採用什麼樣的慣用方法，並且將列表編入列表非常少用慣用語（或者是一個好主意）。

對於收集堆棧，您需要索引訪問;他們只是偶然的一個序列。 A good default here would be Data.IntMap，它是由trie表示的鍵值集合，這意味着查找時間受鍵的大小限制（散列表具有相似的特徵，因爲計算散列函數也與鍵大小成比例）。

這裏有很多可能的結構有一個小麻煩，那就是你必須檢查一個索引是否是一個有效的棧。因此，另一種選擇是創建一個枚舉類型data Stack = Stack1 | Stack2 | ...，而使用Data.Map，這是一個二叉搜索樹，Stack作爲鍵和卡的集合作爲值。這樣，每個可能的密鑰都是有效的堆棧，並且只要您首先初始化Map，就可以安全地假定您需要的任何值都存在。

IntMap或Map要比使用堆棧，大元組或列表中的任何內容更爲可取。

對於單個堆棧，我實際上考慮將它們作爲列表中的最後一個元素存儲在表中 - 因爲您可以將有效的卡片序列移動到一起，以此順序存儲卡片意味着您只需在列表之間交換尾部，而不是遍歷和重建列表。

另一種選擇是將卡片序列表示爲單個值（最低卡片，最高卡片），然後可以移動或稍後拆分。

一個更通用的方法，避免完全選擇列表方向，是to use Data.Sequence instead，這是一個連續的（明顯的）數據結構，在兩端都有高效的操作。

請注意，我建議的所有三種類型都來自同一個包，這是一個標準庫，如果列表不適合您的需要，通常應該首先查找純數據結構。

編輯：上「載體」類型的主題的增編：The vector package used often in Haskell是在被一個1維陣列通常意義上的矢量數據結構，具有恆定時間索引，所有 - 或 - 對於不可變的Vector s沒有任何更新，並且對順序生成和使用的向量進行了一些很好的優化。

但是，我發現，在Scala和Clojure中使用的「持久向量」是而不是通常意義上的簡單不變的向量;相反，它們是一種更復雜的數據結構，旨在儘可能地接近實際使用中可預期的向量性能。實際的實現似乎是在每個節點上都有一個小數組的陣列;這與Data.IntMap類似，但針對類似數組的使用（在有限範圍內的許多值）進行了優化，而不是使用鍵值風格（存儲在任意索引處的稀疏數據）。

來源

2012-10-07 16:34:55

像往常一樣優秀的職位。當然，你是對的。當我第一次瞭解到f.p.時，Orwell中的列表索引操作符是'！'，講師稱之爲'尖叫'，但在Haskell中，它是'!!'，我想很多人會稱之爲'bang-bang'。尖叫是RTS在你詢問'[xs !! 5232，xs !! 324，xs !! 3547]'和砰砰響聲就是它所反覆敲擊列表的聲音。 – AndrewC

感謝您的優秀回答。我將需要仔細考慮我將用於堆棧和卡片列表的數據結構。我會研究你提到的那些。 – Ralph

@Ralph：我用一些額外的信息編輯了答案，這可能有助於將我的建議與您在Scala或Clojure中使用的內容聯繫起來。 –

聽起來像Vector package將適合您的一套[Card] s。但是，只有少量的堆，所以它並不重要 - 如果您必須瀏覽長度爲8的列表，那麼您的應用程序將不會無響應，因此請使用您認爲最合適的方法。由於數字較小，我不確定這是多麼重要的選擇。

選項：

矢量 - 最佳選擇，但你可以決定它的矯枉過正
列表 - 使用!!等。爲此目的，熟悉的不intractably慢，但讀C.A.McCann的回答。我不應該引導你成爲壞習慣！
直接使用數組
抽象數據類型data Piles = Piles [Card] [Card] [Card] [Card] [Card] [Card] [Card] [Card] - 不是很方便
元組([Card],[Card],[Card],[Card],[Card],[Card],[Card],[Card]) - 不是很方便

來源

2012-10-07 12:53:18 AndrewC

我看到你的帖子的第一反應是使用'Vector' - 這將是我在Scala或Clojure中的選擇。不過，鑑於C.A.麥坎的回答，我必須仔細考慮。 – Ralph

@Ralph：如果你需要一些可以很好地處理爲數組或列表的東西，那麼'Vector'是一個很好的默認選擇。用不可變數組或單個元素替換單個元素的效率相對較低 - 如果您需要通過索引讀取單個元素，但大多執行批量更新，則它們是最好的。請注意，順便說一句，Haskell中的「Vector」與Scala和Clojure稱之爲矢量的數據結構不同。 –

哈斯克爾代表蜘蛛紙牌畫面

回答

相關問題