Сведение вложенные списки одного и того же типа

Question

Допустим, я хочу, чтобы сгладить вложенные списки одного и того же типа ... Например

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

Я предпочитаю рекурсивный путь. В целом я хотел бы сделать что-то вроде этого:

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

это немного более общий характер, чем тот, предлагаемый в этом вопросе, так как вам не нужно беспокоиться ли аргумент является lišta или LISTB и он также будет работать, если в будущем йо Вы добавите ListC.

Однако это не решит вашу более общую проблему для сплющивания на произвольной глубине, так как flatten (ListA (...)) также должен возвращать ListA (...) в конце - в случае выше него возвращает список, который теряет его первоначальное значение. Решение этой проблемы может быть:

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 бит является чистым шаблонный. С другой стороны, эта версия поддерживает общность вышеуказанного решения.

Третье предложение, которое может включать в себя реорганизацию вашего кода немного больше, заключается в том, чтобы вообще отказаться от типов ListA и ListB, поскольку мне кажется, что их цель - предоставить тег в список Exp. Так считают это решение:

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

Это не может соответствовать вашей проблемы, тем не менее, очень жаль, если я ушел рельсы немного там.