Markov Chain in Haskell

Chain.hs

module Chain where

import Data.Map.Strict(Map,insertWith,empty,member,(!))
import System.Random(randomRIO)

data Chain = Chain (Map String [String]) Int deriving (Show)

build :: [String] -> [String] -> Chain -> Chain
build []  _ chain = chain
build [_] _ chain = chain
build (w:ws) p (Chain c l) = 
  let prefix = if length p < l then p ++ [w] else (tail p) ++ [w]
      m      = (insertWith (++) (unwords prefix) [head ws] c)
      chain  = (Chain m l) in
        build ws prefix chain

generate :: Int -> Chain -> [String] -> IO [String]
generate 0 _ _ = return []
generate n (Chain c l) ws = 
  do
    let k = (unwords ws)
    choice <- if member k c then pick (c ! k) else return []
    let prefix = if length ws < l then ws ++ [choice] else (tail ws) ++ [choice]
    next <- (generate (n - 1) (Chain c l) prefix)
    return (choice:next)

pick :: [a] -> IO a
pick xs = randomRIO (0, length xs - 1) >>= return . (xs !!)
 
main :: IO ()
main = do
  let c = (build ["", "a", "man", "a", "plan", "a", "canal", "panama"] [] (Chain empty 1))
  out <- (generate 10 c [""])
  print out

-- ["a","plan","a","plan","a","man","a","man","a","plan"]

Then, ghc-mod tells us:

/Users/jfuentes/code/oss/swim/markov.hs: line 26, column 11:
  Warning: Use liftM
  Found:
    randomRIO (0, length xs - 1) >>= return . (xs !!)
  Why not:
    Control.Monad.liftM (xs !!) (randomRIO (0, length xs - 1))

So, let's change that:

import Control.Monad (liftM)

pick :: [a] -> IO a
pick xs = liftM (xs !!) (randomRIO (0, length xs - 1))

I made a fork of this to provide some algorithmic and stylistic feedback: see here (along with the accompanying comment).