foldLeft, initialize with first operation and skip first

Question

I have a collection I'm foldLefting over to yield another collection. I initialize the foldLeft with an empty collection of the desired type.

collection1.foldLeft(collection[T]())(op)

My first test tests whether or not the collection in the fold operation is empty, and then creates one out of the folded collection if so.

collection1.foldLeft(collection[T]())({
  { case(t,otherstuff) =>
     if(t.isEmpty) new T(otherstuff) else ...}
})

Seeing as how I'm initializing an empty collection and always throwing it away, is it possible to do the initial collection creation (the response to the empty collection) in the initialization stage?

collection1.foldLeft(new T(collection1.first))({ // but SKIP first
  { case(t,otherstuff) =>
     ...}
})

Answer 1

This mostly just strikes me as a bad idea, the reason you'd initialize the accumulator with an empty collection is so that you can operate uniformly, i.e. normally you don't have special-case logic like if(t.isEmpty) ... else ...

I don't know your application, though, so let's suppose you really need to do this, that whatever you are doing in your ordinary operation requires a nonempty Collection which must first be initialized with a single-element Collection that contains the first encountered element but then must operate differently thereafter.

The first thing to point out is that your existing approach may not be terrible. You are working to eliminate one object allocation, which is unlikely to be a performance bottleneck. "Premature optimization is the root of all evil", sez Donald Knuth.

A second thing to point out is that you oughtn't in general create an empty Collection in scala as collection[T](). If collection stands in for the name of some collection class or trait, there is probably a method like collection.empty[T] that provides an empty instance without a new allocation each time. So the simplest optimization is just...

collection1.foldLeft(collection.empty[T])({
  { case(t,otherstuff) =>
     if(t.isEmpty) new T(otherstuff) else ...}
})

If collection stands in for some custom immutable collection class whose companion does not offer an empty method, define one, in the collection's companion object if you can, elsewhere if you can't.

private val emptyCollection = collection[Nothing]() 
def empty[T] : collection = emptyCollection.asInstanceOf[T]

If you are sure that the collection you fold over will contain at least one element, you could avoid the empty check every time with:

val pair = collection1.splitAt(1)
pair._2.foldLeft(pair._1){(col, next) =>
  ...
}

Where ... is the else case of your original empty check, no more if necessary. To make that general, wrap it in a test

if ( !collection1.isEmpty ) {
  val pair = collection1.splitAt(1)
  pair._2.foldLeft(pair._1){(col, next) =>
    ...
  }
} else {
  appropriateDefaultResult
}

Answer 2

You don't really want to use a fold to yield another collection. Folds are essentially a variation reduce. reduce uses some value in the collection as a starting point to accumulate a value, and is designed specifically for a commutative and associative operation on a collection. fold operations lack both of these constraints, but they can't be split into concurrent operations because each accumulation must happen in order.

Is there a reason that standard for-loop list comprehensions won't work for you?

Answer 3

IIUYC, then you need to pick first item out of collection and perform fold on the tail of the collection. If the input collection is empty you would like to return an empty collection.

I don't think fold is the right tool here. Try reduceLeftOption. It seems to be the perfect tool for this job. It will pick the leftmost element as accumulator for the first iteration and do fold on the remaining items.

collection1.reduceLeftOption[T]((accumulator, element) => ...)

You can then perform match on the result of the above expression to return what you want.

collection1.reduceLeftOption[T]((accumulator, element) => ...)
    .getOrElse(collection[T]())

See a full example here.