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. Setting Default Integer and Real Types (Lorenzo Isella)
2. Re: randomize the order of a list (Heinrich Apfelmus)
3. [OT] To Mock A Mockingbird (Patrick LeBoutillier)
4. Re: Setting Default Integer and Real Types (Brent Yorgey)
5. Re: Setting Default Integer and Real Types (Daniel Fischer)
6. Re: [OT] To Mock A Mockingbird (Brent Yorgey)
7. Re: [OT] To Mock A Mockingbird (Lyndon Maydwell)
8. Re: [OT] To Mock A Mockingbird (Stephen Tetley)
9. Convert String to List/Array of Numbers (Lorenzo Isella)
----------------------------------------------------------------------
Message: 1
Date: Wed, 08 Sep 2010 12:58:48 +0200
From: Lorenzo Isella <[email protected]>
Subject: [Haskell-beginners] Setting Default Integer and Real Types
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Dear All,
I am quite new to Haskell and planning to see where it will lead me in
scientific computing (I will be looking into hmatrix soon).
Unless there are real memory problems, I would like to make sure that
all real numbers are Double and all integer numbers are Integer types.
Now, I understand that Haskell in most of the cases is smart enough to
infer the type of a variable (integer, real, etc...), but can I also set
its default precision once for all?
I.e. if I say a=5.2 I want a to be used as a double precision real
everywhere in the code.
Cheers
Lorenzo
------------------------------
Message: 2
Date: Wed, 08 Sep 2010 13:55:17 +0200
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: randomize the order of a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
Gabriel Scherer 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.
No worries, my statement about the probability of the length of the left
part being k doesn't make sense, either, since the probabilities 1/(n
`over` k) don't even add up to a total of one. What is clear is that
there is no *a priori* reason that 1/2 should work.
> If I understand it correctly, your solution doesn't pick a pivot
> position, but dynamically adapt list size probabilities during
> traversal.
Yes. Note, however, that I intended to pick a pivot *element*, i.e. an
element which, just like in ordinary quick sort, will not be permuted
subsequently. This is subtly different from a pivot *position* that
divides the list into two parts but has no element associated to it. I
think this is important when trying to analyze the naive 1/2 scheme, but
it's immaterial in your proposal:
> 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
Yes, this algorithm should work. Of course, while the probability
(number of elements left to pick) / (number of elements left to scan)
for picking an element x seems to be the only sensible choice, one still
has to prove that this gives a uniform distribution. (Embarrassingly, my
article about "merge shuffle" lacks a proof, too, I plan to rewrite it
at some point.)
Proving uniformity proceeds in two steps:
First, we have to argue that picking the first k elements uniformly
and then permuting them does give a uniform *total* permutation. This is
fairly obvious, though. Namely, the set of possible permutations of n
elements can be partitioned into (n `over` k) classes, where two
permutations belong to the same class if they have the same first k
elements (in any order). For instance,
k = 3, n = 5
[1,2,3,5,4] is the same class as [3,2,1,4,5]
because the first k elements are {1,2,3}
[1,2,3,5,4] is in a different class than [4,2,1,3,5]
because the first k elements are {1,2,3} and {1,2,4} resp.
Now, to pick a random permutation, we first pick a class at random and
then pick a permutation from this class. The point is that for reasons
of symmetry, all classes have the same size! Namely, there are k! *
(n-k)! permutations in every class. That means we should pick the class
with uniform probability, and that's exactly what the split function
intends to do.
Second, we have to argue that split does indeed pick a class (= a set
of k elements) *uniformly*. The reasoning for that is as follows:
Consider a particular element x . There are
(n-1 `over` k-1) classes that contain x
(n-1 `over` k ) classes that don't contain x
(This correctly adds up to (n `over` k) classes in total). Hence, the
probability that the class contains x is
classes with x / total classes
= (n-1 `over` k-1) / (n `over` k)
= ( (n-1)! / ((k-1)!(n-k)!) ) / ( n! / (k!(n-k)!) )
= (n-1)! / n! * k! / (k-1)!
= k / n
= elements left to pick / elements left to scan
This shows that split does indeed use the correct probability for
including x .
Regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 3
Date: Wed, 8 Sep 2010 07:57:14 -0400
From: Patrick LeBoutillier <[email protected]>
Subject: [Haskell-beginners] [OT] To Mock A Mockingbird
To: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi all,
I've been reading the book "To Mock A Mockingbird" by Robert Smullyan
recently and I don't get the part about the birds at all. I think I
understand that a bird is a function, but what would it's type be in
Haskell?
It says that birds hear a call and answer by another call, so I
thought String -> String or something like that. But if you have a
mockingbird that can answer what a bird would answer to itself, that
means that it's input must contain the other bird... Do all the birds
have the same type?
Thanks,
Patrick
--
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada
------------------------------
Message: 4
Date: Wed, 8 Sep 2010 08:04:18 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Setting Default Integer and Real
Types
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Wed, Sep 08, 2010 at 12:58:48PM +0200, Lorenzo Isella wrote:
> Dear All,
> I am quite new to Haskell and planning to see where it will lead me
> in scientific computing (I will be looking into hmatrix soon).
> Unless there are real memory problems, I would like to make sure that
> all real numbers are Double and all integer numbers are Integer
> types.
> Now, I understand that Haskell in most of the cases is smart enough
> to infer the type of a variable (integer, real, etc...), but can I
> also set its default precision once for all?
> I.e. if I say a=5.2 I want a to be used as a double precision real
> everywhere in the code.
Sure, just give a type signature:
a :: Double
a = 5.2
-Brent
------------------------------
Message: 5
Date: Wed, 8 Sep 2010 14:07:00 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Setting Default Integer and Real
Types
To: [email protected]
Cc: Lorenzo Isella <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Wednesday 08 September 2010 12:58:48, Lorenzo Isella wrote:
> Dear All,
> I am quite new to Haskell and planning to see where it will lead me in
> scientific computing (I will be looking into hmatrix soon).
> Unless there are real memory problems, I would like to make sure that
> all real numbers are Double and all integer numbers are Integer types.
> Now, I understand that Haskell in most of the cases is smart enough to
> infer the type of a variable (integer, real, etc...), but can I also set
> its default precision once for all?
Haskell has default declarations
http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-790004.3.4
for that.
The default default is
default (Integer, Double)
which means that if possible, an ambiguous number type is instantiated as
Integer, if that's not possible (due to a Fractional or Floating constraint
for example), Double is tried. If neither is possible, you get a compile
error (ambiguous type variable ...).
> I.e. if I say a=5.2 I want a to be used as a double precision real
> everywhere in the code.
There's a slight catch in that.
The inferred type of a binding a = 5.2 is
a :: Fractional n => n
and the binding is really
a = fromRational (26 % 5)
Depending on whether the monomorphism restriction applies and the
optimisation level, it could be that without type signature, the call to
fromRational is evaluated at each use, which can slow down performance.
But basically, you get your desired behaviour automatically.
However, it's good practice to use a lot of type signatures although the
compiler's type inference makes that not necessary (apart from the
documentational effect of type signatures, specifying a monomorphic type
instead of the inferred polymorphic type can give significant performance
gains).
> Cheers
>
> Lorenzo
------------------------------
Message: 6
Date: Wed, 8 Sep 2010 08:08:37 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] [OT] To Mock A Mockingbird
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Wed, Sep 08, 2010 at 07:57:14AM -0400, Patrick LeBoutillier wrote:
> Hi all,
>
> I've been reading the book "To Mock A Mockingbird" by Robert Smullyan
> recently and I don't get the part about the birds at all. I think I
> understand that a bird is a function, but what would it's type be in
> Haskell?
>
> It says that birds hear a call and answer by another call, so I
> thought String -> String or something like that. But if you have a
> mockingbird that can answer what a bird would answer to itself, that
> means that it's input must contain the other bird... Do all the birds
> have the same type?
No, each bird has its own type; each bird represents some particular
combinator (= polymorphic function).
-Brent
------------------------------
Message: 7
Date: Wed, 8 Sep 2010 20:19:43 +0800
From: Lyndon Maydwell <[email protected]>
Subject: Re: [Haskell-beginners] [OT] To Mock A Mockingbird
To: Brent Yorgey <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
I've just read this.
Check out: http://dkeenan.com/Lambda/
Best analysis ever.
On Wed, Sep 8, 2010 at 8:08 PM, Brent Yorgey <[email protected]> wrote:
> On Wed, Sep 08, 2010 at 07:57:14AM -0400, Patrick LeBoutillier wrote:
>> Hi all,
>>
>> I've been reading the book "To Mock A Mockingbird" by Robert Smullyan
>> recently and I don't get the part about the birds at all. I think I
>> understand that a bird is a function, but what would it's type be in
>> Haskell?
>>
>> It says that birds hear a call and answer by another call, so I
>> thought String -> String or something like that. But if you have a
>> mockingbird that can answer what a bird would answer to itself, that
>> means that it's input must contain the other bird... Do all the birds
>> have the same type?
>
> No, each bird has its own type; each bird represents some particular
> combinator (= polymorphic function).
>
> -Brent
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 8
Date: Wed, 8 Sep 2010 14:20:47 +0100
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] [OT] To Mock A Mockingbird
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On 8 September 2010 13:08, Brent Yorgey <[email protected]> wrote:
> No, each bird has its own type; each bird represents some particular
> combinator (= polymorphic function).
Also, bear in mind that some of the birds cannot be typed in Haskell.
------------------------------
Message: 9
Date: Wed, 08 Sep 2010 15:31:19 +0200
From: Lorenzo Isella <[email protected]>
Subject: [Haskell-beginners] Convert String to List/Array of Numbers
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Dear All,
I must be stuck on something pretty basic (I am struggling badly with I/O).
Let us assume you have a rather simple file mydata.dat (3 columns of
integer numbers), see below.
1246191122 1336 1337
1246191142 1336 1337
1246191162 1336 1337
1246191182 1336 1337
1246191202 1336 1337
1246191222 1336 1337
1246191242 1336 1337
1246191262 1336 1337
1246191282 1336 1337
1246191302 1336 1337
1246191322 1336 1337
1246191342 1336 1337
1246191362 1336 1337
1246191382 1336 1337
1246191402 1336 1337
1246191422 1336 1337
Now, my intended pipeline could be
read file as string--> convert to list of integers-->pass it to hmatrix
(or try to convert it into a matrix/array).
Leaving aside the last step, I can easily do something like
let dat=readFile "mydata.dat"
in the interactive shell and get a string, but I am having problems in
converting this to a list or anything more manageable (where every entry
is an integer number i.e. something which can be summed, subtracted
etc...). Ideally even a list where every entry is a row (a list in
itself) would do.
I found online this suggestion
http://bit.ly/9jv1WG
but I am not sure if it really applies to this case.
Many thanks
Lorenzo
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 27, Issue 18
*****************************************
