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: randomize the order of a list (Lyndon Maydwell)
2. Re: randomize the order of a list (Felipe Lessa)
3. Re: instances of different kinds (Brandon S Allbery KF8NH)
----------------------------------------------------------------------
Message: 1
Date: Sat, 28 Aug 2010 22:31:21 +0800
From: Lyndon Maydwell <[email protected]>
Subject: Re: [Haskell-beginners] randomize the order of a list
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
If perfectly random data isn't important to you, but you have a vast
amount of data with an expensive lookup cost to randomize, there is a
way to achieve excellent memory / processor usage by using a variant
of TEA (Tiny Encryption Algorithm), that allows you to shuffle an
indexed array based on indexes and bounds, this could be used to
create a lazy list quite easily. I've used the technique in java to
effectively randomize millions of items for very little cost (to
randomize crawling pages in order not to swamp web-servers), but it
should be fairly painless to convert to haskell.
Unfortunately TEA is far from perfect in terms of encryption, but it
fitted my needs perfectly for the task at hand.
I can't find the references to the modified algorithm, but I could dig
up the source if anyone is interested.
On Sat, Aug 28, 2010 at 9:49 PM, A Smith <[email protected]> wrote:
>
>
> I've abeen recommended on good authority(my son, a Cambridge Pure maths
> graduate, and Perl/Haskell expert) , and backed by a Google search that
> Fisher-Yates shuffle is the  one to use, as it produces total unbiased
> results with every combination equally possible.
> As with most things with computers,don't reinvent the eheel, it's almost
> certainly been done before by someone brighter that you, Fisher,Yates. &
> Knuth!
> --
> Andrew Smith B.Sc(Hons),MBA
> Edinburgh,Scotland
>
> On 27 August 2010 21:02, Gaius Hammond <[email protected]> wrote:
>>
>> Hi all,
>>
>>
>>
>> I am trying to randomly reorder a list (e.g. shuffle a deck of cards) . My
>> initial approach is to treat it as an array, generate a list of unique
>> random numbers between 0 and n - 1, then use those numbers as new indexes. I
>> am using a function to generate random numbers in the State monad as
>> follows:
>>
>>
>>
>> randIntâ· Â Int â Â State StdGen Int
>> randInt x = do g â Â get
>> Â Â Â Â Â Â Â (v,g') â Â return $ randomR (0, x) g
>> Â Â Â Â Â Â Â put g'
>> Â Â Â Â Â Â Â return v
>>
>>
>>
>> This is pretty much straight from the documentation. My function for the
>> new indexes is:
>>
>>
>>
>> -- return a list of numbers 0 to x-1 in random order
>> Â Â Â Â Â Â Â Â randIndexâ· Int â StdGen â ([Int], StdGen)
>> randIndex x = runState $ do
>> Â Â let randIndex' acc r
>> Â Â Â Â Â Â | (length acc â¡ x) = acc
>>       | (r `elem` acc) ⨠(r â¡ Â (â1)) = do
>> Â Â Â Â Â Â Â Â r' â randInt (x â 1)
>> Â Â Â Â Â Â Â Â randIndex' acc r'
>> Â Â Â Â Â Â | otherwise = do
>> Â Â Â Â Â Â Â Â r' â randInt (x â 1)
>> Â Â Â Â Â Â Â Â randIndex' r:acc r'
>> Â Â Â Â in
>> Â Â Â Â randIndex' [] (â1)
>>
>>
>>
>> This fails to compile on
>>
>>
>>
>>
>> Â Couldn't match expected type `[a]'
>> Â Â Â Â Â against inferred type `State StdGen b'
>> Â Â In a stmt of a 'do' expression: r' <- randInt (x - 1)
>> Â Â In the expression:
>> Â Â Â Â do { r' <- randInt (x - 1);
>> Â Â Â Â Â Â randIndex' acc r' }
>>
>>
>>
>>
>> I can see what's happening here - it's treating randIndex' as the second
>> argument to randInt instead of invisibly putting the State in there. Or am I
>> going about this completely the wrong way?
>>
>>
>> Thanks,
>>
>>
>>
>> G
>>
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
------------------------------
Message: 2
Date: Sat, 28 Aug 2010 11:38:49 -0300
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] randomize the order of a list
To: A Smith <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sat, Aug 28, 2010 at 10:49 AM, A Smith <[email protected]> wrote:
> I've abeen recommended on good authority(my son, a Cambridge Pure maths
> graduate, and Perl/Haskell expert) , and backed by a Google search that
> Fisher-Yates shuffle is the  one to use, as it produces total unbiased
> results with every combination equally possible.
> As with most things with computers,don't reinvent the eheel, it's almost
> certainly been done before by someone brighter that you, Fisher,Yates. &
> Knuth!
That shuffle requires O(n) time and O(1) space for arrays. Here we're
dealing with lists, so either you copy everything between lists and
array or use another algorithm.
Cheers!
--
Felipe.
------------------------------
Message: 3
Date: Sat, 28 Aug 2010 11:04:40 -0400
From: Brandon S Allbery KF8NH <[email protected]>
Subject: Re: [Haskell-beginners] instances of different kinds
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 8/28/10 06:44 , Greg wrote:
> On Aug 27, 2010, at 8:15 PM, Brandon S Allbery KF8NH wrote:
>> The instance doesn't conform to the class definition; it includes a
>> constraint that the class does not, as the class insists that the type of
>> the result must be independent of the type of the argument, while the
>> instance insists that they must be identical.
>
> I think what you're saying is that not only can an instance do no less than
> the class has guaranteed, it can do no *more*-- meaning the instance can't
> further restrict the return type even if that return type still conforms to
> the class definition. In this case returning a Float breaks the class
> contract because I've gone and said what type of Floating type will be
> returned.
Right. You're not the only one vexed by this; one of the advanced Haskell
tricks is "restricted monads", which are an attempt to deal with the fact
that (for example) a Set is a monad but can't be a Monad because Monad
doesn't have an Ord constraint.
Another way of thinking about this, btw, is that when you use a typeclass
function the only things "visible" about the type are the things defined by
the class; so if the instance wants to do something different, there's no
way to enforce it. Think of it as a mechanical translator that can
faithfully translate specific phrases that it knows about but garbles
anything else.
> The class definition doesn't mean "div2pi can return any type of Floating
> value", it means "div2pi *will* return any type of floating value".
More precisely, it means that when something invokes div2pi, it has the
right to request any type of floating value at its sole discretion. But the
instance says "nuh-uh, you get the same type you feed it, nothing else".
>> class TwoPi a where
>> div2pi :: (Floating b) => a -> b
>
> is essentially impossible to conform to because b is completely untethered
> to anything else in the code and not all "(Floating b)"'s are created equal.
It's possible, but you need to use a polymorphic function to produce it.
Problem is, there is no standard function that does so for Floating. There
are ways to do so for Fractional and for RealFloat (the latter being fairly
horrid in practice) but not for Floating which sits in between them in the
numeric typeclass hierarchy.
(This may be another instance of "the Haskell numeric typeclass hierarchy is
woefully misdesigned". You might want to take a look at
http://www.haskell.org/haskellwiki/Numeric_Prelude. Warning: "well
designed" for Haskellers means "conforms to mathematical theory", so expect
to get lost in a soup of groups, rings, fields, and the like :)
> I think the intent of the functional dependency in the suggestion you
> provided in your second email is essentially to tether b to something.
> Unfortunately if chokes in the second, non-Foo, instance.
Probably; when I write code late at night it's likely to be buggy :)
> I think I've mistakenly been thinking of instances as more like subclasses,
> but that's apparently not quite right (thus the "instance" keyword, I
> suppose).
The OO terminology is somewhat unfortunate; they don't actually follow any
standard OO rules fully, only just enough to cause confusion.
- --
brandon s. allbery [linux,solaris,freebsd,perl] [email protected]
system administrator [openafs,heimdal,too many hats] [email protected]
electrical and computer engineering, carnegie mellon university KF8NH
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.10 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iEYEARECAAYFAkx5JYcACgkQIn7hlCsL25VAswCeKNt7/jYXjcWVDKob9kGPqov7
M60An2dgLpI/rpkng/IKcFYSxkBLdr45
=9DKm
-----END PGP SIGNATURE-----
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 26, Issue 55
*****************************************
