Каким был бы функциональный подход к смещению определенных элементов массива?

Question

У меня есть приложение Scala со списком элементов с флажками, поэтому пользователь выбирает некоторые из них и нажимает кнопку, чтобы переместить их на одну позицию вверх (влево). Я решил написать функцию для сдвига элементов произвольного типа, которые соответствуют заданному предикату. Итак, если у вас есть эти элементы:

a b c D E f g h I

и предикат "прописные буквы", функция будет возвращать это:

a b D E c f g I h

Короче говоря, любая последовательность смежных элементов, которые соответствуют предикату, заменяется одним элементом слева от него.

Я придумал следующую безобразную императивную реализацию. Я хотел бы видеть хорошее и, надеюсь, читаемое, функциональное решение.

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
}

РЕДАКТИРОВАТЬ: Спасибо всем, я надеюсь, вам понравилось упражнение!

Answer 1

Вот чисто функциональная реализация

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
}

А вот тот, который использует изменчивость внутри, чтобы быть быстрее

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 2

Возможно, вы могли бы сделать это через foldLeft (также известный как /:):

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

Требуется работа для обработки пустой строки, но:

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

Я оставлю это в качестве упражнения о том, как преобразовать это в решение на основе массива

Answer 3

Это в основном императивный алгоритм с функциональным стилем.

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
}

Изменяет массив на месте, с побочным эффектом. Я думаю, что это действительно похоже на версию в вопросе, за исключением того, что ее легче читать. Императив не должен быть безобразным ...

Редактировать: штопать, не мог заснуть, пока я не записал это (так же, как выше, только более компактно):

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
}

Answer 4

Я не знаю достаточно, чтобы написать это в Scala, но эта проблема специально разработана для функций списка takeWhile и dropWhile. Идея состоит в том, что вы разделяете список предметов на три части:

• Левая часть, вычисленная с помощью takeWhile, содержит крайние левые элементы, не удовлетворяющие предикату.

• Средняя часть - это группа элементов, которую вы хотите сдвинуть влево, вычисленная путем отбрасывания левых элементов, а затем takeWhile остатка.

• Правая часть - это все, что осталось; dropWhile средние элементы.

Вот оно в Хаскеле:

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

А вот единичный тестовый тест:

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

Программисты на Haskell могут использовать List.break или List.span для объединения вызовов на takeWhile и dropWhile, но я не уверен, есть ли в Scala такие вещи. Кроме того, takeWhile и dropWhile являются хорошими значащими именами, в то время как break и span, по крайней мере, я считаю менее заметными.

EDIT : исправлен рекурсивный вызов, чтобы сделать shift p right вместо right, чтобы сдвинуть все группы вверх.

Answer 5

Вот еще один вариант ответа Джеффа:

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

Быстро протестировано с использованием

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

Вот вторая версия

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 6

Я не утверждаю, что этот материал ниже, чтобы быть эффективным или читабельным. К сожалению, все хорошие ответы, кажется, приняты, поэтому я иду за оригинальность. : -)

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

Итак, вот что происходит. Сначала я связываю каждый символ с его индексом (a.zipWithIndex), а затем разделяю его на areP и notP в зависимости от того, удовлетворяет ли символ p или нет.

Итак, на данный момент у меня есть две последовательности, каждая из которых состоит из символа и его индекса в исходной последовательности.

Затем я просто сдвигаю индекс элементов в первой последовательности, вычитая 1, и вычисляю shifted.

Вычислить новый индекс несмещенных элементов намного сложнее. Для каждого из этих элементов (notP map) я сделаю foldLeft. Аккумулятором левого сгиба будет сам элемент (всегда с его индексом). Сложенная последовательность является последовательностью сдвинутых элементов, поэтому можно видеть, что для каждого несмещенного элемента я пересекаю всю последовательность сдвинутых элементов (крайне неэффективно!).

Итак, мы сравниваем индекс несмещенного элемента с индексом каждого сдвинутого элемента. Если они равны, увеличьте индекс несмещенного элемента. Поскольку последовательность смещенных элементов упорядочена (partition не меняет порядок), мы знаем, что сначала мы проверим на более низкие индексы, а затем на более высокие индексы, гарантируя, что индекс элемента будет увеличен настолько, насколько необходимо.

При этом мы соединяем две последовательности, упорядочиваем их по новым индексам и затем отображаем обратно на элемент.

Answer 7

Не самый быстрый, но не только String и использующий ту же логику, что и @ 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 8

Решение в J:

   ('abcdefghijklmnopqrstuvwxyz';'ABCDEFGHIJKLMNOPQRSTUVWXYZ') (4 : '(y#~y e. >1{x)([: I. '' ''= ])} }._1&|.&.((1,~y e. >0{x)&#)y,'' ''') 'abcDEfghI'
abDEcfgIh

Давайте разберем это на именованные фрагменты для более легкого понимания. Последняя строка «abDEcfgIh» является результатом применения функции к строке «abcDEfghI», которая является правильным аргументом для функции. Пара алфавитов составляет левый аргумент функции (которая начинается с части «(4 :…»)). Таким образом, вместо двухэлементного вектора строк в штучной упаковке мы можем назвать каждую из них по отдельности:

   'lc uc'=. 'abcdefghijklmnopqrstuvwxyz';'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

Теперь, когда у нас есть две переменные «lc» и «uc» для строчных и прописных алфавитов, давайте рассмотрим тело функции более подробно. Взяв логически связный фрагмент с правого конца, так как это будет оценено в первую очередь, мы можем назвать это так:

   rmUCshift=: 4 : 0
   }._1&|.&.((1,~y e. >0{x)&#)y,' '
)

Это определяет «rmUCshift» как то, что требует правого и левого аргумента (это указывает «4 :»), причем тело начинается со следующей строки и продолжается до чистого закрывающего элемента. Форма «4 : 0», за которой следует тело, является вариантом формы «4 :‘ body », показанной изначально. Этот глагол rmUCshift может быть вызван независимо, как это:

   (lc;'') rmUCshift 'abcDEfghI'  NB. Remove upper-case, shift, then insert
ab  cfg h                         NB. spaces where the upper-case would now be.

Вызов имеет отступ в три пробела, и результат сразу следует за ним. Левый аргумент (lc;'') - это двухэлементный вектор с пустым массивом, указанным в качестве второго элемента, поскольку он не используется в этом фрагменте кода - мы могли бы использовать любое значение после точки с запятой, но две одинарные кавычки легко набрать .

Следующие названия, которые следует назвать, - это (определения, сопровождаемые примерами):

  ixSpaces=: [:I.' '=]
  ixSpaces 'ab  cfg h'
2 3 7
   onlyUC=: 4 : 'y#~y e.>1{x'
   ('';uc) onlyUC 'abcDEfghI'
DEI

Объединение этих именованных частей вместе дает нам следующее:

   (lc;uc) (4 : '(x onlyUC y)(ixSpaces x rmUCshift y)}x rmUCshift y') 'abcDEfghI'
abDEcfgIh

Однако повторение «x rmUCshift y» не является необходимым и может быть упрощено, чтобы дать нам это:

   (lc;uc) (4 : '(x onlyUC y) ((ixSpaces ]) } ]) x rmUCshift y') 'abcDEfghI'
abDEcfgIh

Answer 9

Редактировать: это на самом деле не решает поставленную проблему - оно решает связанную, но другую проблему (увеличивая приоритет отмеченных элементов на единицу). Я оставляю это здесь для справки, однако.

---

Вот "одна строка", использующая массивы по запросу, для 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)

Я оставляю читателю в качестве упражнения выяснить, как это работает. (Если вы действительно хотите использовать дженерики с T, в Scala 2.8 он даст вам GenericArray; затем вы можете переписать его, если вам нужен потенциально-примитивный массив Java).