The List, ListState, and Player monads

If we want to use the nice, imperative do blocks of Haskell to produce a lazy list from another lazy list, we have a few options: the List monad, the ListState monad, and the Player monad.

The List monad :

• is essentially [a] -> [b], allowing each differing lengths.
• runs your do block once for the each element in the list, preventing you from keeping any state based on previous elements.
• x <- xs takes an arbitrary input element.
• [a, b, c] squeezes a, b, and c into the list where the input element used to be.

An example that outputs a number that number of times ([0, 1, 2, 3] → [1, 2, 2, 3, 3, 3]) :

nTimes :: Integral a => [a] -> [a]
nTimes ns = do n <- ns
               map (const n) [1..n]

The definition of the List monad :

instance Monad [] where
  return x = [x]
  []     >>= _ = []
  (x:xs) >>= f = f x ++ (xs >>= f)

The ListState monad :

• is essentially [a] -> [b], allowing each differing lengths.
• runs your do block once for the entire list, so that you can easily keep state based on previous elements.
• x <- getNext takes the next input element, advancing the input list.
• putNext x gives the next output element, advancing the output list.

This example shows how state allows you to go beyond the List monad. You can flip pairs of elements ([1, 2, 3, 4] → [2, 1, 4, 3]) :

flipPairs :: [a] -> [a]
flipPairs = processList . forever $ do x <- getNext
                                       y <- getNext
                                       putNext y
                                       putNext x

This example shows how running once for the whole list rather than once per element allows you to go beyond the List monad. You can flip the first pair and drop the rest of the list ([1, 2, 3, 4] → [2, 1]) :

firstPairFlipped :: [a] -> [a]
firstPairFlipped = processList $ do x <- getNext
                                    y <- getNext
                                    putNext y
                                    putNext x

The definition of the ListState monad :

module ListState  (processList, getNext, putNext) where

import Data.Maybe  (isNothing)

newtype ListState a b r = ListState { runListState :: Maybe [a] -> [b] -> (r, Maybe [a], [b]) }

-- |Process this list and return the new list.
processList :: ListState a b r -> [a] -> [b]
processList f xs = let (_, _, ys) = runListState f (Just xs) []
                   in ys

-- Make a custom welding of state and reverse state (http://lukepalmer.wordpress.com/2008/08/10/mindfuck-the-reverse-state-monad/) monads.
instance Monad (ListState a b) where
  return x = ListState $ \fwd rev -> (x, fwd, rev)
  m >>= f  = ListState g
    where
      g xs ys = let (a, xs', ys'') = runListState m xs ys'
                    (b, xs'', ys') = if isNothing xs'
                        then (undefined, xs', ys)
                        else runListState (f a) xs' ys
                in (b, xs'', ys'')

getNext :: ListState a b a
getNext = ListState f
  where
    f (Just [])     ys = (undefined, Nothing, ys)
    f (Just (x:xs)) ys = (x,         Just xs, ys)

putNext :: b -> ListState a b ()
putNext y = ListState $ \xs ys -> ((), xs, y:ys)

The Player monad :

• is essentially [a] -> [[b]], where the [a] is the same length as the [[b]].
• runs your do block once for the entire list, so that you can easily keep state based on previous elements.
• x <- getState repeatedly takes the current input element without advancing.
• move x adds an item to the current output element without advancing.
• endTurn advances the input and output lists.

If you’re writing the code for a bot that plays a game, the Player monad is quite nice. The monad will take a lazy list of each turn’s starting information and immediately give you a lazy list of each turn’s moves for that bot. The bot sees this turn’s starting information, gives move after move, tells when it’s finished with the turn, and can keep between-turn state.

module Player  (playWith, getState, move, endTurn) where

import Data.Maybe  (isNothing)

newtype Player a b r = Player { runPlayer :: (a, Maybe [a]) -> ([b], [[b]]) -> (r, (a, Maybe [a]), ([b], [[b]])) }

-- |Play the game with this player and return a list of each turn's moves.
playWith :: Player a b r -> [a] -> [b]
playWith _ []     = []
playWith f (x:xs) = let (_, _, (_, ys)) = runPlayer f (x, Just xs) ([], [])
                in ys

-- Make a custom welding of state and reverse state (http://lukepalmer.wordpress.com/2008/08/10/mindfuck-the-reverse-state-monad/) monads.
instance Monad (Player a b) where
  return x = Player $ \fwd rev -> (x, fwd, rev)
  m >>= f  = Player g
    where
      g xs ys = let (a, xs', ys'') = runPlayer m xs ys'
                    (b, xs'', ys') = if isNothing . snd $ xs'
                        then (undefined, xs', ys)
                        else runPlayer (f a) xs' ys
                in (b, xs'', ys'')

getState :: Player a b a
getState = Player $ \xxs@(x, _) yys = (x, xxs, yys)

move :: b -> Player a b ()
move z = Player $ \xxs (y, ys) -> ((), xxs, (z:y, ys))

endTurn :: Player a b ()
endTurn = Player g
  where
    g (_, Just [])     (y, ys) = ((), (undefined, Nothing), (undefined, y:ys))
    g (_, Just (x:xs)) (y, ys) = ((), (x,         Just xs), ([],        y:ys))