How would be a functional approach to shifting certain array elements?

Question

I have a Scala app with a list of items with checkboxes so the user select some, and click a button to shift them one position up (left). I decided to write a function to shift elements of some arbitrary type which meet a given predicate. So, if you have these elements:

a b c D E f g h I

and the predicate is "uppercase characters", the function would return this:

a b D E c f g I h

In short, any sequence of contiguous elements that meet the predicate are swapped with the single element at the left of it.

I came up with the following ugly imperative implementation. I would like to see a nice, and hopefully readable, functional solution.

def shiftUp[T](a:Array[T], shiftable: T => Boolean) = {
    val s = new Array[T](a.length)
    var i = 0
    var j = 0
    while(i < a.length)
    {
        if(!shiftable(a(i)) && i < a.length - 1 && shiftable(a(i+1)))
        {
            var ii = i + 1
            while(ii < a.length && shiftable(a(ii)))
            {
                s(j) = a(ii)
                ii = ii+1
                j = j+1
            }
            s(j) = a(i)
            i = ii
        }
        else
        {
            s(j) = a(i)
            i = i+1
        }
        j = j+1
    }
    s
}

EDIT: Thanks all, I hope you have enjoyed the exercise!

Answer 1

You could probably do this via a foldLeft (also known as /:):

(str(0).toString /: str.substring(1)) { (buf, ch) =>
    if (ch.isUpper) buf.dropRight(1) + ch + buf.last  else buf + ch
}

It needs work to handle the empty String but:

def foo(Str: String)(p: Char => Boolean) : String = (str(0).toString /: str.substring(1)) { 
   (buf, ch) => if (p(ch) ) buf.dropRight(1) + ch + buf.last else buf + ch
}

val pred = (ch: Char) => ch.isUpper
foo("abcDEfghI")(pred) //prints abDEcfgIh

I'll leave it as an exercise as to how to modify this into the array-based solution

Answer 2

Here's a purely functional implementation

def shiftElements[A](l: List[A], pred: A => Boolean): List[A] = {
  def aux(lx: List[A], accum: List[A]): List[A] = {
    lx match {
      case Nil => accum
      case a::b::xs if pred(b) && !pred(a) => aux(a::xs, b::accum)
      case x::xs => aux(xs, x::accum)
    }
  }
  aux(l, Nil).reverse
}

And here's one that uses mutability on the inside to be faster

import scala.collection.mutable.ListBuffer
def shiftElements2[A](l: List[A], pred: A => Boolean): List[A] = {
  val buf = new ListBuffer[A]
  def aux(lx: List[A]) {
    lx match {
      case Nil => ()
      case a::b::xs if pred(b) && !pred(a) => {
        buf.append(b)
        aux(a::xs)
      }
      case x::xs => {
        buf.append(x)
        aux(xs)
      }
    }
  }
  aux(l)
  buf.toList
}

Answer 3

Not the fastest, but not limited to String and using the same logic as @oxbow_lakes

def shift[T](iter: Iterable[T])(p: T=>Boolean): Iterable[T] = 
  iter.foldLeft(Iterable[T]())((buf, elm) => 
    if (p(elm) && buf.nonEmpty) 
      buf.dropRight(1) ++ Iterable[T](elm) ++ Iterable[T](buf.last) 
    else 
      buf++Iterable[T](elm)
  )

def upperCase(c:Char)=c.isUpper

shift("abcDEfghI")(upperCase).mkString
    //scala> res86: String = abDEcfgIh

val array="abcDEfghI".toArray
shift(array)(upperCase).toArray
    //res89: Array[Char] = Array(a, b, D, E, c, f, g, I, h)

def pair(i:Int)=i%2==0
val l=List(1,2,3,5,4,6,7,9,8)
shift(l)(pair)
    //scala> res88: Iterable[Int] = List(2, 1, 3, 4, 6, 5, 7, 8, 9)

Answer 4

I don't claim this stuff below to be efficient or readable. Unfortunately, all the good answers seem to be taken, so I'm going for originality. :-)

def shift[T](a: Seq[T], p: T => Boolean) = {
  val (areP, notP) = a.zipWithIndex partition { case (t, index) => p(t) }
  val shifted = areP map { case (t, index) => (t, index - 1) }
  val others = notP map (shifted.foldLeft(_){
    case ((t, indexNotP), (_, indexIsP)) => 
      if (indexNotP == indexIsP) (t, indexNotP + 1) else (t, indexNotP)
  })
  (shifted ++ others).sortBy(_._2).map(_._1)
}

So, here's what's happening. First, I associate each character with its index (a.zipWithIndex), and then separate then into areP and notP depending on whether the character satisfies p or not.

So, at this point, I have two sequences, each composed of a character and its index in the original sequence.

Next, I simply shift the index of the elements in the first sequence, by subtracting 1, and compute shifted.

Computing the new index of the unshifted elements is much harder. For each of those elements (notP map), I'll do a foldLeft. The accumulator of the fold left will be the element itself (always with its index). The sequence that is being folded is the sequence of shifted elements -- so one can see that for each unshifted element, I traverse the whole sequence of shifted elements (highly inefficient!).

So, we compare the index of the unshifted element to the index of each shifted element. If they are equal, increase the index of the unshifted element. Because the sequence of shifted elements is ordered (partition doesn't change the order), we know that we'll test first for lower indices, and then for higher indices, guaranteeing that an element will have its index increased as much as necessary.

With that, we join the two sequences, order them by their new indices, and then map back to the element.

Answer 5

Edit: this doesn't actually solve the posed problem--it solves a related but different problem (bumping up the priority of marked items by one). I'm leaving it here for reference, however.

---

Here's a "one-liner", using arrays as requested, for Scala 2.8.

def shiftUp[T](a: Array[T], p: T => Boolean) = {
  a.zipWithIndex.map(ci => {
    (ci._1 , if (p(ci._1)) ci._2 - 1.5 else ci._2.toDouble)
  }).sortWith((l,r) => l._2 < r._2).map(_._1)
}

scala> shiftUp(Array('h','E','l','l','O'),(c:Char)=>c.isUpper).toArray
res0: Array[Char] = Array(E, h, l, O, l)

scala> shiftUp("HeLlO".toArray,(c:Char)=>c.isUpper).toArray
res1: Array[Char] = Array(H, L, e, O, l)

I leave it as an exercise to the reader to figure out how it works. (If you really want generics with T, in Scala 2.8 it's going to give you an GenericArray; you then can toArray it if you want a Java potentially-primitive array.)

Answer 6

Here's another variant on Geoff's answer:

def shift[T](l: List[T], p: T => Boolean): List[T] = {
  l match {
    case a::b::t if ! p(a) && p(b) => b::shift(a::t, p)
    case a::t => a::shift(t, p)
    case Nil => l
  }
}

Quickly tested using

scala> def pred(c: Char) = c.isUpper
pred: (c: Char)Boolean

scala> shift("abcDEfghI".toList, pred)
res3: List[Char] = List(a, b, D, E, c, f, g, I, h)

scala> shift("AbCd".toList, pred)
res4: List[Char] = List(A, C, b, d)

scala> shift(Nil, pred)
res5: List[Nothing] = List()

Here's version two

def shift[T](l: List[T], p: T => Boolean, r: List[T] = Nil): List[T] = {
  l match {
    case a::b::t if ! p(a) && p(b) => shift(a::t, p, b::r)
    case a::t => shift(t, p, a::r)
    case Nil => r.reverse
  }
}

Answer 7

I don't know enough to write it in Scala, but this problem is tailor-made for the list functions takeWhile and dropWhile. The idea is that you split the list of items into three parts:

• Left part, computed with takeWhile, contains leftmost elements not satisfying the predicate.

• Middle part is the group of elements you want to shift left, computed by dropping the left elements and then takeWhile the remainder.

• Right part is everything left over; dropWhile the middle elements.

Here it is in Haskell:

-- take first group of elements satisfying p and shift left one
shift :: (a -> Bool) -> [a] -> [a]
shift p l = case reverse left of 
              []     -> l
              (a:as) -> reverse as ++ middle ++ a : shift p right
  where left    = takeWhile (not . p) l  -- could be done with List.break
        notLeft = dropWhile (not . p) l
        middle  = takeWhile p notLeft    -- could be done with List.span
        right   = dropWhile p notLeft

And here's a single unit test:

*Shiftup> shift (>9) [1, 2, 3, 44, 55, 6, 7, 8]
[1,2,44,55,3,6,7,8]

Haskell programmers might use List.break or List.span to combine calls to takeWhile and dropWhile, but I'm not sure if Scala has these things. Besides, takeWhile and dropWhile are nice meaningful names, whereas I at least find break and span less perspicuous.

EDIT: fixed recursive call to do shift p right instead of right to shift up all groups.

Answer 8

This is basically an imperative algorithm with a functional style.

def shifWithSwap[T](a: Array[T], p: T => Boolean) = {
  def swap(i:Int, j:Int) = {
    val tmp = a(i); a(i) = a(j); a(j) = tmp
  }
  def checkAndSwap(i:Int) = i match {
    case n if n < a.length - 1 && !p(a(i)) && p(a(i+1)) => swap(i, i+1)
    case _ =>
  }
  (0 until a.length - 1) map checkAndSwap
  a
}

It modifies the Array in place, with a side effect. I think it really does it like the version in the question, except it's easier to read. Imperative does not have to be ugly...

Edit: darn, couldn't fall asleep until I wrote this down (same as above, just more compact):

def shift[T](a: Array[T], p: T => Boolean) = {
  for (i <- 0 until a.length - 1; if !p(a(i)) && p(a(i+1))) {
    val tmp = a(i); a(i) = a(i+1); a(i+1) = tmp // swap
  }
  a
}