Выкл по одному со скольжением? - PullRequest
13 голосов
/ 07 августа 2011

Одним из преимуществ отсутствия обработки коллекций с помощью индексов является предотвращение отдельных ошибок.Это, конечно, не единственное преимущество, но это одно из них.

Теперь я часто использую sliding в некоторых алгоритмах в Scala, но я чувствую, что это обычно приводит к чему-то очень похожему на отключениеошибки, потому что sliding из m элементов в коллекции размером n имеет размер n - m + 1 элементов.Или, более тривиально, list sliding 2 на один элемент короче, чем list.

Я чувствую, что в этом шаблоне отсутствует абстракция, что-то, что будет частью sliding, что-то большее -- как foldLeft до reduceLeft.Однако я не могу думать о том, что это может быть.Может ли кто-нибудь помочь мне найти просветление здесь?

ОБНОВЛЕНИЕ

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

def capitalize(s: String) = s(0).toUpper +: s.toSeq.sliding(2).map {
  case Seq(c1, c2) if c2.isLetter => if (c1.isLetter) c2.toLower else c2.toUpper
  case Seq(_, x) => x
}.mkString

Ответы [ 10 ]

6 голосов
/ 07 августа 2011

Я принимаю ответ Оуэна в качестве вдохновения для этого.

Если вы хотите применить простой diff() к списку, это можно рассматривать как эквивалент следующегоумножение матриц.

a = (0 1 4 3).T

M = ( 1 -1  0  0)
    ( 0  1 -1  0)
    ( 0  0  1 -1)

diff(a) = M * a = (1 3 1).T

Теперь мы можем использовать ту же схему для операций общего списка, если мы заменим сложение и умножение (и если мы обобщим чисел в нашей матрице M).

Итак, с плюсом, являющимся операцией добавления списка (с flatten впоследствии - или просто с операцией collect), а мультипликативным эквивалентом является либо Some(_), либо None, слайд с размером окнаиз двух становится:

M = (Some(_) Some(_) None None)
    (None Some(_) Some(_) None)
    (None None Some(_) Some(_))

slide(a) = M “*” a = ((0 1) (1 4) (4 3)).T

Не уверен, если это тот тип абстракции, который вы ищете, но это будет обобщением для класса операций, которые изменяют количество элементов.

diff или slide операции порядка m для ввода длины n потребуется использовать матрицы размера n-m + 1 × n.


Редактировать: Решением может быть передачаот List[A] до List[Some[A]], а затем добавить или добавить (slideLeft или slideRight) их с None.Таким образом, вы можете справиться со всей магией в методе map.

list.slideLeft(2) {
  case Seq(Some(c1), Some(c2)) if c2.isLetter => if (c1.isLetter) c2.toLower else c2.toUpper
  case Seq(_, Some(x)) => x
}
2 голосов
/ 08 августа 2011

Преобразование, которое вы запрашиваете, по своей сути уменьшает размер данных. Извините - другого способа посмотреть на это нет. tail также выдает отдельные ошибки.

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

В этом случае вам могут потребоваться эти методы для List:

initializedSliding(init: List[A]) = (init ::: this).sliding(1 + init.length)
finalizedSliding(tail: List[A]) = (this ::: tail).sliding(1 + tail.length)

, которая будет поддерживать длину вашего списка. (Я уверен, что вы можете представить, как обобщать не в списки.)

Это аналог сложения влево / вправо в том смысле, что вы предоставляете недостающие данные для выполнения попарной (или более) операции над каждым элементом списка.

2 голосов
/ 08 августа 2011

В вашем примере, я думаю, что код сделан более сложным, потому что вы в основном хотите сделать map, но работать с sliding, который вводит граничные условия способом, который не работает хорошо.Я думаю, что сгиб, оставленный с аккумулятором, который запоминает соответствующее состояние, может быть концептуально проще:

def capitalize2(s: String) = (("", true) /: s){ case ((res, notLetter), c) => 
  (res + (if (notLetter) c.toUpper else c.toLower), !c.isLetter)
}._1

Я думаю, что это можно обобщить так, чтобы notLetter мог запомнить n элементов, где n - размерраздвижное окно.

2 голосов
/ 07 августа 2011

Я постоянно сталкиваюсь с этой проблемой в python / R / Matlab, где вы задаете diff () вектор, а затем не можете выровнять его с оригинальным!Это очень расстраивает.

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

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

Это лучшееЯ думал об этом до сих пор.

РЕДАКТИРОВАТЬ

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

EDIT

Другим следствием будет то, что преобразования, подобные sliding, фактически представляют два преобразования, одно для зависимых переменных и одно для их оси.

1 голос
/ 09 ноября 2014

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

def slidingFoldLeft[A, B] (seq: Seq[A], window: Int)(acc: B)(
    f: (B, Seq[A]) => B): B = {
  if (window > 0) {
    val iter = seq.sliding(window)
    iter.foldLeft(acc){
      // Operate normally
      case (acc, next) if iter.hasNext => f(acc, next)
      // It's at the last <window> elements of the seq, handle current case and 
      // call recursively with smaller window
      case (acc, next) =>
        slidingFoldLeft(next.tail, window - 1)(f(acc, next))(f)
    }
  } else acc
}

def capitalizeAndQuestionIncredulously(s: String) =
  slidingFoldLeft(s.toSeq, 2)("" + s(0).toUpper) {
    // Normal iteration
    case (acc, Seq(c1, c2)) if c1.isLetter && c2.isLetter => acc + c2.toLower
    case (acc, Seq(_, c2))  if c2.isLetter                => acc + c2.toUpper
    case (acc, Seq(_, c2))                                => acc + c2
    // Last element of string
    case (acc, Seq(c)) => acc + "?!"
  }

def capitalizeAndInterruptAndQuestionIncredulously(s: String) =
  slidingFoldLeft(s.toSeq, 3)("" + s(0).toUpper) {
    // Normal iteration
    case (acc, Seq(c1, c2, _)) if c1.isLetter && c2.isLetter => acc + c2.toLower
    case (acc, Seq(_, c2, _))  if c2.isLetter                => acc + c2.toUpper
    case (acc, Seq(_, c2, _))                                => acc + c2
    // Last two elements of string
    case (acc, Seq(c1, c2)) => acc + " (commercial break) " + c2
    // Last element of string
    case (acc, Seq(c)) => acc + "?!"
  }

println(capitalizeAndQuestionIncredulously("hello my name is mAtthew"))
println(capitalizeAndInterruptAndQuestionIncredulously("hello my name is mAtthew"))

А на выходе:

Hello My Name Is Matthew?!
Hello My Name Is Matthe (commercial break) w?!
1 голос
/ 08 августа 2011

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

Заимствование из этих подходов для скольжения привело бы к абстракции, в которой не было бы одной проблемы:

(1::2::3::Nil).sliding(2)

даст

(1,2), (2,3), (3,1)

для круговых граничных условий и

(1,2), (2,3), (3,2)

для круговых граничных условий с обращением.

1 голос
/ 08 августа 2011

Ошибки «один за другим» предполагают, что вы пытаетесь поместить исходный список в однозначное соответствие со скользящим списком, но происходит нечто странное, поскольку в скользящем списке меньше элементов.

Формулировка задачи для вашего примера может быть примерно сформулирована следующим образом: «Прописные буквы каждого символа, если он (a) является первым символом или (b) следует за буквенным символом».Как указывает Оуэн, первый символ - это особый случай, и любая абстракция должна это учитывать.Вот возможность,

def slidingPairMap[A, B](s: List[A], f1: A => B, f2: (A, A) => B): List[B] = s match {
  case Nil => Nil
  case x :: _ => f1(x) +: s.sliding(2).toList.map { case List(x, y) => f2(x, y) } 
}

(не лучшая реализация, но вы поняли идею).Это обобщает на скользящие тройки, с ошибками в два раза и так далее.Тип slidingPairMap дает понять, что выполняется специальный корпус.

Эквивалентная подпись может быть

def slidingPairMap[A, B](s: List[A], f: Either[A, (A, A)] => B): List[B]

Тогда f может использовать сопоставление с образцом, чтобы выяснить, работает ли онс первым элементом или с последующим.


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

def slidingPairs[A](s: List[A]): List[Either[A, (A, A)]]

Я полагаю, что эта последняя идея изоморфна тому, что Дебилски предлагает в комментариях: добавьте начало списка с помощью None, оберните все существующие элементы с помощью Some, а затем вызовите sliding.

0 голосов
/ 09 августа 2011

Это проблема, подходящая для функционального языка, ориентированного на массивы, такого как J. По сути, мы генерируем логическое значение, которое соответствует первой букве каждого слова. Для этого мы начнем с логической разметки пробелов в строке. Например (строки с отступом в три пробела являются входными данными; результаты отображаются слева от поля; "NB." начинает комментарий):

   str=. 'now  is  the    time'    NB. Example w/extra spaces for interest
   ]whspc=. ' '=str                NB. Mark where spaces are=1
0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0

Убедитесь, что (*.-.) ("а не") возвращает единицу только для "1 0":

   ]tt=. #:i.4                     NB. Truth table
0 0
0 1
1 0
1 1
   (*.-.)/"1 tt                    NB. Apply to 1-D sub-arrays (rows)
0 0 1 0                            NB. As hoped.

Слайд нашей молчаливой функции по парам в логическом:

   2(*.-.)/\whspc                  NB. Apply to 2-ples
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0

Но это не относится к краевому условию начальной буквы, поэтому выведите единицу в первую позицию Это на самом деле помогает, так как сокращение в 2 раза оставило нам одну короткую позицию. Здесь мы сравниваем длины исходного логического и целевого логического:

   #whspc
20
   #1,2(*.-.)/\whspc
20
   1,2(*.-.)/\whspc
1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0

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

   'lc uc'=. 'abcdefghijklmnopqrstuvwxyz';'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
   (uc,' '){~lc i. str
NOW  IS  THE    TIME

Убедитесь, что вставка с помощью логического значения дает правильный результат:

       (1,2(*.-.)/\whspc) } str,:(uc,' '){~lc i. str
Now  Is  The    Time

Настало время объединить все это в одно утверждение:

   (1,2(*.-.)/\' '=str) } str,:(uc,' '){~lc i. str
Now  Is  The    Time
0 голосов
/ 08 августа 2011

Я не уверен, что это решит вашу конкретную проблему, но мы могли бы легко представить пару методов, например slidingFromLeft(z: A, size: Int) и slidingToRight(z: A, size: Int) (где A - тип элемента коллекции), который при вызове, например,

List(1, 2, 3, 4, 5)

с аргументами, например (0, 3), должны производить соответственно

List(0, 0, 1), List(0, 1, 2), List(1, 2, 3), List(2, 3, 4), List(3, 4, 5)

и

List(1, 2, 3), List(2, 3, 4), List(3, 4, 5), List(4, 5, 0), List(5, 0, 0)
0 голосов
/ 08 августа 2011

Я бы добавил None после сопоставления с Some(_) элементами; обратите внимание, что очевидный способ сделать это (сопоставление для двух Some в случае по умолчанию, как это было сделано при редактировании Дебилски) неверен, поскольку мы должны иметь возможность изменить даже первую букву. Таким образом, абстракция учитывает тот факт, что просто иногда нет предшественника. Использование getOrElse(false) гарантирует, что отсутствующий предшественник будет считаться не прошедшим тест.

((None +: "foo1bar".toSeq.map(Some(_))) sliding 2).map {
   case Seq(c1Opt, Some(c2)) if c2.isLetter => if (c1Opt.map(_.isLetter).getOrElse(false)) c2.toLower else c2.toUpper
   case Seq(_, Some(x)) => x
}.mkString
res13: String = "Foo1Bar"

Благодарности: идея отображения элементов с помощью Some(_) пришла ко мне через пост Дебильски.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...