Adding a duplicate entry randomly into a list in haskell using random monad

Question

There's a new version of this as v2 - Adding a duplicate entry randomly into a list in haskell using random monad

I wrote this trying to set up a Haskell testcase. The aim is to take a list and add a single duplicate from any place in the list to anywhere else in the list.

I'm trying to learn to use the Random Monad properly so the main aims should be clear, simple, idiomatic and pure code. However any recommendations for improvement are appreciated.

-- duplicate-to-list-randmonad.hs by Michael De La Rue 2014 
-- licensed to StackEschange under cc by-sa 3.0 
-- may also be used under AGPLv3 
-- N.B. Trivial copying of code fragments does not normally require any license.
import Data.List
import Control.Monad.Random
main :: IO ()
main = do putStrLn $ "list comparison " ++ prettyList list
 g <- getStdGen
 let shuffled = evalRand (infiniteDuplicateLists list) g
 putStrLn $ "lists after \n" ++ intercalate "\n" ( map prettyList (take 5 shuffled))
 where
 list = ["a","b","c"]
infiniteDuplicateLists genlist = do
 firstelt <- addRandomDuplicate genlist
 restoflist <- infiniteDuplicateLists genlist
 return $ firstelt : restoflist
prettyList :: (Show a) => [a] -> String
prettyList list = " [ " ++ intercalate "," (map show list) ++ " ] "
addRandomDuplicate :: MonadRandom m => [a] -> m [a]
addRandomDuplicate genlist = do 
 frompos <- getRandomR (0 ,length genlist - 1)
 topos <- getRandomR (0 ,length genlist)
 let newlist = listEntryDuplicate (fromIntegral frompos) (fromIntegral topos) genlist 
 return newlist
listEntryDuplicate from to list = 
 start ++ [repeat] ++ end 
 where 
 repeat = list !! from 
 (start, end) = splitAt to list 

(edited to move fixed code to a new question version for neatness)

Answer 1

It's very good that you structured your code into several smaller functions.

Some ideas for improvement:

• Style: It's very useful to stick to a particular style guide and maximum line width. Also I'd recommend to avoid

  name = do exp1
   exp2
  

  in favor of

  name = do
   exp1
   exp2
  

  because if you need to change name, you need to change the whole code block (and your code is indented unnecessarily to the right).

• Do include signatures for all top-level functions. This makes code much more readable and safer (because the compiler helps you typecheck that the function do what you intended). And, it helps to specialize functions properly, for example, with properly typed listEntryDuplicate you won't need those fromIntegral calls.

• Function infiniteDuplicateLists can be expressed using mapM and repeat as

  infiniteDuplicateLists :: (MonadRandom m) => [a] -> m [[a]]
  infiniteDuplicateLists = mapM addRandomDuplicate . repeat
  

  However note that it relies on the fact that MonadRandom allows to traverse infinite lists, which is a bit strong assumption. While it works, I don't think MonadRandom gives any guarantees that it will work in the future. Traversing infinite lists works generally only for some specific monads, see also Why the Haskell sequence function can't be lazy or why recursive monadic functions can't be lazy? Instead I'd recommend sticking to finite lists, like

  duplicateLists :: (MonadRandom m) => Int -> [a] -> m [[a]]
  duplicateLists n = replicateM n . addRandomDuplicate
  

• In addRandomDuplicate you unnecessarily compute the length of the list twice.

The full code could look like

import Data.List
import Control.Monad
import Control.Monad.Random
main :: IO ()
main = do
 putStrLn $ "list comparison " ++ prettyList list
 g <- getStdGen
 let shuffled = evalRand (duplicateLists count list) g
 putStrLn $ "lists after \n"
 ++ intercalate "\n" (map prettyList shuffled)
 where
 count = 5
 list = ["a","b","c"]
duplicateLists :: (MonadRandom m) => Int -> [a] -> m [[a]]
duplicateLists n = replicateM n . addRandomDuplicate
prettyList :: (Show a) => [a] -> String
prettyList list = " [ " ++ intercalate "," (map show list) ++ " ] "
addRandomDuplicate :: MonadRandom m => [a] -> m [a]
addRandomDuplicate genlist = do 
 let l = length genlist
 frompos <- getRandomR (0, l - 1)
 topos <- getRandomR (0, l)
 return $ listEntryDuplicate frompos topos genlist 
listEntryDuplicate :: Int -> Int -> [a] -> [a]
listEntryDuplicate from to list = 
 start ++ [repeat] ++ end 
 where 
 repeat = list !! from 
 (start, end) = splitAt to list 

---

Another room for improvement is replacing lists with a better data structure. For small lists it's not necessary, but if you are going to use longer lists, I'd definitely recommend using Seq, whose operations have only O(log n) time complexity as opposed to O(n) for lists. (See also How fast is Data.Sequence.Seq compared to []?)

• Michael: thanks very much for that; it was really helpful; now I will go and play further ;-)