4
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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 []?)

\$\endgroup\$
  • \$\begingroup\$ thanks very much for that; it was really helpful; now I will go and play further ;-) \$\endgroup\$ – Michael May 25 '14 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.