[Haskell-cafe] Re: Producing MinimumValue
Sebastian Sylvan wrote: minimumValue :: [Int] - Int minimumValue ns = head (iSort ns) If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n). Actually, since Haskell is lazy and only the first element is required for minimumValue, the above algorithm should be O(n). Just for reference: http://thread.gmane.org/gmane.comp.lang.haskell.general/15007 Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Producing MinimumValue
On 2007-07-19, Sebastian Sylvan [EMAIL PROTECTED] wrote: On 19/07/07, Steve Schafer [EMAIL PROTECTED] wrote: On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote: The question suggests to use some functions defined in the section, and one of them is iSort. Aha. Well, that one certainly lends itself better to this particular proplen than either map or filter. minimumValue :: [Int] - Int minimumValue ns = head (iSort ns) If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n). Actually, since Haskell is lazy and only the first element is required for minimumValue, the above algorithm should be O(n). I'm pretty sure that it's possible for to get O(n) behaviour, but that it's not guaranteed. It really should depends on the sort supplied. -- Aaron Denney -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Producing MinimumValue
On 19/07/07, Aaron Denney [EMAIL PROTECTED] wrote: On 2007-07-19, Sebastian Sylvan [EMAIL PROTECTED] wrote: On 19/07/07, Steve Schafer [EMAIL PROTECTED] wrote: On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote: The question suggests to use some functions defined in the section, and one of them is iSort. Aha. Well, that one certainly lends itself better to this particular proplen than either map or filter. minimumValue :: [Int] - Int minimumValue ns = head (iSort ns) If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n). Actually, since Haskell is lazy and only the first element is required for minimumValue, the above algorithm should be O(n). I'm pretty sure that it's possible for to get O(n) behaviour, but that it's not guaranteed. It really should depends on the sort supplied. Well iSort is the typical name one gives to insertion sort, so I assumed that was what the algorithm he was referring to. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
