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

Question

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?

possible duplicate of [Convert a List of Options to an Option of List using Scalaz](http://stackoverflow.com/questions/2569014/convert-a-list-of-options-to-an-option-of-list-using-scalaz). Not exactly the same use case but the expected result is the same. — kiritsuku, Feb 19 '13 at 15:20
It's never clear what someone's intent is when there are several (5) compilation errors in the code presented... — Randall Schulz, Feb 19 '13 at 15:28
I would like to avoid a scalaz solution, thanks. If there is no idiomatic scala solution, that is an acceptable answer. — Lance Gatlin, Feb 19 '13 at 15:31
Compiles just fine for me. Scala 2.10 -- perhaps you accidentally copied the comments? — Lance Gatlin, Feb 19 '13 at 15:33
As a suggestion I'd call the function "sequence" since it's a naming convention already established in more than one case, to identify a transformation from a sequence of monads to a monad of sequence. Do as you see fit. — pagoda_5b, Feb 19 '13 at 17:00

score 1 · Accepted Answer · answered Feb 19 '13 at 15:49

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)

score 0 · Answer 2 · answered Feb 19 '13 at 15:31

0

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)
}

answered Feb 19 '13 at 15:31

Randall Schulz

26,420
4
61
81

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

2 Answers2