Recursively handle nested lists in scala

Question

I'm teaching myself scala and trying to fatten my FP skills.

One of my references, Essentials of Programming Languages (available here), has a handy list of easy recursive functions. On page page 27/50, we are asked to implement swapper() function.

(swapper s1 s2 slist) returns a list the same as slist, but with all occurrences of s1 replaced by s2 and all occurrences of s2 replaced by s1. > (swapper ’a ’d ’(a b c d)) (d b c a) > (swapper ’a ’d ’(a d () c d)) (d a () c a) > (swapper ’x ’y ’((x) y (z (x)))) ((y) x (z (y)))

In scala, this is:

swapper("a", "d", List("a","b","c","d")) swapper("a", "d", List("a","d",List(),"c","d")) swapper("x", "y", List( List("x"), "y", List("z", List("x"))))

My scala version handles all versions save the final x.

def swapper(a: Any, b: Any, lst: List[Any]): List[Any] ={ def r(subList :List[Any], acc : List[Any]): List[Any] ={ def swap (x :Any, xs: List[Any]) = if(x == a){ r(xs, acc :+ b) } else if (x == b) { r(xs, acc :+ a) } else { r(xs, acc :+ x) } subList match { case Nil => acc case List(x) :: xs => r(xs, r(List(x), List()) +: acc) case x :: xs => swap(x,xs) //case List(x) :: xs => } } r(lst, List()) }

Instinctively, I think this is because I have no swap on the section "case List(x) :: xs" but I'm still struggling to fix it.

More difficult, still, this case breaks the tail-call optimization. How can I do this and where can I go to learn more about the general solution?

Nyavro · Accepted Answer · 2016-09-06 04:18:14Z

You can use this foldRight with pattern match approach:

def swapper(a:Any, b:Any, list:List[Any]):List[Any] = list.foldRight(List.empty[Any]) { case (item, acc) if item==a => b::acc case (item, acc) if item==b => a::acc case (item:List[Any], acc) => swapper(a, b, item)::acc case (item, acc) => item::acc }

or even simplier (thanks to @marcospereira):

def swapper(a:Any, b:Any, list:List[Any]):List[Any] = list.map { case item if item==a => b case item if item==b => a case item:List[Any] => swapper(a, b, item) case item => item }

OK! Thanks for your insight, this sure simplifies things. Though adding the annotation @tailrec does complain the recursive call is not a tail position.

marcospereira · Accepted Answer · 2016-09-06 03:56:11Z

A simpler way to solve this is just use map:

def swapper[T](a: T, b: T, list: List[T]): List[T] = list.map { item => if (item == a) b else if (item == b) a else item }

jwvh · Accepted Answer · 2016-09-06 09:29:11Z

This seems to work.

def swapper[T](a: T, b: T, lst: List[_]): List[_] = { val m = Map[T, T](a -> b, b -> a).withDefault(identity) def swap(arg: List[_]): List[_] = arg.map{ case l: List[_] => swap(l) case x: T => m(x) } swap(lst) }

The List elements are inconsistent because it might be an element or it might be another List, so the type is List[Any], which is a sure sigh that someone needs to rethink this data representation.

Collectives™ on Stack Overflow

Recursively handle nested lists in scala

3 Answers 3

1 Comment

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Related