User loginNavigation 
Question about Lazyness and algorithmic runtime analysisConsider the following Haskellish 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 lightbulb 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. By Logan Capaldo at 20060519 23:01  LtU Forum  previous forum topic  next forum topic  other blogs  6018 reads

Browse archivesActive forum topics
New forum topics

Recent comments
4 days 7 hours ago
6 days 2 hours ago
2 weeks 3 days ago
3 weeks 2 days ago
4 weeks 2 days ago
6 weeks 8 hours ago
6 weeks 3 days ago
7 weeks 4 days ago
8 weeks 10 hours ago
8 weeks 14 hours ago