Re: Best recursion choice for penultimax
Mark P Jones wrote: Moreover, in attempting to optimize the code, you might instead break it and introduce some bugs that will eventually come back and bite. Indeed! If we take Mark Phillips's original version of penultimax as our specification, all four alternate versions are incorrect: They fail to ignore duplicates of the maximum value. Here are fixed versions. penultimax2a :: [Int] - Int penultimax2a ms = penultimax2' ms 0 0 where penultimax2' :: [Int] - Int - Int - Int penultimax2' [] p q = q penultimax2' (m:ms) p q | mp = penultimax2' ms m p | m==p = penultimax2' ms p q | mq = penultimax2' ms p m | otherwise = penultimax2' ms p q penultimax3a :: [Int] - Int penultimax3a ms = snd (maxpenmax ms) where maxpenmax :: [Int] - (Int,Int) maxpenmax [] = (0,0) maxpenmax [m] = (m,0) maxpenmax (m:ms) | mp = (m,p) | m==p = (p,q) | mq = (p,m) | otherwise = (p,q) where (p,q) = maxpenmax ms penultimax1a :: Ord a = [a] - a penultimax1a = head . head . tail . group . sortBy (flip compare) penultimaxa :: Ord a = [a] - a penultimaxa = snd . tournament . map enter where enter x = (x, []) tournament [(x, xds)] = (x, maximum xds) tournament others = tournament (round others) round ((x,xds):(y,yds):others) | xy = (x, y:xds) : rest | x==y = (x, xds++yds) : rest | otherwise = (y, x:yds) : rest where rest = round others round xs = xs -- Dean ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Best recursion choice for penultimax
On Sun, Nov 24, 2002 at 10:06:42PM -0800, Mark P Jones wrote: To your three implementations, let me add another two. If you are looking for the smallest possible definition, consider the following: import List penultimax1 :: Ord a = [a] - a penultimax1 = head . tail . sortBy (flip compare) Hmm, I think penultimax was underspecified. What should be the value of penultimax [3, 4, 5, 5] ? Your version would say 5, while Dr. Phillips's original version would say 4. If 4 is the correct answer, then the definition could be corrected this way: penultimax1' :: Ord a = [a] - a penultimax1' = head . tail . sortBy (flip compare) . nub Doing both sort and nub is probably overkill, though I'm not sure how expensive it actually is if only the first two elements are needed. The order in which sort and nub are applied might make a difference, too. Removing duplicate elements from a sorted list is much simpler than nub: penultimax1'' :: Ord a = [a] - a penultimax1'' = head . tail . uniq . sortBy (flip compare) uniq :: (Eq a) = [a] - [a] uniq (x : y : xs) | x == y = uniq (y : xs) | otherwise = x : uniq (y : xs) uniq xs = xs -- empty and singleton lists Richard Braakman ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: Best recursion choice for penultimax
Some quick tests with Hugs +s on a example list that I constructed with 576 elements give food for thought: reductions cells my one liner 403511483 tournament705312288 your penultimax 1671520180 your penultimax2 746610344 your penultimax3 860513782 And with GHC -O, the results are quite different: Mark's one liner 0.60s tournament 0.25s your penultimax 0.26s your penultimax2 0.25s your penultimax3 0.25s the tests were with random numbers (different seed each time), but there was only a little little fluctuation from run to run. I specialised all the algorithms to Int. Hugs doesn't do much optimisation, so the reductions/cells counts tend to vary quite a bit between programs which GHC will optimise to the same or similar code. The moral, as usual, is YMMV... Cheers, Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: Best recursion choice for penultimax
Thanks for your alternative solutions. (I also take Mark Jones' point that there was an error with some of my initial solutions.) On Mon, 2002-11-25 at 16:36, Mark P Jones wrote: To your three implementations, let me add another two. If you are looking for the smallest possible definition, consider the following: import List penultimax1 :: Ord a = [a] - a penultimax1 = head . tail . sortBy (flip compare) A little more algorithmic sophistication leads to the following alternative that can find the penultimax with only n + log2 n comparisons (approx), where n is the length of the list. Is this n + log(2n) or n + (log n)^2 or perhaps n + log_base_2 n? Also, how did you calculate this? (I am new to O(.) calculations involving lots of recursion (ie in functional languages)) penultimax :: Ord a = [a] - (a, a) penultimax = tournament . map enter where enter x = (x, []) tournament [(x, xds)] = (x, maximum xds) tournament others = tournament (round others) round ((x,xds):(y,yds):others) | x=y = (x, y:xds) : rest | otherwise = (y, x:yds) : rest where rest = round others round xs = xs Neat algorithm eh? But be careful ... It is interesting! | How do I work out which is best to use? Is there | one clear winner, or will they each have pros and | cons? Some quick tests with Hugs +s on a example list that I constructed with 576 elements give food for thought: Thanks for the idea of using hugs +s. I haven't seen this before. reductions cells my one liner 403511483 tournament705312288 your penultimax 1671520180 your penultimax2 746610344 your penultimax3 860513782 Hope this helps (or at least, is entertaining :-) Yes. Thanks! Mark. -- Dr Mark H Phillips Research Analyst (Mathematician) AUSTRICS - smarter scheduling solutions - www.austrics.com Level 2, 50 Pirie Street, Adelaide SA 5000, Australia Phone +61 8 8226 9850 Fax +61 8 8231 4821 Email [EMAIL PROTECTED] ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Best recursion choice for penultimax
On Tue, 2002-11-26 at 02:38, Richard Braakman wrote: penultimax1' :: Ord a = [a] - a penultimax1' = head . tail . sortBy (flip compare) . nub What does nub stand for? (This is the first I've heard of it.) From the definition in List.hs it seems to remove repeats, keeping only the first. Is there documentation on List.hs, along the lines of the A Tour of the Haskell Prelude? Thanks, Mark. -- Dr Mark H Phillips Research Analyst (Mathematician) AUSTRICS - smarter scheduling solutions - www.austrics.com Level 2, 50 Pirie Street, Adelaide SA 5000, Australia Phone +61 8 8226 9850 Fax +61 8 8231 4821 Email [EMAIL PROTECTED] ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: Best recursion choice for penultimax
Hi, (maybe I got the message to the community this time, Mark P ;-) I would like to know if anyone (maybe Mark P) knows the status of Cartesian classes in different Haskell implementations. I.e., does anyone implement the suggested functional dependencies or the less general parameterized type classes? I have need for the multi-variable classes quite often (especially in a genetic algorithm framework I am building in Haskell). Although I would hesitate to extend beyond Haskell 98, if there exist a common view on how to best implement Cartesian classes (read it will be part of Haskell 2) and/or a stable implementation for it, I am willing to be a bit adventurous... /David -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Mark P Jones Sent: Monday, November 25, 2002 1:07 AM To: 'Dr Mark H Phillips' Cc: 'Haskell Mailing List'; Mark P Jones Subject: RE: Best recursion choice for penultimax Hi Mark, | I have just implemented the function penultimax which takes a list | of positive integers and produces the penultimate maximum, that is, | the next biggest integer in the list after the maximum. Eg: | | penultimax [15,7,3,11,5] = 11 To your three implementations, let me add another two. If you are looking for the smallest possible definition, consider the following: import List penultimax1 :: Ord a = [a] - a penultimax1 = head . tail . sortBy (flip compare) In other words, to find the second largest, sort (in descending order, which is why I use flip compare) and then extract the second element. (You could also use (!!1), but I think that head . tail is nicer.) Thanks to lazy evaluation, using sort in this way isn't as expensive as you might think; because we ask only for the first two elements, only a small part of the full sort computation will be needed. A little more algorithmic sophistication leads to the following alternative that can find the penultimax with only n + log2 n comparisons (approx), where n is the length of the list. penultimax :: Ord a = [a] - (a, a) penultimax = tournament . map enter where enter x = (x, []) tournament [(x, xds)] = (x, maximum xds) tournament others = tournament (round others) round ((x,xds):(y,yds):others) | x=y = (x, y:xds) : rest | otherwise = (y, x:yds) : rest where rest = round others round xs = xs The inspiration for this code is a knock-out tournament, treating the values in the input list as teams. To enter the competition, each team is paired with the (initially) empty list of teams that it has defeated. In each round, we play the teams against each other in pairs (if there are an odd number of teams, the last one gets a by to the next round). In each game, the team with the highest value wins, and adds the opponent to its list of victories. The tournament concludes when only one team remains. And here comes the clever part: the penultimax must be the largest entry in the victors list of defeats because it would have won all of its games until, at some point, being knocked out of the competition by the eventual winner. And hence we need only scan that list for its maximum. [I'm afraid I don't know who invented this---I learned about it while teaching a class on algorithms---but the rendering above in Haskell is mine, and could be buggy!] Neat algorithm eh? But be careful ... | How do I work out which is best to use? Is there | one clear winner, or will they each have pros and | cons? Some quick tests with Hugs +s on a example list that I constructed with 576 elements give food for thought: reductions cells my one liner 403511483 tournament705312288 your penultimax 1671520180 your penultimax2 746610344 your penultimax3 860513782 With the caveat that this is just one example (although others I tried gave similar results), the conclusion seems to be that my one liner is probably the winner, beating all of the others in reductions, all but one of the others in space, and with the simplest definition of all. The fact that it is coded entirely using prelude functions might also be a benefit if you use a compile that provides fancy implementations or optimizations for such functions. My advice is that you should always start with the simplest definition (i.e., the one that is easiest to code, easiest to understand, and most easily seen to be correct). You should not worry about rewriting it in what you hope may be a more efficient form unless you find later, by profiling or other means, that its performance really is a problem. (In which case, you'll be able to collect some real, representative data against which you can test and evaluate the alternatives.) For starters, a supposedly improved version might not actually be more efficient (constant
Re: Best recursion choice for penultimax
What does nub stand for? (This is the first I've heard of it.) From the definition in List.hs it seems to remove repeats, keeping only the first. Yes, that's what it does. It doesn't stand for anything, it's a word: nub: small knob or lump, esp. of coal; small residue, stub; point or gist (of matter or story). Concise OED. It's the second or third meaning which is implied here. Hmm, maybe that's not such a great explanation. I wonder who can come up with the best acronym? My contribution is Note Unique Bits John ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: Best recursion choice for penultimax
Hi Mark, | I have just implemented the function penultimax which takes a list | of positive integers and produces the penultimate maximum, that is, | the next biggest integer in the list after the maximum. Eg: | | penultimax [15,7,3,11,5] = 11 To your three implementations, let me add another two. If you are looking for the smallest possible definition, consider the following: import List penultimax1 :: Ord a = [a] - a penultimax1 = head . tail . sortBy (flip compare) In other words, to find the second largest, sort (in descending order, which is why I use flip compare) and then extract the second element. (You could also use (!!1), but I think that head . tail is nicer.) Thanks to lazy evaluation, using sort in this way isn't as expensive as you might think; because we ask only for the first two elements, only a small part of the full sort computation will be needed. A little more algorithmic sophistication leads to the following alternative that can find the penultimax with only n + log2 n comparisons (approx), where n is the length of the list. penultimax :: Ord a = [a] - (a, a) penultimax = tournament . map enter where enter x = (x, []) tournament [(x, xds)] = (x, maximum xds) tournament others = tournament (round others) round ((x,xds):(y,yds):others) | x=y = (x, y:xds) : rest | otherwise = (y, x:yds) : rest where rest = round others round xs = xs The inspiration for this code is a knock-out tournament, treating the values in the input list as teams. To enter the competition, each team is paired with the (initially) empty list of teams that it has defeated. In each round, we play the teams against each other in pairs (if there are an odd number of teams, the last one gets a by to the next round). In each game, the team with the highest value wins, and adds the opponent to its list of victories. The tournament concludes when only one team remains. And here comes the clever part: the penultimax must be the largest entry in the victors list of defeats because it would have won all of its games until, at some point, being knocked out of the competition by the eventual winner. And hence we need only scan that list for its maximum. [I'm afraid I don't know who invented this---I learned about it while teaching a class on algorithms---but the rendering above in Haskell is mine, and could be buggy!] Neat algorithm eh? But be careful ... | How do I work out which is best to use? Is there | one clear winner, or will they each have pros and | cons? Some quick tests with Hugs +s on a example list that I constructed with 576 elements give food for thought: reductions cells my one liner 403511483 tournament705312288 your penultimax 1671520180 your penultimax2 746610344 your penultimax3 860513782 With the caveat that this is just one example (although others I tried gave similar results), the conclusion seems to be that my one liner is probably the winner, beating all of the others in reductions, all but one of the others in space, and with the simplest definition of all. The fact that it is coded entirely using prelude functions might also be a benefit if you use a compile that provides fancy implementations or optimizations for such functions. My advice is that you should always start with the simplest definition (i.e., the one that is easiest to code, easiest to understand, and most easily seen to be correct). You should not worry about rewriting it in what you hope may be a more efficient form unless you find later, by profiling or other means, that its performance really is a problem. (In which case, you'll be able to collect some real, representative data against which you can test and evaluate the alternatives.) For starters, a supposedly improved version might not actually be more efficient (constant factors do matter sometimes!). Moreover, in attempting to optimize the code, you might instead break it and introduce some bugs that will eventually come back and bite. Hope this helps (or at least, is entertaining :-) All the best, Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
