Ответ 1
Говоря строго о проблеме замены, моим предпочтительным решением является функция, которая может быть доступна в предстоящем Scala 2.8, что позволяет заменять шаблоны регулярных выражений с помощью функции. Используя его, проблему можно свести к следующему:
def replaceRegex(input: String, values: IndexedSeq[String]) =
"""\$(\d+)""".r.replaceAllMatchesIn(input, {
case Regex.Groups(index) => values(index.toInt)
})
Что уменьшает проблему до того, что вы на самом деле собираетесь делать: замените все шаблоны $N на соответствующее N-е значение списка.
Или, если вы действительно можете установить стандарты для своей строки ввода, вы можете сделать это следующим образом:
"select col1 from tab1 where id > %1$s and name like %2$s" format ("one", "two")
Если это все, что вы хотите, вы можете остановиться здесь. Если, однако, вы заинтересованы в том, как эффективно решать такие проблемы, не имея умных функций библиотеки, пожалуйста, продолжайте читать.
Мышление функционально об этом означает мышление о функции. У вас есть строка, некоторые значения, и вы хотите вернуть строку. В статически типизированном функциональном языке это означает, что вы хотите что-то вроде этого:
(String, List[String]) => String
Если учесть, что эти значения могут использоваться в любом порядке, мы можем попросить тип, более подходящий для этого:
(String, IndexedSeq[String]) => String
Это должно быть достаточно хорошо для нашей функции. Теперь, как мы разрушаем работу? Есть несколько стандартных способов сделать это: рекурсия, понимание, сгибание.
RECURSION
Начнем с рекурсии. Рекурсия означает разделить проблему на первый шаг, а затем повторить ее по оставшимся данным. Для меня наиболее очевидным делением здесь было бы следующее:
- Заменить первый заполнитель
- Повторите с оставшимися заполнителями
Это на самом деле довольно прямолинейно, поэтому давайте вдав в подробности. Как заменить первый заполнитель? Единственное, чего нельзя избежать, это то, что мне нужно знать, что это заполнитель, потому что мне нужно получить индекс от моих значений. Поэтому мне нужно найти его:
(String, Pattern) => String
После того как я найден, я могу заменить его на строку и повторить:
val stringPattern = "\\$(\\d+)"
val regexPattern = stringPattern.r
def replaceRecursive(input: String, values: IndexedSeq[String]): String = regexPattern findFirstIn input match {
case regexPattern(index) => replaceRecursive(input replaceFirst (stringPattern, values(index.toInt)))
case _ => input // no placeholder found, finished
}
Это неэффективно, потому что он многократно производит новые строки, а не просто конкатенирует каждую часть. Попытайтесь быть более умными в этом.
Чтобы эффективно построить строку с помощью конкатенации, нам нужно использовать StringBuilder. Мы также хотим избежать создания новых строк. StringBuilder может принимать CharSequence, который мы можем получить из String. Я не уверен, что новая строка действительно создана или нет - если это так, мы могли бы свернуть собственный CharSequence таким образом, чтобы он отображался как String вместо создания нового String. Заверили, что мы сможем легко изменить это, если потребуется, я буду исходить из предположения, что это не так.
Итак, рассмотрим, какие функции нам нужны. Естественно, нам понадобится функция, которая возвращает индекс в первый placeholder:
String => Int
Но мы также хотим пропустить любую часть строки, на которую мы уже посмотрели. Это означает, что нам также нужен начальный индекс:
(String, Int) => Int
Есть одна небольшая деталь. Что делать, если на другом месте? Тогда не было бы никакого индекса для возврата. Java повторно использует индекс, чтобы вернуть это исключение. Однако при выполнении функционального программирования всегда лучше вернуть то, что вы имеете в виду. И мы имеем в виду, что мы можем вернуть индекс, иначе мы не сможем. Подпись для этого такова:
(String, Int) => Option[Int]
Давайте построим эту функцию:
def indexOfPlaceholder(input: String, start: Int): Option[Int] = if (start < input.lengt) {
input indexOf ("$", start) match {
case -1 => None
case index =>
if (index + 1 < input.length && input(index + 1).isDigit)
Some(index)
else
indexOfPlaceholder(input, index + 1)
}
} else {
None
}
Это довольно сложно, в основном для решения граничных условий, таких как индекс, выходящий за пределы диапазона, или ложных срабатываний при поиске заполнителей.
Чтобы пропустить местозаполнитель, нам также нужно знать длину, подпись (String, Int) => Int:
def placeholderLength(input: String, start: Int): Int = {
def recurse(pos: Int): Int = if (pos < input.length && input(pos).isDigit)
recurse(pos + 1)
else
pos
recurse(start + 1) - start // start + 1 skips the "$" sign
}
Далее, мы также хотим знать, что именно, индекс значения, на который стоит местозаполнитель. Подпись для этого несколько неоднозначна:
(String, Int) => Int
Первый Int - это индекс на входе, а второй - индекс в значения. Мы могли бы что-то с этим сделать, но не так легко или эффективно, поэтому пусть игнорирует его. Вот для него реализация:
def indexOfValue(input: String, start: Int): Int = {
def recurse(pos: Int, acc: Int): Int = if (pos < input.length && input(pos).isDigit)
recurse(pos + 1, acc * 10 + input(pos).asDigit)
else
acc
recurse(start + 1, 0) // start + 1 skips "$"
}
Мы могли бы использовать длину также и добиться более простой реализации:
def indexOfValue2(input: String, start: Int, length: Int): Int = if (length > 0) {
input(start + length - 1).asDigit + 10 * indexOfValue2(input, start, length - 1)
} else {
0
}
В качестве примечания, использование фигурных скобок вокруг простых выражений, таких как выше, не одобряется обычным стилем Scala, но я использую его здесь, чтобы его можно было легко вставить в REPL.
Итак, мы можем получить индекс для следующего заполнителя, его длины и индекса значения. Это почти все, что необходимо для более эффективной версии replaceRecursive:
def replaceRecursive2(input: String, values: IndexedSeq[String]): String = {
val sb = new StringBuilder(input.length)
def recurse(start: Int): String = if (start < input.length) {
indexOfPlaceholder(input, start) match {
case Some(placeholderIndex) =>
val placeholderLength = placeholderLength(input, placeholderIndex)
sb.append(input subSequence (start, placeholderIndex))
sb.append(values(indexOfValue(input, placeholderIndex)))
recurse(start + placeholderIndex + placeholderLength)
case None => sb.toString
}
} else {
sb.toString
}
recurse(0)
}
Гораздо эффективнее и функционально, чем можно использовать StringBuilder.
ОСОЗНАНИЕ
Понимание на самом базовом уровне означает преобразование T[A] в T[B] с помощью функции A => B. Это вещь монады, но ее легко понять, когда дело доходит до коллекций. Например, я могу преобразовать List[String] имен в List[Int] длин имен с помощью функции String => Int, которая возвращает длину строки. Это понимание списка.
Существуют и другие операции, которые могут выполняться посредством понятий, заданных функциями с сигнатурами A => T[B] или A => Boolean.
Это означает, что мы должны видеть входную строку как T[A]. Мы не можем использовать Array[Char] в качестве входных данных, потому что мы хотим заменить весь placeholder, который больше, чем один char. Поэтому предлагаем такую подпись типа:
(List[String], String => String) => String
Так как мы получаем вход String, нам нужна функция String => List[String], которая разделит наш вход на заполнители и не-заполнители. Я предлагаю следующее:
val regexPattern2 = """((?:[^$]+|\$(?!\d))+)|(\$\d+)""".r
def tokenize(input: String): List[String] = regexPattern2.findAllIn(input).toList
Другая проблема заключается в том, что мы получили IndexedSeq[String], но нам нужен String => String. Есть много способов обойти это, но разрешите с этим:
def valuesMatcher(values: IndexedSeq[String]): String => String = (input: String) => values(input.substring(1).toInt - 1)
Нам также нужна функция List[String] => String, но List mkString делает это уже. Так что осталось немного оставить в стороне составление всего этого:
def comprehension(input: List[String], matcher: String => String) =
for (token <- input) yield (token: @unchecked) match {
case regexPattern2(_, placeholder: String) => matcher(placeholder)
case regexPattern2(other: String, _) => other
}
Я использую @unchecked, потому что не должно быть никакого шаблона, кроме этих двух выше, если мой шаблон регулярного выражения был построен правильно. Однако компилятор не знает этого, поэтому я использую эту аннотацию, чтобы отключить предупреждение, которое оно произведет. Если выбрано исключение, появляется ошибка в шаблоне регулярного выражения.
Конечная функция затем объединяет все:
def replaceComprehension(input: String, values: IndexedSeq[String]) =
comprehension(tokenize(input), valuesMatcher(values)).mkString
Одна из проблем с этим решением заключается в том, что я дважды применяю шаблон регулярного выражения: один раз для разбивки строки, а другой для определения заполнителей. Другая проблема заключается в том, что List токенов - ненужный промежуточный результат. Мы можем решить это с помощью этих изменений:
def tokenize2(input: String): Iterator[List[String]] = regexPattern2.findAllIn(input).matchData.map(_.subgroups)
def comprehension2(input: Iterator[List[String]], matcher: String => String) =
for (token <- input) yield (token: @unchecked) match {
case List(_, placeholder: String) => matcher(placeholder)
case List(other: String, _) => other
}
def replaceComprehension2(input: String, values: IndexedSeq[String]) =
comprehension2(tokenize2(input), valuesMatcher(values)).mkString
Складывающиеся
Складывание немного похоже на рекурсию и понимание. С складыванием мы берем вход T[A], который можно понять, a B "seed" и функцию (B, A) => B. Мы понимаем список, используя функцию, всегда беря B, которая была получена из обработанного последнего элемента (первый элемент принимает семя). Наконец, мы возвращаем результат последнего постигаемого элемента.
Я признаю, что с трудом объяснил это менее чем неясным образом. То, что происходит, когда вы пытаетесь сохранить абстрактный. Я объяснил это таким образом, чтобы сигнатуры типа были понятны. Но давайте просто посмотрим тривиальный пример складчатости, чтобы понять его использование:
def factorial(n: Int) = {
val input = 2 to n
val seed = 1
val function = (b: Int, a: Int) => b * a
input.foldLeft(seed)(function)
}
Или, как однострочный:
def factorial2(n: Int) = (2 to n).foldLeft(1)(_ * _)
Хорошо, так как же мы будем решать проблему со складыванием? Результатом, конечно же, должна быть строка, которую мы хотим создать. Поэтому семя должно быть пустой строкой. Позвольте использовать результат из tokenize2 в качестве понятного ввода и сделайте следующее:
def replaceFolding(input: String, values: IndexedSeq[String]) = {
val seed = new StringBuilder(input.length)
val matcher = valuesMatcher(values)
val foldingFunction = (sb: StringBuilder, token: List[String]) => {
token match {
case List(_, placeholder: String) => sb.append(matcher(placeholder))
case List(other: String, _) => sb.append(other)
}
sb
}
tokenize2(input).foldLeft(seed)(foldingFunction).toString
}
И, с этим, я заканчиваю показывать самые обычные способы, которые можно было бы сделать это в функциональной манере. Я прибегал к StringBuilder, потому что конкатенация String медленная. Если бы это было не так, я мог бы легко заменить StringBuilder на функции выше на String. Я также мог бы преобразовать Iterator в Stream и полностью избавиться от изменчивости.
Это Scala, хотя и Scala касается балансировки потребностей и средств, а не пуристических решений. Хотя, конечно, вы можете пойти пуристом.: -)