¿Forma genérica y segura para apilar colecciones anidadas arbitrariamente en Scala?

Question

En ocasiones me tomo un tiempo para jugar con Scala, cuya combinación de características me atrae a pesar de la incapacidad de usarlo en mi propio trabajo (hasta ahora). Para las patadas, decidí probar los primeros 99 Haskell Problems de la manera más genérica posible, operando y devolviendo cualquier clase de colección aplicable. Las primeras preguntas no fueron demasiado difíciles, pero me encuentro totalmente bloqueado por flatten. Simplemente no puedo entender cómo escribir tal cosa.

Para ser específico sobre mi pregunta: ¿es posible escribir una función de tipo seguro que aplana de forma arbitraria SeqLike s? Así que, por ejemplo,

flatten(List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))) 

volvería

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12): List[Int] 

? Tenga en cuenta que esta no es la misma pregunta que en los conjuntos de problemas de Haskell y Scala; Intento escribir una función que aplana listas no heterogéneas, sino más bien secuencias homogéneas pero anidadas.

Buscando en la web Encontré translation into Scala de esa pregunta, pero funciona y devuelve una Lista [Cualquiera]. ¿Estoy en lo correcto al decir que esto requeriría algún tipo de recursión de tipo? ¿O estoy haciendo que esto sea más difícil de lo que es?

Answer 1

Lo siguiente funciona en Scala 2.10.0-M7. Usted tendrá que añadir casos extra para Array apoyo, y tal vez refinarlo para tener tipos de colección de salida más específicos, pero supongo que todo se puede hacer a partir de aquí:

sealed trait InnerMost { 
    implicit def innerSeq[A]: CanFlatten[Seq[A]] { type Elem = A } = 
    new CanFlatten[Seq[A]] { 
     type Elem = A 
     def flatten(seq: Seq[A]): Seq[A] = seq 
    } 
} 
object CanFlatten extends InnerMost { 
    implicit def nestedSeq[A](implicit inner: CanFlatten[A]) 
    : CanFlatten[Seq[A]] { type Elem = inner.Elem } = 
    new CanFlatten[Seq[A]] { 
     type Elem = inner.Elem 
     def flatten(seq: Seq[A]): Seq[inner.Elem] = 
     seq.flatMap(a => inner.flatten(a)) 
    } 
} 
sealed trait CanFlatten[-A] { 
    type Elem 
    def flatten(seq: A): Seq[Elem] 
} 

implicit final class FlattenOp[A](val seq: A)(implicit val can: CanFlatten[A]) { 
    def flattenAll: Seq[can.Elem] = can.flatten(seq) 
} 

// test   
assert(List(1, 2, 3).flattenAll == Seq(1, 2, 3)) 
assert(List(Seq(List(1, 2, 3), List(4, 5, 6)), Seq(List(7, 8, 9), 
       List(10, 11, 12))).flattenAll == (1 to 12).toSeq) 

Answer 2

Usted está enfrentando los mismos problemas que están describiendo en el Haskell solution: No hay List heterogéneos en Scala. Afortunadamente, puede seguir exactamente el mismo camino que siguen en la solución Haskell.

definir algunos tipos de datos que se pueden anidarse:

sealed trait NestedList[A] 
case class Elem[A](a: A) extends NestedList[A] 
case class AList[A](a: List[NestedList[A]]) extends NestedList[A] 

y luego escribir una función aplanar genérica para ese tipo:

def flatten[A](l: NestedList[A]): List[A] = l match { 
    case Elem(x) => List(x) 
    case AList(x :: xs) => flatten(x) ::: flatten(AList(xs)) 
    case AList(Nil) => Nil 
} 

o incluso

def flatten[A](l: NestedList[A]): List[A] = l match { 
    case Elem(x) => List(x) 
    case AList(x) => x.flatMap(flatten) 
} 

Uso:

flatten(AList(Elem(1) :: Elem(2) :: AList(Elem(3) :: Nil) :: Nil)) 

Por supuesto, también podríamos haber agregado esto como un método directamente al rasgo NestedList.

Answer 3

Parece que lo que hay que hacer es llamar a .flatten el número correcto de veces:

scala> val x = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12))) 
x: List[Array[List[Int]]] = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12))) 

scala> x.flatten.flatten 
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) 

Desde Scala se escribe, siempre se sabe de antemano la profundidad de la anidación ocurre con la variable específica. Como ya sabe esto con anticipación, no tiene mucho valor manejar una estructura arbitraria como si no estuviera seguro de cuántas veces se necesitó llamar al .flatten.