Говоря строго о проблеме замены, я предпочитаю решение, включенное функцией, которая, вероятно, должна быть доступна в следующей версии Scala 2.8, а именно возможностью заменять шаблоны регулярных выражений с помощью функции. Используя это, проблема может быть уменьшена до этого:
def replaceRegex(input: String, values: IndexedSeq[String]) =
"""\$(\d+)""".r.replaceAllMatchesIn(input, {
case Regex.Groups(index) => values(index.toInt)
})
Что сводит проблему к тому, что вы на самом деле намереваетесь сделать: замените все $ N на соответствующие Nth значения списка.
Или, если вы действительно можете установить стандарты для входной строки, вы можете сделать это следующим образом:
"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
. Уверенный, что мы можем легко изменить это при необходимости, я буду исходить из предположения, что это не так.
Итак, давайте рассмотрим, какие функции нам нужны. Естественно, нам понадобится функция, которая возвращает индекс в первый заполнитель:
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
.
ПОНИМАНИЕ
Понимание Scala на самом базовом уровне означает преобразование T[A]
в T[B]
с помощью функции A => B
, известной как функтор. Это легко понять, когда дело доходит до коллекций. Например, я могу преобразовать List[String]
имен в List[Int]
длин имен с помощью функции String => Int
, которая возвращает длину строки. Это понимание списка.
Существуют и другие операции, которые могут быть выполнены с помощью пониманий, с помощью функций с сигнатурами A => T[B]
, которые связаны с монадами, или A => Boolean
.
Это означает, что мы должны видеть входную строку как T[A]
. Мы не можем использовать Array[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]
вход, который можно понять, 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 - это баланс между потребностями и средствами, а не пуристическими решениями. Хотя, конечно, вы свободны в том, чтобы быть пуристом. : -)