[Haskell-cafe] Re: Producing MinimumValue

[Sebastian Sylvan]

On 19/07/07, Aaron Denney <wnoise at ofb.net> wrote:
> On 2007-07-19, Sebastian Sylvan <sebastian.sylvan at gmail.com> wrote:
> > On 19/07/07, Steve Schafer <steve at fenestra.com> 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