3 ms·

The example you gave is not of lazy evaluation. An "ORDER BY" that's truly lazy, followed by a LIMIT, would behave like Quickselect [1], meaning that the comple

The example you gave is not of lazy evaluation. An "ORDER BY" that's truly lazy, followed by a LIMIT, would behave like Quickselect [1], meaning that the complexity would be O(n), but not as a special optimization and definitely not for the reasons you mention. Sorting in Haskell behaves like this. When dealing with functional programming (e.g. pure functions, immutable data-structures, referential transparency), sooner or later you need to deal with recursive algorithms and data-structures. Usually tail-recursive, so they take constant stack space, but recursive nonetheless. And when dealing with recursive algorithms or data-structures, you end up wanting laziness, because otherwise you cannot express the algorithms that you want to express. You mentioned LIMIT. This operation can be expressed in terms of "foldRight", a really, really useful operation for functional programming. But here's the catch: if it's not lazy, then it's not going to work for infinite streams (and it should), it will need O(n) memory and depending on implementation, it will probably blow up your stack. My current language is Scala. And in Scala the "foldRight" implemented on the standard collections is totally useless. Which is a pity really. Going back to your original assertion, laziness isn't really about preventing a result to be evaluated, although sometimes that's a useful side-effect. No, lazy evaluation is about being able to short-circuit the iteration ;-) [1] https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect

cousin_it 11y ago
> When dealing with functional programming (e.g. pure functions, immutable data-structures, referential transparency), sooner or later you need to deal with recursive algorithms and data-structures. Usually tail-recursive, so they take constant stack space, but recursive nonetheless. And when dealing with recursive algorithms or data-structures, you end up wanting laziness, because otherwise you cannot express the algorithms that you want to express. This might be tangential to your point, but tail recursion doesn't really work with laziness, e.g. foldl in Haskell takes linear space.
- bad_user 11y ago
  If foldLeft is strict, like in Scala, then it needs constant stack space, but then you can't short-circuit it so you need to traverse the whole list to return a result, which might lead to O(n) space depending on what you want to get out of it. And by tail recursion I'm not necessarily referring to the actual call-stack. Maybe I'm a little loose with the terms here. Tail-recursive algorithms are those that can use constant memory (stack or heap) and which in a language like Scala can be translated to usage of a loop or a trampoline, whereas the actually recursive algorithms are those that really need some sort of stack to work and that grows directly proportional to the input size. Usage of a stack is the definition of recursivity from algorithms books, like Cormen et al. For example doing an in-depth traversal of a balanced tree will really, really need a O(log2 n) stack, regardless if the evaluation is strict or lazy or whatever language tricks you can pull. Does that make any sense? :-)

cousin_it 11y ago

> When dealing with functional programming (e.g. pure functions, immutable data-structures, referential transparency), sooner or later you need to deal with recursive algorithms and data-structures. Usually tail-recursive, so they take constant stack space, but recursive nonetheless. And when dealing with recursive algorithms or data-structures, you end up wanting laziness, because otherwise you cannot express the algorithms that you want to express. This might be tangential to your point, but tail recursion doesn't really work with laziness, e.g. foldl in Haskell takes linear space.

bad_user 11y ago
If foldLeft is strict, like in Scala, then it needs constant stack space, but then you can't short-circuit it so you need to traverse the whole list to return a result, which might lead to O(n) space depending on what you want to get out of it. And by tail recursion I'm not necessarily referring to the actual call-stack. Maybe I'm a little loose with the terms here. Tail-recursive algorithms are those that can use constant memory (stack or heap) and which in a language like Scala can be translated to usage of a loop or a trampoline, whereas the actually recursive algorithms are those that really need some sort of stack to work and that grows directly proportional to the input size. Usage of a stack is the definition of recursivity from algorithms books, like Cormen et al. For example doing an in-depth traversal of a balanced tree will really, really need a O(log2 n) stack, regardless if the evaluation is strict or lazy or whatever language tricks you can pull. Does that make any sense? :-)