Как идиоматически итеративно flatMap коллекция против своих членов?

Question

Простой класс с flatMap/карта, которая не делает ничего, но лениво хранить значение:

[Note1: этот класс может быть заменен любого класса с flatMap/карты. Вариант - это только один конкретный пример, этот вопрос относится к общему случаю]

[Примечание2: scalaz - интересная библиотека, но этот вопрос не относится к ней. Если нет станд Scala решение библиотеки, кроме того, что я писал ниже, что является приемлемым]

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

Функция, которая итеративно применяется flatMap к своим членам:.

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

функции в действии:

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

Есть ли способ переписать «инвертировать» идиоматически? Кроме того, есть ли функциональный «глагол», который фиксирует то, что я здесь делаю?

Answer 1

Проблема с вашим решением является то, что он даст переполнение стека для больших списков, как это полностью (не только хвост) рекурсивный. Я бы вместо того, чтобы сложить:

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

Answer 2

Вы можете сделать invert немного яснее спичкой шаблона, но это по сути тот же код:

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