Re: avoid foldRight stack over flow by using for loop

I think this is general restriction. It cannot be used for any large collection.

btw, I wrote a similar code in different language.

fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
var a0 = a;
for (var iter = bs.iterator(); iter.hasNext(); ) {
val b = iter.next();
a0 := f(a0, b);
}
return a0;
}

It is so simple, I wondered there might have been another
consideration for this issue..

nc

On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral wrote:
> You could always use a collection more suited to foldRight too.
>
> On Mon, Apr 12, 2010 at 6:39 PM, calathus wrote:
>>
>> It is enough to make stack overflow to use just 3000 elements in my
>> environment.
>>
>> (1 to 3000).toList.foldRight(0)(_ + _)
>>
>> this is practically very small limit.
>>
>> nc
>>
>>
>> On Mon, Apr 12, 2010 at 2:30 PM, calathus wrote:
>> > Hi,
>> > There is relatively small upper limit for foldRight to avoid stack over
>> > flow.
>> > for instance,  following code will fail with stack over flow
>> >
>> > (1 to 999999).toList.foldRight(0)(_ + _)
>> >
>> > In particular, collection object will often contain much larger number
>> > of elements, this problem will limit the usability of foldRight.
>> > I decided not to use the method, and use for loop instead.
>> > But if these library avoid recursion in the implementation of
>> > foldRight, it would not have such problem and application will be more
>> > declarative.
>> >
>> > Are there any action for this?
>> >
>> > nc
>> >
>
>
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
>

On Mon, Apr 12, 2010 at 02:51:25PM -0700, calathus wrote:
> It is so simple, I wondered there might have been another
> consideration for this issue..

As always, searching trac is revealing.

https://lampsvn.epfl.ch/trac/scala/ticket/2818
"List.foldRight throws StackOverflowError"
(closed wontfix)

Although I admit I kind of like john connor's idea. Has a certain
low-elegance, high-practicality cunning.

I thought foldLeft is also using recursion, but it seems not using it.

(1 to 9999999).toList.foldLeft(0)(_ + _)

the above code failed with java.lang.OutOfMemoryError: Java heap space.
So I will use foldLeft if it is possible.

But for some data structure like array, would it have the same behavior?
This is because List is difficult to reverse the order?
If we use a collection like Vector which can provide efficient reverse
iterator, would it use iterator instead of recursion?

But in general, List is so frequent used structure, this kind of
difference should be pointed out somewhere(already??)

nc

On Mon, Apr 12, 2010 at 2:52 PM, martin odersky wrote:
>
>
> On Mon, Apr 12, 2010 at 11:30 PM, calathus wrote:
>>
>> Hi,
>> There is relatively small upper limit for foldRight to avoid stack over
>> flow.
>> for instance,  following code will fail with stack over flow
>>
>> (1 to 999999).toList.foldRight(0)(_ + _)
>>
>> In particular, collection object will often contain much larger number
>> of elements, this problem will limit the usability of foldRight.
>> I decided not to use the method, and use for loop instead.
>
> But a for loop corresponds to a foldLeft, not a foldRight. Why not use
> foldLeft?
>

As Martin said, that's a foldLeft down there, not a foldRight. Anyway, you think incorrectly. Just staying with the "to" methods and leaving Map and Set out of it, it works every everyone except List and Stream. Ie, it works with toTraversable, toIterable, toIterator, toSeq, toIndexedSeq and toArray.

On Mon, Apr 12, 2010 at 6:51 PM, calathus <calathus [at] gmail [dot] com> wrote:

I think this is general restriction. It cannot be used for any large collection.

btw, I wrote a similar code in different language.

fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
   var a0 = a;
   for (var iter = bs.iterator(); iter.hasNext(); ) {
       val b = iter.next();
       a0 := f(a0, b);
   }
   return a0;
}

It is so simple, I wondered there might have been another
consideration for this issue..

nc



On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
> You could always use a collection more suited to foldRight too.
>
> On Mon, Apr 12, 2010 at 6:39 PM, calathus <calathus [at] gmail [dot] com> wrote:
>>
>> It is enough to make stack overflow to use just 3000 elements in my
>> environment.
>>
>> (1 to 3000).toList.foldRight(0)(_ + _)
>>
>> this is practically very small limit.
>>
>> nc
>>
>>
>> On Mon, Apr 12, 2010 at 2:30 PM, calathus <calathus [at] gmail [dot] com> wrote:
>> > Hi,
>> > There is relatively small upper limit for foldRight to avoid stack over
>> > flow.
>> > for instance,  following code will fail with stack over flow
>> >
>> > (1 to 999999).toList.foldRight(0)(_ + _)
>> >
>> > In particular, collection object will often contain much larger number
>> > of elements, this problem will limit the usability of foldRight.
>> > I decided not to use the method, and use for loop instead.
>> > But if these library avoid recursion in the implementation of
>> > foldRight, it would not have such problem and application will be more
>> > declarative.
>> >
>> > Are there any action for this?
>> >
>> > nc
>> >
>
>
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
>

--
Daniel C. Sobral

I travel to the future all the time.

On Mon, Apr 12, 2010 at 03:05:58PM -0700, calathus wrote:
> But for some data structure like array, would it have the same
> behavior? This is because List is difficult to reverse the order? If
> we use a collection like Vector which can provide efficient reverse
> iterator, would it use iterator instead of recursion?

There's always the last resort available, trying it out:

scala> Vector(1 to 10000000: _*).foldRight(0)(_ + _)
res0: Int = -2004260032

scala> Vector(1 to 10000000: _*).toArray.foldRight(0)(_ + _)
res1: Int = -2004260032

I agree that more specialized knowledge is required than ought to be
necessary.

some variation is:

def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op) else z )
else {
toArray.foldRight(z)(op)
}
}

although I have not tested this code.

But I tested this works.
(1 to 999999).toList.toArray.foldRight(0)(_ + _)

but this throws StackOver flow exception.
(1 to 999999).toList.iterator.foldRight(0)(_ + _)

So this fix looks not bad. it increase the usability of foldRight for List.

nc.

On Mon, Apr 12, 2010 at 2:51 PM, calathus wrote:
> I think this is general restriction. It cannot be used for any large collection.
>
> btw, I wrote a similar code in different language.
>
> fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
>    var a0 = a;
>    for (var iter = bs.iterator(); iter.hasNext(); ) {
>        val b = iter.next();
>        a0 := f(a0, b);
>    }
>    return a0;
> }
>
> It is so simple, I wondered there might have been another
> consideration for this issue..
>
> nc
>
>
>
> On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral wrote:
>> You could always use a collection more suited to foldRight too.
>>
>> On Mon, Apr 12, 2010 at 6:39 PM, calathus wrote:
>>>
>>> It is enough to make stack overflow to use just 3000 elements in my
>>> environment.
>>>
>>> (1 to 3000).toList.foldRight(0)(_ + _)
>>>
>>> this is practically very small limit.
>>>
>>> nc
>>>
>>>
>>> On Mon, Apr 12, 2010 at 2:30 PM, calathus wrote:
>>> > Hi,
>>> > There is relatively small upper limit for foldRight to avoid stack over
>>> > flow.
>>> > for instance,  following code will fail with stack over flow
>>> >
>>> > (1 to 999999).toList.foldRight(0)(_ + _)
>>> >
>>> > In particular, collection object will often contain much larger number
>>> > of elements, this problem will limit the usability of foldRight.
>>> > I decided not to use the method, and use for loop instead.
>>> > But if these library avoid recursion in the implementation of
>>> > foldRight, it would not have such problem and application will be more
>>> > declarative.
>>> >
>>> > Are there any action for this?
>>> >
>>> > nc
>>> >
>>
>>
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>>
>

scala.List is a strict immutable singly linked list. This has
consequences. Try writing your own foldRight without changing any of
these three adjectives.

Tony Morris
http://tmorris.net/

On Apr 13, 2010, at 8:48, calathus wrote:

> some variation is:
>
> def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
> if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op)
> else z )
> else {
> toArray.foldRight(z)(op)
> }
> }
>
> although I have not tested this code.
>
> But I tested this works.
> (1 to 999999).toList.toArray.foldRight(0)(_ + _)
>
> but this throws StackOver flow exception.
> (1 to 999999).toList.iterator.foldRight(0)(_ + _)
>
> So this fix looks not bad. it increase the usability of foldRight
> for List.
>
> nc.
>
> On Mon, Apr 12, 2010 at 2:51 PM, calathus wrote:
>> I think this is general restriction. It cannot be used for any
>> large collection.
>>
>> btw, I wrote a similar code in different language.
>>
>> fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
>> var a0 = a;
>> for (var iter = bs.iterator(); iter.hasNext(); ) {
>> val b = iter.next();
>> a0 := f(a0, b);
>> }
>> return a0;
>> }
>>
>> It is so simple, I wondered there might have been another
>> consideration for this issue..
>>
>> nc
>>
>>
>>
>> On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral
>> wrote:
>>> You could always use a collection more suited to foldRight too.
>>>
>>> On Mon, Apr 12, 2010 at 6:39 PM, calathus
>>> wrote:
>>>>
>>>> It is enough to make stack overflow to use just 3000 elements in my
>>>> environment.
>>>>
>>>> (1 to 3000).toList.foldRight(0)(_ + _)
>>>>
>>>> this is practically very small limit.
>>>>
>>>> nc
>>>>
>>>>
>>>> On Mon, Apr 12, 2010 at 2:30 PM, calathus
>>>> wrote:
>>>>> Hi,
>>>>> There is relatively small upper limit for foldRight to avoid
>>>>> stack over
>>>>> flow.
>>>>> for instance, following code will fail with stack over flow
>>>>>
>>>>> (1 to 999999).toList.foldRight(0)(_ + _)
>>>>>
>>>>> In particular, collection object will often contain much larger
>>>>> number
>>>>> of elements, this problem will limit the usability of foldRight.
>>>>> I decided not to use the method, and use for loop instead.
>>>>> But if these library avoid recursion in the implementation of
>>>>> foldRight, it would not have such problem and application will
>>>>> be more
>>>>> declarative.
>>>>>
>>>>> Are there any action for this?
>>>>>
>>>>> nc
>>>>>
>>>
>>>
>>>
>>> --
>>> Daniel C. Sobral
>>>
>>> I travel to the future all the time.
>>>
>>

What do you mean by "strict" in this sense?  Both cal's and my solutions work perfectly well--mine for any immutable data structure--even if it does transiently use mutable arrays (accessible only within that method).

The machine's stack, incidentally, is a mutable array, so I don't think that should be a problem.

I'm much more worried about infinite collections where foldRight does not make logical sense anyway.  It would be nice to have a well-defined divergence mode (e.g. throw an InfinityIsUnimplementable exception instead of overflowing the stack).

  --Rex

On Tue, Apr 13, 2010 at 5:38 PM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:

scala.List is a strict immutable singly linked list. This has consequences. Try writing your own foldRight without changing any of these three adjectives.

Tony Morris
http://tmorris.net/


On Apr 13, 2010, at 8:48, calathus <calathus [at] gmail [dot] com> wrote:

some variation is:

def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
 if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op) else z )
 else {
  toArray.foldRight(z)(op)
 }
}

although I have not tested this code.

But I tested this works.
(1 to 999999).toList.toArray.foldRight(0)(_ + _)

but this throws StackOver flow exception.
(1 to 999999).toList.iterator.foldRight(0)(_ + _)

So this fix looks not bad. it increase the usability of foldRight for List.

nc.

On Mon, Apr 12, 2010 at 2:51 PM, calathus <calathus [at] gmail [dot] com> wrote:

I think this is general restriction. It cannot be used for any large collection.

btw, I wrote a similar code in different language.

fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
  var a0 = a;
  for (var iter = bs.iterator(); iter.hasNext(); ) {
      val b = iter.next();
      a0 := f(a0, b);
  }
  return a0;
}

It is so simple, I wondered there might have been another
consideration for this issue..

nc



On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:

You could always use a collection more suited to foldRight too.

On Mon, Apr 12, 2010 at 6:39 PM, calathus <calathus [at] gmail [dot] com> wrote:

It is enough to make stack overflow to use just 3000 elements in my
environment.

(1 to 3000).toList.foldRight(0)(_ + _)

this is practically very small limit.

nc


On Mon, Apr 12, 2010 at 2:30 PM, calathus <calathus [at] gmail [dot] com> wrote:

Hi,
There is relatively small upper limit for foldRight to avoid stack over
flow.
for instance,  following code will fail with stack over flow

(1 to 999999).toList.foldRight(0)(_ + _)

In particular, collection object will often contain much larger number
of elements, this problem will limit the usability of foldRight.
I decided not to use the method, and use for loop instead.
But if these library avoid recursion in the implementation of
foldRight, it would not have such problem and application will be more
declarative.

Are there any action for this?

nc

--
Daniel C. Sobral

I travel to the future all the time.

By strict I mean fully evaluated. The implications of these three
properties of List make it impossible to write a foldRight that does not
exhibit the behaviour originally described (cal's "solution" is
incorrect and I didn't see yours).

foldRight "makes more sense" for infinite data structures.
Unfortunately, scala.Stream's foldRight is broken. What "doesn't make
sense" for infinite data structures is foldLeft where "doesn't make
sense" means "does not terminate."

Rex Kerr wrote:
> What do you mean by "strict" in this sense? Both cal's and my solutions
> work perfectly well--mine for any immutable data structure--even if it does
> transiently use mutable arrays (accessible only within that method).
>
> The machine's stack, incidentally, is a mutable array, so I don't think that
> should be a problem.
>
> I'm much more worried about infinite collections where foldRight does not
> make logical sense anyway. It would be nice to have a well-defined
> divergence mode (e.g. throw an InfinityIsUnimplementable exception instead
> of overflowing the stack).
>
> --Rex
>
> On Tue, Apr 13, 2010 at 5:38 PM, Tony Morris wrote:
>
>
>> scala.List is a strict immutable singly linked list. This has consequences.
>> Try writing your own foldRight without changing any of these three
>> adjectives.
>>
>> Tony Morris
>> http://tmorris.net/
>>
>>
>>
>> On Apr 13, 2010, at 8:48, calathus wrote:
>>
>> some variation is:
>>
>>> def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
>>> if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op) else z )
>>> else {
>>> toArray.foldRight(z)(op)
>>> }
>>> }
>>>
>>> although I have not tested this code.
>>>
>>> But I tested this works.
>>> (1 to 999999).toList.toArray.foldRight(0)(_ + _)
>>>
>>> but this throws StackOver flow exception.
>>> (1 to 999999).toList.iterator.foldRight(0)(_ + _)
>>>
>>> So this fix looks not bad. it increase the usability of foldRight for
>>> List.
>>>
>>> nc.
>>>
>>> On Mon, Apr 12, 2010 at 2:51 PM, calathus wrote:
>>>
>>>
>>>> I think this is general restriction. It cannot be used for any large
>>>> collection.
>>>>
>>>> btw, I wrote a similar code in different language.
>>>>
>>>> fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
>>>> var a0 = a;
>>>> for (var iter = bs.iterator(); iter.hasNext(); ) {
>>>> val b = iter.next();
>>>> a0 := f(a0, b);
>>>> }
>>>> return a0;
>>>> }
>>>>
>>>> It is so simple, I wondered there might have been another
>>>> consideration for this issue..
>>>>
>>>> nc
>>>>
>>>>
>>>>
>>>> On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral
>>>> wrote:
>>>>
>>>>
>>>>> You could always use a collection more suited to foldRight too.
>>>>>
>>>>> On Mon, Apr 12, 2010 at 6:39 PM, calathus wrote:
>>>>>
>>>>>
>>>>>> It is enough to make stack overflow to use just 3000 elements in my
>>>>>> environment.
>>>>>>
>>>>>> (1 to 3000).toList.foldRight(0)(_ + _)
>>>>>>
>>>>>> this is practically very small limit.
>>>>>>
>>>>>> nc
>>>>>>
>>>>>>
>>>>>> On Mon, Apr 12, 2010 at 2:30 PM, calathus wrote:
>>>>>>
>>>>>>
>>>>>>> Hi,
>>>>>>> There is relatively small upper limit for foldRight to avoid stack
>>>>>>> over
>>>>>>> flow.
>>>>>>> for instance, following code will fail with stack over flow
>>>>>>>
>>>>>>> (1 to 999999).toList.foldRight(0)(_ + _)
>>>>>>>
>>>>>>> In particular, collection object will often contain much larger number
>>>>>>> of elements, this problem will limit the usability of foldRight.
>>>>>>> I decided not to use the method, and use for loop instead.
>>>>>>> But if these library avoid recursion in the implementation of
>>>>>>> foldRight, it would not have such problem and application will be more
>>>>>>> declarative.
>>>>>>>
>>>>>>> Are there any action for this?
>>>>>>>
>>>>>>> nc
>>>>>>>
>>>>>>>
>>>>>>>
>>>>> --
>>>>> Daniel C. Sobral
>>>>>
>>>>> I travel to the future all the time.
>>>>>
>>>>>
>>>>>
>
>

On Tue, Apr 13, 2010 at 7:01 PM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:

By strict I mean fully evaluated. The implications of these three
properties of List make it impossible to write a foldRight that does not
exhibit the behaviour originally described (cal's "solution" is
incorrect and I didn't see yours).

Mine was just like his except I created a transient ArrayBuffer and added the list to it.

You could also def foldRight(...) = this.reverse.foldLeft(z)(op).

Why would this make any difference to complete evaluation?
 

foldRight "makes more sense" for infinite data structures.
Unfortunately, scala.Stream's foldRight is broken.

Why does it make any sense at all to start at "the last element" when the last element is undefined?  You can't even define a partial (finite) sequence that way.

What "doesn't make
sense" for infinite data structures is foldLeft where "doesn't make
sense" means "does not terminate."

foldLeft defines a perfectly sensible series:
  z
  z OP head
  z OP head OP tail.head
and thus there is a possibility that a limit exists, which is at least well-defined mathematically even if you can't compute it with Scala.  foldRight on an infinite sequence is just nonsense.

  --Rex
 

Rex Kerr wrote:
> What do you mean by "strict" in this sense?  Both cal's and my solutions
> work perfectly well--mine for any immutable data structure--even if it does
> transiently use mutable arrays (accessible only within that method).
>
> The machine's stack, incidentally, is a mutable array, so I don't think that
> should be a problem.
>
> I'm much more worried about infinite collections where foldRight does not
> make logical sense anyway.  It would be nice to have a well-defined
> divergence mode (e.g. throw an InfinityIsUnimplementable exception instead
> of overflowing the stack).
>
>   --Rex
>
> On Tue, Apr 13, 2010 at 5:38 PM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:
>
>
>> scala.List is a strict immutable singly linked list. This has consequences.
>> Try writing your own foldRight without changing any of these three
>> adjectives.
>>
>> Tony Morris
>> http://tmorris.net/
>>
>>
>>
>> On Apr 13, 2010, at 8:48, calathus <calathus [at] gmail [dot] com> wrote:
>>
>>  some variation is:
>>
>>> def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
>>>  if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op) else z )
>>>  else {
>>>   toArray.foldRight(z)(op)
>>>  }
>>> }
>>>
>>> although I have not tested this code.
>>>
>>> But I tested this works.
>>> (1 to 999999).toList.toArray.foldRight(0)(_ + _)
>>>
>>> but this throws StackOver flow exception.
>>> (1 to 999999).toList.iterator.foldRight(0)(_ + _)
>>>
>>> So this fix looks not bad. it increase the usability of foldRight for
>>> List.
>>>
>>> nc.
>>>
>>> On Mon, Apr 12, 2010 at 2:51 PM, calathus <calathus [at] gmail [dot] com> wrote:
>>>
>>>
>>>> I think this is general restriction. It cannot be used for any large
>>>> collection.
>>>>
>>>> btw, I wrote a similar code in different language.
>>>>
>>>> fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
>>>>   var a0 = a;
>>>>   for (var iter = bs.iterator(); iter.hasNext(); ) {
>>>>       val b = iter.next();
>>>>       a0 := f(a0, b);
>>>>   }
>>>>   return a0;
>>>> }
>>>>
>>>> It is so simple, I wondered there might have been another
>>>> consideration for this issue..
>>>>
>>>> nc
>>>>
>>>>
>>>>
>>>> On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral <dcsobral [at] gmail [dot] com>
>>>> wrote:
>>>>
>>>>
>>>>> You could always use a collection more suited to foldRight too.
>>>>>
>>>>> On Mon, Apr 12, 2010 at 6:39 PM, calathus <calathus [at] gmail [dot] com> wrote:
>>>>>
>>>>>
>>>>>> It is enough to make stack overflow to use just 3000 elements in my
>>>>>> environment.
>>>>>>
>>>>>> (1 to 3000).toList.foldRight(0)(_ + _)
>>>>>>
>>>>>> this is practically very small limit.
>>>>>>
>>>>>> nc
>>>>>>
>>>>>>
>>>>>> On Mon, Apr 12, 2010 at 2:30 PM, calathus <calathus [at] gmail [dot] com> wrote:
>>>>>>
>>>>>>
>>>>>>> Hi,
>>>>>>> There is relatively small upper limit for foldRight to avoid stack
>>>>>>> over
>>>>>>> flow.
>>>>>>> for instance,  following code will fail with stack over flow
>>>>>>>
>>>>>>> (1 to 999999).toList.foldRight(0)(_ + _)
>>>>>>>
>>>>>>> In particular, collection object will often contain much larger number
>>>>>>> of elements, this problem will limit the usability of foldRight.
>>>>>>> I decided not to use the method, and use for loop instead.
>>>>>>> But if these library avoid recursion in the implementation of
>>>>>>> foldRight, it would not have such problem and application will be more
>>>>>>> declarative.
>>>>>>>
>>>>>>> Are there any action for this?
>>>>>>>
>>>>>>> nc
>>>>>>>
>>>>>>>
>>>>>>>
>>>>> --
>>>>> Daniel C. Sobral
>>>>>
>>>>> I travel to the future all the time.
>>>>>
>>>>>
>>>>>
>
>


--
Tony Morris
http://tmorris.net/

This solution has a different complexity to foldRight. It is interesting
to note that reverse is a specialisation of foldLeft (def reverse =
_.foldLeft(Nil)((a, b) => b :: a)). In other words, you're writing
foldRight by calling foldLeft twice and subsequently performing two list
traversals. This is a well known property of list folds.

However, this only happens to be equivalent (complexity aside) because
List is strict. Given a lazy data structure, a correct foldRight would
terminate in cases where calling foldLeft twice would not. It's not
possible to have an infinite scala.List. In other words, foldRight is
very much beneficial for lazy data structures.

As an interesting exercise, consider writing for example (there are many
others), scala.Stream.map using scala.Stream.foldRight. It should be
possible but it is not (including termination characteristics). The
exercise would be to observe this, then consider how it might be
corrected. Here is a related exercise (an addendum is currently pending)
http://blog.tmorris.net/revised-scala-exercises/

Here is a functioning foldRight (foldr) from which you can derive a
successfully map (correct termination characteristics) in a different
language:

>> let mymap f = (\a b -> f a : b) `foldr` [] in 5 `take` (mymap (1+) [1..])
[2,3,4,5,6]

Rex Kerr wrote:
> On Tue, Apr 13, 2010 at 7:01 PM, Tony Morris wrote:
>
>
>> By strict I mean fully evaluated. The implications of these three
>> properties of List make it impossible to write a foldRight that does not
>> exhibit the behaviour originally described (cal's "solution" is
>> incorrect and I didn't see yours).
>>
>>
>
> Mine was just like his except I created a transient ArrayBuffer and added
> the list to it.
>
> You could also def foldRight(...) = this.reverse.foldLeft(z)(op).
>
> Why would this make any difference to complete evaluation?
>
>
>
>> foldRight "makes more sense" for infinite data structures.
>> Unfortunately, scala.Stream's foldRight is broken.
>>
>
>
> Why does it make any sense at all to start at "the last element" when the
> last element is undefined? You can't even define a partial (finite)
> sequence that way.
>
> What "doesn't make
>
>> sense" for infinite data structures is foldLeft where "doesn't make
>> sense" means "does not terminate."
>>
>>
>
> foldLeft defines a perfectly sensible series:
> z
> z OP head
> z OP head OP tail.head
> and thus there is a possibility that a limit exists, which is at least
> well-defined mathematically even if you can't compute it with Scala.
> foldRight on an infinite sequence is just nonsense.
>
> --Rex
>
>
>
>> Rex Kerr wrote:
>>
>>> What do you mean by "strict" in this sense? Both cal's and my solutions
>>> work perfectly well--mine for any immutable data structure--even if it
>>>
>> does
>>
>>> transiently use mutable arrays (accessible only within that method).
>>>
>>> The machine's stack, incidentally, is a mutable array, so I don't think
>>>
>> that
>>
>>> should be a problem.
>>>
>>> I'm much more worried about infinite collections where foldRight does not
>>> make logical sense anyway. It would be nice to have a well-defined
>>> divergence mode (e.g. throw an InfinityIsUnimplementable exception
>>>
>> instead
>>
>>> of overflowing the stack).
>>>
>>> --Rex
>>>
>>> On Tue, Apr 13, 2010 at 5:38 PM, Tony Morris
>>>
>> wrote:
>>
>>>
>>>> scala.List is a strict immutable singly linked list. This has
>>>>
>> consequences.
>>
>>>> Try writing your own foldRight without changing any of these three
>>>> adjectives.
>>>>
>>>> Tony Morris
>>>> http://tmorris.net/
>>>>
>>>>
>>>>
>>>> On Apr 13, 2010, at 8:48, calathus wrote:
>>>>
>>>> some variation is:
>>>>
>>>>
>>>>> def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
>>>>> if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op) else
>>>>>
>> z )
>>
>>>>> else {
>>>>> toArray.foldRight(z)(op)
>>>>> }
>>>>> }
>>>>>
>>>>> although I have not tested this code.
>>>>>
>>>>> But I tested this works.
>>>>> (1 to 999999).toList.toArray.foldRight(0)(_ + _)
>>>>>
>>>>> but this throws StackOver flow exception.
>>>>> (1 to 999999).toList.iterator.foldRight(0)(_ + _)
>>>>>
>>>>> So this fix looks not bad. it increase the usability of foldRight for
>>>>> List.
>>>>>
>>>>> nc.
>>>>>
>>>>> On Mon, Apr 12, 2010 at 2:51 PM, calathus wrote:
>>>>>
>>>>>
>>>>>
>>>>>> I think this is general restriction. It cannot be used for any large
>>>>>> collection.
>>>>>>
>>>>>> btw, I wrote a similar code in different language.
>>>>>>
>>>>>> fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
>>>>>> var a0 = a;
>>>>>> for (var iter = bs.iterator(); iter.hasNext(); ) {
>>>>>> val b = iter.next();
>>>>>> a0 := f(a0, b);
>>>>>> }
>>>>>> return a0;
>>>>>> }
>>>>>>
>>>>>> It is so simple, I wondered there might have been another
>>>>>> consideration for this issue..
>>>>>>
>>>>>> nc
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral
>>>>>> wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>> You could always use a collection more suited to foldRight too.
>>>>>>>
>>>>>>> On Mon, Apr 12, 2010 at 6:39 PM, calathus
>>>>>>>
>> wrote:
>>
>>>>>>>
>>>>>>>> It is enough to make stack overflow to use just 3000 elements in my
>>>>>>>> environment.
>>>>>>>>
>>>>>>>> (1 to 3000).toList.foldRight(0)(_ + _)
>>>>>>>>
>>>>>>>> this is practically very small limit.
>>>>>>>>
>>>>>>>> nc
>>>>>>>>
>>>>>>>>
>>>>>>>> On Mon, Apr 12, 2010 at 2:30 PM, calathus
>>>>>>>>
>> wrote:
>>
>>>>>>>>
>>>>>>>>> Hi,
>>>>>>>>> There is relatively small upper limit for foldRight to avoid stack
>>>>>>>>> over
>>>>>>>>> flow.
>>>>>>>>> for instance, following code will fail with stack over flow
>>>>>>>>>
>>>>>>>>> (1 to 999999).toList.foldRight(0)(_ + _)
>>>>>>>>>
>>>>>>>>> In particular, collection object will often contain much larger
>>>>>>>>>
>> number
>>
>>>>>>>>> of elements, this problem will limit the usability of foldRight.
>>>>>>>>> I decided not to use the method, and use for loop instead.
>>>>>>>>> But if these library avoid recursion in the implementation of
>>>>>>>>> foldRight, it would not have such problem and application will be
>>>>>>>>>
>> more
>>
>>>>>>>>> declarative.
>>>>>>>>>
>>>>>>>>> Are there any action for this?
>>>>>>>>>
>>>>>>>>> nc
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>> --
>>>>>>> Daniel C. Sobral
>>>>>>>
>>>>>>> I travel to the future all the time.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>
>> --
>> Tony Morris
>> http://tmorris.net/
>>
>>
>>
>>
>
>

I found the latest svn code base implementing none recursive foldRight
for iterator of List:
val a = (1 to 9999999).toList.iterator.foldRight(0)(_ + _) // OK
>> a = -2014260032

val a = (1 to 99999999).toList.iterator.foldRight(0)(_ + _) // fails
by java.lang.OutOfMemoryError:
(
see the call sequence from dump. and this show also it is not recursion.
Exception in thread "Thread-0" java.lang.OutOfMemoryError: Java heap space
at scala.collection.mutable.ListBuffer.$plus$eq(ListBuffer.scala:120)
at scala.collection.mutable.ListBuffer.$plus$eq(ListBuffer.scala:43)
at scala.collection.generic.Growable$$anonfun$$plus$plus$eq$1.apply(Growable.scala:49)
at scala.collection.generic.Growable$$anonfun$$plus$plus$eq$1.apply(Growable.scala:49)
at scala.collection.immutable.Range$ByOne$class.foreach(Range.scala:259)
at scala.collection.immutable.Range$$anon$1.foreach(Range.scala:251)
at scala.collection.generic.Growable$class.$plus$plus$eq(Growable.scala:49)
at scala.collection.mutable.ListBuffer.$plus$plus$eq(ListBuffer.scala:43)
at scala.collection.TraversableOnce$class.toList(TraversableOnce.scala:393)
at scala.collection.immutable.Range.toList(Range.scala:40)
)

But if we do call original code:
val a = (1 to 9999999).toList.foldRight(0)(_ + _) // this fails with
java.lang.StackOverflowError

Exception in thread "Thread-0" java.lang.StackOverflowError
at scala.collection.immutable.$colon$colon.tail(List.scala:407)
at scala.collection.LinearSeqOptimized$class.foldRight(LinearSeqOptimized.scala:133)
at scala.collection.immutable.List.foldRight(List.scala:46)
at scala.collection.LinearSeqOptimized$class.foldRight(LinearSeqOptimized.scala:133)
at scala.collection.immutable.List.foldRight(List.scala:46)

I think this difference of iteration is surprising. they should be the same.

BTW, the code of foldRight in the TraversableOnce is :
def foldRight[B](z: B)(op: (A, B) => B): B =
reversed.foldLeft(z)((x, y) => op(y, x))

protected[this] def reversed = {
var elems: List[A] = Nil
self foreach (elems ::= _)
elems
}

So these are the same as Rex suggested.

the drawback of this type of approach is inefficient space usage. it
first copies whole elements, then iterate them.
one idea to reduce the space usage to root n(n^1/2), where n is the
size of collection, is to use 2 arrays of size n^1/2.
one array is used to keep intermediate list elements(::) with interval
n^1/2. the other array is use to copy the elements of some interval.
we apply foldRight for this array. repeat n^1/2 times this process.
This will be the optimized way for the space usage for one directional link.
Also using simple Array would be the most space efficient.

nc

On Tue, Apr 13, 2010 at 8:37 PM, Tony Morris wrote:
> This solution has a different complexity to foldRight. It is interesting
> to note that reverse is a specialisation of foldLeft (def reverse =
> _.foldLeft(Nil)((a, b) => b :: a)). In other words, you're writing
> foldRight by calling foldLeft twice and subsequently performing two list
> traversals. This is a well known property of list folds.
>
> However, this only happens to be equivalent (complexity aside) because
> List is strict. Given a lazy data structure, a correct foldRight would
> terminate in cases where calling foldLeft twice would not. It's not
> possible to have an infinite scala.List. In other words, foldRight is
> very much beneficial for lazy data structures.
>
> As an interesting exercise, consider writing for example (there are many
> others), scala.Stream.map using scala.Stream.foldRight. It should be
> possible but it is not (including termination characteristics). The
> exercise would be to observe this, then consider how it might be
> corrected. Here is a related exercise (an addendum is currently pending)
> http://blog.tmorris.net/revised-scala-exercises/
>
> Here is a functioning foldRight (foldr) from which you can derive a
> successfully map (correct termination characteristics) in a different
> language:
>
>>> let mymap f = (\a b -> f a : b) `foldr` [] in 5 `take` (mymap (1+) [1..])
> [2,3,4,5,6]
>
>
>
> Rex Kerr wrote:
>> On Tue, Apr 13, 2010 at 7:01 PM, Tony Morris wrote:
>>
>>
>>> By strict I mean fully evaluated. The implications of these three
>>> properties of List make it impossible to write a foldRight that does not
>>> exhibit the behaviour originally described (cal's "solution" is
>>> incorrect and I didn't see yours).
>>>
>>>
>>
>> Mine was just like his except I created a transient ArrayBuffer and added
>> the list to it.
>>
>> You could also def foldRight(...) = this.reverse.foldLeft(z)(op).
>>
>> Why would this make any difference to complete evaluation?
>>
>>
>>
>>> foldRight "makes more sense" for infinite data structures.
>>> Unfortunately, scala.Stream's foldRight is broken.
>>>
>>
>>
>> Why does it make any sense at all to start at "the last element" when the
>> last element is undefined?  You can't even define a partial (finite)
>> sequence that way.
>>
>> What "doesn't make
>>
>>> sense" for infinite data structures is foldLeft where "doesn't make
>>> sense" means "does not terminate."
>>>
>>>
>>
>> foldLeft defines a perfectly sensible series:
>>   z
>>   z OP head
>>   z OP head OP tail.head
>> and thus there is a possibility that a limit exists, which is at least
>> well-defined mathematically even if you can't compute it with Scala.
>> foldRight on an infinite sequence is just nonsense.
>>
>>   --Rex
>>
>>
>>
>>> Rex Kerr wrote:
>>>
>>>> What do you mean by "strict" in this sense?  Both cal's and my solutions
>>>> work perfectly well--mine for any immutable data structure--even if it
>>>>
>>> does
>>>
>>>> transiently use mutable arrays (accessible only within that method).
>>>>
>>>> The machine's stack, incidentally, is a mutable array, so I don't think
>>>>
>>> that
>>>
>>>> should be a problem.
>>>>
>>>> I'm much more worried about infinite collections where foldRight does not
>>>> make logical sense anyway.  It would be nice to have a well-defined
>>>> divergence mode (e.g. throw an InfinityIsUnimplementable exception
>>>>
>>> instead
>>>
>>>> of overflowing the stack).
>>>>
>>>>   --Rex
>>>>
>>>> On Tue, Apr 13, 2010 at 5:38 PM, Tony Morris
>>>>
>>> wrote:
>>>
>>>>
>>>>> scala.List is a strict immutable singly linked list. This has
>>>>>
>>> consequences.
>>>
>>>>> Try writing your own foldRight without changing any of these three
>>>>> adjectives.
>>>>>
>>>>> Tony Morris
>>>>> http://tmorris.net/
>>>>>
>>>>>
>>>>>
>>>>> On Apr 13, 2010, at 8:48, calathus wrote:
>>>>>
>>>>>  some variation is:
>>>>>
>>>>>
>>>>>> def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
>>>>>>  if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op) else
>>>>>>
>>> z )
>>>
>>>>>>  else {
>>>>>>   toArray.foldRight(z)(op)
>>>>>>  }
>>>>>> }
>>>>>>
>>>>>> although I have not tested this code.
>>>>>>
>>>>>> But I tested this works.
>>>>>> (1 to 999999).toList.toArray.foldRight(0)(_ + _)
>>>>>>
>>>>>> but this throws StackOver flow exception.
>>>>>> (1 to 999999).toList.iterator.foldRight(0)(_ + _)
>>>>>>
>>>>>> So this fix looks not bad. it increase the usability of foldRight for
>>>>>> List.
>>>>>>
>>>>>> nc.
>>>>>>
>>>>>> On Mon, Apr 12, 2010 at 2:51 PM, calathus wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>> I think this is general restriction. It cannot be used for any large
>>>>>>> collection.
>>>>>>>
>>>>>>> btw, I wrote a similar code in different language.
>>>>>>>
>>>>>>> fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
>>>>>>>   var a0 = a;
>>>>>>>   for (var iter = bs.iterator(); iter.hasNext(); ) {
>>>>>>>       val b = iter.next();
>>>>>>>       a0 := f(a0, b);
>>>>>>>   }
>>>>>>>   return a0;
>>>>>>> }
>>>>>>>
>>>>>>> It is so simple, I wondered there might have been another
>>>>>>> consideration for this issue..
>>>>>>>
>>>>>>> nc
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral
>>>>>>> wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>> You could always use a collection more suited to foldRight too.
>>>>>>>>
>>>>>>>> On Mon, Apr 12, 2010 at 6:39 PM, calathus
>>>>>>>>
>>> wrote:
>>>
>>>>>>>>
>>>>>>>>> It is enough to make stack overflow to use just 3000 elements in my
>>>>>>>>> environment.
>>>>>>>>>
>>>>>>>>> (1 to 3000).toList.foldRight(0)(_ + _)
>>>>>>>>>
>>>>>>>>> this is practically very small limit.
>>>>>>>>>
>>>>>>>>> nc
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Mon, Apr 12, 2010 at 2:30 PM, calathus
>>>>>>>>>
>>> wrote:
>>>
>>>>>>>>>
>>>>>>>>>> Hi,
>>>>>>>>>> There is relatively small upper limit for foldRight to avoid stack
>>>>>>>>>> over
>>>>>>>>>> flow.
>>>>>>>>>> for instance,  following code will fail with stack over flow
>>>>>>>>>>
>>>>>>>>>> (1 to 999999).toList.foldRight(0)(_ + _)
>>>>>>>>>>
>>>>>>>>>> In particular, collection object will often contain much larger
>>>>>>>>>>
>>> number
>>>
>>>>>>>>>> of elements, this problem will limit the usability of foldRight.
>>>>>>>>>> I decided not to use the method, and use for loop instead.
>>>>>>>>>> But if these library avoid recursion in the implementation of
>>>>>>>>>> foldRight, it would not have such problem and application will be
>>>>>>>>>>
>>> more
>>>
>>>>>>>>>> declarative.
>>>>>>>>>>
>>>>>>>>>> Are there any action for this?
>>>>>>>>>>
>>>>>>>>>> nc
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>> --
>>>>>>>> Daniel C. Sobral
>>>>>>>>
>>>>>>>> I travel to the future all the time.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>
>>> --
>>> Tony Morris
>>> http://tmorris.net/
>>>
>>>
>>>
>>>
>>
>>
>
>

On Tue, Apr 13, 2010 at 10:30:15PM -0700, calathus wrote:
> I think this difference of iteration is surprising. they should be the
> same.

Why?

How do you imagine you might implement foldRight on an Iterator? Why
would you want to impose those constraints on Lists?

> Also using simple Array would be the most space efficient.

What size Array would that be?

Setting language aside, I had hard time to understand what's the mathematical meaning of foldRight is, so I thought to spell that out.For example, foldLeft(0)(_+_) on the series 1/2^n is an infinite sum, which might converge to something (including infinity not currently represented by scala). The infinite sum S=a_1+a_2+a_3+... might be described inductively as b_i = b_{i-1}+a_iWe'll have then that S=b_\infty.Generally speaking, given a function f(x,y), and a series of items a_1,a_2,.... we have foldLeft described as b_\infty whereb_i=f(b_{i-1},a_i) For example if f(x,y)=x+yb_3=f(f(a_1,a_2),a_3) = (a_1+a_2)+a_3Given that definition foldRight might be defined by reverse as c_\infty wherec_i=f(a_i,b_{i-1})In that case c_3=f(a_3,f(a_2,a_1))=a_3+(a_2+a_1)
On Wed, Apr 14, 2010 at 6:37 AM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:

This solution has a different complexity to foldRight. It is interesting
to note that reverse is a specialisation of foldLeft (def reverse =
_.foldLeft(Nil)((a, b) => b :: a)). In other words, you're writing
foldRight by calling foldLeft twice and subsequently performing two list
traversals. This is a well known property of list folds.

However, this only happens to be equivalent (complexity aside) because
List is strict. Given a lazy data structure, a correct foldRight would
terminate in cases where calling foldLeft twice would not. It's not
possible to have an infinite scala.List. In other words, foldRight is
very much beneficial for lazy data structures.

As an interesting exercise, consider writing for example (there are many
others), scala.Stream.map using scala.Stream.foldRight. It should be
possible but it is not (including termination characteristics). The
exercise would be to observe this, then consider how it might be
corrected. Here is a related exercise (an addendum is currently pending)
http://blog.tmorris.net/revised-scala-exercises/

Here is a functioning foldRight (foldr) from which you can derive a
successfully map (correct termination characteristics) in a different
language:

>> let mymap f = (\a b -> f a : b) `foldr` [] in 5 `take` (mymap (1+) [1..])
[2,3,4,5,6]



Rex Kerr wrote:
> On Tue, Apr 13, 2010 at 7:01 PM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:
>
>
>> By strict I mean fully evaluated. The implications of these three
>> properties of List make it impossible to write a foldRight that does not
>> exhibit the behaviour originally described (cal's "solution" is
>> incorrect and I didn't see yours).
>>
>>
>
> Mine was just like his except I created a transient ArrayBuffer and added
> the list to it.
>
> You could also def foldRight(...) = this.reverse.foldLeft(z)(op).
>
> Why would this make any difference to complete evaluation?
>
>
>
>> foldRight "makes more sense" for infinite data structures.
>> Unfortunately, scala.Stream's foldRight is broken.
>>
>
>
> Why does it make any sense at all to start at "the last element" when the
> last element is undefined?  You can't even define a partial (finite)
> sequence that way.
>
> What "doesn't make
>
>> sense" for infinite data structures is foldLeft where "doesn't make
>> sense" means "does not terminate."
>>
>>
>
> foldLeft defines a perfectly sensible series:
>   z
>   z OP head
>   z OP head OP tail.head
> and thus there is a possibility that a limit exists, which is at least
> well-defined mathematically even if you can't compute it with Scala.
> foldRight on an infinite sequence is just nonsense.
>
>   --Rex
>
>
>
>> Rex Kerr wrote:
>>
>>> What do you mean by "strict" in this sense?  Both cal's and my solutions
>>> work perfectly well--mine for any immutable data structure--even if it
>>>
>> does
>>
>>> transiently use mutable arrays (accessible only within that method).
>>>
>>> The machine's stack, incidentally, is a mutable array, so I don't think
>>>
>> that
>>
>>> should be a problem.
>>>
>>> I'm much more worried about infinite collections where foldRight does not
>>> make logical sense anyway.  It would be nice to have a well-defined
>>> divergence mode (e.g. throw an InfinityIsUnimplementable exception
>>>
>> instead
>>
>>> of overflowing the stack).
>>>
>>>   --Rex
>>>
>>> On Tue, Apr 13, 2010 at 5:38 PM, Tony Morris <tonymorris [at] gmail [dot] com>
>>>
>> wrote:
>>
>>>
>>>> scala.List is a strict immutable singly linked list. This has
>>>>
>> consequences.
>>
>>>> Try writing your own foldRight without changing any of these three
>>>> adjectives.
>>>>
>>>> Tony Morris
>>>> http://tmorris.net/
>>>>
>>>>
>>>>
>>>> On Apr 13, 2010, at 8:48, calathus <calathus [at] gmail [dot] com> wrote:
>>>>
>>>>  some variation is:
>>>>
>>>>
>>>>> def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
>>>>>  if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op) else
>>>>>
>> z )
>>
>>>>>  else {
>>>>>   toArray.foldRight(z)(op)
>>>>>  }
>>>>> }
>>>>>
>>>>> although I have not tested this code.
>>>>>
>>>>> But I tested this works.
>>>>> (1 to 999999).toList.toArray.foldRight(0)(_ + _)
>>>>>
>>>>> but this throws StackOver flow exception.
>>>>> (1 to 999999).toList.iterator.foldRight(0)(_ + _)
>>>>>
>>>>> So this fix looks not bad. it increase the usability of foldRight for
>>>>> List.
>>>>>
>>>>> nc.
>>>>>
>>>>> On Mon, Apr 12, 2010 at 2:51 PM, calathus <calathus [at] gmail [dot] com> wrote:
>>>>>
>>>>>
>>>>>
>>>>>> I think this is general restriction. It cannot be used for any large
>>>>>> collection.
>>>>>>
>>>>>> btw, I wrote a similar code in different language.
>>>>>>
>>>>>> fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
>>>>>>   var a0 = a;
>>>>>>   for (var iter = bs.iterator(); iter.hasNext(); ) {
>>>>>>       val b = iter.next();
>>>>>>       a0 := f(a0, b);
>>>>>>   }
>>>>>>   return a0;
>>>>>> }
>>>>>>
>>>>>> It is so simple, I wondered there might have been another
>>>>>> consideration for this issue..
>>>>>>
>>>>>> nc
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral <dcsobral [at] gmail [dot] com>
>>>>>> wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>> You could always use a collection more suited to foldRight too.
>>>>>>>
>>>>>>> On Mon, Apr 12, 2010 at 6:39 PM, calathus <calathus [at] gmail [dot] com>
>>>>>>>
>> wrote:
>>
>>>>>>>
>>>>>>>> It is enough to make stack overflow to use just 3000 elements in my
>>>>>>>> environment.
>>>>>>>>
>>>>>>>> (1 to 3000).toList.foldRight(0)(_ + _)
>>>>>>>>
>>>>>>>> this is practically very small limit.
>>>>>>>>
>>>>>>>> nc
>>>>>>>>
>>>>>>>>
>>>>>>>> On Mon, Apr 12, 2010 at 2:30 PM, calathus <calathus [at] gmail [dot] com>
>>>>>>>>
>> wrote:
>>
>>>>>>>>
>>>>>>>>> Hi,
>>>>>>>>> There is relatively small upper limit for foldRight to avoid stack
>>>>>>>>> over
>>>>>>>>> flow.
>>>>>>>>> for instance,  following code will fail with stack over flow
>>>>>>>>>
>>>>>>>>> (1 to 999999).toList.foldRight(0)(_ + _)
>>>>>>>>>
>>>>>>>>> In particular, collection object will often contain much larger
>>>>>>>>>
>> number
>>
>>>>>>>>> of elements, this problem will limit the usability of foldRight.
>>>>>>>>> I decided not to use the method, and use for loop instead.
>>>>>>>>> But if these library avoid recursion in the implementation of
>>>>>>>>> foldRight, it would not have such problem and application will be
>>>>>>>>>
>> more
>>
>>>>>>>>> declarative.
>>>>>>>>>
>>>>>>>>> Are there any action for this?
>>>>>>>>>
>>>>>>>>> nc
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>> --
>>>>>>> Daniel C. Sobral
>>>>>>>
>>>>>>> I travel to the future all the time.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>
>> --
>> Tony Morris
>> http://tmorris.net/
>>
>>
>>
>>
>
>

On Tue, Apr 13, 2010 at 10:47 PM, Paul Phillips wrote:
> On Tue, Apr 13, 2010 at 10:30:15PM -0700, calathus wrote:
>> I think this difference of iteration is surprising. they should be the
>> same.
>
> Why?
Just for the usability. I was thinking iterator and collection are
somehow exchangeable if they can be used in the similar situation.

>
> How do you imagine you might implement foldRight on an Iterator? Why
> would you want to impose those constraints on Lists?
>
>> Also using simple Array would be the most space efficient.
>
> What size Array would that be?
if we do foldRight for 1,000,000 elements, the working array size
should be 1000. we need 2 arrays, so the total array size will be
2000.
compared to List the same size array will consume less than half of
the list representation.

>
> --
> Paul Phillips      | If this is raisin, make toast with it.
> Moral Alien        |
> Empiricist         |
> slap pi uphill!    |----------* http://www.improving.org/paulp/ *----------
>

The mathematical meaning is called a catamorphism.
http://en.wikipedia.org/wiki/Catamorphism

This is because foldRight applied to the List constructors gives an
identity function.
forall x. x.foldRight(Nil)(::) == x

It's possible to reimplement List using its catamorphism as a single
abstract function (you should try it):

trait List[A] {
def foldRight[A, B](a: B)(f: (A, B) => B): B

// all the concrete List functions
}

Here is same for Option:

trait Option[A] {
def fold[B](none: => B, some: A => B): B

// all the concrete Option functions
}

Elazar Leibovich wrote:
> Setting language aside, I had hard time to understand what's the
> mathematical meaning of foldRight is, so I thought to spell that out.
> For example, foldLeft(0)(_+_) on the series 1/2^n is an infinite sum, which
> might converge to something (including infinity not currently represented by
> scala). The infinite sum S=a_1+a_2+a_3+... might be described inductively as
> b_i = b_{i-1}+a_i
> We'll have then that S=b_\infty.
> Generally speaking, given a function f(x,y), and a series of items
> a_1,a_2,.... we have foldLeft described as b_\infty where
> b_i=f(b_{i-1},a_i)
> For example if f(x,y)=x+y
> b_3=f(f(a_1,a_2),a_3) = (a_1+a_2)+a_3
> Given that definition foldRight might be defined by reverse as c_\infty
> where
> c_i=f(a_i,b_{i-1})
> In that case
> c_3=f(a_3,f(a_2,a_1))=a_3+(a_2+a_1)
>
> On Wed, Apr 14, 2010 at 6:37 AM, Tony Morris wrote:
>
>
>> This solution has a different complexity to foldRight. It is interesting
>> to note that reverse is a specialisation of foldLeft (def reverse =
>> _.foldLeft(Nil)((a, b) => b :: a)). In other words, you're writing
>> foldRight by calling foldLeft twice and subsequently performing two list
>> traversals. This is a well known property of list folds.
>>
>> However, this only happens to be equivalent (complexity aside) because
>> List is strict. Given a lazy data structure, a correct foldRight would
>> terminate in cases where calling foldLeft twice would not. It's not
>> possible to have an infinite scala.List. In other words, foldRight is
>> very much beneficial for lazy data structures.
>>
>> As an interesting exercise, consider writing for example (there are many
>> others), scala.Stream.map using scala.Stream.foldRight. It should be
>> possible but it is not (including termination characteristics). The
>> exercise would be to observe this, then consider how it might be
>> corrected. Here is a related exercise (an addendum is currently pending)
>> http://blog.tmorris.net/revised-scala-exercises/
>>
>> Here is a functioning foldRight (foldr) from which you can derive a
>> successfully map (correct termination characteristics) in a different
>> language:
>>
>>
>>>> let mymap f = (\a b -> f a : b) `foldr` [] in 5 `take` (mymap (1+)
>>>>
>> [1..])
>> [2,3,4,5,6]
>>
>>
>>
>> Rex Kerr wrote:
>>
>>> On Tue, Apr 13, 2010 at 7:01 PM, Tony Morris
>>>
>> wrote:
>>
>>>
>>>> By strict I mean fully evaluated. The implications of these three
>>>> properties of List make it impossible to write a foldRight that does not
>>>> exhibit the behaviour originally described (cal's "solution" is
>>>> incorrect and I didn't see yours).
>>>>
>>>>
>>>>
>>> Mine was just like his except I created a transient ArrayBuffer and added
>>> the list to it.
>>>
>>> You could also def foldRight(...) = this.reverse.foldLeft(z)(op).
>>>
>>> Why would this make any difference to complete evaluation?
>>>
>>>
>>>
>>>
>>>> foldRight "makes more sense" for infinite data structures.
>>>> Unfortunately, scala.Stream's foldRight is broken.
>>>>
>>>>
>>> Why does it make any sense at all to start at "the last element" when the
>>> last element is undefined? You can't even define a partial (finite)
>>> sequence that way.
>>>
>>> What "doesn't make
>>>
>>>
>>>> sense" for infinite data structures is foldLeft where "doesn't make
>>>> sense" means "does not terminate."
>>>>
>>>>
>>>>
>>> foldLeft defines a perfectly sensible series:
>>> z
>>> z OP head
>>> z OP head OP tail.head
>>> and thus there is a possibility that a limit exists, which is at least
>>> well-defined mathematically even if you can't compute it with Scala.
>>> foldRight on an infinite sequence is just nonsense.
>>>
>>> --Rex
>>>
>>>
>>>
>>>
>>>> Rex Kerr wrote:
>>>>
>>>>
>>>>> What do you mean by "strict" in this sense? Both cal's and my
>>>>>
>> solutions
>>
>>>>> work perfectly well--mine for any immutable data structure--even if it
>>>>>
>>>>>
>>>> does
>>>>
>>>>
>>>>> transiently use mutable arrays (accessible only within that method).
>>>>>
>>>>> The machine's stack, incidentally, is a mutable array, so I don't think
>>>>>
>>>>>
>>>> that
>>>>
>>>>
>>>>> should be a problem.
>>>>>
>>>>> I'm much more worried about infinite collections where foldRight does
>>>>>
>> not
>>
>>>>> make logical sense anyway. It would be nice to have a well-defined
>>>>> divergence mode (e.g. throw an InfinityIsUnimplementable exception
>>>>>
>>>>>
>>>> instead
>>>>
>>>>
>>>>> of overflowing the stack).
>>>>>
>>>>> --Rex
>>>>>
>>>>> On Tue, Apr 13, 2010 at 5:38 PM, Tony Morris
>>>>>
>>>>>
>>>> wrote:
>>>>
>>>>
>>>>>> scala.List is a strict immutable singly linked list. This has
>>>>>>
>>>>>>
>>>> consequences.
>>>>
>>>>
>>>>>> Try writing your own foldRight without changing any of these three
>>>>>> adjectives.
>>>>>>
>>>>>> Tony Morris
>>>>>> http://tmorris.net/
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Apr 13, 2010, at 8:48, calathus wrote:
>>>>>>
>>>>>> some variation is:
>>>>>>
>>>>>>
>>>>>>
>>>>>>> def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
>>>>>>> if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op)
>>>>>>>
>> else
>>
>>>> z )
>>>>
>>>>
>>>>>>> else {
>>>>>>> toArray.foldRight(z)(op)
>>>>>>> }
>>>>>>> }
>>>>>>>
>>>>>>> although I have not tested this code.
>>>>>>>
>>>>>>> But I tested this works.
>>>>>>> (1 to 999999).toList.toArray.foldRight(0)(_ + _)
>>>>>>>
>>>>>>> but this throws StackOver flow exception.
>>>>>>> (1 to 999999).toList.iterator.foldRight(0)(_ + _)
>>>>>>>
>>>>>>> So this fix looks not bad. it increase the usability of foldRight for
>>>>>>> List.
>>>>>>>
>>>>>>> nc.
>>>>>>>
>>>>>>> On Mon, Apr 12, 2010 at 2:51 PM, calathus
>>>>>>>
>> wrote:
>>
>>>>>>>
>>>>>>>
>>>>>>>> I think this is general restriction. It cannot be used for any large
>>>>>>>> collection.
>>>>>>>>
>>>>>>>> btw, I wrote a similar code in different language.
>>>>>>>>
>>>>>>>> fun foldl(f: `x*`y->`x, a:`x, bs:list<`y>) {
>>>>>>>> var a0 = a;
>>>>>>>> for (var iter = bs.iterator(); iter.hasNext(); ) {
>>>>>>>> val b = iter.next();
>>>>>>>> a0 := f(a0, b);
>>>>>>>> }
>>>>>>>> return a0;
>>>>>>>> }
>>>>>>>>
>>>>>>>> It is so simple, I wondered there might have been another
>>>>>>>> consideration for this issue..
>>>>>>>>
>>>>>>>> nc
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Mon, Apr 12, 2010 at 2:46 PM, Daniel Sobral
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>> You could always use a collection more suited to foldRight too.
>>>>>>>>>
>>>>>>>>> On Mon, Apr 12, 2010 at 6:39 PM, calathus
>>>>>>>>>
>>>>>>>>>
>>>> wrote:
>>>>
>>>>
>>>>>>>>>> It is enough to make stack overflow to use just 3000 elements in
>>>>>>>>>>
>> my
>>
>>>>>>>>>> environment.
>>>>>>>>>>
>>>>>>>>>> (1 to 3000).toList.foldRight(0)(_ + _)
>>>>>>>>>>
>>>>>>>>>> this is practically very small limit.
>>>>>>>>>>
>>>>>>>>>> nc
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Mon, Apr 12, 2010 at 2:30 PM, calathus
>>>>>>>>>>
>>>>>>>>>>
>>>> wrote:
>>>>
>>>>
>>>>>>>>>>> Hi,
>>>>>>>>>>> There is relatively small upper limit for foldRight to avoid
>>>>>>>>>>>
>> stack
>>
>>>>>>>>>>> over
>>>>>>>>>>> flow.
>>>>>>>>>>> for instance, following code will fail with stack over flow
>>>>>>>>>>>
>>>>>>>>>>> (1 to 999999).toList.foldRight(0)(_ + _)
>>>>>>>>>>>
>>>>>>>>>>> In particular, collection object will often contain much larger
>>>>>>>>>>>
>>>>>>>>>>>
>>>> number
>>>>
>>>>
>>>>>>>>>>> of elements, this problem will limit the usability of foldRight.
>>>>>>>>>>> I decided not to use the method, and use for loop instead.
>>>>>>>>>>> But if these library avoid recursion in the implementation of
>>>>>>>>>>> foldRight, it would not have such problem and application will be
>>>>>>>>>>>
>>>>>>>>>>>
>>>> more
>>>>
>>>>
>>>>>>>>>>> declarative.
>>>>>>>>>>>
>>>>>>>>>>> Are there any action for this?
>>>>>>>>>>>
>>>>>>>>>>> nc
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> Daniel C. Sobral
>>>>>>>>>
>>>>>>>>> I travel to the future all the time.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>> --
>>>> Tony Morris
>>>> http://tmorris.net/
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>
>
>

in addition, probably array would be more kind for GC..

On Tue, Apr 13, 2010 at 11:04 PM, calathus wrote:
> On Tue, Apr 13, 2010 at 10:47 PM, Paul Phillips wrote:
>> On Tue, Apr 13, 2010 at 10:30:15PM -0700, calathus wrote:
>>> I think this difference of iteration is surprising. they should be the
>>> same.
>>
>> Why?
> Just for the usability. I was thinking iterator and collection are
> somehow exchangeable if they can be used in the  similar situation.
>
>
>>
>> How do you imagine you might implement foldRight on an Iterator? Why
>> would you want to impose those constraints on Lists?
>>
>>> Also using simple Array would be the most space efficient.
>>
>> What size Array would that be?
> if we do foldRight for 1,000,000 elements, the working array size
> should be 1000. we need 2 arrays, so the total array size will be
> 2000.
> compared to List the same size array will consume less than half of
> the list representation.
>
>
>>
>> --
>> Paul Phillips      | If this is raisin, make toast with it.
>> Moral Alien        |
>> Empiricist         |
>> slap pi uphill!    |----------* http://www.improving.org/paulp/ *----------
>>
>

On Tue, Apr 13, 2010 at 11:04:34PM -0700, calathus wrote:
> Just for the usability. I was thinking iterator and collection are
> somehow exchangeable if they can be used in the similar situation.

If they were the same thing the smart thing would be to get rid of one
of them.

> if we do foldRight for 1,000,000 elements, the working array size
> should be 1000. we need 2 arrays, so the total array size will be
> 2000.

When you submit this implementation I'll be first in line to review it.

On Tue, Apr 13, 2010 at 11:37 PM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:

This solution has a different complexity to foldRight.

It has the same space and time complexity, albeit with a different constant factor on the time (~ 2x in either the reverse case or the ArrayBuffer case, though the latter only uses primitive operations so in practice is much easier on the GC and is faster).  Or do you mean something else by complexity?
 

It is interesting
to note that reverse is a specialisation of foldLeft (def reverse =
_.foldLeft(Nil)((a, b) => b :: a)). In other words, you're writing
foldRight by calling foldLeft twice and subsequently performing two list
traversals. This is a well known property of list folds.

Sure, and you do _the same thing with the CPU's stack_ in the recursive definition.  (Or, with a sufficiently clever compiler, the heap functioning as a stack.)  With reverse, you're just making it explicit that using a stack is necessary.

We don't use computational architecture that views
  f(x0,f(x1,f(x2,...f(xN,b)...)
and
  f(xN,...f(x1,f(x0,b))...)
as computationally equivalent unless you have random access to xi.
 

However, this only happens to be equivalent (complexity aside) because
List is strict. Given a lazy data structure, a correct foldRight would
terminate in cases where calling foldLeft twice would not. It's not
possible to have an infinite scala.List. In other words, foldRight is
very much beneficial for lazy data structures.

With lazy data structures you can change your stack overflow into a heap overflow, but you've still got the same fundamental limitations of needing to store your values since you operate on them inside-out.  Although conceptually you can replace :: with any function f: (A,B) => B (as long as you supply a replacement terminator b0 for Nil), if you want to actually evaluate the tree rather than just constructing the syntax tree, you do in fact need to store all your values so that you can evaluate the innermost.  You might decide that you could drop a lot of your tree before evaluating the head, which would help, but it's equivalent to dropping that same portion of the original list and then applying the fold.

Anyway, foldLeft can work the same way as well, as long as you view it as a map from your list to a list of partial results, with the last element being the answer.

  --Rex

Hi Paul,
I implemented the algorithm and compared the performance against other
methods(array, iterator, vector, ListBuffer).
I will attach the graph in png format.

Although it does not keep running for twice larger size of array case,
but in general, this looks better than array.
Actually Array is quite good compared to other structure as this can
be expected.

the graph will stop when it crash with out of space. new algorithm
will survive longest.

Other interesting finding is ListBuffer will not succeed any of test.
it is using recursive call,
I think recursive call should be banned for iteration of collection
elements. stack overflow is fatal, and difficult to estimate when it
will overflow since it depends on system and runtime environment.
it will make application very fragile, unusable.

Anyway, following is the code I wrote:

object foldList {

def foldRight[A: Manifest, B](es: List[A])(z: B)(op: (A, B) => B): B = {
val es_sz = es.size
val sz: Int = Math.ceil(Math.sqrt(es_sz)).toInt

def createNodes: (Array[List[A]], Int, Int) = {
val nodes = new Array[List[A]](sz)
var ndIdx = 0
var es0 = es
for (i <- 0 until es_sz) {
if (i % sz == 0) {
nodes(ndIdx) = es0
ndIdx += 1
}
es0 = es0.tail
}
ndIdx -= 1
(nodes, ndIdx, es_sz - ndIdx*sz)
}

def copyInterval(es: List[A], interval: Array[A]): Array[A] = {
val size = interval.size
val iter = es.iterator
//println(">> size: "+size)
for (i <- 0 until size) {
interval(i) = iter.next
//println(">> interval: ["+i+" ]= "+interval(i))
}
interval
}

val (nodes, ndIdx0, residue) = createNodes
var ndIdx = ndIdx0
//println(">> nodes: "+nodes)
//println(">> ndIdx: "+ndIdx)
var interval = new Array[A](residue)
var z1 = copyInterval(nodes(ndIdx), interval).foldRight(z)(op)
//println(">> z1 = "+z1)
if (residue != sz) interval = new Array[A](sz)

while ({ndIdx -= 1; ndIdx >= 0}) {
z1 = copyInterval(nodes(ndIdx), interval).foldRight(z1)(op)
//println(">> z1 = "+z1)
//ndIdx -= 1
}
z1
}
}

object foldListTest {
import foldList._

def currentTime = System.currentTimeMillis()
def benchmark[B](title: String, f: =>B): (B, Long) = {
val startTime = currentTime
val v = f
val duration = currentTime - startTime
//println(title+", v: "+v+", time: "+duration)
(v, duration)
}
def main(args: Array[String]): Unit = {
def test0 {
val x1 = (1 to 100).toList.foldRight(0)(_ + _)
println("x1: "+x1)
val x2 = foldRight((1 to 100).toList)(0)(_ + _)
println("x2: "+x2)
val x3 = foldRight((1 to 102).toList)(0)(_ + _)
println("x3: "+x3)
val x4 = foldRight((1 to 99).toList)(0)(_ + _)
println("x4: "+x4)
}

def test1 {
def test1(num: Int) {
val es = (1 to num).toList
//val (v1, t1) = benchmark("new["+num+"]", foldRight(es)(0)(_ + _))
//val (v2, t2) = benchmark("arr["+num+"]",
es.toArray.foldRight(0)(_ + _))
//val (v3, t3) = benchmark("vec["+num+"]",
(Vector()++es).foldRight(0)(_ + _))
val (v3, t3) = benchmark("listb["+num+"]",
(ListBuffer[Int]()++es).foldRight(0)(_ + _))
//val (v4, t4) = benchmark("itr["+num+"]",
es.iterator.foldRight(0)(_ + _))
//println("["+num+"] new: "+t1)
//println("["+num+"] arr: "+t2)
println(num+" "+t3)
//println("["+num+"] new: "+t1+", array: "+t2)
//println("["+num+"] new: "+t1+", array: "+t2+", vec: "+t3+",
iter: "+t4)
}
for (i <- 1 to 140) {
test1(100000*i)
}
}

//test0

val (_, t) = benchmark("test1", test1)
println("time: "+t)
}
}

see the attached png file for the test result.

nc

On Tue, Apr 13, 2010 at 11:38 PM, Paul Phillips wrote:
> On Tue, Apr 13, 2010 at 11:04:34PM -0700, calathus wrote:
>> Just for the usability. I was thinking iterator and collection are
>> somehow exchangeable if they can be used in the similar situation.
>
> If they were the same thing the smart thing would be to get rid of one
> of them.
>
>> if we do foldRight for 1,000,000 elements, the working array size
>> should be 1000. we need 2 arrays, so the total array size will be
>> 2000.
>
> When you submit this implementation I'll be first in line to review it.
>
> --
> Paul Phillips      | Where there's smoke, there's mirrors!
> Vivid              |
> Empiricist         |
> i pull his palp!   |----------* http://www.improving.org/paulp/ *----------
>

On Thu, 2010-04-15 at 02:30 -0700, calathus wrote:
...
> I think recursive call should be banned for iteration of collection
> elements. stack overflow is fatal, and difficult to estimate when it
> will overflow since it depends on system and runtime environment.
> it will make application very fragile, unusable.
...

I second that.

Linas.

On Thursday April 15 2010, calathus wrote:
> Hi Paul,
> I implemented the algorithm and compared the performance against
> other methods(array, iterator, vector, ListBuffer).
> I will attach the graph in png format.

How about attaching the source so it does not get mangled and can easily
be saved to a file?

> ...
>
> nc

Randall Schulz

What about collections on infinite length? Recursion allows one to write a definition of foldRight that's perfectly valid for both finite and infinite collections:

def foldr[A, B](xs: Seq[A], z: B, f: (A, => B) => B) = if(xs.isEmpty) z else f(xs.head, foldr(xs.tail, z, f))

def f(n: Int, ns: => Stream[Stream[Int]]) = Stream.from(n) #:: ns

scala> foldr(Stream.from(1), Stream.empty: Stream[Stream[Int]], f)
res1: scala.collection.immutable.Stream[scala.collection.immutable.Stream[Int]] = Stream(Stream(1, ?), ?)

scala> res1.drop(10).head.take(5).toList
res2: List[Int] = List(11, 12, 13, 14, 15)

scala> res1.drop(100000).head.take(5).toList
res3: List[Int] = List(100001, 100002, 100003, 100004, 100005)

- Colin

On Thu, Apr 15, 2010 at 4:03 PM, Colin Bullock <cmbullock [at] gmail [dot] com> wrote:

What about collections on infinite length? Recursion allows one to write a definition of foldRight that's perfectly valid for both finite and infinite collections:

def foldr[A, B](xs: Seq[A], z: B, f: (A, => B) => B) = if(xs.isEmpty) z else f(xs.head, foldr(xs.tail, z, f))

def f(n: Int, ns: => Stream[Stream[Int]]) = Stream.from(n) #:: ns

scala> foldr(Stream.from(1), Stream.empty: Stream[Stream[Int]], f)
res1: scala.collection.immutable.Stream[scala.collection.immutable.Stream[Int]] = Stream(Stream(1, ?), ?)

scala> res1.drop(10).head.take(5).toList
res2: List[Int] = List(11, 12, 13, 14, 15)

scala> res1.drop(100000).head.take(5).toList
res3: List[Int] = List(100001, 100002, 100003, 100004, 100005)

- Colin

Modify that to use @scala.annotation.tailrec

Cheers,
--
Viktor Klang
| "A complex system that works is invariably
| found to have evolved from a simple system
| that worked." - John Gall

Akka - the Actor Kernel: Akkasource.org
Twttr: twitter.com/viktorklang

ok,
I will attach the source code.

nc

On Thu, Apr 15, 2010 at 7:03 AM, Randall R Schulz wrote:
> On Thursday April 15 2010, calathus wrote:
>> Hi Paul,
>> I implemented the algorithm and compared the performance against
>> other methods(array, iterator, vector, ListBuffer).
>> I will attach the graph in png format.
>
> How about attaching the source so it does not get mangled and can easily
> be saved to a file?
>
>
>> ...
>>
>> nc
>
>
> Randall Schulz
>

I updated the code to extend it to reverse iterator for LinearSeq.
This would be more general way to handle foldRight problem.

I uploaded the code to github
http://github.com/calathus

and additional info on
http://scalathus.blogspot.com

On Thu, Apr 15, 2010 at 8:31 AM, calathus wrote:
> ok,
> I will attach the source code.
>
> nc
>
> On Thu, Apr 15, 2010 at 7:03 AM, Randall R Schulz wrote:
>> On Thursday April 15 2010, calathus wrote:
>>> Hi Paul,
>>> I implemented the algorithm and compared the performance against
>>> other methods(array, iterator, vector, ListBuffer).
>>> I will attach the graph in png format.
>>
>> How about attaching the source so it does not get mangled and can easily
>> be saved to a file?
>>
>>
>>> ...
>>>
>>> nc
>>
>>
>> Randall Schulz
>>
>