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

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

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

Очень интересный вопрос - я думаю, что лучше всего решить проблему парой прямоугольников за один раз, а не смотреть на 3 или более одновременно. Начните с удаления этих элементов в других прямоугольниках. Теперь у вас есть только 3 вида пересечений - угловое перекрытие и сквозное перекрытие и частичное перекрытие (где прямоугольник не проходит весь путь). Каждый из них создает новый набор прямоугольников, правильно?

Числите ваши начальные прямоугольники от 1 до N. Начиная с прямоугольника 1 цикл до тех пор, пока вы не найдете пересекающийся прямоугольник. Создание новых прямоугольников. Удалите два пересекающихся прямоугольника и добавьте 3 или более вновь созданных прямоугольников в набор и начните заново.

Результатом будет целый набор неперекрывающихся прямоугольников. Создает ли это наименьшее количество прямоугольников? Возможно, нет, но вы не указали, что минимизация количества прямоугольников была важна. Занимает ли это время o (n ^ 2)? Вероятно.

Лучшее, что вы можете сделать, это использовать unicodedata.normalize () для разложения символа и фильтрации акцентов.

Не забудьте использовать в коде литералы юникод и юникод.

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

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.zipWireIndex ), а затем разделяю его на areP и notP в зависимости от того, удовлетворяет ли символ p или нет.

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

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

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

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

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

Я не знаю достаточно, чтобы написать это на 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 , но я не уверен, есть ли в Scala эти вещи. Кроме того, takeWhile и dropWile - хорошие значащие имена, тогда как я, по крайней мере, нахожу break и span менее заметными.

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

AFAIK, HierarchicalDataTemplate не может группировать нижестоящие элементы.

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

И представление получит вид

public interface ITreeNode
{
    string Title;
    IList<ITreeNode> ChildNodes;  
}

и отобразит его с помощью HierarchicalDataTemplate .

Я делаю намотку самого последнего (1,9,9,9) и предыдущего (1,9,7,8) выпуска FSharp.

Я обратил внимание на множество добавленных вызовов, которые были сделаны в отношении (в Array, Seq, Reflect и модуле Quotation). Я предполагаю, что эти вызовы были добавлены, чтобы защитить F # libs от передачи нулей с другого языка, такого как C #. Есть понимание Брайана? Функция startArg выдает ArgumentStartException.

let inline checkNonNull argName arg = 
    match box arg with 
    | null -> nullArg argName 
    | _ -> ()

• Существует новое переопределение ToString в наборе и улучшенное форматирование для печати набора и карты с помощью sformat aka printf "% A".
• Некоторая внутренняя очистка BigInteger для использования с .net 4.0.
• Я вижу много внутренних изменений в асинхронном режиме, как упомянул Брайан.
• Некоторые внутренние изменения в Event для использования IObserver.

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

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

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

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

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