Chip shuffling program

chips.hs

import Data.List

data Chip = Red | Blue
    deriving Show

-- Shuffle two stacks of chips into one. The stack listed first will be on the
-- "bottom"
mergeChip :: [Chip] -> [Chip] -> [Chip]
mergeChip xs [] = xs
mergeChip [] ys = ys
mergeChip (x:xs) (y:ys) = x : y : mergeChip xs ys

-- take the stack of chips and split it into two halves
cutChipStack :: [Chip] -> ([Chip], [Chip])
cutChipStack stack =
    let halfStackSize = length stack `div` 2
    in  splitAt halfStackSize stack

-- Cut the stack of chips in two, and redistribute the top half in between the
-- chips in the bottom half
shuffleChip :: [Chip] -> [Chip]
shuffleChip stack = {-trace (show stack) $-}
    let chipHalves = cutChipStack stack
    in  mergeChip (snd chipHalves) (fst chipHalves)

-- Given x red chips and x blue chips, return the number of shuffles it takes
-- to return them to their original order
getNumberOfShuffles :: Int -> Int
getNumberOfShuffles x =
    let redChip = take x $ repeat Red
        blueChip = take x $ repeat Blue
    in  shuffleTillShuffled $ redChip ++ blueChip

shuffleTillShuffled :: [Chip] -> Int
shuffleTillShuffled stack =
    let shuffleTillShuffled' stack x =
            if isShuffled stack && x > 0
                then {-trace (show stack) $-} x
                else shuffleTillShuffled' (shuffleChip stack) (x + 1)
    in  shuffleTillShuffled' stack 0


isShuffled :: [Chip] -> Bool
-- is Shuffled: return True if the bottom half of the deck is all red, and the
-- top half is all blue
isShuffled stack =
    let isHalfShuffled :: [Chip] -> Chip -> Bool
        isHalfShuffled [] _ = True
        isHalfShuffled (Blue:xs) Red = False
        isHalfShuffled (Red:xs) Blue = False
        isHalfShuffled (x:xs) chipColor = isHalfShuffled xs chipColor

        chipHalves = cutChipStack stack
    in
        isHalfShuffled (fst chipHalves) Red &&
            isHalfShuffled (snd chipHalves) Blue