algorithm - この Haskell コードをより簡潔にするにはどうすればよいでしょうか?

Question

練習として、Haskell でカジノ ゲーム「戦争」のシミュレーションを書こうとしています。

http://en.wikipedia.org/wiki/Casino_war

ルールが少ないとてもシンプルなゲームです。それ以外の場合は、私が知っている命令型言語で書くのは非常に簡単な問題ですが、Haskell で書くのに苦労しています。

私がこれまでに持っているコード:

 -- Simulation for the Casino War

import System.Random
import Data.Map

-------------------------------------------------------------------------------
-- stolen from the internet

fisherYatesStep :: RandomGen g => (Map Int a, g) -> (Int, a) -> (Map Int a, g)
fisherYatesStep (m, gen) (i, x) = ((insert j x . insert i (m ! j)) m, gen')
    where
        (j, gen') = randomR (0, i) gen

fisherYates :: RandomGen g => g -> [a] -> ([a], g)
fisherYates gen [] = ([], gen)
fisherYates gen l = toElems $ Prelude.foldl
        fisherYatesStep (initial (head l) gen) (numerate (tail l))
    where
        toElems (x, y) = (elems x, y)
        numerate = zip [1..]
        initial x gen = (singleton 0 x, gen)

-------------------------------------------------------------------------------

data State = Deal | Tie deriving Show

-- state: game state
-- # cards to deal
-- # cards to burn
-- cards on the table
-- indices for tied players
-- # players
-- players winning
-- dealer's winning
type GameState = (State, Int, Int, [Int], [Int], Int, [Int], Int)

gameRound :: GameState -> Int -> GameState
gameRound (Deal, toDeal, toBurn, inPlay, tied, numPlayers, pWins, dWins) card
    | toDeal > 0 =
        -- not enough card, deal a card
        (Deal, toDeal - 1, 0, card:inPlay, tied, numPlayers, pWins, dWins)
    | toDeal == 0 =
        -- enough cards in play now
        -- here should detemine whether or not there is any ties on the table,
        -- and go to the tie state
        let
            dealerCard = head inPlay
            p = zipWith (+) pWins $ (tail inPlay) >>=
                (\x -> if x < dealerCard then return (-1) else return 1)
            d = if dealerCard == (maximum inPlay) then dWins + 1 else dWins - 1
        in
            (Deal, numPlayers + 1, 0, [], tied, numPlayers, p, d)
gameRound (Tie, toDeal, toBurn, inPlay, tied, numPlayers, pWins, dWins) card
    -- i have no idea how to write the logic for the tie state AKA the "war" state
    | otherwise = (Tie, toDeal, toBurn, inPlay, tied, numPlayers, pWins, dWins)

-------------------------------------------------------------------------------

main = do
    rand <- newStdGen
    -- create the shuffled deck
    (deck, _) <- return $ fisherYates rand $ [2 .. 14] >>= (replicate 6)
    -- fold the state updating function over the deck
    putStrLn $ show $ Prelude.foldl gameRound
        (Deal, 7, 0, [], [], 6, [0 ..], 0) deck

-------------------------------------------------------------------------------

乱数を作成するために余分な作業が必要な理由は理解していますが、基本的な構造や概念が欠けていると確信しています。状態のコレクションを保持し、入力のリストに対して分岐ロジックを実行することは、これほど厄介なことではありません。テーブルに同点の場合のロジックを記述する良い方法さえ思いつきませんでした。

完全な解決策を求めているわけではありません。誰かが私が間違っていること、または関連するいくつかの良い読み物を指摘できれば、それは本当に素晴らしいことです.

前もって感謝します。

Answer 1

アプリケーションの状態を維持するための便利な設計パターンは、いわゆる状態モナドです。ここで説明といくつかの導入例を見つけることができます。また、 のタプルではなく、名前付きフィールドを持つデータ型の使用を検討することもできますGameState。次に例を示します。

data GameState = GameState { state :: State, 
                             toDeal :: Int
                           -- and so on
                           }

これにより、レコード構文を使用して個々のフィールドに簡単にアクセス/更新できるようになります。

Answer 2

コードを読みやすくするには、ゲームの構造を意味のあるコンポーネントに分割し、それに応じてコードを再編成する必要があります。ここまでで、ゲームのすべての状態を 1 つのデータ構造にまとめました。その結果、常にすべてのゲームの詳細に対処する必要があります。

ゲームは、各プレーヤーとディーラーのスコアを追跡します。スコアに 1 を足したり、1 を引いたりすることがあります。スコアはそれ以外には使用されません。スコア管理を他のコードから分離します。

-- Scores for each player and the dealer
data Score = Score [Int] Int

-- Outcome for each player and the dealer.  'True' means a round was won.
data Outcome = Outcome [Bool] Bool

startingScore :: Int -> Score
startingScore n = Score (replicate n 0) 0

updateScore :: Outcome -> Score -> Score
updateScore (Outcome ps d) (Score pss ds) = Score (zipWith upd pss pos) (update ds d)
  where upd s True  = s+1
        upd s False = s-1

配られるカードは、プレーヤーとディーラーにも関連付けられています。ラウンドの勝敗は、カードの値のみに基づいています。スコアの計算を他のコードから分離します。

type Card = Int
data Dealt = Dealt [Card] Card

scoreRound :: Dealt -> Outcome
scoreRound (Dealt ps dealerCard) = Outcome (map scorePlayer ps) (dealerCard == maximumCard)
  where
    maximumCard = maximum (dealerCard : ps)
    scorePlayer p = p >= dealerCard

ゲーム ラウンドは、単一のOutcome. それに応じてコードを再編成します。

type Deck = [Card]

deal :: Int -> Deck -> (Dealt, Deck)
deal n d = (Dealt (take n d) (head $ drop n d), drop (n+1) d) -- Should check whether deck has enough cards

-- The 'input-only' parts of GameState
type GameConfig =
  GameConfig {nPlayers :: Int}

gameRound :: GameConfig -> Deck -> (Deck, Outcome)
gameRound config deck = let
  (dealt, deck') = deal (nPlayers config) deck
  outcome        = scoreRound dealt
  in (deck', outcome)

これは、元のコードにあったもののほとんどをカバーしています。同様の方法で残りにアプローチできます。

---

あなたが得るべき主な考えは、Haskell がプログラムをそれ自体が意味のある小さな断片に分解することを容易にするということです。これにより、コードの操作が容易になります。

すべてを に入れる代わりに、 、、、およびGameStateを作成しました。これらのデータ型の一部は、元の. 他のものは元のコードにはまったくありませんでした。それらは、複雑なループが編成される方法に暗黙のうちにありました。ゲーム全体を に入れる代わりに、 、、、およびその他の関数を作成しました。これらはそれぞれ、ほんの数個のデータとやり取りします。ScoreOutcomeDealtDeckGameStategameRoundupdateScorescoreRounddeal

Answer 3

「StateTを使用する」という推奨事項は少し不透明かもしれないと思いました。そこで、そこからどのように進むかがわかることを期待して、少し専門用語に翻訳しました。ゲームの状態にデッキの状態を含めるのが最善かもしれません。 gameround以下は、StateTの用語で関数を言い換えたものです。前の定義でgameは、deckゲーム状態のフィールドであり、継続的に縮小され、ゲーム全体が含まれます。IOアクションを紹介するのは、それがどのように行われるかを示すためだけです。したがって、ghciでmainを呼び出すと、状態の継承を確認できます。IOアクションをStateT機構に「リフト」して、getsおよびputsと同じレベルに配置します。moseサブケースでは、新しい状態を設定してから、アクションを繰り返すように要求します。これにより、doブロックに完全な再帰操作が含まれるようになります。（ネクタイと空のデッキはすぐにゲームを終了します。）次に、この自己更新の最後の行mainでrunStateTgame関数GameState->IO（GameState、（））;を生成します。次に、ランダムに決定されたデッキを含む特定の開始状態をこれにフィードして、メインビジネスであるIOアクションを取得します。（私はゲームがどのように機能するかについては従いませんが、アイデアを広めるために物事を機械的に動かしていました。）

import Control.Monad.Trans.State
import Control.Monad.Trans
import System.Random
import Data.Map

data Stage = Deal | Tie deriving Show
data GameState = 
  GameState   { stage      :: Stage
              , toDeal     :: Int
              , toBurn     :: Int
              , inPlay     :: [Int]
              , tied       :: [Int]
              , numPlayers :: Int
              , pWins      :: [Int]
              , dWins      :: Int
              , deck      ::  [Int]} deriving Show
              -- deck field is added for the `game` example
type GameRound m a = StateT GameState m a

main = do
   rand <- newStdGen
   let deck = fst $ fisherYates rand $ concatMap (replicate 6) [2 .. 14] 
   let startState = GameState Deal 7 0 [] [] 6 [0 ..100] 0 deck
   runStateT game startState 

game  ::   GameRound IO ()
game = do
  st <- get
  lift $ putStrLn "Playing: " >> print st
  case deck st of 
    []            -> lift $ print "no cards"
    (card:cards)  -> 
      case (toDeal st, stage st) of 
        (0, Deal) ->  do put (first_case_update st card cards) 
                         game -- <-- recursive call with smaller deck
        (_, Deal) ->  do put (second_case_update st card cards)
                         game
        (_,  Tie) ->  do lift $ putStrLn "This is a tie"
                         lift $ print st

 where    -- state updates:
          -- I separate these out hoping this will make the needed sort 
          -- of 'logic' above clearer.
  first_case_update s card cards= 
     s { numPlayers = numPlayers s + 1
       , pWins = [if x < dealerCard  then -1 else  1 |
                    x <-  zipWith (+) (pWins s)  (tail (inPlay s)) ]
       , dWins = if dealerCard == maximum (inPlay s) 
                     then dWins s + 1 
                     else dWins s - 1
       , deck = cards }
            where  dealerCard = head (inPlay s)

  second_case_update s card cards = 
     s { toDeal = toDeal s - 1 
       , toBurn = 0 
       , inPlay = card : inPlay s
       , deck = cards}

--  a StateTified formulation of your gameRound
gameround  ::  Monad m => Int -> GameRound m ()
gameround card = do
  s <- get
  case (toDeal s, stage s) of 
    (0, Deal) -> 
        put $ s { toDeal = numPlayers s + 1
                , pWins = [if x < dealerCard  then -1 else  1 |
                             x <-  zipWith (+) (pWins s)  (tail (inPlay s)) ]
                , dWins = if dealerCard == maximum (inPlay s) 
                              then dWins s + 1 
                              else dWins s - 1}
                     where  dealerCard = head (inPlay s)
    (_, Deal) -> 
        put $ s { toDeal = toDeal s - 1 
                 , toBurn = 0 
                 , inPlay = card : inPlay s}
    (_,  Tie) -> return ()


fisherYatesStep :: RandomGen g => (Map Int a, g) -> (Int, a) -> (Map Int a, g)
fisherYatesStep (m, gen) (i, x) = ((insert j x . insert i (m ! j)) m, gen')
    where
        (j, gen') = randomR (0, i) gen

fisherYates :: RandomGen g => g -> [a] -> ([a], g)
fisherYates gen [] = ([], gen)
fisherYates gen l = toElems $ Prelude.foldl
        fisherYatesStep (initial (head l) gen) (numerate (tail l))
    where
        toElems (x, y) = (elems x, y)
        numerate = zip [1..]
        initial x gen = (singleton 0 x, gen)