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 ****************************************