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

好吧，这里有一个可行的方法，不过看起来有点丑：

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

Answer 2

这个解决方案更安全一些，但不需要使用树这种结构（虽然树也不是个坏主意，不过已经有人做过了 :）。它将会是一个包含整数或者整数列表的列表。因此，它只能有两个层级——如果你想要更多层级，就得使用树结构了。

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

我不太想把这个称作“列表的列表”，因为这样并不能说明这些列表里有什么。这个结构其实是一个树，更准确地说，是一棵叶子树，只有叶子上有数据。也就是说：

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

接下来，添加一个叫做 map 的方法，用来对树中的每个值应用一个函数。

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)，你就会得到输出。

结果的显示有点丑，因为使用了可变参数 Tree[A]*。你可以通过在 Node 中添加 override def toString = "Node(" + children.mkString(", ") + ")" 来改善这个问题。

你可能更喜欢把这个方法放在一个地方，要么在类外面，要么直接放在 Tree 里。这里是作为 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) 对我来说并没有比直接把值放在列表里更安全，反而显得更加冗长，而且没有树的安全性和清晰性，无法明显地区分节点和叶子。