Scala: recursively modify lists of elements/lists

I was hoping someone could provide me with some basic code help in Scala. I've written some demo code in Python.

Consider a list of elements, where an element can hold either an integer or a list of other elements. I'd like to recursively examine this structure and modify it while keeping the overall structure.

To represent this in python, I've made each 'element' a dictionary with one key ('i' for item). The value corresponding to that key is either an int, or a list of similar dicts. Thus,

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)

>>>开发者_JS百科;
Input:
{'i': 1}
{'i': 2}
{'i': [{'i': 5}, {'i': 6}]}
{'i': 3}

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

I understand it's a bit of a weird way to go about doing things, but the data I have been provided is structured like that. I think my issue is that python lets you return different types from the same function, while I don't believe Scala does.

Also for the record, the Scala elements are represented as Elem(4), or Elem(List(Elem(3)..., so I assume pattern matching can come into it somewhat.

I would rather not call that a List of List, as that does not tell what those lists contains. The structure is a tree, more precisely a leafy tree, where there are data only in the leaves. That would be :

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

then add a method map to apply a function on each value in the tree

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

Then your input is :

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

And if you call input.map(_ + 1) you get your output

The result display is somewhat ugly because of the varargs Tree[A]*. You may improve by adding in Node override def toString = "Node(" + children.mkString(", ") + ")"

You may prefer the method in one place only, either outside the classes, or directly in Tree. Here as a method in 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))
}

Working the untyped way as in Python is not very scala like but may be done.

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

(putting values directly in the list. Your map (dictionary) with key "i" complicates it and force accepting a compiler warning, as we would have to force a cast that could not be checked, namely that a map accepts string as keys : case map: Map[String, _])

Using case Elem(content: Any) sounds to me as giving no extra safety compared to putting values directly in List, while being much more verbose, and none of the safety and clarity of calling it a tree and distinguishing nodes and leaves without being noticeably terser.

Well, here's something that works but a little bit ugly :

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

Example :

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

This solution is more type safe, but without resorting to going the way of a tree (which isn't a bad solution, but someone already made it :). It will be a list of either an int or a list of int. As such, it can only have two levels -- if you want more, make a tree.

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