What's a good and functional way to swap collection elements in Scala?

Question

Hi!

In a project of mine one common use case keeps coming up. At some point I've got a sorted collection of some kind (List, Seq, etc... doesn't matter) and one element of this collection. What I want to do is to swap the given element with it's following element (if this element exists) or at some times with the preceding element.

I'm well aware of the ways to achieve this using procedural programming techniques. My question is what would be a good way to solve the problem by means of functional programming (in Scala)?

---

Thank you all for your answers. I accepted the one I myself did understand the most. As I'm not a functional programmer (yet) it's kind of hard for me to decide which answer was truly the best. They are all pretty good in my opinion.

Answer 1

The following is the functional version of swap with the next element in a list, you just construct a new list with elements swapped.

def swapWithNext[T](l: List[T], e : T) : List[T] = l match {
  case Nil => Nil
  case `e`::next::tl => next::e::tl
  case hd::tl => hd::swapWithNext(tl, e)
}

Answer 2

An alternative implementation for venechka's method:

def swapWithNext[T](l: List[T], e: T): List[T] = {
  val (h,t) = l.span(_ != e)
  h ::: t.tail.head :: e :: t.tail.tail
}

Note that this fails with an error if e is the last element.

If you know both elements, and every element occurs only once, it gets more elegant:

def swap[T](l: List[T], a:T, b:T) : List[T] = l.map(_ match {
  case `a` => b
  case `b` => a
  case e => e }
)

Answer 3

A generic version of Landei's:

import scala.collection.generic.CanBuildFrom
import scala.collection.SeqLike
def swapWithNext[A,CC](cc: CC, e: A)(implicit w1: CC => SeqLike[A,CC],
                                        w2: CanBuildFrom[CC,A,CC]): CC = {
    val seq: SeqLike[A,CC] = cc
    val (h,t) = seq.span(_ != e)
    val (m,l) = (t.head,t.tail)
    if(l.isEmpty) cc
    else (h :+ l.head :+ m) ++ l.tail
}

some usages:

scala> swapWithNext(List(1,2,3,4),3)
res0: List[Int] = List(1, 2, 4, 3)

scala> swapWithNext("abcdef",'d')
res2: java.lang.String = abcedf

scala> swapWithNext(Array(1,2,3,4,5),2)
res3: Array[Int] = Array(1, 3, 2, 4, 5)

scala> swapWithNext(Seq(1,2,3,4),3)
res4: Seq[Int] = List(1, 2, 4, 3)

scala>

Answer 4

A zipper is a pure functional data structure with a pointer into that structure. Put another way, it's an element with a context in some structure.

For example, the Scalaz library provides a Zipper class which models a list with a particular element of the list in focus.

You can get a zipper for a list, focused on the first element.

import scalaz._
import Scalaz._

val z: Option[Zipper[Int]] = List(1,2,3,4).toZipper

You can move the focus of the zipper using methods on Zipper, for example, you can move to the next offset from the current focus.

val z2: Option[Zipper[Int]] = z >>= (_.next)

This is like List.tail except that it remembers where it has been.

Then, once you have your chosen element in focus, you can modify the elements around the focus.

val swappedWithNext: Option[Zipper[Int]] =
  for (x <- z2;
       y <- x.delete)
    yield y.insertLeft(x.focus)

Note: this is with the latest Scalaz trunk head, in which a bug with Zipper's tail-recursive find and move methods has been fixed.