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

У меня есть приложение 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
}

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

Источник

9 ответов

Решение

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

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
}
Источник

Вы могли бы сделать это через 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

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

Источник

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

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
}
Источник

Я не знаю достаточно, чтобы написать это в 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 менее заметен

РЕДАКТИРОВАТЬ: исправлен рекурсивный вызов, чтобы сделать shift p right вместо right сдвинуть вверх все группы.

Источник

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

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 не меняет порядок), мы знаем, что сначала мы проверим на более низкие индексы, а затем на более высокие индексы, гарантируя, что индекс элемента будет увеличен по мере необходимости.

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

Источник

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

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
  }
}
Источник

Не самый быстрый, но не только 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)
Источник

Решение в 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 :Форма "тело", показанная изначально. Этот глагол 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
Источник

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

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

Источник
Другие вопросы по тегам