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: question on typeclasses and applicatives (Daniel Fischer)
2. Re: randomize the order of a list (Gabriel Scherer)
3. Re: randomize the order of a list (Gabriel Scherer)
4. Re: question on typeclasses and applicatives (Alec Benzer)
5. Graham Scan exercise from Chapter 3 RWH -Spoilers. Don't
read if you want to do this exercise. (Michael Litchard)
6. Re: Ranges and List Comprehensions in SQL (Toby Thain)
----------------------------------------------------------------------
Message: 1
Date: Fri, 3 Sep 2010 00:49:01 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] question on typeclasses and
applicatives
To: Alec Benzer <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Friday 03 September 2010 00:17:22, Alec Benzer wrote:
> I guess I'm still sort of confused or perturbed with why it's disabled
> by default. If the compiler has the ability to do it and there are no
> problems with doing it, why not just allow it without requiring you to
> pass a flag to the compiler?
It's disabled by default because the language standard laid down different
rules. Generally, compiler writers tend to avoid enabling too much non-
standard behaviour by default (though chapter 12 of the GHC user's guide
lists a couple of deviations). However, often there's useful stuff that
goes against the standard (well, it seemed to be a good idea at the time),
so many compilers offer extensions to go beyond the standard.
------------------------------
Message: 2
Date: Thu, 2 Sep 2010 15:34:07 +0200
From: Gabriel Scherer <[email protected]>
Subject: Re: [Haskell-beginners] randomize the order of a list
To: [email protected]
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
I must apologize : a part of my post about quicksort didn't make sense
: if one choose the pivot position randomly, elements shouldn't be
splitted with even probability, because there would be no control over
the size of the results list.
If I understand it correctly, your solution doesn't pick a pivot
position, but dynamically adapt list size probabilities during
traversal.
I have a different solution, that pick a pivot position, then choose
the elements with carefully weighted probability to get the right
left-hand and right-hand sizes. The key idea comes from your analysis
(more precisely, from the presence of the n `over` k probabilities) :
for a given k (the pivot), choose a random subset of k elements as the
left-hand side of the pivot.
import Random (Random, StdGen, randomRIO)
import Control.Monad (liftM)
quickshuffle :: [a] -> IO [a]
quickshuffle [] = return []
quickshuffle [x] = return [x]
quickshuffle xs = do
(ls, rs) <- partition xs
sls <- quickshuffle ls
srs <- quickshuffle rs
return (sls ++ srs)
-- The idea is that to partition a list of length n, we choose a pivot
-- position randomly (1 < k < n), then choose a subset of k elements
-- in the list to be on the left side, and the other n-k on the right
-- side.
--
-- To choose a random subset of length k among n, scan the list and
-- add each element with probability
-- (number of elements left to pick) / (number of elements left to scan)
--
partition :: [a] -> IO ([a], [a])
partition xs = do
let n = length xs
k <- randomRIO (1, n-1)
split n k ([], []) xs
where split n k (ls, rs) [] = return (ls, rs)
split n k (ls, rs) (x:xs) = do
p <- randomRIO (1, n)
if p <= k
then split (n - 1) (k - 1) (x:ls, rs) xs
else split (n - 1) k (ls, x:rs) xs
I have also written an implementation for my former algorithm :
import Data.List (mapAccumL, sortBy)
import System.Random (RandomGen, split, randoms)
import Data.Ord (Ordering)
import Data.Function (on)
-- compare two real numbers as infinite sequences of booleans
real_cmp :: [Bool] -> [Bool] -> Ordering
real_cmp (True:_) (False:_) = LT
real_cmp (False:_) (True:_) = GT
real_cmp (_:xs) (_:ys) = real_cmp xs ys
-- weight each element with a random real number
weight_list :: RandomGen g => g -> [a] -> [([Bool], a)]
weight_list g = snd . mapAccumL weight g
where weight g x =
let (g1, g2) = split g in
(g1, (randoms g2, x))
-- shuffle by sorting on weights
shuffle :: RandomGen g => g -> [a] -> [a]
shuffle g = map snd . sort_on_weights . weight_list g
where sort_on_weights = sortBy (real_cmp `on` fst)
> Interesting question! Adapting quick sort is not that easy, though.
>
> First, you can skip choosing the pivot position because it is already
> entailed by the choices of elements left and right to it.
>
> Second, probability 1/2 won't work, it doesn't give a uniform
> distribution. In order to get that, the remaining input xs has to be
> partitioned into two lists xs = (ls,rs) such that
>
> probability that length ys == k is 1/(n `over` k)
>
> where
>
> n `over` k = n! / (k! * (n-k)!)
>
> is the binomial coefficient. After all, calling "quickrandom"
> recursively on each of the two lists will give two permutations with
> probability 1/k! and 1/(n-k)! and the probability for a compound
> permutation is
>
> 1/(n `over` k) * 1/k! * 1/(n-k)! = 1/n!
>
> as desired. In contrast, distributing elements with probability 1/2
> would give
>
> probability that length ys == k is (n `over` k) * 2^(-n)
>
> which would skew the distribution heavily towards permutations where the
> pivot element is in the middle.
>
>
> However, it is possible to divide the list properly, though I haven't
> worked out the exact numbers. The method would be
>
> divide (x:xs) = do
> (ls,rs) <- divide xs
> random <- uniform (0, 1) :: Random Double
> if random <= p (length xs) (length ls)
> then return (x:ls, rs)
> else return (ls, x:rs)
>
> where the probability p of putting the element x into the left part
> has to be chosen such that
>
> 1/(n `over` k) =
> 1/(n-1 `over` k-1) * p (n-1) (k-1)
> + 1/(n-1 `over` k ) * (1 - p (n-1) k)
>
>
> Regards,
> Heinrich Apfelmus
------------------------------
Message: 3
Date: Thu, 2 Sep 2010 15:45:23 +0200
From: Gabriel Scherer <[email protected]>
Subject: Re: [Haskell-beginners] randomize the order of a list
To: [email protected]
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
A small remark I forgot.
First, It seems to me that the choice of k need not be random, but
only arbitrary. I believe that any fixed k would work. In particular,
it is interesting to compare this algorithm with k = n/2, and Heinrich
Apfelmus's algorithm based on mergesort (
http://apfelmus.nfshost.com/articles/random-permutations.html ):
- mergeshuffle split the unshuffled list directly, shuffle each part,
then merge them carefully
- quickshuffle split the unshuffled list carefully, shuffle each part,
then merge them directly
mergeshuffle's `merge` and quickshuffle's `split` are very similar
and, in a sense, dual.
`merge` reason on the probability (number of elements in the left list
to merge) / (total number of elements to merge)
`split` reason on the probability (number of elements left to put in
the left list) / (total number of elements left to split)
On Thu, Sep 2, 2010 at 3:34 PM, Gabriel Scherer
<[email protected]> wrote:
> I must apologize : a part of my post about quicksort didn't make sense
> : if one choose the pivot position randomly, elements shouldn't be
> splitted with even probability, because there would be no control over
> the size of the results list.
>
> If I understand it correctly, your solution doesn't pick a pivot
> position, but dynamically adapt list size probabilities during
> traversal.
>
> I have a different solution, that pick a pivot position, then choose
> the elements with carefully weighted probability to get the right
> left-hand and right-hand sizes. The key idea comes from your analysis
> (more precisely, from the presence of the n `over` k probabilities) :
> for a given k (the pivot), choose a random subset of k elements as the
> left-hand side of the pivot.
>
> import Random (Random, StdGen, randomRIO)
> import Control.Monad (liftM)
>
> quickshuffle :: [a] -> IO [a]
> quickshuffle [] = return []
> quickshuffle [x] = return [x]
> quickshuffle xs = do
> (ls, rs) <- partition xs
> sls <- quickshuffle ls
> srs <- quickshuffle rs
> return (sls ++ srs)
>
> -- The idea is that to partition a list of length n, we choose a pivot
> -- position randomly (1 < k < n), then choose a subset of k elements
> -- in the list to be on the left side, and the other n-k on the right
> -- side.
> --
> -- To choose a random subset of length k among n, scan the list and
> -- add each element with probability
> -- (number of elements left to pick) / (number of elements left to scan)
> --
> partition :: [a] -> IO ([a], [a])
> partition xs = do
> let n = length xs
> k <- randomRIO (1, n-1)
> split n k ([], []) xs
> where split n k (ls, rs) [] = return (ls, rs)
> split n k (ls, rs) (x:xs) = do
> p <- randomRIO (1, n)
> if p <= k
> then split (n - 1) (k - 1) (x:ls, rs) xs
> else split (n - 1) k (ls, x:rs) xs
>
>
>
> I have also written an implementation for my former algorithm :
>
> import Data.List (mapAccumL, sortBy)
> import System.Random (RandomGen, split, randoms)
> import Data.Ord (Ordering)
> import Data.Function (on)
> -- compare two real numbers as infinite sequences of booleans
> real_cmp :: [Bool] -> [Bool] -> Ordering
> real_cmp (True:_) (False:_) = LT
> real_cmp (False:_) (True:_) = GT
> real_cmp (_:xs) (_:ys) = real_cmp xs ys
> -- weight each element with a random real number
> weight_list :: RandomGen g => g -> [a] -> [([Bool], a)]
> weight_list g = snd . mapAccumL weight g
> where weight g x =
> let (g1, g2) = split g in
> (g1, (randoms g2, x))
> -- shuffle by sorting on weights
> shuffle :: RandomGen g => g -> [a] -> [a]
> shuffle g = map snd . sort_on_weights . weight_list g
> where sort_on_weights = sortBy (real_cmp `on` fst)
>
>> Interesting question! Adapting quick sort is not that easy, though.
>>
>> First, you can skip choosing the pivot position because it is already
>> entailed by the choices of elements left and right to it.
>>
>> Second, probability 1/2 won't work, it doesn't give a uniform
>> distribution. In order to get that, the remaining input xs has to be
>> partitioned into two lists xs = (ls,rs) such that
>>
>> probability that length ys == k is 1/(n `over` k)
>>
>> where
>>
>> n `over` k = n! / (k! * (n-k)!)
>>
>> is the binomial coefficient. After all, calling "quickrandom"
>> recursively on each of the two lists will give two permutations with
>> probability 1/k! and 1/(n-k)! and the probability for a compound
>> permutation is
>>
>> 1/(n `over` k) * 1/k! * 1/(n-k)! = 1/n!
>>
>> as desired. In contrast, distributing elements with probability 1/2
>> would give
>>
>> probability that length ys == k is (n `over` k) * 2^(-n)
>>
>> which would skew the distribution heavily towards permutations where the
>> pivot element is in the middle.
>>
>>
>> However, it is possible to divide the list properly, though I haven't
>> worked out the exact numbers. The method would be
>>
>> divide (x:xs) = do
>> (ls,rs) <- divide xs
>> random <- uniform (0, 1) :: Random Double
>> if random <= p (length xs) (length ls)
>> then return (x:ls, rs)
>> else return (ls, x:rs)
>>
>> where the probability p of putting the element x into the left part
>> has to be chosen such that
>>
>> 1/(n `over` k) =
>> 1/(n-1 `over` k-1) * p (n-1) (k-1)
>> + 1/(n-1 `over` k ) * (1 - p (n-1) k)
>>
>>
>> Regards,
>> Heinrich Apfelmus
>
------------------------------
Message: 4
Date: Thu, 2 Sep 2010 20:11:22 -0400
From: Alec Benzer <[email protected]>
Subject: Re: [Haskell-beginners] question on typeclasses and
applicatives
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On Thu, Sep 2, 2010 at 6:49 PM, Daniel Fischer <[email protected]> wrote:
> On Friday 03 September 2010 00:17:22, Alec Benzer wrote:
>> I guess I'm still sort of confused or perturbed with why it's disabled
>> by default. If the compiler has the ability to do it and there are no
>> problems with doing it, why not just allow it without requiring you to
>> pass a flag to the compiler?
>
> It's disabled by default because the language standard laid down different
> rules. Generally, compiler writers tend to avoid enabling too much non-
> standard behaviour by default (though chapter 12 of the GHC user's guide
> lists a couple of deviations). However, often there's useful stuff that
> goes against the standard (well, it seemed to be a good idea at the time),
> so many compilers offer extensions to go beyond the standard.
>
I guess I would then be concerned with why they didn't allow it in the
standard (though I guess "well, it seemed to be a good idea at the
time" answers that).
I think I also would want to avoid doing things not in the language
standard on principle, since my instinct would tell me that if only a
particular compiler implements, I shouldn't use it because it'll
produce non-standard code. Though this sort of comes comes from C/C++
where there are different compilers on different platforms, but I
guess with haskell people pretty much use ghc everywhere?
------------------------------
Message: 5
Date: Thu, 2 Sep 2010 17:21:45 -0700
From: Michael Litchard <[email protected]>
Subject: [Haskell-beginners] Graham Scan exercise from Chapter 3 RWH
-Spoilers. Don't read if you want to do this exercise.
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Below is my solution for the Graham Scan Algorithm.
I tried to limit myself to information in the first three chapters
while completing this problem.
Now, I want to remove the explicit recursion and use more idiomatic
Haskell. I'd like to get some advice on which functions/modules would
be helpful in this.
<code>
data Direction = DStraight
| DLeft
| DRight
deriving (Eq,Show)
type PointXY = (Double,Double)
calcTurn :: PointXY -> PointXY -> PointXY -> Direction
calcTurn a b c
| crossProduct == 0 = DStraight
| crossProduct > 0 = DLeft
| otherwise = DRight
where crossProduct = ((fst b - fst a) * (snd c - snd a)) -
((snd b - snd a) * (fst c - fst a))
calcDirectionList :: [PointXY] -> [Direction]
calcDirectionList (x:y:z:zs) = (calcTurn x y z) : (calcDirectionList (y:z:zs))
calcDirectionList _ = []
sortListByY :: [PointXY] -> [PointXY]
sortListByY [] = []
sortListByY [a] = [a]
sortListByY (a:as) = insert (sortListByY as)
where insert [] = [a]
insert (b:bs) | snd a <= snd b = a : b : bs
| otherwise = b : insert bs
sortListByCoTangent :: [PointXY] -> [PointXY]
sortListByCoTangent [] = []
sortListByCoTangent [a] = [a]
sortListByCoTangent (a:as) = a : insert (sortListByCoTangent as)
where insert :: [PointXY] -> [PointXY]
insert [b] = [b]
insert (b:c:cs) | (myCoTan a b) >= (myCoTan a
c) = b : insert (c:cs)
| otherwise
= c : insert (b:cs)
where myCoTan :: PointXY -> PointXY -> Double
myCoTan p1 p2 = (fst p2 - fst p1) /
(snd p2 - snd p1)
createHull :: [PointXY] -> [PointXY]
createHull (a:b:c:cs) = a : filterPoint (createHull (b:c:cs))
where filterPoint :: [PointXY] -> [PointXY]
filterPoint (x:y:z:zs)
| calcTurn x y z == (DLeft) = [x] ++ [y]
++ [z] ++ filterPoint (zs)
| otherwise = [x] ++ [z]
++ filterPoint (zs)
filterPoint [x] = a:[x]
filterPoint _ = []
createHull _ = []
main :: IO ()
main = do
let points = [(5.0,0.0),(5.0,6.0),(3.0,-4.2),(0.0,6.0)]
print $ createHull points
------------------------------
Message: 6
Date: Thu, 2 Sep 2010 20:34:35 -0400
From: Toby Thain <[email protected]>
Subject: Re: [Haskell-beginners] Ranges and List Comprehensions in SQL
To: Tom Murphy <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On 2-Sep-10, at 3:54 PM, Tom Murphy wrote:
> Hi Everyone,
>
> Is there a "From SQL"-type function that "restores" a range or
> list comprehension?
>
> Example:
> Let's say I want to keep track of which episodes of a TV show I've
> seen. I have an SQL table, in which is a record:
> id (INTEGER): 30
> title (VARCHAR): "The Simpsons"
> episodes_watched (Some data format): [1..4], [14], [18..21],
> [23..25]
To model this relationally, episodes_watched cannot be some kind of
composite value. You need two relations, for example:
CREATE TABLE tv_show (
id INTEGER NOT NULL, -- etc
title VARCHAR(80),
PRIMARY KEY (id)
);
CREATE TABLE episodes_watched (
tv_show_id INTEGER NOT NULL,
episode_number INTEGER,
PRIMARY KEY (tv_show_id, episode_number)
-- and ideally a foreign key constraint
);
Data:
tv_show (30, "The Simpsons")
episodes_watched (30,1), (30,2), (30,3), (30,4), (30,14), (30,18),
(30,19), (30,20), (30,21), (30,23), (30,24), (30,25)
--Toby
>
> Then, when I pull the record, in Haskell, the "Episodes Watched" is
> already one list:
> [1,2,3,4,14,18,19,21,23,24,25]
>
> , or a series of lists that I can append together:
> [1,2,3,4], [14], [18,19,20,21], [23,24,25]
>
>
> Note in the example that I would like to be able to store multiple
> ranges within a single record.
>
>
> Thanks so much for any help!
> Tom
> _______________________________________________
> 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/20100902/53f4dfbc/attachment.html
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 27, Issue 7
****************************************
