Extract a random element from a list (and remove it), learning monads

1
votes

Im learning monads in Haskell with the haskell wikibook and my own newbie experiments

As my first step, i've copypasted the parts of the book related to monads to my own PDF using the great HaTeX library (by Daniel Díaz) while lightly reading such hard text (hard because of its content).

Below is my first attempt to practice what i learned: 7 versions of a function that takes a list and returns a random element from that list

Now my main question is, should i be using monad Transformers for the "remove the element" part? i've read they are used to mix monads, and i know i will be using the State monad and the List monad

Other than that, any comments on my code will be gratefully recieved (the style ones the most, as monads are about writing with style? :P)

import System.Random
import Control.Monad.Trans.State
import Control.Monad

------------------------ PRIMER INTENTO DE RANDOMNESS ------------------------

extractR' :: [a] -> a
extractR' xs = xs !! randomPos
  where
    n         = length xs
    randomPos = fst pareja
    pareja    = randomR (0,n-1) stdGen
    stdGen    = mkStdGen 0


-- extractR' siempre devuelve la misma cosa, al llamarla sobre la misma
-- lista   (por tanto NO SIRVE, NO ES ALEATORIO)
-- EJ:
-- *Deck> extractR' [1..100]
-- 46
-- (0.00 secs, 0 bytes)
-- *Deck> extractR' [1..100]
-- 46
-- (0.02 secs, 0 bytes)
-- *Deck> extractR' [1..100]
-- 46
-- (0.00 secs, 0 bytes)

------------------------ SEGUNDO INTENTO DE RANDOMNESS ------------------------

stdGen = mkStdGen 0


extractR'' :: StdGen -> [a] -> (a, StdGen)
extractR'' gen xs = (xs !! randPos , newGen)
  where 
    n = length xs
    (randPos, newGen) = randomR (0,n-1) gen


-- esta version permite arrastrar el RNGenerator, pero es incomodisima de usar:

-- *Deck> extractR'' stdGen [1..100]
-- (46,40014 40692)
-- (0.00 secs, 0 bytes)
-- *Deck> let x = snd (extractR'' stdGen [1..100]) in extractR'' x [1..100]
-- (56,1601120196 1655838864)
-- (0.00 secs, 0 bytes)

------------------------ TERCER INTENTO DE RANDOMNESS -------------------------

extractR''' :: [a] -> State StdGen a
extractR''' xs = state sol
  where
    n   = length xs
    sol = \s -> ( xs !! (randPos s) ,  newGen s)
    randPos st = fst $ randomR (0,n-1) st
    newGen st  = snd $ randomR (0,n-1) st

-- extractR''' xs = 
--   state ( \s -> 
--     ( xs !! (fst $ randomR (0, (length xs)-1) s ) 
--     , 
--     snd $ randomR (0, (length xs)-1) s ) )

-- pruebas en pantalla:

-- *Main> runState (extractR ['a'..'z']) (mkStdGen 0)
-- ('d',40014 40692)
-- (0.00 secs, 0 bytes)
-- *Main> runState (extractR ['a'..'z']) (mkStdGen 0)
-- ('d',40014 40692)
-- (0.00 secs, 0 bytes)
-- *Main> runState (extractR ['a'..'z']) (mkStdGen 7854)
-- ('n',314309970 40692)
-- (0.00 secs, 0 bytes)

-- works well, but the code is bad (non-monadic)
-- but we are in the State monad, so the following works:

extractR2 :: [a] -> State StdGen (a,a)
extractR2 xs = liftM2 (,) (extractR''' xs) (extractR''' xs)

------------------------ CUARTO INTENTO DE RANDOMNESS -------------------------

extractR'''' :: [a] -> State StdGen a
extractR'''' xs = pr1 >>= f
  where
    n   = length xs
    pr1 = state $ randomR (0,n-1)
    f   = \k -> state ( \s -> (xs !! k , s) )


-- monadic code, se actualiza 1 vez el StdGen

------------------------ QUINTO INTENTO DE RANDOMNESS -------------------------

extractR_ :: [a] -> State StdGen a
extractR_ xs = pr1 >>= f
  where
    n   = length xs
    pr1 = state $ randomR (0,n-1)
    f   = \k -> state ( \s -> (xs !! k , g s) )  
    g   = \stdG -> snd $ next stdG


-- monadic code, se actualiza 2 veces el StdGen

------------------------ SEXTO INTENTO DE RANDOMNESS --------------------------

extractR_' :: [a] -> State StdGen a
extractR_' xs = 
  do
    generator <- get              -- get = state $ \st -> (st,st)
    let n = length xs
    let (k, newGen) = randomR (0,n-1) generator
    put newGen
    return (xs!!k)


-- traduccion del codigo:
extractR_'' xs = 
  get >>= 
    \generator -> let n=length xs in 
      ( let (k, newGen)=randomR (0,n-1) generator in 
        (put newGen >> return (xs!!k) ) )


-- *Main> :t extractR_''
-- extractR_'' :: (RandomGen t, Monad m) => [b] -> StateT t m b
-- *Main> :t extractR_
-- extractR_ :: [a] -> State StdGen a



-- ======o     o======
--    ___________
--   |___________|    -------------------------------------------------------------------------------
--    |\  /\  /\|     ------------------------        VERSION FINAL          ------------------------
--    |_\/__\/__|     -------------------------------------------------------------------------------
--   |___________| 



 --    ??????????????????? (dont know which to choose)

By the way im doing this to finish my Maths degree, and after that i'll be looking to earn my livings through Haskell :D (am i asking for a miracle?)

2
haskellrandommonad-transformersstate-monad
All except the first version are sensible (that one is a misuse of PRNG - nothing to do with Haskell or Monads) - what you "should" be doing is what is most useful to solve your particular problem, there is no one way. – user2407038

2 Answers

2
votes

should i be using monad Transformers for the "remove the element" part? i've read they are used to mix monads, and i know i will be using the State monad and the List monad

But you are not using the list monad! You are just using lists. To say you are using the list monad would mean you are using (>>=) or return specialized to lists (or similar Monad-polymorphic functions specialized to lists), which you are not doing. So I think it makes perfect sense to use State, and not use any transformers.

Other than that, any comments on my code will be gratefully recieved (the style ones the most, as monads are about writing with style? :P)

I like your fourth attempt the best, which as a reminder was this one:

extractR'''' :: [a] -> State StdGen a
extractR'''' xs = pr1 >>= f
  where
    n   = length xs
    pr1 = state $ randomR (0,n-1)
    f   = \k -> state ( \s -> (xs !! k , s) )

The only tweak I would make is that I find your f a bit too complicated. Since you are not modifying the state at all, you need not use State-specific functions; one could write

    f   = \k -> return (xs !! k)

instead. And then one can apply a monad law, namely:

m >>= (\x -> return (f x)) = fmap f m

The final implementation I would want to see is thus:

extractR :: [a] -> State StdGen a
extractR xs = fmap (xs!!) pr1
  where
    n   = length xs
    pr1 = state $ randomR (0,n-1)

(One can of course spell fmap in several other ways, that in this case differ primarily in aesthetics, like (<$>), liftA, or liftM.)

1
votes

You may want to take a look to the MonadRandom package.

import Control.Monad.Random

extractR :: MonadRandom m => [a] -> m a
extractR xs = (xs !!) <$> getRandomR (0, length xs - 1)

The MonadRandom constraint is satisfied by IO and RandT g m, which is essentially a StateT StdGen-based monad, usable in pure code.

Also, the library defines uniform, which is equivalent to your extractR (albeit its implementation is rather complex).