Lambda the Ultimate

From the abstract:

When programmers develop and evolve software, they frequently copy and paste (C&P) code from an existing code base, or sources such as web pages or documentation. We believe that programmers follow a small number of well defined C&P usage patterns when they program, and understanding these patterns would enable us to design tools to improve the quality of software.

I noticed this paper in the references of a (draft) paper on subtext, which is a project previously discussed on LtU. I think that this is interesting from a language design perspective and couldn't find a previous discussion on LtU. (I'll defer my other comments (read: critique) to a later post - if any.)

Consider the following Haskell-ish functions: (I'm not actually gonna type them into hugs or anything so forgive any syntactical errors)

naiveMin [x]  = x
naiveMin x:xs = if x < y then x else y where y = naiveMin xs

qsort []   = []
qsort x:xs = qsort [ a | a <- xs, a < x] ++ [x] ++ qsort [ b | b <- xs, b >= x ]

lazyMin xs = head (take 1 (qsort xs))

Now what I'm asking is, if we have lazy evaluation semantics, in the lazyMin function, when we call qsort, will the only part that gets evaluated be

qsort [ a | a <- xs, a < x]

or possibly at most:

qsort [ a | a <- xs, a < x] ++ [x]

since we are only taking 1 element from the list. Does this mean it's runtime is O(n), like naiveMin? Are we using lazy evaluation to complete change how much code gets run from outside the function? I'm guessing the answer is probably yes, which also kind of turned on the light-bulb as far as the usefulness of lazy evaluation goes. (Oh yeah you can have an infinite list, but um, so what?). I just want to make sure I'm not missing anything here.