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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
