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

3

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

<code>    ListA(Element(A), Element(B), ListA(Element(C), Element(D)), ListB(Element(E),Element(F)))
</code>

ListA содержит вложенный список того же типа (ListA(Element(C), Element(D))) поэтому я хочу заменить его значениями, которые он содержит, поэтому результат верхнего примера должен выглядеть следующим образом:

<code>ListA(Element(A), Element(B), Element(C), Element(D), ListB(Element(E),Element(F)))
</code>

Текущая иерархия классов:

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

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

First solution:

<code>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
    }
</code>

Second solution:

<code>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
}
</code>

Third solution

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

Мой вопрос заключается в том, есть ли лучший, более общий способ достижения той же функциональности, что и во всех трех верхних решениях - повторение кода?

Это дерево, нет? ziggystar
Глубина "не ограничена". Но не хотела усложнять вопрос еще больше. PrimosK
Но ваши решения не обрабатывают неограниченное вложение. ziggystar
В некотором смысле это так. Если есть что-то еще, что я должен объяснить, пожалуйста, дайте мне знать ... Третье решение является наиболее близким, которое я могу получить, но мне не нравятся два почти одинаковых оператора case (для ListA и ListB) ... Должен быть какой-то более общий способ сделать это, возможно, с параметрами типа? PrimosK
Ответ зависит от того, что вы имеете в видуbetter, Третье решение является кратким функциональным решением. С помощьюscalaz, вы можете представить свои данные в видеTree а потом просто позвонить.flatten в теме. Вы уверены, что ваше дерево имеет только глубину 2? ziggystar

Ваш Ответ

3   ответа
0

где не было бы убого убитого типа, вы бы сделали что-то вроде этого:

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

Он немного более общий, чем предложенный в вопросе, поскольку вам не нужно беспокоиться о том, является ли аргумент ListA или ListB, и он также будет работать, если в будущем вы добавите ListC.

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

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

Однако это может не соответствовать вашей проблеме, так что извините, если я немного сошел с рельсов там.

13

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)
}
Да, вы можете, и, вероятно, является более эффективным.
В третьем случае вы не можете просто добавить элемент кh :: flatten(tail)вместо созданияList(h) а затем объединить его с:::?
что-то, с чем я боролся, пытаясь реализовать это сам - я не осознавал, что вы можете использовать case (x: Type) :: xs = & gt; чтобы предоставить тип для первого элемента, я получаю сообщение об ошибке от компилятора (что он ожидает a = & gt;)
0

я бы сделал что-то вроде этого:

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

Обратите внимание, что даже список [List [List [List [A]]]] будет сведен в список [A].

Похожие вопросы