Newbie - emulating Pythons random.shuffle

[Aidan]

Hi everyone,

I'm very new to haskell and functional programing in general... I've been
experimenting with a few tutorials to get a feel for haskell, and it's
mostly been an enlightening experience.

I am having some trouble understanding the System.Random module.
Essentially, I'm trying to find a way to implement an equivalent of pythons
random.shuffle function in haskell - but in true newbie fashion, all I can
manage to produce is type errors.

Here's the code I have so far:

{- Begin -}
import System.Random

random_element l = do
x <- randomRIO(1,(length l))
let ele = l !! (x-1)
return ele

shuffle [] = []
shuffle l = do
e <- random_element l
rest <- shuffle [x | x <- l, not (x==e)]
return (e : rest)
{- End -}

To my surprise, I have found that if I redefine shuffle as:

shuffle l = random_element l : shuffle [x | x <- l, not (x==(head l))]

that it will load into my interpreter - however I'm not able to do much of
anything with the result as the list is composed of IO types.

Can anyone give me any clues as to how I might make the first implementation
stop generating errors, or maybe how I might take the value of the second
implementation and produce a list of non-IO types?

Thanks in advance.

[Joachim Durchholz]

Aidan schrieb:

> I am having some trouble understanding the System.Random module.
> Essentially, I'm trying to find a way to implement an equivalent of pythons
> random.shuffle function in haskell - but in true newbie fashion, all I can
> manage to produce is type errors.

That's a commonly-visited pitfall.
Basically, you can't have a function that returns different results
every time it's called and still have equational reasoning (because then
equations like 2*rand = rand + rand won't hold anymore).

To phrase a random number generator as a pure function, it must take the
generator state as an input parameter, and return the new state and the
random number.

You'd have to pass the state around any function that uses random
numbers, which can be a pain. So in most cases it is hidden inside a monad.
State would be one possibility to do that.
IO is another, and it makes somewhat more sense because there are
random-number sources that are fed from external hardware (such as
/dev/random on Linux systems, or hardware devices that generate random
numbers).

> how I might take the value of the second
> implementation and produce a list of non-IO types?

You can't do that.
Well, there's always UnsafePerformIO, but you shouldn't use it because
it is, well, unsafe. E.g. it may interact in unexpected ways with
compiler optimizations unless you know what the compiler might or might
not do.

(Just explaining the situation. I'll leave concrete step-by-step advice
to people who're more familiar with this kind of situation.)

Regards,
Jo

[chry...@gmail.com]

The compiler/interpreter seems to be inferring conflicting types for
shuffle. The first definition of shuffle ("shuffle [] = []") implies
"[a] -> [a]". However, the second ("shuffle l" = do ...) implies "[a]
-> IO [a]".

First, decide on which of the two implied types you want your
definition of "shuffle" to follow. Joachim's post hints at the
correct answer to this one. Next, fix the definition with the
different type.

Good luck! ;)

[Kalman Noel]

Aidan:

> I am having some trouble understanding the System.Random module.
> Essentially, I'm trying to find a way to implement an equivalent of pythons
> random.shuffle function in haskell - but in true newbie fashion, all I can
> manage to produce is type errors.

You program will typecheck if you change this

> shuffle [] = []

into this

< shuffle [] = return []

However, here is an alternative implementation. Note how

* I pass random generators around, so I do not have to use IO
everywhere. As you can observe, my auxiliary function “shuff” does
not incorporate IO, so there is no need for using “return” there! By
the way, I suppose the concept of random “generators” only exists in
System.Random so we can write non-IO functions like “shuff”.

* I split the list into two at a random position (which makes my program
behave quite different from yours; ask if you do not understand why).

* I keep track of the length of the list in an extra parameter of type
Int, so I do not have to use length in every recursion step. Always
using length, as you do, gives very bad performance on long lists.

module Shuffle where

import System.Random

shuffle :: [a] -> IO [a]
shuffle xs = newStdGen >>= return . shuff (length xs) xs

shuff :: (RandomGen gen) => Int -> [a] -> gen -> [a]
shuff 0 _ _ = []
shuff n xs gen = let (i,gen') = randomR (0,n-1) gen
(as,(b:bs)) = splitAt i xs
in b : (shuff (n-1) (as ++ bs) gen)

Kalman