Traversable and foldRight/reduceRight/dropRight/takeRight

Good catch, Jorge! We should avoid that inconsistency. I am not quite
sure yet whether we should move reverse, dropRight, takeRight from
Iterable to Traversable, or whether we
should rather move foldRight, reduceRight, :\ from Traversable to
Iterable. All 6 methods are in the same class -- they can be
implemented by Traversable only with the help of building another
size-n data-structure, whereas they have more efficient
implementations once Iterable's elements method is available.

Cheers

2009/5/14 martin odersky :
> Good catch, Jorge! We should avoid that inconsistency. I am not quite
> sure yet whether we should move reverse, dropRight, takeRight from
> Iterable to Traversable, or whether we
> should rather move foldRight, reduceRight, :\ from Traversable to
> Iterable. All 6 methods are in the same class -- they can be
> implemented by Traversable only with the help of building another
> size-n data-structure, whereas they have more efficient
> implementations once Iterable's elements method is available.

Note that the more efficient implementations will stack overflow on
non-trivially large collections, so this is probably not actually a
desirable thing to do.

I don't particularly care whether it's added or not (though if I had to I'd probably vote for inclusion), but can't it always be overriden in subclasses if there's a more efficient approach? Though, as David points out, the "more efficient" implementation isn't actually more efficient.

--j

On Thu, May 14, 2009 at 3:03 AM, martin odersky <martin.odersky@epfl.ch> wrote:

Good catch, Jorge! We should avoid that inconsistency. I am not quite
sure yet whether we should move reverse, dropRight, takeRight from
Iterable to Traversable, or whether we
should rather move foldRight, reduceRight, :\ from Traversable to
Iterable. All 6 methods are in the same class -- they can be
implemented by Traversable only with the help of building another
size-n data-structure, whereas they have more efficient
implementations once Iterable's elements method is available.

Cheers

While on the subject of consistency and other API issues, I'm going to air out all the dirty laundry I've found so far:

1) What's the deal with reduceLeftOpt/reduceRightOpt vs firstOption/tailOption? I'm not really happy with either naming convention, but we should pick one and stick to it.

2) I count 14 uses of breakable/break. Of those, 1 is strictly unnecessary, and the rest can be implemented with just "return". Now, I know both break and return compile down to throwing an exception, but at least return is statically checked, guaranteed to be caught, and much harder to throw by mistake. If someone should, for example, call break (and forget to catch it) inside the function passed to "find", their program might be very subtly broken and they'd never realize it. It'd be much harder to accidentally call return than call break.

3) What's the difference between Array.concat and TraversableFactory#concat? Can we get rid of the one on Array (object)?

4) What's this Iterable.toOld/fromOld business? I imagine it was there from transition purposes. Is it obsolete now?

5) Will the new @specialized annotation be used? Everywhere or just judiciously? For example, there's a few methods on Array (object) that seem to be prime candidates.

6) There's a few comments in which there's an autor/author typo.

That's it for now. I'm sure I'll find more.

--j

On Thu, May 14, 2009 at 3:39 AM, Jorge Ortiz <jorge.ortiz@gmail.com> wrote:

I don't particularly care whether it's added or not (though if I had to I'd probably vote for inclusion), but can't it always be overriden in subclasses if there's a more efficient approach? Though, as David points out, the "more efficient" implementation isn't actually more efficient.

--j

On Thu, May 14, 2009 at 3:03 AM, martin odersky <martin.odersky@epfl.ch> wrote:

Good catch, Jorge! We should avoid that inconsistency. I am not quite
sure yet whether we should move reverse, dropRight, takeRight from
Iterable to Traversable, or whether we
should rather move foldRight, reduceRight, :\ from Traversable to
Iterable. All 6 methods are in the same class -- they can be
implemented by Traversable only with the help of building another
size-n data-structure, whereas they have more efficient
implementations once Iterable's elements method is available.

Cheers

On Thu, May 14, 2009 at 1:10 PM, Jorge Ortiz wrote:
> While on the subject of consistency and other API issues, I'm going to air
> out all the dirty laundry I've found so far:
>
> 1) What's the deal with reduceLeftOpt/reduceRightOpt vs
> firstOption/tailOption? I'm not really happy with either naming convention,
> but we should pick one and stick to it.

Agreed. Which one should it be? I believe Option has been around for
2.7, so probably pick that (I also do not care for either operation).

> 2) I count 14 uses of breakable/break. Of those, 1 is strictly unnecessary,

Which one?

> and the rest can be implemented with just "return". Now, I know both break
> and return compile down to throwing an exception, but at least return is
> statically checked, guaranteed to be caught, and much harder to throw by
> mistake.

Yes, but break should be more efficient, and that's what counts most here.

> If someone should, for example, call break (and forget to catch it)
> inside the function passed to "find", their program might be very subtly
> broken and they'd never realize it. It'd be much harder to accidentally call
> return than call break.
>
This could be solved by having a collection-private version of break.
But I am not sure it's worth it. It might be. But users that let break
escape in first-class functions are inviting disaster, no matter what.

> 3) What's the difference between Array.concat and TraversableFactory#concat?
> Can we get rid of the one on Array (object)?
>
Array.concat is more efficient because it can pre-allocate the array
after computing the right lengths. I think there's no harm leaving
both versions in. There are several other places where
we have overloaded specializations of a method which take specialized
parameter types.

> 4) What's this Iterable.toOld/fromOld business? I imagine it was there from
> transition purposes. Is it obsolete now?
>
Yes, I just removed them.

> 5) Will the new @specialized annotation be used? Everywhere or just
> judiciously? For example, there's a few methods on Array (object) that seem
> to be prime candidates.
>
That will take some more experimentation.

> 6) There's a few comments in which there's an autor/author typo.
>
OK, I'll go chase them

Thanks for the feedback!

On Thu, May 14, 2009 at 02:04:00PM +0200, martin odersky wrote:
> > 1) What's the deal with reduceLeftOpt/reduceRightOpt vs
> > firstOption/tailOption? I'm not really happy with either naming convention,
> > but we should pick one and stick to it.
>
> Agreed. Which one should it be? I believe Option has been around for
> 2.7, so probably pick that (I also do not care for either operation).

I think the temptation to add Opt/Option methods should be resisted with
great prejudice. It has to be antipattern. Look at the doc:

* @return If the iterable is non-empty,
the result of the operations as an Option, otherwise None.

Isn't that the very definition of mapping across the container? Can we
not instead devise a way to use all the existing methods which already
do this sort of thing?

And failing that, at least let us generalize the wrapper this amounts
to, for which this implementation might not be optimal in this case, but
anyway:

def wrap[T](f: => T): Option[T] =
try Some(f) catch { _: UnsupportedOperationException => None }

Now's our chance to raise the level of abstraction!

I think the Exception Zoo is a bit too complicated for some method like the "wrap" you proposed to be useful enough.

How about a "wap" (wrap + map?) method on Traversable that looks like:

  def wap(f: Traversable[T] => S): Option[S] =
    if (this.isEmpty) None else Some(f(this))

Then you've got

  t.reduceRight(_ + _)
  vs
  t.wap(_.reduceRight(_ + _))

  t.first
  vs
  t.wap(_.first)

Ok, so my name is a bit terrible. Some alternatives: wrap, wmap, wrapMap, guard...

An alternative implementation might be:

  def wrap: Option[Traversable[T]] =
    if (this.isEmpty) None else Some(this)

  t.wrap.map(_.first)
  t.first

--j

On Thu, May 14, 2009 at 10:53 AM, Paul Phillips <paulp@improving.org> wrote:

On Thu, May 14, 2009 at 02:04:00PM +0200, martin odersky wrote:
> > 1) What's the deal with reduceLeftOpt/reduceRightOpt vs
> > firstOption/tailOption? I'm not really happy with either naming convention,
> > but we should pick one and stick to it.
>
> Agreed. Which one should it be? I believe Option has been around for
> 2.7, so probably pick that (I also do not care for either operation).

I think the temptation to add Opt/Option methods should be resisted with
great prejudice.  It has to be antipattern.  Look at the doc:

  *  @return  If the iterable is non-empty,
     the result of the operations as an Option, otherwise None.

Isn't that the very definition of mapping across the container? Can we
not instead devise a way to use all the existing methods which already
do this sort of thing?

And failing that, at least let us generalize the wrapper this amounts
to, for which this implementation might not be optimal in this case, but
anyway:

 def wrap[T](f: => T): Option[T] =
   try Some(f) catch { _: UnsupportedOperationException => None }

Now's our chance to raise the level of abstraction!

--
Paul Phillips      | Adultery is the application of democracy to love.
Stickler           |     -- H. L. Mencken
Empiricist         |
all hip pupils!    |----------* http://www.improving.org/paulp/ *----------