压扁相同类型的嵌套列表(Flattening nested lists of the same ty

比方说，我要弄平相同类型的嵌套列表...例如

    ListA(Element(A), Element(B), ListA(Element(C), Element(D)), ListB(Element(E),Element(F)))

ListA包含相同类型（嵌套列表ListA(Element(C), Element(D))所以我想用它包含的值来替代它，所以上面例子的结果应该是这样的：

ListA(Element(A), Element(B), Element(C), Element(D), ListB(Element(E),Element(F)))

目前的类层次结构：

abstract class SpecialList() extends Exp {
    val elements: List[Exp]
}

case class Element(name: String) extends Exp

case class ListA(elements: List[Exp]) extends SpecialList {
        override def toString(): String = "ListA("+elements.mkString(",")+")"
}

case class ListB(elements: List[Exp]) extends SpecialList {
        override def toString(): String = "ListB("+elements.mkString(",")+")"
}

object ListA{def apply(elements: Exp*):ListA = ListA(elements.toList)}
object ListB{def apply(elements: Exp*):ListB = ListB(elements.toList)}

我做了三种解决方案的工作，但我认为必须要更好的方式来实现这一目标：

第一个解决方案：

def flatten[T <: SpecialList](parentList: T): List[Exp] = {
        val buf = new ListBuffer[Exp]

        for (feature <- parentList.elements) feature match {
            case listA:ListA if parentList.isInstanceOf[ListA] => buf ++= listA.elements
            case listB:ListB if parentList.isInstanceOf[ListB] => buf ++= listB.elements
            case _ => buf += feature
        }
        buf.toList
    }

解决方法二：

def flatten[T <: SpecialList](parentList: T): List[Exp] = {
    val buf = new ListBuffer[Exp]

    parentList match {
        case listA:ListA => for (elem <- listA.elements) elem match {
                                case listOfTypeA:ListA => buf ++= listOfTypeA.elements
                                case _ => buf += elem
                            }

        case listB:ListB => for (elem <- listB.elements) elem match {
                                case listOfTypeB:ListB => buf ++= listOfTypeB.elements
                                case _ => buf += elem
                            }
    }

    buf.toList
}

第三种解决方案

def flatten[T <: SpecialList](parentList: T): List[Exp] = parentList.elements flatMap {
    case listA:ListA if parentList.isInstanceOf[ListA] => listA.elements
    case listB:ListB if parentList.isInstanceOf[ListB] => listB.elements
    case other => List(other)
}

我的问题是，是否有任何更好的，更通用的方法来实现相同的功能在所有上面的三个解决方案有码重复？

Answer 1:

一个真正的功能性的方式。 如果不使用一个变量。

def flatten[A](list: List[A]): List[A] = list match {
   case Nil => Nil
   case (ls: List[A]) :: tail => flatten(ls) ::: flatten(tail)
   case h :: tail => h :: flatten(tail)
}

Answer 2:

我prefere一个递归的方式。 一般来说，我会做这样的事情：

def flattenList[A](l: List[Any]): List[A] = {
  var acc = List[A]()
  l foreach ( entry => entry match {
    case a: List[Any] => acc = acc ::: flattenList(a)
    case b: A => acc = acc :+ b
  })
  acc
}

这将压扁你一个List(Element(A), Element(B), List(Element(C), Element(D), List(Element(E), Element(F))))以List(Element(A), Element(B), Element(C), Element(D), Element(E), Element(F))

Answer 3:

在一个理想的世界里，可怜的类型擦除将不存在，你会做这样的事情：

// WON'T WORK
def flatten[T <: SpecialList](parentList: T): List[Exp] = parentList.elements flatMap {
    case x:T => x.elements
    case somethingElse => List(somethingElse)
}

但在这种情况下最好的解决办法是，在我看来，这一个：

def flatten[T <: SpecialList](parentList: T): List[Exp] = parentList.elements flatMap {
    case x:SpecialList if x.getClass == parentList.getClass => x.elements
    case somethingElse => List(somethingElse)
}

这比问题提出了一个更通用的一点，因为你不需要理会参数是否为利斯塔或数组listB，它也将工作，如果将来你将添加一个ListC。

不过，这不会解决你的更一般的问题在任意深度的扁平化，扁平化以来（利斯塔（...））也必须在最后返回利斯塔（...） - 在上述情况下，它返回一个列表，其失去其初始的意义。 解决这个问题可能是：

abstract class SpecialList {
    val elements: List[Exp]

    def flatten: SpecialList = createAnother(elements flatMap {
        case x: SpecialList => {
            val flattenX = x.flatten
            if (flattenX.getClass == this.getClass) flattenX.elements else List(flattenX)
        }
        case somethingElse => List(somethingElse)
    })

    // Creates another special list of the same type
    def createAnother(elements: List[Exp]): SpecialList

}


case class ListA(elements: List[Exp]) extends SpecialList {
    override def toString: String = "ListA("+elements.mkString(",")+")"

    def createAnother(elements: List[Exp]) = ListA(elements)
}

case class ListB(elements: List[Exp]) extends SpecialList {
    override def toString: String = "ListB("+elements.mkString(",")+")"

    def createAnother(elements: List[Exp]) = ListB(elements)
}

在这种情况下的问题是， createAnother位是纯粹的样板。 在另一方面，该版本保持了上述解决方案的通用性。

第三个建议，其中可能涉及重构你的代码多一点是完全放弃了利斯塔和数组listB类型，因为它在我看来，他们的目的是提供一个标签与实验的列表。 因此，考虑这种解决方案：

case class SpecialList(tag: Tag, elements: List[Exp]) extends Exp {
    def flatten: SpecialList = {
        val newElems = elements flatMap {
            case x: SpecialList => {
                val flattenX = x.flatten
                if (flattenX.tag == this.tag) flattenX.elements else List(flattenX)
            }
            case somethingElse => List(somethingElse)
        }
        SpecialList(tag, newElems)
    }

    override def toString = tag.toString ++ "(" + elements.mkString(",") + ")"

}


sealed abstract class Tag {

    // Syntactic sugar to maintain the notation used in the question
    def apply(elements: Exp*): SpecialList = SpecialList(this, elements.toList)

}

object ListA extends Tag { override val toString = "ListA" }
object ListB extends Tag { override val toString = "ListB" }

从一个语法点，这几乎是相同的，既然你有

val x = ListA(Element(A), Element(B), ListA(Element(C), Element(D)), ListB(Element(E),Element(F), ListA(Element(C), ListA(Element(D)))))
x.flatten => ListA(Element(A),Element(B),Element(C),Element(D),ListB(Element(E),Element(F),ListA(Element(C),Element(D))))

如果我出轨了一下有这种可能不适合你的问题，但是，很抱歉。

文章来源: Flattening nested lists of the same type