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 (Gaius Hammond)
2. randomize the order of a list (Gabriel Scherer)
3. simplifying algebraic expression (Alexander.Vladislav.Popov )
4. Re: simplifying algebraic expression (Alexander.Vladislav.Popov )
5. Re: simplifying algebraic expression (J?rgen Doser)
----------------------------------------------------------------------
Message: 1
Date: Tue, 31 Aug 2010 22:03:57 +0100
From: Gaius Hammond <[email protected]>
Subject: Re: [Haskell-beginners] randomize the order of a list
To: Gabriel Scherer <[email protected]>
Cc: [email protected], [email protected],
[email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
Thanks everyone! As always with Haskell, it's surprising how easy it
is when you know how :-)
G
On 30 Aug 2010, at 10:14, Gabriel Scherer wrote:
> Gaius Hammond wrote:
>> 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.
>
> Felipe Lessa wrote:
>> Note: you could use random-shuffle package [1].
>>
>> [1] http://hackage.haskell.org/package/random-shuffle
>
> Heinrich Apfelmus wrote:
>> For another approach, see also
>>
>> http://apfelmus.nfshost.com/articles/random-permutations.html
>
> Thanks for the link apfelmus, it's fairly interesting. The key to
> making it work is the weighting of lists during merging based on their
> lengths. I wonder if other sort algorithm can be adapted in such a
> way, while preserving uniformity. Quicksort for example : is it enough
> to choose the result position of the pivot randomly, and then placing
> elements on either side with a probability of 1/2 ?
>
> There is another sort-based approach that is probably less elegant,
> but simpler in the sense that you don't have to rewrite your sorting
> routines : pick random "weights" for each of your elements, and sort
> the list based on the weights. This approach has been studied and
> criticized by [Oleg], whose analysis is the base of the random-shuffle
> package. Oleg rightly points out that this method does not achieve
> uniformity in general. What he failed to notice is that there is a
> simple workaround to regain uniformity with minimal changes.
>
> [Oleg] http://okmij.org/ftp/Haskell/perfect-shuffle.txt
>
> The uniformity breaker is the case were two elements get equal
> weights. In his example, weights for a 2-size lists are choosed in {0,
> 1}. In the two corner case were both elements get picked the same
> weight, the sorting routine make an arbitrary choice : for example, if
> it is stable, it will put first the element occuring sooner in the
> list. This arbitrary choice breaks uniformity.
>
> The workaround is simple : pick weights that are all differents. If
> the weights are picked among [1, n] were n is the size of the list, it
> is difficult and inneficient to generate a list of unique random
> numbers. But you can choose weights in arbitrary intervals. The bigger
> it is, the smaller the chance you have to pick weights again becomes
> (though due to the birthday paradox, it does not decrease that fast).
>
> To sum it up, here is the algorithm to shuffle a list :
>
> - for each element in the list, pick a random list
> - pick another weight list while two equal weights were picked
> - once you've picked *unique* weights, shuffle the elements of the
> list by comparing their weights
>
> If the weight are taken in a big enough interval (say [1, 2^64]), the
> average number of repicks necessary is small enough for this algorithm
> to be just a sorting using your preferred algorithm. I haven't went
> through the trouble of computing the necessary interval bound to get a
> small enough chance of conflict, but I believe the forth power of the
> size of the list should be enough.
>
> An even better technique is to use lazy lists of {0, 1} (representing
> real numbers) as weights, with each list element lazily randomly
> computed. You are sure than no two such lists are equal (they're
> different with probability 1). This amounts to a dynamical random
> refining of weights during the sorting : "two of my real number
> weights are equal at granularity 2^-N ? Let's make a random choice so
> that their {N-1}th digit is different !"
------------------------------
Message: 2
Date: Mon, 30 Aug 2010 11:14:36 +0200
From: Gabriel Scherer <[email protected]>
Subject: [Haskell-beginners] randomize the order of a list
To: [email protected]
Cc: [email protected], [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Gaius Hammond wrote:
> 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.
Felipe Lessa wrote:
> Note: you could use random-shuffle package [1].
>
> [1] http://hackage.haskell.org/package/random-shuffle
Heinrich Apfelmus wrote:
> For another approach, see also
>
> http://apfelmus.nfshost.com/articles/random-permutations.html
Thanks for the link apfelmus, it's fairly interesting. The key to
making it work is the weighting of lists during merging based on their
lengths. I wonder if other sort algorithm can be adapted in such a
way, while preserving uniformity. Quicksort for example : is it enough
to choose the result position of the pivot randomly, and then placing
elements on either side with a probability of 1/2 ?
There is another sort-based approach that is probably less elegant,
but simpler in the sense that you don't have to rewrite your sorting
routines : pick random "weights" for each of your elements, and sort
the list based on the weights. This approach has been studied and
criticized by [Oleg], whose analysis is the base of the random-shuffle
package. Oleg rightly points out that this method does not achieve
uniformity in general. What he failed to notice is that there is a
simple workaround to regain uniformity with minimal changes.
[Oleg] http://okmij.org/ftp/Haskell/perfect-shuffle.txt
The uniformity breaker is the case were two elements get equal
weights. In his example, weights for a 2-size lists are choosed in {0,
1}. In the two corner case were both elements get picked the same
weight, the sorting routine make an arbitrary choice : for example, if
it is stable, it will put first the element occuring sooner in the
list. This arbitrary choice breaks uniformity.
The workaround is simple : pick weights that are all differents. If
the weights are picked among [1, n] were n is the size of the list, it
is difficult and inneficient to generate a list of unique random
numbers. But you can choose weights in arbitrary intervals. The bigger
it is, the smaller the chance you have to pick weights again becomes
(though due to the birthday paradox, it does not decrease that fast).
To sum it up, here is the algorithm to shuffle a list :
- for each element in the list, pick a random list
- pick another weight list while two equal weights were picked
- once you've picked *unique* weights, shuffle the elements of the
list by comparing their weights
If the weight are taken in a big enough interval (say [1, 2^64]), the
average number of repicks necessary is small enough for this algorithm
to be just a sorting using your preferred algorithm. I haven't went
through the trouble of computing the necessary interval bound to get a
small enough chance of conflict, but I believe the forth power of the
size of the list should be enough.
An even better technique is to use lazy lists of {0, 1} (representing
real numbers) as weights, with each list element lazily randomly
computed. You are sure than no two such lists are equal (they're
different with probability 1). This amounts to a dynamical random
refining of weights during the sorting : "two of my real number
weights are equal at granularity 2^-N ? Let's make a random choice so
that their {N-1}th digit is different !"
------------------------------
Message: 3
Date: Wed, 1 Sep 2010 15:19:08 +0600
From: "Alexander.Vladislav.Popov "
<[email protected]>
Subject: [Haskell-beginners] simplifying algebraic expression
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="utf-8"
Hi.
Please, tell me where I'm wrong and how to improve my approach.
I'm trying to simplify algebraic expressions this way:
import Data.Ratio
data Func = Const (Ratio Int)
| Pow (Ratio Int)
| Add Func Func
| Mul Func Func
instance Show Func where
show (Const n) = "(" ++ show n ++ ")"
show (Pow n) | n == 0 = "1"
| n == 1 = "x"
| otherwise = "(x**(" ++ show n ++ "))"
show (Add t1 t2) ="(" ++ (show t1) ++ "+" ++ (show t2) ++ ")"
show (Mul t1 t2) ="(" ++ (show t1) ++ "*" ++ (show t2) ++ ")"
deriv (Const _) = Const 0
deriv (Pow 1) = Const 1
deriv (Pow n) = Const n `Mul` Pow (n-1)
deriv (Add a b) = deriv a `Add` deriv b
deriv (Mul a b) = Add (deriv a `Mul` b) (a `Mul` deriv b)
p0 = Const 1
p1 = p0 `Add` (Mul (Pow 1) (Const 2))
p2 = p1 `Add` (Mul (Pow 2) (Const 3))
s rdc (Const x) = Const x
s rdc (Pow 0) = Const 1
s rdc (Pow x) = Pow x
s rdc (Add (Const a) (Const b)) = Const (a+b)
s rdc (Mul (Const 0) _) = Const 0
s rdc (Mul _ (Const 0)) = Const 0
s rdc (Mul (Const a) (Const b)) = Const (a*b)
s rdc (Mul (Pow n) (Pow m)) = Pow (n+m)
s rdc (Add x (Const 0)) = rdc x
s rdc (Add (Const 0) x) = rdc x
s rdc (Mul (Const m) (Mul (Const n) x)) = rdc $ Mul (Const (n*m)) (rdc x)
s rdc (Mul x (Const 1)) = rdc x
s rdc (Mul x (Const a)) = rdc $ Mul (Const a) (rdc x)
s rdc (Mul (Const 1) x) = rdc x
s rdc (Mul x (Add a b)) = Mul (rdc x) (rdc a) `Add` Mul (rdc x) (rdc b)
s rdc (Mul (Add a b) x) = Mul (rdc a) (rdc x) `Add` Mul (rdc b) (rdc x)
s rdc (Mul a b) = rdc a `Mul` rdc b
s rdc (Add a b) = rdc a `Add` rdc b
fix f = f (fix f)
The result I got is :
*Main> fix s $ deriv p2
(((2 % 1)+(0 % 1))+(((6 % 1)*x)+(0 % 1)))
instead of the anticipated expression ((2 % 1)+((6 % 1)*x)).
And worst of all, I must apply (fix s) repeatedly to achieve correct
answer:
*Main> fix s $ fix s $ deriv p2
((2 % 1)+((6 % 1)*x)).
I'll be very much appriciated for any help and useful links.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100901/6fca1bab/attachment-0001.html
------------------------------
Message: 4
Date: Wed, 1 Sep 2010 16:36:39 +0600
From: "Alexander.Vladislav.Popov "
<[email protected]>
Subject: Re: [Haskell-beginners] simplifying algebraic expression
To: jean verdier <[email protected]>, [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="utf-8"
It has given me an infinite loop and out-of-memory exception. I tried
different variations but not found the valid one and don't know what to do
next.
2010/9/1 jean verdier <[email protected]>
> I think that you need to reduce inner expressions before simplification.
>
> s rdc (Add a b) = rdc a `Add` rdc b
>
> will not reduce the Add result. What you need is something like
>
> s rdc (Add a b) = rdc (rdc a `Add` rdc b)
>
> that might not terminate but is your target.
>
>
> On Wed, 2010-09-01 at 15:19 +0600, Alexander.Vladislav.Popov wrote:
> > Hi.
> >
> > Please, tell me where I'm wrong and how to improve my approach.
> >
> > I'm trying to simplify algebraic expressions this way:
> >
> > import Data.Ratio
> >
> > data Func = Const (Ratio Int)
> > | Pow (Ratio Int)
> > | Add Func Func
> > | Mul Func Func
> >
> > instance Show Func where
> > show (Const n) = "(" ++ show n ++ ")"
> > show (Pow n) | n == 0 = "1"
> > | n == 1 = "x"
> > | otherwise = "(x**(" ++ show n ++ "))"
> > show (Add t1 t2) ="(" ++ (show t1) ++ "+" ++ (show t2) ++ ")"
> > show (Mul t1 t2) ="(" ++ (show t1) ++ "*" ++ (show t2) ++ ")"
> >
> >
> > deriv (Const _) = Const 0
> > deriv (Pow 1) = Const 1
> > deriv (Pow n) = Const n `Mul` Pow (n-1)
> > deriv (Add a b) = deriv a `Add` deriv b
> > deriv (Mul a b) = Add (deriv a `Mul` b) (a `Mul` deriv b)
> >
> > p0 = Const 1
> > p1 = p0 `Add` (Mul (Pow 1) (Const 2))
> > p2 = p1 `Add` (Mul (Pow 2) (Const 3))
> >
> >
> > s rdc (Const x) = Const x
> > s rdc (Pow 0) = Const 1
> > s rdc (Pow x) = Pow x
> > s rdc (Add (Const a) (Const b)) = Const (a+b)
> > s rdc (Mul (Const 0) _) = Const 0
> > s rdc (Mul _ (Const 0)) = Const 0
> > s rdc (Mul (Const a) (Const b)) = Const (a*b)
> > s rdc (Mul (Pow n) (Pow m)) = Pow (n+m)
> >
> > s rdc (Add x (Const 0)) = rdc x
> > s rdc (Add (Const 0) x) = rdc x
> > s rdc (Mul (Const m) (Mul (Const n) x)) = rdc $ Mul (Const (n*m)) (rdc
> > x)
> > s rdc (Mul x (Const 1)) = rdc x
> > s rdc (Mul x (Const a)) = rdc $ Mul (Const a) (rdc x)
> > s rdc (Mul (Const 1) x) = rdc x
> > s rdc (Mul x (Add a b)) = Mul (rdc x) (rdc a) `Add` Mul (rdc x) (rdc
> > b)
> > s rdc (Mul (Add a b) x) = Mul (rdc a) (rdc x) `Add` Mul (rdc b) (rdc
> > x)
> > s rdc (Mul a b) = rdc a `Mul` rdc b
> > s rdc (Add a b) = rdc a `Add` rdc b
> >
> > fix f = f (fix f)
> >
> > The result I got is :
> >
> > *Main> fix s $ deriv p2
> > (((2 % 1)+(0 % 1))+(((6 % 1)*x)+(0 % 1)))
> >
> > instead of the anticipated expression ((2 % 1)+((6 % 1)*x)).
> > And worst of all, I must apply (fix s) repeatedly to achieve correct
> > answer:
> >
> > *Main> fix s $ fix s $ deriv p2
> > ((2 % 1)+((6 % 1)*x)).
> >
> > I'll be very much appriciated for any help and useful links.
> > _______________________________________________
> > Beginners mailing list
> > [email protected]
> > http://www.haskell.org/mailman/listinfo/beginners
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100901/b6bc5c97/attachment-0001.html
------------------------------
Message: 5
Date: Wed, 01 Sep 2010 13:31:20 +0200
From: J?rgen Doser <[email protected]>
Subject: Re: [Haskell-beginners] simplifying algebraic expression
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
El mié, 01-09-2010 a las 16:36 +0600, Alexander.Vladislav.Popov
escribió:
> It has given me an infinite loop and out-of-memory exception. I tried
> different variations but not found the valid one and don't know what
> to do next.
you have to reduce the inner expressions recursively, then pattern-match
on those results to simplify:
rdc (Add a b) = case (rdc a, rdc b) of
(Const 0, x) -> x
(x, Const 0) -> x
...
You can now be sure that whatever you pattern-match on is already a
fully simplified algebraic expression (i.e., a sum of rational powers of
x with rational coefficients). This should make it easier to think about
the necessary cases you have to handle.
Btw., is there a particular reason why you did not try to write the
recursion explicitely, but used the function s?
Jürgen
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 27, Issue 1
****************************************
