Как поддерживать неизменяемый список, когда вы воздействуете на объект, связанный друг с другом в этом списке

Ответ 1

Говоря о вашей проблеме с отличительными фронтами (после обновления 2):

val (left,right) = population.partition(_.node.value == 0)
List(left, right.map(_.copy(node = node.copy(value = node.value - 1))))

Не нужно ничего мутировать здесь. copy скопирует все, кроме полей, которые вы указали с новыми значениями. Говоря о коде, новая копия будет связана с одним и тем же списком детей, но с новым value = value - 1.

P.S. У меня такое чувство, что вы действительно можете сделать что-то вроде этого:

case class A(id: String, level: Int)
val a = A("a", 1)
val b = A("b", 2)
val c = A("c", 2)
val d = A("d", 3)

clusterize(List(a,b,c,d)) === List(List(a), List(b,c), List(d))

Это просто реализовать:

def clusterize(list: List[A]) = 
   list.groupBy(_.level).toList.sortBy(_._1).map(_._2)

Тест:

scala> clusterize(List(A("a", 1), A("b", 2), A("c", 2), A("d", 3)))
res2: List[List[A]] = List(List(A(a,1)), List(A(b,2), A(c,2)), List(A(d,3)))

P.S.2. Пожалуйста, рассмотрите лучшие соглашения об именах, например здесь.

Говоря о "мутирующих" элементах в некоторой сложной структуре:

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

• заранее рассчитать изменения
• применить их

Код:

 case class A(v: Int)
 case class AA(a: A, seq: Seq[A]) //decoratedA

 def update(input: Seq[AA]) = {
    //shows how to decrement each value wherever it is:
    val stats = input.map(_.a).groupBy(identity).mapValues(_.size) //domination count for each A
    def upd(a: A) = A(a.v - stats.getOrElse(a, 0)) //apply decrement
    input.map(aa => aa.copy(aa = aa.seq.map(upd))) //traverse and "update" original structure
 }

Итак, я ввел новую структуру Map[A, Int], которая показывает, как изменить исходную. Этот подход основан на очень упрощенной версии Концепция Applicative Functor. В общем случае он должен быть Map[A, A => A] или даже Map[K, A => B] или даже Map[K, Zipper[A] => B] как прикладной функтор (input <*> map). * Застежка-молния (см. 1, 2) на самом деле может дать вам информацию о текущем элементе контекст.

Примечания:

• Я предположил, что A с одинаковым значением одинаковы; это поведение по умолчанию для classessess, иначе вам нужно предоставить дополнительные id (или переопределить hashCode/equals).

• Если вам нужно больше уровней - например, AA(AA(AA(...)))) - просто сделайте stats и upd рекурсивным, если вес diecrement зависит от уровня вложенности - просто добавьте уровень вложенности в качестве параметра в свою рекурсивную функцию.

• Если декремент зависит от родительского node (например, только декремент A(3) ', который принадлежит A(3)) - добавьте родительский элемент node (s) как часть ключа stats и проанализируйте его во время upd.

• Если существует некоторая зависимость между вычислением статистики (насколько уменьшится), скажем input(1) из input(0) - вы должны использовать foldLeft с частичной статистикой в ​​качестве аккумулятора: val stats = input.foldLeft(Map[A, Int]())((partialStats, elem) => partialStats ++ analize(partialStats, elem))

Btw, здесь требуется O(N) (линейная память и использование процессора)

Пример:

scala> val population = Seq(A(3), A(6), A(8), A(3))
population: Seq[A] = List(A(3), A(6), A(8), A(3))

scala> val input = Seq(AA(population(1),Seq(population(2),population(3))), AA(population(2),Seq(population(1),population(3))))
input: Seq[AA] = List(AA(A(6),List(A(8), A(3))), AA(A(8),List(A(6), A(3))))

scala> update(input)
res34: Seq[AA] = List(AA(A(5),List(A(7), A(3))), AA(A(7),List(A(5), A(3))))