Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Re: permuting a list (Felipe Lessa)
2. Re: permuting a list (Heinrich Apfelmus)
3. Re: Re: permuting a list (Daniel Fischer)
4. Re: permuting a list (Heinrich Apfelmus)
5. Re: Re: permuting a list (Daniel Fischer)
6. Re: permuting a list (Jon Fairbairn)
7. Re: [Haskell-cafe] Re: permuting a list (Alberto Ruiz)
8. Re: [Haskell-cafe] Re: permuting a list (Felipe Lessa)
9. Re: [Haskell-cafe] Re: permuting a list (Paul Johnson)
10. Re: permuting a list (Henning Thielemann)
----------------------------------------------------------------------
Message: 1
Date: Fri, 13 Feb 2009 08:03:27 -0200
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] Re: permuting a list
To: Daniel Fischer <[email protected]>
Cc: [email protected], [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Fri, Feb 13, 2009 at 7:56 AM, Daniel Fischer
<[email protected]> wrote:
> You need the forall a to bring the type variable a into scope. Without it, the
> a in
>
> arr0 <- (newListArray (0, n) xs :: IO (IOArray Int a))
>
> would be implicitly universally quantified, too, and you would say that all
> elements of xs had type (forall b. b), which means all are _|_.
> Having brought the a from permute's type signature into scope, the a in the
> above line is the *same* a as the one in permute's type signature.
Whoops, sorry about that, didn't see that ScopedTypeVariables was active. :)
--
Felipe.
------------------------------
Message: 2
Date: Fri, 13 Feb 2009 11:25:04 +0100
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: permuting a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-15
Jan Snajder wrote:
> Brent Yorgey wrote:
>
>> The problem seems to be that
>> Haskell has no way to know what sort of array you want to use. I was
>> able to get the code to work, but it's sort of sneaky:
>>
>>> {-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-}
>>>
>>> import Data.Array.MArray
>>> import Data.Array.IO
>>> import Control.Monad
>>> import System.Random
>>> permute :: forall a. (MArray IOArray a IO) => [a] -> IO [a]
>>> permute xs = do
>>> let n = length xs - 1
>>> arr0 <- (newListArray (0, n) xs :: IO (IOArray Int a))
>>> arr <- foldM swap arr0 [n..1]
>>> getElems arr
>>> where swap arr n = do
>>> x <- readArray arr n
>>> r <- randomRIO (0, n)
>>> y <- readArray arr r
>>> writeArray arr n y
>>> writeArray arr r x
>>> return arr
The type class constraint is not needed because IOArray can hold any
element type anyway. (It's unboxed arrays that only work for certain
element types). Thus, you can write FlexibleConstraints extension and
simply write
permute :: forall a. [a] -> IO [a]
instead.
Also, I think that specifying the type of arr0 as
(arr0 :: IOArray Int a) <- newListArray (0, n) xs
should work as well.
--
http://apfelmus.nfshost.com
------------------------------
Message: 3
Date: Fri, 13 Feb 2009 11:30:34 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: permuting a list
To: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-15"
Am Freitag, 13. Februar 2009 10:23 schrieb Jan Snajder:
> Brent Yorgey wrote:
> > It seems everyone has just been reading the first few words of Jan's
> > email and not the actual content. Jan is clearly trying to write a
> > *random list shuffling* function, not a function to generate
> > permutations. Let's try to be helpful, people...
> > </rant>
>
> Thanks Brant, I forgot to mention explicitly that I need a random
> permutation.
>
> > Jan, this is tricky. The type of permute is indeed (MArray a1 a IO)
> > => [a] -> IO [a], but this is fine, it just means that there has to be
> > some sort of mutable array which can store the things you are trying
> > to shuffle.
> > This is not the problem. The problem seems to be that
> > Haskell has no way to know what sort of array you want to use. I was
> >
> > able to get the code to work, but it's sort of sneaky:
> > > {-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-}
>
> I guess by 'sneaky' you mean this solution is GHC-specific?
It can be made a little less sneaky, you don't need FlexibleContexts, because
the type signature
permute :: forall a. [a] -> IO [a]
works, too (code otherwise unchanged).
But that still doesn't work with hugs :(
However, if you bring the array-creation to top level, it doesn't need any
module-specific language extensions:
module Perms where
import Data.Array.MArray
import Data.Array.IO
import Control.Monad
import System.Random
-- call with toArray (length xs - 1) xs
toArray :: Int -> [a] -> IO (IOArray Int a)
toArray n xs = newListArray (0,n) xs
permute :: [a] -> IO [a]
permute xs = do
let n = length xs - 1
arr0 <- toArray n xs
arr <- foldM swap arr0 [n, n-1 .. 1]
getElems arr
where
swap arr n = do
x <- readArray arr n
r <- randomRIO (0, n)
y <- readArray arr r
writeArray arr n y
writeArray arr r x
return arr
and it works in hugs, too (needs the -98 flag, because one of the imports
needs ST.hs, which has foralled type signatures).
Cheers,
Daniel
------------------------------
Message: 4
Date: Sat, 14 Feb 2009 16:37:44 +0100
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: permuting a list
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Daniel Fischer wrote:
> Thomas Davie wrote:
>> Brent Yorgey wrote:
>>> Andrew Wagner wrote:
>>>> Brent Yorgey wrote
>>>>> <rant> It seems everyone has just been reading the first few
>>>>> words of Jan's email and not the actual content. Jan is
>>>>> clearly trying to write a *random list shuffling* function,
>>>>> not a function to generate permutations. Let's try to be
>>>>> helpful, people... </rant>
>>>>
>>>> Agreed, I've been quite confused by this thread. In the spirit
>>>> of laziness, though, wouldn't it seem like the "right" method
>>>> is to generate all the permutations lazily, and then choose a
>>>> random element of that list?
>>>
>>> Well, it sounds nice, but it's pretty inefficient. And by
>>> "pretty inefficient" I mean "horrendously, terribly inefficient"
>>> -- there are n! permutations of a list of length n, so this would
>>> take time O(n!) as opposed to O(n); O(n!) is even worse than
>>> O(2^n).
>>
>> Would it? We're talking about lazyness here... it's not gonna
>> compute one it doesn't need, and if you're somewhat cleverer with
>> your permute function than I was, I'm sure you can do as little
>> computation as the imperative version.
>
> But to find the k-th permutation, it would have to traverse k cons
> cells containing thunks, wouldn't it?
>
> Well, the following is O(n^2), not quite O(n), but at least it's not
> "horrendously, terribly inefficient".
That of course begs the question whether there is a faster but purely
functional algorithm for generating random permutations without indexes
and arrays?
The answer is a resounding "yes" and the main idea is that shuffling a
list is *essentially the same* as sorting a list; the minor difference
being that the former chooses a permutation at random while the latter
chooses a very particular permutation, namely the one that sorts the input.
For the full exposition, see
http://apfelmus.nfshost.com/random-permutations.html
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 5
Date: Sat, 14 Feb 2009 17:46:52 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: permuting a list
To: Heinrich Apfelmus <[email protected]>,
[email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Samstag, 14. Februar 2009 16:37 schrieb Heinrich Apfelmus:
>
> That of course begs the question whether there is a faster but purely
No, it didn't beg any question. (Sorry for being a humourless pedant here)
> functional algorithm for generating random permutations without indexes
> and arrays?
>
> The answer is a resounding "yes" and the main idea is that shuffling a
> list is *essentially the same* as sorting a list; the minor difference
> being that the former chooses a permutation at random while the latter
> chooses a very particular permutation, namely the one that sorts the input.
>
> For the full exposition, see
>
> http://apfelmus.nfshost.com/random-permutations.html
Excellent work, thanks.
>
>
> Regards,
> apfelmus
Cheers,
Daniel
------------------------------
Message: 6
Date: Sun, 15 Feb 2009 11:10:28 +0000
From: Jon Fairbairn <[email protected]>
Subject: [Haskell-beginners] Re: permuting a list
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Heinrich Apfelmus <[email protected]> writes:
> The answer is a resounding "yes" and the main idea is that shuffling a
> list is *essentially the same* as sorting a list; the minor difference
> being that the former chooses a permutation at random while the latter
> chooses a very particular permutation, namely the one that sorts the input.
>
> For the full exposition, see
>
> http://apfelmus.nfshost.com/random-permutations.html
I haven't been following the thread, but my initial reaction
would have been something like use System.Random.randoms to
get a list rs and then do (roughly)
randomPerm = map snd . sortBy (compare `on` fst) . zip rs
How bad is that? I mean, how unfair does it get?
--
Jón Fairbairn [email protected]
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html (updated 2009-01-31)
------------------------------
Message: 7
Date: Sun, 15 Feb 2009 13:22:51 +0100
From: Alberto Ruiz <[email protected]>
Subject: [Haskell-beginners] Re: [Haskell-cafe] Re: permuting a list
To: Heinrich Apfelmus <[email protected]>
Cc: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
Heinrich Apfelmus wrote:
> Jon Fairbairn wrote:
>> Heinrich Apfelmus writes:
>>
>>> The answer is a resounding "yes" and the main idea is that shuffling a
>>> list is *essentially the same* as sorting a list; the minor difference
>>> being that the former chooses a permutation at random while the latter
>>> chooses a very particular permutation, namely the one that sorts the input.
>>>
>>> For the full exposition, see
>>>
>>> http://apfelmus.nfshost.com/random-permutations.html
>> I haven't been following the thread, but my initial reaction
>> would have been something like use System.Random.randoms to
>> get a list rs and then do (roughly)
>>
>> randomPerm = map snd . sortBy (compare `on` fst) . zip rs
>>
>> How bad is that? I mean, how unfair does it get?
>
> It's fair, but may duplicate elements, i.e. it doesn't necessarily
> create a permutation. For example, rs could be something like
>
> rs = [5,3,3,3,2,4]
>
How about using random doubles?
randomPerm xs = fmap (map snd . sort . flip zip xs) rs
where rs = fmap (randoms . mkStdGen) randomIO :: IO [Double]
------------------------------
Message: 8
Date: Sun, 15 Feb 2009 10:23:57 -0200
From: Felipe Lessa <[email protected]>
Subject: [Haskell-beginners] Re: [Haskell-cafe] Re: permuting a list
To: Heinrich Apfelmus <[email protected]>
Cc: [email protected], [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sun, Feb 15, 2009 at 9:47 AM, Heinrich Apfelmus
<[email protected]> wrote:
> It's fair, but may duplicate elements, i.e. it doesn't necessarily
> create a permutation. For example, rs could be something like
>
> rs = [5,3,3,3,2,4]
>
But our sort doesn't discard values when the keys are the same. For example,
[1,2,3,4] == map snd . sortBy (compare `on` fst) . zip (repeat 1) $ [1,2,3,4]
Nothing gets duplicated. Or did I miss something?
--
Felipe.
------------------------------
Message: 9
Date: Sun, 15 Feb 2009 15:05:21 +0000
From: Paul Johnson <[email protected]>
Subject: [Haskell-beginners] Re: [Haskell-cafe] Re: permuting a list
To: Alberto Ruiz <[email protected]>
Cc: Heinrich Apfelmus <[email protected]>,
[email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
See http://okmij.org/ftp/Haskell/perfect-shuffle.txt
Paul.
------------------------------
Message: 10
Date: Sun, 15 Feb 2009 01:04:32 +0100 (CET)
From: Henning Thielemann <[email protected]>
Subject: [Haskell-beginners] Re: permuting a list
To: Daniel Fischer <[email protected]>
Cc: Heinrich Apfelmus <[email protected]>,
[email protected], [email protected]
Message-ID:
<alpine.deb.2.00.0902150103030.32...@anubis.informatik.uni-halle.de>
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
On Sat, 14 Feb 2009, Daniel Fischer wrote:
> Am Samstag, 14. Februar 2009 16:37 schrieb Heinrich Apfelmus:
>>
>> For the full exposition, see
>>
>> http://apfelmus.nfshost.com/random-permutations.html
>
> Excellent work, thanks.
Interesting read.
Btw. a further development of the PFP library is also on Hackage:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/probability
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 12
****************************************
