o/~ You... slice up my life... o/~

That's a big slice of crazy,
but I like that.

All hail Hastur, the King in Yellow

On Thu, Feb 24, 2011 at 11:12 PM, Paul Phillips <paulp@improving.org> wrote:

// "What up, Home Slice!?"
//    or
// A Little Life of Slice
//
//   by extempore
//   with thanks to 4.5 hours in the air with no wifi
//   it's all written on the plane and I'm sending from baggage claim
//   so don't hold me to any of it, or anything else, ever again
//
// PRELUDE: ASK NOT FOR WHOM THE SLICE DROPS...
//
//    scala> scala.collection.mutable.ListBuffer(1 to 3: _*).slice(-3, -1)
//    res0: scala.collection.mutable.ListBuffer[Int] = ListBuffer(1, 2)
//
// Investigating the behavior shown above led me to discover there
// are 25 concrete implementations of "slice" in the collections.
// Resolved to discover how that could possibly be given that the
// 2.8 collections should represent a triumph of not repeating ourselves,
// I embarked on a journey which I recorded with my programmer helmetcam.
// Come relive it with me, if you dare.  Pregnant programmers and those
// with heart conditions are advised to avoid this ride.
//
// Some slices literally implement the claim in the docs that
//
//   xs.slice(from, to)  ===  xs.drop(from).take(to - from)
//
// Unfortunately the literal interpretation results in undesirable
// behavior when given any negative arguments.  More importantly, some
// slices adjust their arguments to avoid this, some don't, and which
// you get is a spin of implementation roulette.
//
// scala> (1 to 10).iterator.slice(-8, -5).toList
// res0: List[Int] = List(1, 2, 3)
//
// scala> (1 to 10).toBuffer.slice(-8, -5)
// res1: scala.collection.mutable.Buffer[Int] = ArrayBuffer()
//
// scala> scala.collection.mutable.ListBuffer(1 to 10: _*).slice(-8, -5)
// res2: scala.collection.mutable.ListBuffer[Int] = ListBuffer(1, 2, 3)
//
// scala> scala.collection.mutable.ListBuffer(1 to 10: _*).readOnly.slice(-8, -5)
// res3: List[Int] = List()
//
// Hereafter, "correct" behavior refers not to what's in the docs
// but what I think should happen, i.e. you only ever get back elements
// whose indices lie between your given lower and given upper.
//
// Claim: barring a specific, locally applicable reason otherwise,
// either drop and take should be implemented in terms of slice,
// or slice should be implemented in terms of drop and take.

// Option 1: slice is emperor, take/drop are servants
def slice(from: Int, until: Int): Repr = /* impl */
def take(n: Int): Repr = slice(0, n)
// "end" stands in for length if size/length if that is free,
// or Int.MaxValue otherwise.
def drop(n: Int): Repr = slice(n, end)

// Option 2: take/drop are co-presidents, slice is gopher
def take(n: Int): Repr = /* impl */
def drop(n: Int): Repr = /* impl */
def slice(from: Int, until: Int): Repr = {
 val lo = from max 0
 drop(lo) take (until - lo)
}

// Option 3: if these don't satisfy, slice, take, and drop swear common
// allegiance to Hastur the Unspeakable (sometimes called a private method.)
def take(n: Int): Repr = hastur(n, ...)
def drop(n: Int): Repr = hastur(..., n, ...)
def slice(from: Int, until: Int): Repr = hastur(from, until, ...)
private def hastur(...) = /* impl */

/**** AND NOW LADIES AND GENTLEMEN... THE IMPLEMENTATIONS!
 *  [The slice implementations are the focus, but often can't be
 *  appreciated without seeing drop and take, so those are included
 *  when the circumstances called for them.]
 ****/

TraversableLike
 Recommend: Option 1, possibly with minor adjustment.

// Traversable, the collections patriarch who does everything the hard way.
// "All I have is foreach and I will laboriously discard individual pecans
// until it's time to fill the pecan jar.  I'm old school!""
//
// Behavior in the face of negativity: hosed in unique fashion.  Like
// many implementations in Traversable, it is pretty much impossible
// to encounter it unless you go out of your way, because Iterable
// overrides it. So let's go out of our way.
//
// scala> def f = new Traversable[Int] { def foreach[U](f: Int => U): Unit = List(1, 2, 3, 4, 5) foreach f }
// f: java.lang.Object with Traversable[Int]
//
// scala> f.slice(-3, -1)
// res0: Traversable[Int] = List(1, 2, 3, 4, 5)
//
// scala> f.slice(-1, -3)
// res1: Traversable[Int] = List(1, 2, 3, 4, 5)
//
// scala> f.slice(-1, -1)
// res2: Traversable[Int] = List(1, 2, 3, 4, 5)
//

def slice(from: Int, until: Int): Repr = {
 val b = newBuilder
 b.sizeHintBounded(until - from, this)
 var i = 0
 breakable {
   for (x <- this) {
     if (i >= from) b += x
     i += 1
     if (i == until) break
   }
 }
 b.result
}

// Notice that this does nothing which would distinguish
// it from slice(0, n).
def take(n: Int): Repr = {
 val b = newBuilder
 b.sizeHintBounded(n, this)
 var i = 0
 breakable {
   for (x <- this) {
     if (i >= n) break
     b += x
     i += 1
   }
 }
 b.result
}

// FACT: "take" is overridden in IterableLike, but "drop" is not.
// COROLLARY: this is Iterable's implementation too.
// Can you feel the suspense building?
def drop(n: Int): Repr = {
 val b = newBuilder
 if (n >= 0) b.sizeHint(this, -n)
 var i = 0
 // Uh-oh, no breakable/break!
 for (x <- this) {
   if (i >= n) b += x
   i += 1
 }
 b.result
}

 // SIDEBAR: what happens when TraversableLike implements
 // drop without breaking after n elements.
 // BUG THRILL RATING: 7/10

 /*
 // Take this home and run it yourself! My treat.
 object OrdersOfMagnitude {
   val xs = (1 to 5000000).toList
   // Just a wrapper which exposes the native Traversable implementations.
   val ys = new Traversable[Int] { def foreach[U](f: Int => U): Unit = xs foreach f }
   // As noted earlier, Iterable[Int] is equally exciting.
   // val ys = new Iterable[Int] { def iterator = xs.iterator }

   def timed(body: => Unit): Long = {
     val t1 = System.nanoTime
     body
     val t2 = System.nanoTime
     t2 - t1
   }

   def main(args: Array[String]): Unit = {
     println("xs take 1: " + List.fill(5)(timed(xs take 1)).sum)
     println("xs drop 1: " + List.fill(5)(timed(xs drop 1)).sum)
     println("ys take 1: " + List.fill(5)(timed(ys take 1)).sum)
     println("ys drop 1: " + List.fill(5)(timed(ys drop 1)).sum)
   }
 }
 */

 // Output:
 //
 // % scala29 OrdersOfMagnitude
 // xs take 1: 81000
 // xs drop 1: 17000
 // ys take 1: 565000
 // ys drop 1: 7655007000

IterableLike
 Recommend: override slice, otherwise inherit Option 1 from TraversableLike.

// "I look down my nose at Traversable, my clumsy, slightly deranged
// uncle who I usually keep chained up in the attic.  But I like to let him
// out just often enough to keep things exciting."
//
// Behavior in the face of negativity: hosed in typical fashion.
// (Contrast with TraversableLike.)
//
// scala> def f = new Iterable[Int] { def iterator = List(1, 2, 3, 4, 5).iterator }
// f: java.lang.Object with Iterable[Int]
//
// scala> f.slice(-3, -1)
// res3: Iterable[Int] = List(1, 2)
//
// scala> f.slice(-1, -3)
// res4: Iterable[Int] = List()
//
// scala> f.slice(-1, -1)
// res5: Iterable[Int] = List()
//

override /*TraversableLike*/ def slice(from: Int, until: Int): Repr = {
 val b = newBuilder
 b.sizeHintBounded(until - from, this)
 var i = from
 val it = iterator drop from
 while (i < until && it.hasNext) {
   b += it.next
   i += 1
 }
 b.result
}

// Once again, identical to slice(0, n).
override /*TraversableLike*/ def take(n: Int): Repr = {
 val b = newBuilder
 b.sizeHintBounded(n, this)
 var i = 0
 val it = iterator
 while (i < n && it.hasNext) {
   b += it.next
   i += 1
 }
 b.result
}

/** No drop implementation! Yin without yang? */

List
 Recommend: further study

// "You all use me pretty much everywhere whether it makes sense
// or not.  My reign will go on forever! A ha ha ha!"
//
// Behavior in the face of negativity: correct, returns empty list
// on all nonsense combinations.  Don't feel like analyzing these
// implementations; may or may not be redundant.

override def slice(start: Int, end: Int): List[A] = {
 var len = end
 if (start > 0) len -= start
 drop(start) take len
}

override def take(n: Int): List[A] = {
 val b = new ListBuffer[A]
 var i = 0
 var these = this
 while (!these.isEmpty && i < n) {
   i += 1
   b += these.head
   these = these.tail
 }
 if (these.isEmpty) this
 else b.toList
}

override def drop(n: Int): List[A] = {
 var these = this
 var count = n
 while (!these.isEmpty && count > 0) {
   these = these.tail
   count -= 1
 }
 these
}

Range
 Recommend: VAPORIZE.

// o/~ I am the very model of a redundant slice override... o/~

final override def slice(from: Int, until: Int): Range =
 this drop from take (until - from)

Stream
 Recommend: VAPORIZE.

// o/~ I'm singing... in chorus... with Range! *Jazz Hands* o/~

override def slice(start: Int, end: Int): Stream[A] = {
 var len = end
 if (start > 0) len -= start
 drop(start) take len
}

Vector
 Recommend: Acknowledge higher cleverness level, then VAPORIZE.

// Vector achieves the desirable behavior without doing any arithmetic, even if
// one or both arguments are negative: but we'd still rather reuse one implementation,
// unless this is somehow faster than drop-then-take.  (I don't see how it
// could be, but I don't want to pessimize any more of tiark's code, so...?)

override /*IterableLike*/ def slice(from: Int, until: Int): Vector[A] =
 take(until).drop(from)

IndexedSeqOptimized
 Recommend: Further Study; probably No Action

// Good news! IndexSeqOptimized chose Option 1 before we even called it that.
// I need a refresher on what IndexedSeqOptimized is supposed to do relative
// to IndexedSeqLike.  But if the gist is that for whatever reason we don't
// want to do any overrides in IndexedSeqLike, then it's about ready to go.

override /*IterableLike*/
def slice(from: Int, until: Int): Repr = {
 var i = from max 0
 val end = until min length
 val b = newBuilder
 b.sizeHint(end - i)
 while (i < end) {
   b += this(i)
   i += 1
 }
 b.result
}

override /*TraversableLike*/
def take(n: Int): Repr = slice(0, n)

override /*TraversableLike*/
def drop(n: Int): Repr = slice(n, length)

LinearSeqOptimized
 Recommend: VAPORIZE, use Option 1.

// Narrator: "Only two choices for code in this crazy world.
// Either we get busy executing, or we get busy bitrotting.  When I met
// LinearSeqOptimized I thought for sure he was the second kind, but
// he had depths none of us could have imagined.  By the way, I sound
// exactly like Morgan Freeman: uncanny, isn't it?""

override /*IterableLike*/
def slice(from: Int, until: Int): Repr = {
 val b = newBuilder
 var i = from
 var these = this drop from
 while (i < until && !these.isEmpty) {
   b += these.head
   these = these.tail
   i += 1
 }
 b.result
}

// Notice yet another take implementation which could be slice(0, n).
override /*IterableLike*/
def take(n: Int): Repr = {
 val b = newBuilder
 var i = 0
 var these = repr
 while (!these.isEmpty && i < n) {
   i += 1
   b += these.head
   these = these.tail
 }
 b.result
}

// Poor LinearSeqOptimized gamely attempts to optimize drop by foregoing
// the builder, which would be fine if this were immutable.LinearSeqOptimized.
// But << DA DUH DA >> it's collection.LinearSeqOptimized.
override /*TraversableLike*/
def drop(n: Int): Repr = {
 // I don't need a builder! I'm optimized!
 var these: Repr = repr
 var count = n
 while (!these.isEmpty && count > 0) {
   these = these.tail
   count -= 1
 }
 these
}

// You can hear faint strains of "Singing in the Rain" as we cut over to

 // SIDEBAR: what happens when our enthusiastic friend tries to share
 // That Which Must Not Be Shared.
 // BUG THRILL RATING: 8/10
 //
 // scala> scala.collection.mutable.Queue(1 to 10: _*)
 // res0: scala.collection.mutable.Queue[Int] = Queue(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
 //
 // scala> res0 drop 5
 // res1: scala.collection.mutable.MutableList[Int] = MutableList(6, 7, 8, 9, 10) // minor bug: wrong return type
 //
 // scala> res0(9) = 72
 //
 // scala> res1
 // res3: scala.collection.mutable.MutableList[Int] = MutableList(6, 7, 8, 9, 72) // major bug: oops
 //
 // scala> res0 dropWhile (_ < 6)
 // res4: scala.collection.mutable.MutableList[Int] = Queue(6, 7, 8, 9, 72)
 //
 // scala> res0(8) = 59123
 //
 // scala> res4
 // res6: scala.collection.mutable.MutableList[Int] = Queue(6, 7, 8, 9, 72) // dropWhile doesn't share
 //
 // scala> res1
 // res7: scala.collection.mutable.MutableList[Int] = MutableList(6, 7, 8, 59123, 72) // still oops
 //
 // scala> res3 take 3
 // res8: scala.collection.mutable.MutableList[Int] = MutableList(6, 7, 8)
 //
 // scala> res8(0) = 5591
 //
 // scala> res3
 // res10: scala.collection.mutable.MutableList[Int] = MutableList(6, 7, 8, 59123, 72) // take doesn't share

StringOps
 Recommend: Move to StringLike

// "I am the best example of a legitimate slice override you will
//  ever meet.  I say this not to boast but as simple fact.  I take
//  my job seriously.  I am... StringOps."
//
// True enough, but WrappedString is the same implementation.

override def slice(from: Int, until: Int): String = {
 val start = from max 0
 val end   = until min repr.length

 if (start >= end) ""
 else repr.substring(start, end)
}

WrappedString
 Recommend: Move to StringLike

override def slice(from: Int, until: Int): WrappedString =
 new WrappedString(self.substring(from max 0, until min self.length))

/****
 * And the plane lands! The story disintegrates into an unintelligible
 * jumble! That is, a different one than before!
 *
 ****/

/** Everything beyond this point was published from the author's
 *  private notes, discovered years after his untimely demise.  If you think
 *  "Daisy-Head Maizie" is just as good as "The Glunk that got Thunk"
 *  then you should definitely proceed.
 *
 *  (Actually it's pretty close to done, informationwise.)
 */

// These feel redundant, but I have to look more closely at
// the parallel collections to say.

ParIterableLike

override def slice(unc_from: Int, unc_until: Int): Repr = {
 val from = unc_from min size max 0
 val until = unc_until min size max from
 if ((until - from) <= MIN_FOR_COPY) slice_sequential(from, until)
 else executeAndWaitResult(new Slice(from, until, cbfactory, parallelIterator) mapResult { _.result })
}

private def slice_sequential(from: Int, until: Int): Repr = {
 val cb = newCombiner
 var left = until - from
 val it = parallelIterator drop from
 while (left > 0) {
   cb += it.next
   left -= 1
 }
 cb.result
}

PagedSeq
 Recommend: Host Televised Benefit for Doubt

// Not sure what all is going on here but we'll give it the
// benefit of the doubt.

override def slice(_start: Int, _end: Int): PagedSeq[T] = {
 page(start)
 val s = start + _start
 val e = if (_end == UndeterminedEnd) _end else start + _end
 var f = first1
 while (f.end <= s && !f.isLast) f = f.next
 new PagedSeq(more, f, s, e)
}

At least tell us that this was a long-haul flight, rather than, say, SF to Sacramento?

> Date: Thu, 24 Feb 2011 14:12:59 -0800
> From: paulp@improving.org
> To: scala-internals@googlegroups.com
> Subject: [scala-internals] o/~ You... slice up my life... o/~
>
> // "What up, Home Slice!?"
> // or
> // A Little Life of Slice
>

On 2/25/11 5:55 AM, Chris Marshall wrote:
> At least tell us that this was a long-haul flight, rather than, say, SF
> to Sacramento?

SF to Boston. One of my bugs turns out not to be a bug, too. You
forget how little one can do sensibly when "foreach" is the only tool at
hand.

Great detective/literary works here.
I'm a fan of implementing take/drop in terms of slice, however if we choose the opposite, I think maybe we should think about slice(m,n) = view.take(n).drop(m).force, assuming views are as efficient as they should be with take & drop.  Plus, everyone loves a good view right?
- Josh
On Fri, Feb 25, 2011 at 10:14 AM, Paul Phillips <paulp@improving.org> wrote:

On 2/25/11 5:55 AM, Chris Marshall wrote:

At least tell us that this was a long-haul flight, rather than, say, SF
to Sacramento?

SF to Boston.  One of my bugs turns out not to be a bug, too.  You forget how little one can do sensibly when "foreach" is the only tool at hand.

On 2/25/11 10:41 AM, Josh Suereth wrote:
> I'm a fan of implementing take/drop in terms of slice, however if we
> choose the opposite, I think maybe we should think about slice(m,n) =
> view.take(n).drop(m).force, assuming views are as efficient as they
> should be with take & drop. Plus, everyone loves a good view right?

On paper maybe? I don't have that kind of confidence in views. As the
guy in the muck, it seems like one more thing to go wrong without
offering much recompense besides a slightly cleaner high level method.

Yeah, I'm hoping to get some time here to restore confidence in views.   However, I still think having slice be the core function and implementing everything else in terms of slice is the right way to go.  
On Fri, Feb 25, 2011 at 11:33 AM, Paul Phillips <paulp@improving.org> wrote:

On 2/25/11 10:41 AM, Josh Suereth wrote:

I'm a fan of implementing take/drop in terms of slice, however if we
choose the opposite, I think maybe we should think about slice(m,n) =
view.take(n).drop(m).force, assuming views are as efficient as they
should be with take & drop.  Plus, everyone loves a good view right?

On paper maybe? I don't have that kind of confidence in views.  As the guy in the muck, it seems like one more thing to go wrong without offering much recompense besides a slightly cleaner high level method.

On Fri, Feb 25, 2011 at 8:48 AM, Josh Suereth <joshua.suereth@gmail.com> wrote:

Yeah, I'm hoping to get some time here to restore confidence in views.   However, I still think having slice be the core function and implementing everything else in terms of slice is the right way to go.  

+1.  Splitters can be lumped more easily than lumpers can be split[1]. ;)
-0xe1a
1: http://www.devshed.com/c/a/Practices/The-System-in-So-Many-Words/4/

On Thu, Feb 24, 2011 at 11:12 PM, Paul Phillips <paulp@improving.org> wrote:

// "What up, Home Slice!?"
//    or
// A Little Life of Slice
//
//   by extempore
//   with thanks to 4.5 hours in the air with no wifi
//   it's all written on the plane and I'm sending from baggage claim
//   so don't hold me to any of it, or anything else, ever again
//
// PRELUDE: ASK NOT FOR WHOM THE SLICE DROPS...
//
//    scala> scala.collection.mutable.ListBuffer(1 to 3: _*).slice(-3, -1)
//    res0: scala.collection.mutable.ListBuffer[Int] = ListBuffer(1, 2)
//
// Investigating the behavior shown above led me to discover there
// are 25 concrete implementations of "slice" in the collections.
// Resolved to discover how that could possibly be given that the
// 2.8 collections should represent a triumph of not repeating ourselves,
// I embarked on a journey which I recorded with my programmer helmetcam.
// Come relive it with me, if you dare.  Pregnant programmers and those
// with heart conditions are advised to avoid this ride.
//
// Some slices literally implement the claim in the docs that
//
//   xs.slice(from, to)  ===  xs.drop(from).take(to - from)
//

// Unfortunately the literal interpretation results in undesirable
// behavior when given any negative arguments.  

Oops, you are right. I think the best way forward is to define take and drop in terms of slice then. For views they do it already.

Cheers