5 ms·
The top-voted answer mentions that the example O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does th
by lmkg 15y ago
The top-voted answer mentions that the example O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not?
I sort of view lazily-evaluated data structures (like generator expressions) as not data structures at all, but rather control flow constructs[1]. They control when, how, and if expressions are evaluated and results are returned. As a result, I feel that using lazy equivalents for your data structures qualifies as an algorithmic change. In fact, one could manually code lazy data access in an eager language, and the resulting algorithm would look very different from the original.
On the other hand, the laziness is enabled by the purity of the algorithm, so... well, it depends on your perspective. You could say that laziness makes the functional equivalent just as fast, or you could say that the functional equivalent is slower, but there's a different functional algorithm that is just as fast.
[1] Except they're still data structures. They're like, a quantum superposition of data structure and control-flow operator. Which one it is depends on how you look at it.
- eru 15y agoYes. That's why in Haskell programming a common sentiment is that data structures are control structures. And why we need non-linear data structures for concurrent execution (http://vimeo.com/6624203 http://vimeo.com/6624203).
- agumonkey 15y agoI think of Data structures as extension, value sets. Function as intension. They are dual to each other, sort of, modulo `some` energy.
- jpendry 15y agoYou're getting dangerously close to describing continuations. And I think it's important to remember that just because a programming language doesn't give you access to a data structure, it doesn't mean it's not using it under the covers. The call stack is a data structure in all programming languages, only a few provide you with easy access to it.
- nandemo 15y ago> O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not? I don't think anyone is claiming that it is the same algorithm. Rather, they're claiming that using lazy evaluation gives you more choice of algorithms; and one of these algorithms is faster than the best algorithm under strict evaluation. I haven't been able to download Bird et. al's paper, but I wouldn't assume it's simply "implementing the same algorithm in Haskell instead of strict ML".