- About Scala
- In the Enterprise
- Scala Community
- Language Research
- In the Press
- The Scala Team
- Scala's Prehistory
- Contact Us
- Learning Scala
- Tour of Scala
- Scala API
- Setup & Getting Started
- Programming Guides
- Other Guides
- Code Examples
- Scala Developers
Re: fold/reduce vs foldLeft/reduceLeft?
Why isn't it, though? It seems to me that having O(n) heap space (for
the reversed collection) would be superior to having O(n) stack space,
which may blow up your stack. And they're both O(n) runtime, so
risking a stack overflow seems much more dangerous than running a
constant factor slower.
On Sat, Feb 11, 2012 at 7:32 AM, Rex Kerr wrote:
> On Sat, Feb 11, 2012 at 5:59 AM, Alex Repain wrote:
>> 2012/2/10 Rex Kerr
>>> On Fri, Feb 10, 2012 at 1:36 PM, Haoyi Li wrote:
>>>> Hello Everyone,
>>>> I've been learning scala recently (already know java/c#/python) and
>>>> been thoroughly enjoying the higher order collections functions.
>>>> filter/map is pretty obvious, and I've more or less figured out
>>>> foldLeft/reduceLeft. I've heard somewhere that you probably shouldn't
>>>> use foldRight/reduceRight because of O(n^2) complexity
>>> That would be a strange implementation. The typical implementation
>>> requires O(n) stack space, which is the real problem--for many collections
>>> of practical size, you throw stack overflow exceptions.
>> Does it have to be on the stack though ? Can't the function be tail
>> recursive on the reversed collection ?
> Of course. xs.foldRight(z)(f) is the same as xs.reverse.foldLeft(z)((a,b)
> => f(b,a)). It's often not implemented that way in the library, however.