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

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 
} 

EDIT: Спасибо всем, надеюсь, вам понравилось упражнение!

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

Не самый быстрый, но не ограничиваясь 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 4

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

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 5

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

---

Вот «однострочный», используя массивы по запросу, для 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, вы затем можете ToArray, если вы хотите Java потенциально-примитив массив.)

Answer 6

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

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 7

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

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

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

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

Здесь в 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 

И вот один тестовый модуль:

*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, но Я не уверен, что у Скалы есть такие вещи. Кроме того, takeWhile и dropWhile - приятные значащие имена, в то время как я по крайней мере нахожу break и span менее проницательным.

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

Answer 8

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

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 
} 

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

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

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 9

раствора в J:

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

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

'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