Рекурсия в скале. Попытка изменить List в переданном параметре (что, очевидно, невозможно)

Question

В Java у меня был такой метод.

    public static void digPackageLines( List<PkgLine> pkgLineList, Tree treeParam ) {

    if ( findPkgLineTreeExist( treeParam ) == false ) {
        for ( Tree tree : findParents( treeParam ) ) {
            digPackageLines( pkgLineList, tree );
        }

    } else {

        for ( PkgLineTree pkgLineTree : findPkgLineTreeByTree( treeParam ) ) {
            pkgLineList.add( pkgLineTree.pkgLineId );

        }
    }
}

Это займет список и изменит его, добавив pkgLines в этот список. Теперь в Scala это невозможно, поскольку все параметры имеют значения val и не могут быть изменены.

Это то, что я имею до сих пор.

def digPackageLines(pkgLineList : Seq[ PkgLine ], tree_id : Long) : Unit = {

    if ( PkgLineTree.findPkgLineTreeExist(tree_id) == false ) {  //tree is parent if no lines found

        Tree.findParents(tree_id) map {
            tree =>
                digPackageLines(pkgLineList, tree.tree_id.get) //dig further into tree
        }

    } else { //found lines

        PkgLineTree.findByTreeId(tree_id) map {
            pkgLineTree =>
                PkgLine.findById(pkgLineTree.pkg_line_id).get //add this line to pkgLineList somehow
        }
    }
}

Так что я застрял, что делать. Я смотрел учебники по хвостовой рекурсии, но они довольно простые и имеют дело только с числами. Нужно ли возвращать список из рекурсивной функции? У функций не может быть побочных эффектов, поэтому я предполагаю, что это единственный способ.

Другая моя основная проблема - добавление объектов в список. По-видимому, мне нужно иметь копию списка, а затем добавить объект к нему. Проблема в том, что я не могу создать новую переменную в цикле. Я уверен, что есть гораздо более простой способ. Спасибо за любую помощь.

** EDIT **

В самом конце я сделал это.

val pkgLineList : Seq[ (PkgLine, Tree) ] = User.findUserJoinAllAcl(10) flatMap {
        user =>
            PkgLine.digPackageLines(Vector[ (PkgLine, Tree) ](), user._2.tree_id)
    }

Это выглядит правильно. Я изменил метод, чтобы вернуть кортеж. Единственная разница, хотя. Кажется, работает хорошо.

Answer 1

В Scala у вас есть изменяемые и неизменяемые коллекции. Предпочтение отдается использованию неизменяемого, но вы всегда можете вернуться к изменяемому в зависимости от контекста.

Здесь вы хотите добавить, поэтому использование неизменяемого List не идеально, так как операция добавления принимает O (n). Предпочитает O (1). Типичным способом решения этой проблемы является использование List и предварительное добавление, а в конце - reverse для получения желаемого результата.

Вы можете использовать изменяемый ListBuffer, который можно преобразовать в список в операции O (1):

import collection.mutable.ListBuffer

@annotation.tailrec // check that this is optimized for tail call
def digPackageLines(pkgLineList: ListBuffer[PkgLine], tree_id: Long): Unit = {

  if (PkgLineTree.findPkgLineTreeExist(tree_id) == false) {
    Tree.findParents(tree_id) map { tree =>
      digPackageLines(pkgLineList, tree.tree_id.get)
    }
  } else { //found lines and return result as List
    PkgLineTree.findByTreeId(tree_id) map { pkgLineTree =>
      pkgLineList += PkgLine.findById(pkgLineTree.pkg_line_id).get
    }
  }
}

Но давайте посмотрим, как это сделать более «функционально». Позвольте использовать неизменный Vector, который амортизирует O (1) добавление. Функция вернет объединенные результаты, так как вход не может быть изменен:

def digPackageLines(pkgLines: Vector[PkgLine], tree_id: Long): Vector[PkgLine] ={

  if (PkgLineTree.findPkgLineTreeExist(tree_id) == false) {
      val parentTrees = Tree.findParents(tree_id)
      parentTrees.foldLeft(pkgLines){ (lines, tree) =>
        digPackageLines(lines, tree.tree_id.get)
      }
    }
  } else { //found lines and return result as List
    val additions = PkgLineTree.findByTreeId(tree_id) map { pkgLineTree =>
      PkgLine.findById(pkgLineTree.pkg_line_id).get
    }
    pkgLines ++ additions
  }
}

Тот же отказ от ответственности, что и для Submonoid * (Нет, я не запускал эту программу, поэтому в ней могут быть ошибки.)

Answer 2

Коллекции Scala по умолчанию являются неизменяемыми, что означает, что вы не можете вносить в них изменения. Тем не менее, есть отдельный пакет изменяемых коллекций. Изменяемый вариант List - это ListBuffer, который доступен в пакете scala.collection.mutable. Используя ListBuffer, вы сможете:

pkgLineList += PkgLine.findById(pkgLineTree.pkg_line_id).get

Это будет прямой перевод вашей версии Java. Однако, что вы, вероятно, хотите сделать, это переписать его в гораздо более идиоматическом стиле Scala. Похоже, что вы делаете, проходя некоторую ветвящуюся структуру данных и добавляя результаты вещей в список. Вы можете довольно легко переписать это примитивно-рекурсивным способом, например:

def digPackageLines(tree_id : Long) : Seq[PkgLine] = {
  def _digPackageLines(acc : List[PkgLine], tree_id : Long) : List[PkgLine] = {
    // Base case 
    if (PkgLineTree.findPkgLineTreeExist(tree_id)) {
      PkgLineTree.findByTreeId(tree_id) map {
        pkgLineTree =>
            PkgLine.findById(pkgLineTree.pkg_line_id).get
      } ::: acc
    } else {
      // We use flatMap instead of Map to concatenate the results of the recursive calls
      Tree.findParents(tree_id) flatMap { tree =>
        digPackageLines(pkgLineList, tree.tree_id.get)
      } ::: acc
    }
  }

  // Call our helper function with an empty list
  _digPackageLines(List[PkgLine](), tree_id)
}

(Н.б. Я не запускал это, поэтому в нем могут быть ошибки.)

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