CODEWITHSUNDEEP
scalascala-collections
Lance Gatlin
Lance Gatlin

Reputation: 203

How to idiomatically iteratively flatMap a collection against its own members?

A simple class with flatMap/map that does nothing but lazily store a value:

[Note1: this class could be replaced with any class with flatMap/map. Option is only one concrete example, this question is in regards to the general case]

[Note2: scalaz is an interesting library, but this question is not in regards to it. If there is not a std scala library solution other than what I have posted below, that is acceptable.]

class C[A](value : => A) {
   def flatMap[B](f: A => C[B]) : C[B] = { f(value) }
   def map[B](f: A => B) : C[B] = { new C(f(value)) }
   override def toString = s"C($value)"
}
object C {
   def apply[A](value : => A) = new C[A](value)
}

A function that iteratively applies flatMap to its members:

def invert[A](xs: Traversable[C[A]], acc: List[A] = Nil) : C[List[A]] =
  if(xs.nonEmpty) {
    xs.head flatMap { a => invert(xs.tail, a :: acc) }
  } else {
    C(acc.reverse)
  }

Function in action:

scala> val l = List(C(1),C(2),C(3))
l: List[C[Int]] = List(C(1), C(2), C(3))

scala> invert(l)
res4: C[List[Int]] = C(List(1, 2, 3))

Is there a way rewrite "invert" idiomatically? Also, is there a functional "verb" that captures what I'm doing here?

Upvotes: 2

Views: 174

Answers (2)

Rex Kerr
Rex Kerr

Reputation: 167891

The problem with your solution is that it will give a stack overflow for large lists, as it is fully (not just tail) recursive. I'd fold instead:

def invert[A](xs: Traversable[C[A]]) =
  (C(List[A]()) /: xs){ (c,x) => c.flatMap(l => x.map(_ :: l)) }.map(_.reverse)

Upvotes: 1

Randall Schulz
Randall Schulz

Reputation: 26486

You might make invert a bit clearer with a pattern match, but it's essentially the same code:

xs match {
  case x0 :: xMore => x0.flatMap(a => invert(xMore, a :: acc))
  case Nil => C(acc.reverse)
}

Upvotes: 0

Related Questions