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: permuting a list (Thomas Davie)
2. Re: permuting a list (Brent Yorgey)
3. Re: permuting a list (Daniel Fischer)
4. A possibly foolish question (Alan Cameron)
5. Re: A possibly foolish question (Thomas Davie)
6. RE: cabal-install can't connect (Kirk Martinez)
7. Re: permuting a list (Jan Snajder)
8. Re: Re: permuting a list (Felipe Lessa)
9. Re: Re: permuting a list (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Thu, 12 Feb 2009 20:19:46 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] permuting a list
To: Brent Yorgey <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On 12 Feb 2009, at 19:33, Brent Yorgey wrote:
> On Thu, Feb 12, 2009 at 11:58:21AM -0500, Andrew Wagner 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.
Bob
------------------------------
Message: 2
Date: Thu, 12 Feb 2009 14:40:09 -0500
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] permuting a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Thu, Feb 12, 2009 at 08:19:46PM +0100, Thomas Davie wrote:
>
> On 12 Feb 2009, at 19:33, Brent Yorgey wrote:
>
>> On Thu, Feb 12, 2009 at 11:58:21AM -0500, Andrew Wagner 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.
Indexing into a list is still O(n) in the index, whether you actually
compute the elements or not. That is, if you're actually building a
list of permutations, then even if you don't compute anything about
the permutations you don't need, just traversing through the spine of
the list to get the one you want will take a very long
time---O(n!)---for reasonably large n. However, you can actually
write a pure function with type
Int -> [a] -> [a]
which just computes which permutation "would be" at the given index,
without ever actually constructing a list of them. I'll leave this as
an interesting exercise (hint: convert the input number to "base
factorial"...), although I still think it's not going to be quite as
fast as the imperative version (at least O(n lg n)).
-Brent
------------------------------
Message: 3
Date: Thu, 12 Feb 2009 20:46:22 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] permuting a list
To: Thomas Davie <[email protected]>, Brent Yorgey
<[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Donnerstag, 12. Februar 2009 20:19 schrieb Thomas Davie:
> On 12 Feb 2009, at 19:33, Brent Yorgey wrote:
> > On Thu, Feb 12, 2009 at 11:58:21AM -0500, Andrew Wagner 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.
>
> Bob
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".
module Permutations where
import Data.List (sortBy, genericSplitAt, genericLength)
import Data.Ord (comparing)
factorialDigits :: Integer -> [Integer]
factorialDigits k = go k 2
where
go 0 _ = []
go m d = case m `divMod` d of
(q,r) -> r:go q (d+1)
permIndices :: Integer -> [Integer]
permIndices k = go [0] 1 fds
where
fds = factorialDigits k
go acc d [] = acc ++ [d .. ]
go acc d (p:ps) =
case genericSplitAt (d-p) acc of
(front,back) -> go (front ++ d:back) (d+1) ps
kthPerm :: Integer -> [a] -> [a]
kthPerm k = map snd . sortBy (comparing fst) . zip (permIndices k)
------------------------------
Message: 4
Date: Thu, 12 Feb 2009 20:39:56 -0000
From: "Alan Cameron" <[email protected]>
Subject: [Haskell-beginners] A possibly foolish question
To: <[email protected]>
Message-ID: <e543574985604040a86c8cb5ef7ee...@alanxps>
Content-Type: text/plain; charset="us-ascii"
Is it possible to have a Haskell function or functions included in a C++
program's structure and used as a procedure?
Alan Cameron
------------------------------
Message: 5
Date: Thu, 12 Feb 2009 23:53:49 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] A possibly foolish question
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On 12 Feb 2009, at 21:39, Alan Cameron wrote:
> Is it possible to have a Haskell function or functions included in a
> C++
> program's structure and used as a procedure?
Yes, see the FFI (or Foreign Function Interface) documentation.
That'll let you export Haskell functions into C land, and from there
to C++.
Bob
------------------------------
Message: 6
Date: Thu, 12 Feb 2009 15:36:50 -0800
From: Kirk Martinez <[email protected]>
Subject: RE: [Haskell-beginners] cabal-install can't connect
To: "'Salvatore Insalaco'" <[email protected]>
Cc: "[email protected]" <[email protected]>
Message-ID:
<aaa7e9adec517141984ab6a6d594eff143198c4...@sj-itmsg02.altera.priv.altera.com>
Content-Type: text/plain; charset="us-ascii"
Thanks, Salvatore. I was able to get cabal install working by setting IE to
use a local proxy server which is set up to cascade through to my corporate
proxy. I was already using CCproxy for testing some other proxy stuff
internally, so that's what I used. It works great! I only use IE for those
proxy settings now, and Firefox for my day to day browsing needs.
Thanks a bunch,
Kirk
-----Original Message-----
From: Salvatore Insalaco [mailto:[email protected]]
Sent: Sunday, February 08, 2009 10:59 PM
To: Kirk Martinez
Cc: [email protected]
Subject: Re: [Haskell-beginners] cabal-install can't connect
On Fri, Feb 6, 2009 at 7:25 PM, Kirk Martinez <[email protected]> wrote:
> I'm trying to use cabal-install through the firewall at my work and I am
> consistently denied:
In my experience, cabal-install ignores the http_proxy variable on
Windows, and uses the Internet Explorer proxy registry key.
Another problem could be that your proxy is using NTLM authentication,
that cabal doesn't support.
To solve this problem, if your proxy supports BASIC authentication,
just put the proxy informations in the Internet Explorer proxy dialog;
you have to do it even if there's the "automatic proxy configuration"
setting, as cabal is unable to use it.
If your proxy supports NTLM authentication, just download a package
like http://www.geocities.com/rozmanov/ntlm/ and then put its host and
port as proxy in Internet Explorer.
Salvatore
Confidentiality Notice.
This message may contain information that is confidential or otherwise
protected from disclosure. If you are not the intended recipient, you are
hereby notified that any use, disclosure, dissemination, distribution, or
copying of this message, or any attachments, is strictly prohibited. If you
have received this message in error, please advise the sender by reply e-mail,
and delete the message and any attachments. Thank you.
------------------------------
Message: 7
Date: Fri, 13 Feb 2009 10:23:33 +0100
From: Jan Snajder <[email protected]>
Subject: [Haskell-beginners] Re: permuting a list
To: [email protected]
Message-ID: <1234517013.5888.40.ca...@arjuna>
Content-Type: text/plain
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?
> > 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
Ok, this seems to work! (after replacing '[n..1]' with [n,n-1,..1] as
Daniel noted). Great!
Why do I need 'forall a' ? Aren't type variables implicitly universaly
quantified?
j.
------------------------------
Message: 8
Date: Fri, 13 Feb 2009 07:29:48 -0200
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] Re: permuting a list
To: [email protected]
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Fri, Feb 13, 2009 at 7:23 AM, Jan Snajder <[email protected]> wrote:
> Why do I need 'forall a' ? Aren't type variables implicitly universaly
> quantified?
You don't need it, it's just a matter of style. Some prefer to make it
explicit, others not. I think it is only useful when you have lots of
existentials nearby.
--
Felipe.
------------------------------
Message: 9
Date: Fri, 13 Feb 2009 10:56:16 +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?
>
> > > 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
>
> Ok, this seems to work! (after replacing '[n..1]' with [n,n-1,..1] as
> Daniel noted). Great!
>
> Why do I need 'forall a' ? Aren't type variables implicitly universaly
> quantified?
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.
>
> j.
Cheers,
Daniel
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 11
****************************************
