Функциональное (Scala) программирование: разделить List[Char] на токен
Какова общепринятая реализация рекурсивной функции разделения по токену?
Например:
val s: List[Char] = 'F' :: 'o' :: 'o' :: ' ' :: 'b' :: 'a' :: 'r' :: ' ' :: 'f' :: 'o':: 'o':: ' ' :: 'b' :: 'a' :: 'r' :: Nil
fooSplit(s) // -> List(List('F','o','o'), List('b', 'a', 'r'), List('f', 'o', 'o'), List('b','a','r'))
Вот базовые случаи, которые я придумал при сопоставлении с образцом для параметра:
def fooSplit(text: List[Char]): List[List[Char]] = text match {
case x :: ' ' :: xs =>
// Somehow append old list to fooSplit(xs) <?>
println(x + "_")
fooSplit(xs)
case x :: xs =>
println(x + "")
fooSplit(xs)
case Nil => Nil
}
Большинство моих попыток следовать приведенной выше структуре почти всегда приводят к List('F', List('O', List('O'), ...)...). Не придумав какое-то очень зловещее двойное сопоставление с образцом, я, кажется, не могу обернуть голову, чтобы расширить вместо добавления к внутреннему списку.
Я также хотел бы процитировать Scala Cookbook:
Use flatMap in situations where you run map followed by flatten. The specific situation is this:
• You’re using map (or a for/yield expression) to create a new collection from an existing collection.
• The resulting collection is a list of lists.
• You call flatten immediately after map (or a for/yield expression)
Это кажется очень возможным случаем использования flatMap, может ли кто-нибудь дать представление об этом?
Ответы 2
Тот факт, что вы возвращаете экземпляр List[List[String]], не означает, что вам нужно сгладить его, иногда вам могут понадобиться эти значения. Я бы предложил следующее:
def fooSplit(text: List[Char]): List[List[Char]] = {
@tailrec
def fooSplitHelper(currentListBeforeToken: List[Char] = List.empty, list: List[Char], acc: List[List[Char]] = List.empty): List[List[Char]] = {
if (list.isEmpty) {
currentListBeforeToken.reverse :: acc
} else {
list.head match {
case ' ' => fooSplitHelper(List.empty[Char], list.tail, currentListBeforeToken.reverse :: acc)
case otherChar => fooSplitHelper(otherChar :: currentListBeforeToken, list.tail, acc)
}
}
}
fooSplitHelper(list = text).reverse
}
Интересный! не могли бы вы предоставить некоторые документы?
@AminMal просто подумайте об этом (или посмотрите на реализацию): как бы вы добавили что-то в конец связанного списка. Какова «O-сложность» этой операции?
@LuisMiguelMejíaSuárez, @Dima. спасибо за ваши ответы. если я хочу добавить 5 к [1, 2, 3, 4], я могу либо добавить O (n), либо попытаться изменить исходный список (O (n) в результате [4, 3, 2, 1]) а затем добавьте значение, полученное в результате [5, 4, 3, 2, 1], с O (1)), а затем снова переверните список (O (n), в результате чего [1, 2, 3, 4, 5]) . ссылаясь на документы scala: This includes the index-based lookup of elements, length, append and *reverse*. Я видел, как другие разработчики scala также пытались использовать двойное реверсирование, но я не вижу в этом смысла, я также сделал некоторый код, и добавление было быстрее (в большинстве случаев)!
@AminMal уверен, что для одного добавления лучше сделать это, но для создания List с нуля вы создаете его только путем добавления, а затем отменяете это в конце. Именно так реализуется любой алгоритм хвостовой рекурсии на List.
@LuisMiguelMejíaSuárez Я вижу, ваш первый комментарий был похож на «Не добавлять в список». обязательно отредактирую свой ответ
Во время рекурсии это даже не двойное обращение, а просто однократное обращение. Например, посмотрите на ответ Димы, его можно улучшить, позвонив next.reverse :: out, чтобы избежать map(_.reverse) в конце.
@LuisMiguelMejíaSuárez, я сделал некоторые улучшения на основе приведенного выше обсуждения, не могли бы вы взглянуть? Кроме того, временная сложность next.reverse :: out с реверсом в конце не будет отличаться от .map(_.reverse).reverse (хотя я понимаю, что это может отличаться в действии, но временная сложность та же).
@AminMal да, это выглядит намного лучше :) Нет никакой разницы в сложности, но вызов reverse во время рекурсии вместо map в конце позволит избежать ненужной итерации (хотя технически map и reverse могут быть объединены в одной итерации). - Все остальное, что я могу сказать, является более субъективным и подпадает под категорию стилевых предпочтений, вы можете увидеть мою версию здесь и сделать свои собственные выводы :) scastie.scala-lang.org/BalmungSan/vFodyMILQL6EJJt2FUzz5g/2
@AminMal, чтобы быть ясным, добавление к List в значительной степени всегда «плохо», просто иногда «плохости» можно избежать с помощью трюка с добавлением / обратным, а иногда - нет. Если вам нужно добавить что-то только один раз, это не реальный вариант использования. Более реалистично, у вас, вероятно, есть функция, которая вызывается with. произвольные списки, к которым нужно время от времени добавлять. Вы правы, в этом случае было бы глупо реверсировать внутри функции. Но это не делает добавление "эффективным". Это просто означает, что вы используете неправильную структуру данных для своего сценария.
@ Дима, я понимаю твою точку зрения, это правильно, я, должно быть, неправильно понял первый комментарий, твой и Луиса. Спасибо вам обоим.
Одна важная реализация, позволяющая не допустить, чтобы эта функция стала «зловещей», заключается в том, что вы можете хранить текущий создаваемый подсписок как собственную переменную и добавлять его к результату только после его завершения.
Оттуда это довольно просто.
В основном есть три случая: конец списка (готово!), Текущий элемент — пробел (добавьте промежуточное значение к результату и снова начните с пустого), все остальное (просто продолжайте добавлять к промежуточному), поэтому вы просто пишете их:
@tailrec
def split(
in: List[Char],
next: List[Char] = Nil,
out: List[List[Char]] = Nil
): List[List[Char]] = in match {
case Nil => out.map(_.reverse).reverse
case ' ' :: tail => split(tail, Nil, next :: out)
case head :: tail => split(tail, head :: next, out)
}
Несколько распространенных трюков здесь заключаются в том, что вы передаете фактический результат, который вы создаете, рекурсивным вызовам, а не просто возвращаете его (таким образом, функция может быть оптимизирована как хвостовая рекурсия - не требует места в стеке) и Кроме того, вы строите свои списки в обратном направлении, добавляя к ним элементы, а не добавляя их, а затем реверсивно в конце, когда список завершен (это позволяет реализации оставаться линейной, потому что добавление к списку занимает постоянное время, в отличие от добавления). , что равно O(N), что делает все это квадратичным (фу!).
Не добавляйте к
Listслишком медленно, добавьте к нему иreverseв конце.