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 (Alexander Dunlap)
2. Re: permuting a list (Heinrich Apfelmus)
3. Help with RWH exercises wanted (Alan Cameron)
4. Re: Help with RWH exercises wanted (Daniel Fischer)
5. Re: permuting a list (Brent Yorgey)
6. Re: permuting a list (Andrew Wagner)
7. Re: permuting a list (Daniel Fischer)
8. Re: permuting a list (Brent Yorgey)
9. Re: permuting a list (Andrew Wagner)
----------------------------------------------------------------------
Message: 1
Date: Thu, 12 Feb 2009 07:00:34 -0800
From: Alexander Dunlap <[email protected]>
Subject: Re: [Haskell-beginners] permuting a list
To: [email protected]
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On Thu, Feb 12, 2009 at 1:20 AM, Jan Snajder <[email protected]> wrote:
> Hi!
>
> I'm trying to write a list permutation function, and there is in fact a
> nice explanation of how to do it here:
> http://sneakymustard.com/2008/12/23/shuffling-in-haskell
>
> But for the start I wanted to keep things simple and avoid monad
> transformers (since I'm not into this yet). Instead, I'd like to write a
> function of type:
>
>> permute :: [a] -> IO [a]
>
> and so this is what I did:
>
>> permute xs = do
>> let n = length xs - 1
>> arr0 <- newListArray (0, n) xs
>> 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
>
> Unfortunately, what I get is:
>
>> permute :: (MArray a1 a IO) => [a] -> IO [a]
>
> and so when I try to apply this function:
>
>> permute [1,2,3]
>
> this is what I get:
>
> <interactive>:1:0:
> No instance for (MArray a1 t IO)
> arising from a use of `permute' at <interactive>:1:0-14
> Possible fix: add an instance declaration for (MArray a1 t IO)
> In the expression: permute [1, 2, 3]
> In the definition of `it': it = permute [1, 2, 3]
>
> How can I fix this?
>
> Thanx,
> jan
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
The simplest way to do this is to use base v4, which I believe
contains a "permutations" function in Data.List.
Alex
------------------------------
Message: 2
Date: Thu, 12 Feb 2009 16:11:23 +0100
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: permuting a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Patrick LeBoutillier wrote:
>>
>> permute :: [a] -> [[a]]
>> permute xs = [s:ps | (s,ss) <- select xs, ps <- permute ss]
>>
>> select :: [a] -> [(a,[a])]
>> select [] = []
>> select (x:xs) = (x,xs) : [(s,x:ss) | (s,ss) <- select xs]
>
> When I run this in ghci I always get an empty list:
>
> [patri...@fc9i386 haskell]$ ghci permute.hs
> GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help
> Loading package base ... linking ... done.
> [1 of 1] Compiling Main ( permute.hs, interpreted )
> Ok, modules loaded: Main.
> *Main> permute [1,2,3]
> []
>
>
> Am i missing something?
No. The base case
permute [] = [[]]
was missing.
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 3
Date: Thu, 12 Feb 2009 15:19:40 -0000
From: "Alan Cameron" <[email protected]>
Subject: [Haskell-beginners] Help with RWH exercises wanted
To: <[email protected]>
Message-ID: <e219a68c91644cf9849f7b1467f73...@alanxps>
Content-Type: text/plain; charset="us-ascii"
I am baffled by what the correct solution to the exercises in Recursive type
section of Chapter 3 should be.
<Quote>
1. Write the converse of fromList for the List type: a function that takes a
List a and generates a [a].
2. Define a tree type that has only one constructor, like our Java example.
Instead of the Empty constructor, use the Maybe type to refer to a node's
children.
</Quote>
fromList is defined in listADT.hs thus
-- file: ch03/ListADT.hs
fromList (x:xs) = Cons x (fromList xs)
fromList [] = Nil
Tree is defined in Tree.hs thus
-- file: ch03/Tree.hs
data Tree a = Node a (Tree a) (Tree a)
| Empty
deriving (Show)
At this point in the book I fail to find any previous examples which might
lead me to my own solution and there are no "Answers to Exercises" as far as
I can see. I have a feeling that this might be a fundamental piece of
knowledge to assist me in further reading of the book.
Alan Cameron
------------------------------
Message: 4
Date: Thu, 12 Feb 2009 16:38:19 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Help with RWH exercises wanted
To: [email protected], <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Donnerstag, 12. Februar 2009 16:19 schrieb Alan Cameron:
> I am baffled by what the correct solution to the exercises in Recursive
> type section of Chapter 3 should be.
> <Quote>
> 1. Write the converse of fromList for the List type: a function that takes
> a List a and generates a [a].
Follow the example of fromList, pattern match on the constructors of the List
type and specify for each case what to do (there's only one sensible choice)
toList (Cons x xs) = ...
toList Nil = ...
>
> 2. Define a tree type that has only one constructor, like our Java example.
> Instead of the Empty constructor, use the Maybe type to refer to a node's
> children.
> </Quote>
You know the Maybe type:
data Maybe a = Nothing | Just a
, don't you?
If the Java example is what I expect it to be, you just replace the null
reference with Nothing and a non-null subtree with (Just subtree).
>
> fromList is defined in listADT.hs thus
>
> -- file: ch03/ListADT.hs
> fromList (x:xs) = Cons x (fromList xs)
> fromList [] = Nil
>
> Tree is defined in Tree.hs thus
>
> -- file: ch03/Tree.hs
> data Tree a = Node a (Tree a) (Tree a)
>
> | Empty
>
> deriving (Show)
>
> At this point in the book I fail to find any previous examples which might
> lead me to my own solution and there are no "Answers to Exercises" as far
> as I can see. I have a feeling that this might be a fundamental piece of
> knowledge to assist me in further reading of the book.
>
> Alan Cameron
I hope the above hints help you find the solutions yourself, if not, I could
go into more detail.
Cheers,
Daniel
------------------------------
Message: 5
Date: Thu, 12 Feb 2009 11:53:14 -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 10:20:32AM +0100, Jan Snajder wrote:
>
> this is what I get:
>
> <interactive>:1:0:
> No instance for (MArray a1 t IO)
> arising from a use of `permute' at <interactive>:1:0-14
> Possible fix: add an instance declaration for (MArray a1 t IO)
> In the expression: permute [1, 2, 3]
> In the definition of `it': it = permute [1, 2, 3]
>
> How can I fix this?
>
<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>
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 #-}
> 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
We have to give an explicit type annotation on the newListArray, to
tell Haskell what kind of array we want to use. But then we also need
to use the ScopedTypeVariables extension, so that the 'a' in the type
signature for permute scopes over the definition, so that Haskell
knows we want the 'a' in the IOArray Int a to be the same type as the
'a' in the type signature. Otherwise it doesn't know they are the
same and complains.
Also, when I try running permute, it seems to be the identity
function, but I guess that's a separate issue!
-Brent
------------------------------
Message: 6
Date: Thu, 12 Feb 2009 11:58:21 -0500
From: Andrew Wagner <[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="iso-8859-1"
>
> <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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090212/f236ad73/attachment-0001.htm
------------------------------
Message: 7
Date: Thu, 12 Feb 2009 19:20:27 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] permuting a list
To: Brent Yorgey <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Donnerstag, 12. Februar 2009 17:53 schrieb Brent Yorgey:
> On Thu, Feb 12, 2009 at 10:20:32AM +0100, Jan Snajder wrote:
> > this is what I get:
> >
> > <interactive>:1:0:
> > No instance for (MArray a1 t IO)
> > arising from a use of `permute' at <interactive>:1:0-14
> > Possible fix: add an instance declaration for (MArray a1 t IO)
> > In the expression: permute [1, 2, 3]
> > In the definition of `it': it = permute [1, 2, 3]
> >
> > How can I fix this?
>
> <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>
>
> 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 #-}
> >
> > 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
>
> We have to give an explicit type annotation on the newListArray, to
> tell Haskell what kind of array we want to use. But then we also need
> to use the ScopedTypeVariables extension, so that the 'a' in the type
> signature for permute scopes over the definition, so that Haskell
> knows we want the 'a' in the IOArray Int a to be the same type as the
> 'a' in the type signature. Otherwise it doesn't know they are the
> same and complains.
>
> Also, when I try running permute, it seems to be the identity
> function, but I guess that's a separate issue!
>
That's because [n .. 1] is almost always an empty list. That code changes only
lists of length 2. Make it foldM swap arr0 [n, n-1 .. 1] and it works.
*Main> permute [1 .. 5]
[3,2,1,5,4]
> -Brent
------------------------------
Message: 8
Date: Thu, 12 Feb 2009 13:33:29 -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 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).
-Brent
------------------------------
Message: 9
Date: Thu, 12 Feb 2009 13:45:22 -0500
From: Andrew Wagner <[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="iso-8859-1"
Hrmm, I suppose you're right. I was thinking that we could magically write
permute so that it wound up with n! thunks in an array, and then grab the
nth element in constant time. I guess that's not very correct. And by "not
very" I mean "not even close to".
On Thu, Feb 12, 2009 at 1:33 PM, Brent Yorgey <[email protected]>wrote:
> 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).
>
> -Brent
> _______________________________________________
> 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/20090212/8dc5f5ec/attachment.htm
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 10
****************************************
