Send Beginners mailing list submissions to
beginners@haskell.org
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
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Calculating Time Complexity (Adrian Neumann)
2. deleteM :: (Ord a) => a -> Maybe (Set a) -> Maybe (Set a)
(Martin Hofmann)
3. Re: deleteM :: (Ord a) => a -> Maybe (Set a) -> Maybe (Set
a) (Heinrich Apfelmus)
4. Re: Calculating Time Complexity (Brent Yorgey)
5. Follow up to reference request (Alan Cameron)
6. Re: Follow up to reference request (Andrew Wagner)
7. Re: Follow up to reference request (David Frey)
8. Function Type Confusion .. (Tom Poliquin)
9. Re: Function Type Confusion .. (Yitzchak Gale)
----------------------------------------------------------------------
Message: 1
Date: Mon, 26 Jan 2009 08:31:48 +0100
From: Adrian Neumann <aneum...@inf.fu-berlin.de>
Subject: Re: [Haskell-beginners] Calculating Time Complexity
To: beginners@haskell.org
Message-ID: <643bc7f7-e42e-492f-ab4d-fec7fd35c...@inf.fu-berlin.de>
Content-Type: text/plain; charset="us-ascii"
With iterative algorithms like the one you posted it's usually
reduced to "count the loops". Here we have two nested for-loops, each
going from 1 to n. In each loop we do some constant amount of work,
so we get (c1*n)*(c2*n) = (c1*c2)*n^2 -> Theta(n^2).
With recursion it's usually a bit more complicated, as you have to
find a closed form. There are however nice lemmata you can use, like
the http://en.wikipedia.org/wiki/Master_theorem
Regards,
Adrian
Am 26.01.2009 um 01:04 schrieb Matthew J. Williams:
> Dear all,
>
> In general terms, how would one calculate the time complexity of a
> given algorithm? Feel free to make use of my pseudo code in your
> answer:
>
> /* input:
> 2-D array A of size n by n
> output: a number max */
> Max := 0
> For i := 1 to n
> sum := 0
> For j := 1 to n
> sum := sum + A[i][j]
> End for
> If sum > max then max := sum
> End for
> Output max
>
> Sincerely
> Matthew J. Williams
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 194 bytes
Desc: Signierter Teil der Nachricht
Url :
http://www.haskell.org/pipermail/beginners/attachments/20090126/c4a806e2/PGP-0001.bin
------------------------------
Message: 2
Date: Mon, 26 Jan 2009 10:33:36 +0100
From: Martin Hofmann <martin.hofm...@uni-bamberg.de>
Subject: [Haskell-beginners] deleteM :: (Ord a) => a -> Maybe (Set a)
-> Maybe (Set a)
To: beginners@haskell.org
Message-ID: <1232962416.6142.14.ca...@ios.cogsys.wiai.uni-bamberg.de>
Content-Type: text/plain
I often come across the problem to insert into a collection which might
not exist yet, or delete from it and want the collection to be deleted
if it is empty afterwards.
I always end up with these two functions:
deleteM :: (Ord a) => a -> Maybe (Set a) -> Maybe (Set a)
deleteM e s =
liftM (S.delete e) s >>= \s' ->
if S.null s' then return s' else Nothing
insertM :: (Ord a) => a -> Maybe (Set a) -> Maybe (Set a)
insertM e s =
case s of
(Just s') -> return $ S.insert e s'
Nothing -> return $ S.insert S.empty
Is there a way to express each in a (polymorphic) point-free one-liner?
If not, why isn't there such a function for the standard collection,
because IMHO this is what you need when using 'alter'.
Thanks,
Martin
------------------------------
Message: 3
Date: Mon, 26 Jan 2009 11:22:51 +0100
From: Heinrich Apfelmus <apfel...@quantentunnel.de>
Subject: [Haskell-beginners] Re: deleteM :: (Ord a) => a -> Maybe (Set
a) -> Maybe (Set a)
To: beginners@haskell.org
Message-ID: <glk2sj$9o...@ger.gmane.org>
Content-Type: text/plain; charset=ISO-8859-15
Martin Hofmann wrote:
> I often come across the problem to insert into a collection which might
> not exist yet, or delete from it and want the collection to be deleted
> if it is empty afterwards.
>
> I always end up with these two functions:
>
>
> deleteM :: (Ord a) => a -> Maybe (Set a) -> Maybe (Set a)
> deleteM e s =
> liftM (S.delete e) s >>= \s' ->
> if S.null s' then return s' else Nothing
>
> insertM :: (Ord a) => a -> Maybe (Set a) -> Maybe (Set a)
> insertM e s =
> case s of
> (Just s') -> return $ S.insert e s'
> Nothing -> return $ S.insert S.empty
>
> Is there a way to express each in a (polymorphic) point-free one-liner?
> If not, why isn't there such a function for the standard collection,
> because IMHO this is what you need when using 'alter'.
Yes, there is a way. :)
deleteM e = (\s -> if S.null s then Just s else Nothing) . S.delete e
insertM e = Just . S.insert e . maybe S.empty id
The maybe function is from Data.Maybe .
I did wonder why you want to delete the empty set, but now I see that
you need it for alter .
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 4
Date: Mon, 26 Jan 2009 07:41:41 -0500
From: Brent Yorgey <byor...@seas.upenn.edu>
Subject: Re: [Haskell-beginners] Calculating Time Complexity
To: beginners@haskell.org
Message-ID: <20090126124141.ga11...@seas.upenn.edu>
Content-Type: text/plain; charset=us-ascii
On Mon, Jan 26, 2009 at 12:04:48AM +0000, Matthew J. Williams wrote:
> Dear all,
>
> In general terms, how would one calculate the time complexity of a given
> algorithm? Feel free to make use of my pseudo code in your answer:
>
> /* input:
> 2-D array A of size n by n
> output: a number max */
> Max := 0
> For i := 1 to n
> sum := 0
> For j := 1 to n
> sum := sum + A[i][j]
> End for
> If sum > max then max := sum
> End for
> Output max
This being a Haskell mailing list, I couldn't help also translating
this code into simple Haskell:
maxRowSum :: (Num a, Ord a) => [[a]] -> a
maxRowSum = maximum . map sum
In this form it's a little harder to see how many operations are being
done (and hence the time complexity), however!
-Brent
------------------------------
Message: 5
Date: Mon, 26 Jan 2009 22:22:05 -0000
From: "Alan Cameron" <alan.came...@iname.com>
Subject: [Haskell-beginners] Follow up to reference request
To: <beginners@haskell.org>
Message-ID: <dc9135cdd087428c8ef76b682528f...@alanxps>
Content-Type: text/plain; charset="us-ascii"
Hi,
I am indebted to Andrew Wagner for pointing me in the direction of the book
http://book.realworldhaskell.org/read/
Which I now have time to study. Everything was going fine until I got to the
section in Getting Started where it gives A Simple Program.
Now as someone who is used to the Windows environment CLI is not my forte.
Following instructions which appear to be incomplete I created a file of the
program WC.hs but where should it go?
I tried various places until I reread the :? For the :cd command.
Ah I said that's what I need to do put it in a folder and change the Dir.
Now I can find the file with the :edit command.
Did the same with the file quux.txt same place.
Now run the command $ runghc WC < quux.txt
<interactive>:1:0: parse error on input '$'
What have I done wrong or not done?
It does say "at a shell or command prompt" what's that??
I reverted to the installation instructions provided by GHC for Windows.
2.2 Installing on Windows
2.2.1 Installing GHC on Windows
Checked all that had been done correctly.
Enter the program line 1>
bash$ cat main.hs
<interactive>:1:0: parse error on input '$'
Now bash looks like a modified prompt??
So what is happening?
Regards to all and TIA for reply.
Alan Cameron
------------------------------
Message: 6
Date: Mon, 26 Jan 2009 17:44:58 -0500
From: Andrew Wagner <wagner.and...@gmail.com>
Subject: Re: [Haskell-beginners] Follow up to reference request
To: "alan.came...@iname.com" <alan.came...@iname.com>
Cc: "<beginners@haskell.org>" <beginners@haskell.org>
Message-ID: <65c14ba6-c0ac-49c5-898b-d301f70cb...@gmail.com>
Content-Type: text/plain; charset=us-ascii; format=flowed;
delsp=yes
Alan,
I'd love to help you get started coding in haskell. It sounds like it
might be easier to do interactively though. Can you get on the
#haskell channel on IRC? I'm in and out of there as chessguy and will
be on later tonight.
On Jan 26, 2009, at 5:22 PM, "Alan Cameron" <alan.came...@iname.com>
wrote:
> Hi,
>
> I am indebted to Andrew Wagner for pointing me in the direction of
> the book
> http://book.realworldhaskell.org/read/
> Which I now have time to study. Everything was going fine until I
> got to the
> section in Getting Started where it gives A Simple Program.
>
> Now as someone who is used to the Windows environment CLI is not my
> forte.
> Following instructions which appear to be incomplete I created a
> file of the
> program WC.hs but where should it go?
>
> I tried various places until I reread the :? For the :cd command.
> Ah I said that's what I need to do put it in a folder and change the
> Dir.
>
> Now I can find the file with the :edit command.
> Did the same with the file quux.txt same place.
>
> Now run the command $ runghc WC < quux.txt
>
> <interactive>:1:0: parse error on input '$'
>
> What have I done wrong or not done?
>
> It does say "at a shell or command prompt" what's that??
>
> I reverted to the installation instructions provided by GHC for
> Windows.
> 2.2 Installing on Windows
> 2.2.1 Installing GHC on Windows
>
> Checked all that had been done correctly.
>
> Enter the program line 1>
>
> bash$ cat main.hs
> <interactive>:1:0: parse error on input '$'
>
> Now bash looks like a modified prompt??
> So what is happening?
>
> Regards to all and TIA for reply.
>
> Alan Cameron
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 7
Date: Mon, 26 Jan 2009 14:59:19 -0800
From: "David Frey" <dpf...@shaw.ca>
Subject: Re: [Haskell-beginners] Follow up to reference request
To: beginners@haskell.org
Message-ID: <biddz4eg.1233010759.6442310.df...@localhost>
Content-Type: text/plain; charset=ISO-8859-1
On 1/26/2009, "Alan Cameron" <alan.came...@iname.com> wrote:
>Hi,
>
>I am indebted to Andrew Wagner for pointing me in the direction of the book
>http://book.realworldhaskell.org/read/
>Which I now have time to study. Everything was going fine until I got to the
>section in Getting Started where it gives A Simple Program.
>
>Now as someone who is used to the Windows environment CLI is not my forte.
>Following instructions which appear to be incomplete I created a file of the
>program WC.hs but where should it go?
Put it in any directory you want, but I would suggest putting it in a
directory named "Chapter 1" inside another directory named "Real
World Haskell".
>I tried various places until I reread the :? For the :cd command.
>Ah I said that's what I need to do put it in a folder and change the Dir.
>
>Now I can find the file with the :edit command.
>Did the same with the file quux.txt same place.
It's probably easier to just use the Windows GUI to browse to your
Haskell sources and open them directly in the editor.
>
>Now run the command $ runghc WC < quux.txt
>
><interactive>:1:0: parse error on input '$'
>
>What have I done wrong or not done?
The '$' character is not actually part of the command. It's just
written in the book so that you know that what follows is a command that
you should type into the command line.
So:
$ ghci File.hs
means
1) Open a console, (terminal, command line prompt or whatever you want to
call it)
2) Use the cd command to go into that directory containing File.hs
3) Type (without quotes) "ghci File.hs" and press enter.
Similarly,
ghci> 2 + 3
means type "2 + 3" followed by enter.
I hope that clears things up a bit.
------------------------------
Message: 8
Date: Tue, 27 Jan 2009 09:42:54 -0800
From: Tom Poliquin <poliq...@softcomp.com>
Subject: [Haskell-beginners] Function Type Confusion ..
To: beginners@haskell.org
Message-ID: <200901270942.54234.poliq...@softcomp.com>
Content-Type: text/plain; charset="us-ascii"
I was reading "Arrows and Computation"
http://www.soi.city.ac.uk/~ross/papers/fop.ps.gz
(trying to lose my 'beginner' status) when I saw (on page
one)
add :: (b -> Int) -> (b -> Int) -> (b -> Int)
add f g b = f b + g b
It seemed like the type definition was wrong (short at least).
I tried it anyway ..
module Main where
add :: (b -> Int) -> (b -> Int) -> (b -> Int)
add f g b = f b + g b
main = do
x <- return $ add (+2) (+3) 7
print x
The program compiles and runs and produces '19' !
For fun I loaded into ghci and got what I believe is the proper
type ..
*Main> :t add
add :: (b -> Int) -> (b -> Int) -> b -> Int
When I try the same thing with something simpler
(leaving a bit off the type definition)
I get the expected error (by me) ..
module Main where
dog :: Int -> Int
dog a b = a + b
main = do
x <- return $ dog 2 3
print x
Main.hs:5:0:
The equation(s) for `dog' have two arguments,
but its type `Int -> Int' has only one
What am I missing? .. Apparently something fundamental
about type definitions ..
Any help appreciated.
Tom
------------------------------
Message: 9
Date: Tue, 27 Jan 2009 20:31:23 +0200
From: Yitzchak Gale <g...@sefer.org>
Subject: Re: [Haskell-beginners] Function Type Confusion ..
To: Tom Poliquin <poliq...@softcomp.com>
Cc: beginners@haskell.org
Message-ID:
<2608b8a80901271031l7d44ec42r7afbcc21d3401...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Tom Poliquin wrote:
> add :: (b -> Int) -> (b -> Int) -> (b -> Int)
> add f g b = f b + g b
>
> The program compiles and runs and produces '19' !
>
> For fun I loaded into ghci and got what I believe is the proper
> type ..
>
> *Main> :t add
> add :: (b -> Int) -> (b -> Int) -> b -> Int
>
> When I try the same thing with something simpler
> (leaving a bit off the type definition)
> I get the expected error (by me) ..
In type expressions, the symbol -> is right-associative.
So
... -> (b -> Int)
is exactly the same as
... -> b -> Int
-Yitz
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 7, Issue 21
****************************************
