Scala: рекурсивно изменять списки элементов / списков

Question

Я надеялся, что кто-нибудь сможет мне помочь с базовым кодом в Scala.Я написал некоторый демонстрационный код на Python.

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

Чтобы представить это в python, я сделал каждый «элемент» словарем с одним ключом («i» для элемента),Значение, соответствующее этому ключу, является либо целым числом, либо списком похожих слов.Таким образом,

lst = [{'i': 1}, {'i': 2}, {'i': [{'i': 5}, {'i': 6}]}, {'i': 3}]

def recurse(x):
  if isinstance(x, list):
    return [recurse(a) for a in x]
  else:
    if isinstance(x['i'], list):
      return dict(i=[recurse(a) for a in x['i']])
    else:
      return dict(i=(x['i'] + 1))

print "Input:"
for i in lst:
    print i
print "\nResult:\n%s" % recurse(lst)

>>>
Input:
{'i': 1}
{'i': 2}
{'i': [{'i': 5}, {'i': 6}]}
{'i': 3}

Result:    
[{'i': 2}, {'i': 3}, {'i': [{'i': 6}, {'i': 7}]}, {'i': 4}]

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

Также, для записи, элементы Scala представлены как Elem (4) или Elem(List (Elem (3) ..., поэтому я предполагаю, что сопоставление с образцом может войти в это несколько.

Answer 1

Я бы не стал называть этот список списком, так как он не говорит, что содержится в этих списках.Структура - это дерево, точнее лиственное дерево, где данные есть только в листьях.Это будет:

sealed trait Tree[+A]
case class Node[+A](children: Tree[A]*) extends Tree[A]
case class Leaf[+A](value: A) extends Tree[A]

, затем добавьте карту методов, чтобы применить функцию к каждому значению в дереве

sealed trait Tree[+A] {
  def map[B](f: A => B): Tree[B]
}
case class Node[+A](children: Tree[A]*) extends Tree[A] {
  def map[B](f : A => B) = Node(children.map(_.map(f)): _*)
}
case class Leaf[+A](value: A) extends Tree[A] {
  def map[B](f: A => B) = Leaf(f(value))
}

Тогда ваш ввод:

val input = Node(Leaf(1), Leaf(2), Node(Leaf(5), Leaf(6)), Leaf(3))

И если вы позвоните input.map(_ + 1), вы получите свой вывод

Отображение результата несколько уродливо из-за дерева varargs [A] *.Вы можете улучшить, добавив в Узле override def toString = "Node(" + children.mkString(", ") + ")"

. Вы можете предпочесть метод только в одном месте, либо вне классов, либо непосредственно в Дереве.Здесь, как метод в Tree

def map[B](f: A => B): Tree[B] = this match {
  case Node(children @ _*) => Node(children.map(_.map(f)): _*)
  case Leaf(v) => Leaf(f(v))
}

---

Работа нетипизированным способом, как в Python, не очень похожа на scala, но может быть выполнена.

def recurse(x: Any) : Any = x match {
  case list : List[_] => list.map(recurse(_))
  case value : Int => value + 1
}

(помещение значений непосредственно в список. Ваша карта (словарь) с ключом "i" усложняет его и заставляет принять предупреждение компилятора, поскольку нам пришлось бы принудительно привести приведение, которое не может быть проверено,а именно, что карта принимает строку в качестве ключей: case map: Map [String, _])

---

Использование case Elem(content: Any) звучит для меня как не обеспечивающее дополнительной безопасности по сравнению с помещением значений непосредственно в List, хотягораздо более многословный, и ни одно из безопасности и ясности, называя это деревом и различая узлы и листья, не будучи заметно более кратким.

Answer 2

Это решение является более безопасным для типов, но не прибегая к идее дерева (что не является плохим решением, но кто-то уже сделал это :). Это будет список int или список int. Таким образом, он может иметь только два уровня - если вы хотите больше, создайте дерево.

val lst = List(Left(1), Left(2), Right(List(5, 6)), Left(3))

def recurse(lst: List[Either[Int, List[Int]]]): List[Either[Int, List[Int]]] = lst match {
    case Nil => Nil
    case Left(n) :: tail => Left(n + 1) :: recurse(tail)
    case Right(l) :: tail => Right(l map (_ + 1)) :: recurse(tail)
}

Answer 3

Ну, вот что работает, но немного некрасиво:

def make(o: Any) = Map('i' -> o) // m :: Any => Map[Char,Any]
val lst = List(make(1),make(2),make(List(make(5),make(6))),make(3)) // List[Any]

def recurce(x: Any): Any = x match {
  case l: List[_] => l map recurce
  case m: Map[Char,_] => val a = m('i')
    a match {
      case n: Int => make(n + 1)
      case l: List[_] => make(l map recurce)
    }
}

Пример:

scala> recurce(lst)
res9: Any = List(Map((i,2)), Map((i,3)), Map((i,List(Map(i -> 6), Map(i -> 7)))), Map((i,4)))