title: Haskell: Shuffling deck
body: <p>I'm working on a lab in which we work with randomness and monads.</p>
  
  <p>The parts of the lab are:</p>
  
  <ol>
  <li>write a function randR that generates a random numbers within a given range</li>
  <li>write a function rollTwoDice that simulates rolling two dice</li>
  <li>write a function removeCard which randomly removes a card from a list of PlayingCards</li>
  <li>write a function shuffleDeck which takes the removed card, puts it in front of the deck, then repeats itself until the deck has been completely shuffled.</li>
  </ol>
  
  <p>I have done 1, 2, and 3, but I'm having trouble with 4.</p>
  
  <p>Here's the given code: </p>
  
  <p>RandState.hs</p>
  
  <pre><code>module RandState where
  import UCState
  import System.Random
  
  -- In order to generate pseudo-random numbers, need to pass around generator
  --  state in State monad
  type RandState a = State StdGen a
  
  -- runRandom runs a RandState monad, given an initial random number generator
  runRandom :: RandState a -&gt; StdGen -&gt; a
  runRandom (State f) s = res
      where (res, state) = f s
  
  -- rand is a helper function that generates a random instance of any
  --  type in the Random class, using the RandState monad.
  rand :: Random a =&gt; RandState a
  rand = do
      gen &lt;- get
      let (x, gen') = random gen
      put gen'
      return x
  </code></pre>
  
  <p>UCState.hs</p>
  
  <pre><code>{- 
   - Simplified implementation of the State monad.  The real implementation
   - is in the Control.Monad.State module: using that is recommended for real 
   - programs.
   -}
  module UCState where
  
  data State s a = State { runState :: s -&gt; (a, s) }
  
  instance Monad (State s)
      where
          {-
           - return lifts a function x up into the state monad, turning it into
           -  a state function that just passes through the state it receives
           -}
          return x = State ( \s -&gt; (x, s) )
  
          {- 
           - The &gt;&gt;= combinator combines two functions p and f, and 
           -  gives back a new function (Note: p is originally wrapped in the 
           -  State monad)
           -
           - p: a function that takes the initial state (from right at the start
           - of the monad chain), and gives back a new state and value, 
           - corresponding to the result of the chain up until this &gt;&gt;=
           - f: a function representing the rest of the chain of &gt;&gt;='s
           -}
          (State p) &gt;&gt;= f = State ( \initState -&gt; 
                                    let (res, newState) = p initState
                                        (State g) = f res
                                    in g newState )
  
  -- Get the state
  get :: State s s  
  get = State ( \s -&gt; (s, s) )
  
  -- Update the state
  put :: s -&gt; State s ()
  put s = State ( \_ -&gt; ((), s))
  </code></pre>
  
  <p>Here's my code, which I just wrote inside RandState.hs since I couldn't figure out how to import it (help with importing would be nice as well, although not what I'm most concerned about at this point):</p>
  
  <pre><code>randR :: Random a =&gt; (a, a) -&gt; RandState a
  randR (lo, hi) = do
      gen &lt;- get
      let (x, gen') = randomR (lo, hi) gen
      put gen'
      return x
  
  testRandR1 :: IO Bool
  testRandR1 = do
      gen &lt;- newStdGen
      let genR = runRandom (randR (1,5)) gen :: Int
      return (genR &lt;=5 &amp;&amp; genR &gt;=1)
  
  testRandR2 :: IO Bool
  testRandR2 = do
      gen &lt;- newStdGen
      let genR = runRandom (randR (10.0, 11.5)) gen :: Double
      return (genR &lt;= 11.5 &amp;&amp; genR &gt;= 10.0)
  
  rollTwoDice :: RandState Int
  rollTwoDice = do
      gen &lt;- get
      let (a, gen') = randomR (1, 6) gen :: (Int, StdGen)
      put gen'
      let (b, gen'') = randomR (1, 6) gen' :: (Int, StdGen)
      put gen''
      return $ a + b
  
  testRollTwoDice :: IO Bool
  testRollTwoDice = do
      gen &lt;- newStdGen
      let genR = runRandom (rollTwoDice) gen
      return (genR &lt;= 12 &amp;&amp; genR &gt;= 2)
  
  -- Data types to represent playing cards
  data CardValue = King | Queen | Jack | NumberCard Int
      deriving (Show, Eq)
  data CardSuit = Hearts | Diamonds | Spades | Clubs
      deriving (Show, Eq)
  data PlayingCard = PlayingCard CardSuit CardValue
      deriving (Show, Eq)
  
  {-
   - fullCardDeck will be a deck of cards, 52 in total, with a King, a Queen, 
   - a Jack and NumberCards from 1 to 10 for each suit.
   -}
  -- fullCardDeck and its definition were given in the lab
  fullCardDeck :: [PlayingCard]
  fullCardDeck = [ PlayingCard s v | s &lt;- allsuits, v &lt;- allvals ] where
          allvals = King : Queen : Jack : [ NumberCard i | i &lt;- [1..10] ]
          allsuits = [Hearts, Diamonds, Spades, Clubs]
  
  removeCard :: [a] -&gt; RandState [a]
  removeCard deck = do
      gen &lt;- get
      let n = runRandom (randR(1, length (deck))) gen :: Int
      let (xs, ys) = splitAt (n-1) deck
      return $ head ys : xs ++ tail ys
  
  shuffleDeck deck = do
      gen &lt;- get
      let f deck = head $ runRandom (removeCard deck) gen
      return $ take (length(deck)) (iterate f deck)
  </code></pre>
  
  <p>shuffleDeck doesn't work. The error:</p>
  
  <pre><code>RandState.hs:88:31:
      Occurs check: cannot construct the infinite type: a0 = [a0]
      Expected type: [a0] -&gt; [a0]
        Actual type: [a0] -&gt; a0
      In the first argument of `iterate', namely `f'
      In the second argument of `take', namely `(iterate f deck)'
      In the second argument of `($)', namely `take 52 (iterate f deck)'
  </code></pre>
  
  <p>I guess the issue is that iterate takes a value, applies a function to this value, applies the function to the result, and so on, returning an infinite list of results. I'm handing iterate a function that takes a list, and returns a card, so the result cannot be passed to the next iteration. What would be a better way to approach this problem (4)? I'm also worried that my removeCard function is a little janky since it just puts the "removed" card in front, which I did to make shuffleDeck easier to write. If necessary, what would be a better way to approach this problem (3)?</p>
  
  <p>Thanks,
  Jeff</p>