Random permutations in the standard library.
Harald Korneliussen
As I was exploring haskell by making a little minesweeper game, I ran
in to a little problem when I wanted to populate my board with mines.
I need n random points (x,y), with x in the range 1..breadth and y in
1..height, but the thing is that they have to be distinct. I thought
about various ways of doing it, but the simplest seemed to do a take n
from a random permutation of all the points. But there is no random
permutation method in the standard libraries, as far as I can see.
Does anyone know of a good library which offers random shuffles? I
could roll my own, I suppose, but I hear that functional random
shuffles are tricky to get correct / effective.
Johannes Waldmann
> Does anyone know of a good library which offers random shuffles?
works for me:
permutation :: [a] -> IO [a]
permutation xs = selektion (length xs) xs
selektion :: Int -> [a] -> IO [a]
selektion 0 xs = return []
selektion k xs = do
i <- randomRIO (0, length xs - 1)
let (here, y : there) = splitAt i xs
ys <- selektion (pred k) $ here ++ there
return $ y : ys
Phil Armstrong
Oleg has of course written one:
http://okmij.org/ftp/Haskell/perfect-shuffle.txt
Phil
--
http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt
Mark T.B. Carroll
(snip)
> Does anyone know of a good library which offers random shuffles? I
> could roll my own, I suppose, but I hear that functional random
> shuffles are tricky to get correct / effective.
A probably-suboptimal course I take is that I already have mergesort
code, so I just replace the comparing-elements step with a coin flip.
I've convinced myself this is a good shuffle, but not my friends. (-:
(I'm sure it's not an optimally-efficient shuffle.)
Mark.
--
Functional programming vacancy at http://www.aetion.com/
Phil Armstrong
The only problem with This is that it's O(N^2) in the length of the
list to be shuffled.
Being O(N^2) probably doesn't matter for most uses of this function I
imagine, but the link I gave in my other post does contain Oleg's
O(NlogN) functional algorithm. You pay for the efficiency with extra
complexity of course!
cheers, Phil
Johannes Waldmann
> The only problem with This is that it's O(N^2) in the length of the
> list to be shuffled.
Sure. But that's not a problem with the algorithm itself
but rather with the left-biased list implementation?
I take it that the other, more efficient algorithm
just contains a better implementation of the (abstract)
sequence data type. - Could it be expressed with this:
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Sequence.html
(Rant: It is very unfortunate that using lists in Haskell
is all too easy. That make people (including book authors,
teachers, students) forget about ADTs.
In OO circles, this would be called "primitive obsession".)
Best regards, J. W.
Phil Armstrong
> Phil Armstrong wrote:
>
>> The only problem with This is that it's O(N^2) in the length of the
>> list to be shuffled.
>
> Sure. But that's not a problem with the algorithm itself
> but rather with the left-biased list implementation?
True.
> I take it that the other, more efficient algorithm
> just contains a better implementation of the (abstract)
> sequence data type. - Could it be expressed with this:
> http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Sequence.html
I would think so, yes.
Oleg is using a binary-tree based implementation IIRC. It looks like a
Data.Sequence based implementation ought to do slightly better than
O(NlnN) on average, since splitAt on a Seq is O(ln(min(i,n-i))), but I
haven't worked it out in detail.
> (Rant: It is very unfortunate that using lists in Haskell
> is all too easy. That make people (including book authors,
> teachers, students) forget about ADTs.
> In OO circles, this would be called "primitive obsession".)
Can't disagree with you here; half the trouble is that the list
pattern match syntax makes working with lists so easy...
In general, my rule of thumb is that using O(N) methods on lists
usually implies a need to rethink the data structures -- not that this
is rocket science to anyone reading this group I'd hope.
Harald Korneliussen
> Oleg is using a binary-tree based implementation IIRC. It looks like a
> Data.Sequence based implementation ought to do slightly better than
> O(NlnN) on average, since splitAt on a Seq is O(ln(min(i,n-i))), but I
> haven't worked it out in detail.
I'd looked at Oleg's code before, actually, and I was a bit reluctant
to type it in as I don't completely understand it (why does he roll
his own tree type, for instance? and wasn't there a fixed point
combinator in there somewhere?). I just wondered if there was a
standard function for it which I had missed.
I'm using a variant of Waldmann's suggestion now, and it works OK.
(I'm actually a bit suprised I'm not the only one thinking heretical
thoughts about how perhaps the primacy of lists is a bad habit
inherited from Haskell's typeless ancestors!)
Johannes Waldmann
> (I'm actually a bit suprised I'm not the only one thinking heretical
> thoughts about how perhaps the primacy of lists is a bad habit
> inherited from Haskell's typeless ancestors!)
On abstract vs. concrete data types in Haskell,
look for postings by Robert Will, e.g. this thread
http://www.haskell.org/pipermail/libraries/2004-March/001854.html
This is now mainly of historical interest,
it seems his project (Dessy) has vanished.
Phil Armstrong
> On 19 Feb, 16:13, Phil Armstrong <phil-n...@kantaka.co.uk> wrote:
>> Oleg is using a binary-tree based implementation IIRC. It looks like a
>> Data.Sequence based implementation ought to do slightly better than
>> O(NlnN) on average, since splitAt on a Seq is O(ln(min(i,n-i))), but I
>> haven't worked it out in detail.
>
> I'd looked at Oleg's code before, actually, and I was a bit reluctant
> to type it in as I don't completely understand it (why does he roll
> his own tree type, for instance? and wasn't there a fixed point
> combinator in there somewhere?). I just wondered if there was a
> standard function for it which I had missed.
That's Oleg for you[1]. He uses the fixpoint combinator to build the
binary tree recursively -- it's quite a cute bit of code.
> (I'm actually a bit suprised I'm not the only one thinking heretical
> thoughts about how perhaps the primacy of lists is a bad habit
> inherited from Haskell's typeless ancestors!)
You are not alone!
Phil
[1] Oleg is *exactly* the kind of person who would think 'why write
out the recursion rule explicitly when I can just use the fixpoint
combinator?'. I think the guy dreams in the lambda calculus...