Re:What is the asymptotic cost of purely functional programm...
by nandemo on Wednesday April 11, 2012 @09:22PM
(#3830526)
> 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".
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".