traversable extensions: submitted for your disapproval

Nice.
Any reason permutations returns an Iterator and not an Iterable?
--j

On Mon, Sep 13, 2010 at 6:28 PM, Paul Phillips <paulp@improving.org> wrote:

Let's call this a strawman proposal, don't get too excited about any
particular function or choice of name.  I dredged some subset of the
collections methods I've wished for more than once and assembled it
along with my Iterator/Traversable map/flatMap generalization here:

 http://github.com/scala/scala/tree/traversable-2.9

The branch name is of course merely my optimistic label.  Here's a
summary of what's in there.  Some of these functions might exist only to
make the rest look better, like the really expensive pepper grinder
which makes the "only $50" grinder seem like a bargain.

   // Sequences
   def promoteIndex(index: Int): Repr
   def dropIndex(index: Int): Repr
   def extractIndex(index: Int): (A, Repr)
   def splitAround(index: Int): (Repr, A, Repr)
   def permutations: Iterator[Repr]

   // Traversable
   def inits: List[Repr]
   def tails: List[Repr]
   def cluster[A1 >: A : Equiv]: List[Repr]

   // TraversableOnce
   def mapWith[B](f: A => B): immutable.Map[A, B]
   def multiMapWith[B](f: A => B): immutable.Map[A, List[B]]
   def collectFirst[B](pf: PartialFunction[A, B]): Option[B]
   def maxBy[B](f: A => B)(implicit cmp: Ordering[B]): A
   def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A

Also, sprucing up Equiv (note its use in the cluster tests.)

http://github.com/scala/scala/blob/traversable-2.9/src/library/scala/math/Equiv.scala

The test case is your documentation.

// "Documentation"
class A {
 override def equals(other: Any) = other.isInstanceOf[A]
 override def toString = "A"
}
class B {
 override def equals(other: Any) = other.isInstanceOf[B]
 override def toString = "B"
}

object EquivTest {
 def to_s(xss: Seq[Seq[Any]]) = xss map (_.mkString) mkString " "

 def cluster() = {
   val xs = List("A".intern, "A".intern, new A, new A, new B, new B, new String("B"), new String("B"))

   List(
     to_s(xs.cluster) == "AA AA BB BB",
     to_s(xs cluster Equiv.reference) == "AA A A B B B B",
     to_s(xs cluster (Equiv by ((x: Any) => x.toString))) == "AAAA BBBB"
   )
 }

 def compares() = {
   val xs = List("1", "9", "5", "123", "99", "987", "555")

   List(
     (xs maxBy (_.toInt)) == "987",
     (xs minBy (_.toInt)) == "1",
     (xs mapWith (_.toInt / 3) get ("9")) == Some(3),
     (xs collectFirst { case x if x.last == '7' => x.toInt }) == Some(987)
   )
 }

 def run() = {
   cluster() foreach assert
   compares() foreach assert
 }
}

object SeqTest {
 val letters = "abcdef"

 def indexes() = List(
   (letters promoteIndex 3) == "dabcef",
   (letters dropIndex 3) == "abcef",
   (letters extractIndex 3) == ('d', "abcef"),
   (letters splitAround 3) == ("abc", 'd', "ef")
 )

 def seqs() = List(
   letters.permutations.size == 720,
   letters.permutations.toList.distinct.size == 720,
   "aaaaaaa".permutations.size == 1,
   (letters.tails mkString "-") == "abcdef-bcdef-cdef-def-ef-f-",
   (letters.inits mkString "-") == "abcdef-abcde-abcd-abc-ab-a-"
 )

 def run() = {
   indexes() foreach assert
   seqs() foreach assert
 }
}

object Test {
 def main(args: Array[String]): Unit = {
   EquivTest.run()
   SeqTest.run()
 }
}

--
Paul Phillips      | Every election is a sort of advance auction sale
Apatheist          | of stolen goods.
Empiricist         |     -- H. L. Mencken
pull his pi pal!   |----------* http://www.improving.org/paulp/ *----------

On Mon, Sep 13, 2010 at 10:55:07PM -0400, Jorge Ortiz wrote:
> Any reason permutations returns an Iterator and not an Iterable?

Because I remembered how fast factorial grows. That sucker is huge!

It should probably be an Iterable, but I have acquired some habits which
are hard to break when it comes to huge collections. Iterator, I trust
completely. Give an element the boot and he is booted. Relationship
with the other collections has been a bit more tempestuous.

It could be an Iterable view all the same. There are algorithms for computing iteration Nth.

On Tue, Sep 14, 2010 at 01:28, Paul Phillips <paulp@improving.org> wrote:

On Mon, Sep 13, 2010 at 10:55:07PM -0400, Jorge Ortiz wrote:
> Any reason permutations returns an Iterator and not an Iterable?

Because I remembered how fast factorial grows.  That sucker is huge!

It should probably be an Iterable, but I have acquired some habits which
are hard to break when it comes to huge collections.  Iterator, I trust
completely.  Give an element the boot and he is booted.  Relationship
with the other collections has been a bit more tempestuous.

--
Paul Phillips      | On two occasions, I have been asked, 'Mr. Babbage, if you
Moral Alien        | put into the machine wrong figures, will the right answers
Empiricist         | come out?' I am not able to rightly apprehend the kind of
i pull his palp!   | confusion of ideas that could provoke such a question.

--
Daniel C. Sobral

I travel to the future all the time.

What does "promoteIndex" do on a Sequence?

> Date: Mon, 13 Sep 2010 15:28:31 -0700
> From: paulp@improving.org
> To: scala-internals@listes.epfl.ch
> Subject: [scala-internals] traversable extensions: submitted for your disapproval
>
> Let's call this a strawman proposal...
> http://github.com/scala/scala/tree/traversable-2.9
>
> // Sequences
> def promoteIndex(index: Int): Repr
> def dropIndex(index: Int): Repr
> def extractIndex(index: Int): (A, Repr)
> def splitAround(index: Int): (Repr, A, Repr)
> def permutations: Iterator[Repr]

>>>>> "Paul" == Paul Phillips writes:

Paul> Let's call this a strawman proposal, don't get too excited about
Paul> any particular function or choice of name. I dredged some subset
Paul> of the collections methods I've wished for more than once and
Paul> assembled it along with my Iterator/Traversable map/flatMap
Paul> generalization here:
Paul> http://github.com/scala/scala/tree/traversable-2.9

+1 on inits, tails, maxBy, minBy. I use my own versions of those all
the time.