Best recursion choice for "penultimax"
Hi, 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 One implementation is: penultimax :: [Int] -> Int penultimax ms = foldr max 0 (filter (<msMax) ms) where msMax = foldr max 0 ms But I can think of two variations which might be more efficient: penultimax2 :: [Int] -> Int penultimax2 ms = penultimax2' ms 0 0 where penultimax2' :: [Int] -> Int -> Int -> Int penultimax2' [] p q = q penultimax2' (m:ms) p q | m>p = penultimax2' ms m p | m>q = penultimax2' ms p m | otherwise = penultimax2' ms p q penultimax3 :: [Int] -> Int penultimax3 ms = snd (maxpenmax ms) where maxpenmax :: [Int] -> (Int,Int) maxpenmax [] = (0,0) maxpenmax [m] = (m,0) maxpenmax (m:ms) | m>p = (m,p) | m>q = (p,m) | otherwise = (p,q) where (p,q) = maxpenmax ms How do I work out which is best to use? Is there one clear "winner", or will they each have pros and cons? 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 mark@austrics.com.au
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 4035 11483 tournament 7053 12288 your penultimax 16715 20180 your penultimax2 7466 10344 your penultimax3 8605 13782 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
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 | m>p = penultimax2' ms m p | m==p = penultimax2' ms p q | m>q = 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) | m>p = (m,p) | m==p = (p,q) | m>q = (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) | x>y = (x, y:xds) : rest | x==y = (x, xds++yds) : rest | otherwise = (y, x:yds) : rest where rest = round others round xs = xs -- Dean
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
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 mark@austrics.com.au
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
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 4035 11483 tournament 7053 12288 your penultimax 16715 20180 your penultimax2 7466 10344 your penultimax3 8605 13782
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 mark@austrics.com.au
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: haskell-admin@haskell.org [mailto:haskell-admin@haskell.org] 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 4035 11483 tournament 7053 12288 your penultimax 16715 20180 your penultimax2 7466 10344 your penultimax3 8605 13782 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 Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
David Bergman wrote (on 26-11-02 01:29 -0500):
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...
What do you mean by "cartesian classes"? Do you mean multi-parameter type classes? They're supported by GHC and Hugs, but not NHC98 or HBC. The same goes for functional dependencies. -- Frank
(I am having problem with my lovely Outlook program, so here I send it again, to the whole group; sorry, Frank...) Frank Atanassow wrote:
David Bergman wrote (on 26-11-02 01:29 -0500):
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...
What do you mean by "cartesian classes"? Do you mean multi-parameter type classes?
They're supported by GHC and Hugs, but not NHC98 or HBC. The same goes
for functional dependencies.
Yes, I meant what is commonly known as multi-parameter type classes, although that name IMHO does not make much sense, since only the explicitly parameterized type class should qualify as a any-parameter type class, with the (non-Haskell syntax) "b in C a", where "a" is the parameter, "C a" the resulting type class, and, finally, "b" the (type) element of the class. Side note: functional dependencies would, admittedly, produce parameters for classes, but only implicitly so. In a regular class declaration, "C a", I would argue that "C" is the class, not being single-parameter, but zero-parameter. It is sometimes unfortunate that the syntax of Haskell makes this look like a constructor... What I meant by cartesian is that using several variables, you would get (also in non-Haskell syntax) "(a, b, c) in C", i.e., the class actually being a subclass of the third cartesian power of the universal (implicit) type class. If both GHC and Hugs support functional dependencies, I would probably dare to wander off into the mysterious land of Haskell 2. A very concrete, but naïve, question: what is the syntax for defining functional dependencies in Hugs and GHC? Since Mark Jones' syntax was abstract in his paper, it is kind of hard to deduce an ASCII equivalence (I have tried to figure out how to create a curly arrow from the keyboard ;-) Thanks, David
A very concrete, but na�ve, question: what is the syntax for defining functional dependencies in Hugs and GHC? Since Mark Jones' syntax was abstract in his paper, it is kind of hard to deduce an ASCII equivalence (I have tried to figure out how to create a curly arrow from the keyboard ;-)
I can't comment on the rest, but for this: class Foo a b c e | a b -> c, b -> c d where ... means "a and b together determing c, and b by itself determines c and d"
Curly enough... Thanks, David -----Original Message----- From: haskell-admin@haskell.org [mailto:haskell-admin@haskell.org] On Behalf Of Hal Daume III Sent: Tuesday, November 26, 2002 1:40 PM To: David Bergman Cc: 'Haskell Mailing List' Subject: RE: "cartesian classes"
A very concrete, but naïve, question: what is the syntax for defining functional dependencies in Hugs and GHC? Since Mark Jones' syntax was abstract in his paper, it is kind of hard to deduce an ASCII equivalence (I have tried to figure out how to create a curly arrow from the keyboard ;-)
I can't comment on the rest, but for this: class Foo a b c e | a b -> c, b -> c d where ... means "a and b together determing c, and b by itself determines c and d" _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
participants (8)
-
David Bergman -
Dean Herington -
Dr Mark H Phillips -
Frank Atanassow -
Hal Daume III -
John Hughes -
Mark P Jones -
Richard Braakman