Функциональное (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, может ли кто-нибудь дать представление об этом?

Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
0
0
56
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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
}

Не добавляйте к List слишком медленно, добавьте к нему и reverse в конце.

Luis Miguel Mejía Suárez 09.04.2022 15:41

Интересный! не могли бы вы предоставить некоторые документы?

AminMal 09.04.2022 16:08

@AminMal просто подумайте об этом (или посмотрите на реализацию): как бы вы добавили что-то в конец связанного списка. Какова «O-сложность» этой операции?

Dima 09.04.2022 16:16

@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 09.04.2022 18:49

@AminMal уверен, что для одного добавления лучше сделать это, но для создания List с нуля вы создаете его только путем добавления, а затем отменяете это в конце. Именно так реализуется любой алгоритм хвостовой рекурсии на List.

Luis Miguel Mejía Suárez 09.04.2022 18:53

@LuisMiguelMejíaSuárez Я вижу, ваш первый комментарий был похож на «Не добавлять в список». обязательно отредактирую свой ответ

AminMal 09.04.2022 18:59

Во время рекурсии это даже не двойное обращение, а просто однократное обращение. Например, посмотрите на ответ Димы, его можно улучшить, позвонив next.reverse :: out, чтобы избежать map(_.reverse) в конце.

Luis Miguel Mejía Suárez 09.04.2022 19:03

@LuisMiguelMejíaSuárez, я сделал некоторые улучшения на основе приведенного выше обсуждения, не могли бы вы взглянуть? Кроме того, временная сложность next.reverse :: out с реверсом в конце не будет отличаться от .map(_.reverse).reverse (хотя я понимаю, что это может отличаться в действии, но временная сложность та же).

AminMal 09.04.2022 19:13

@AminMal да, это выглядит намного лучше :) Нет никакой разницы в сложности, но вызов reverse во время рекурсии вместо map в конце позволит избежать ненужной итерации (хотя технически map и reverse могут быть объединены в одной итерации). - Все остальное, что я могу сказать, является более субъективным и подпадает под категорию стилевых предпочтений, вы можете увидеть мою версию здесь и сделать свои собственные выводы :) scastie.scala-lang.org/BalmungSan/vFodyMILQL6EJJt2FUzz5g/2

Luis Miguel Mejía Suárez 09.04.2022 19:21

@AminMal, чтобы быть ясным, добавление к List в значительной степени всегда «плохо», просто иногда «плохости» можно избежать с помощью трюка с добавлением / обратным, а иногда - нет. Если вам нужно добавить что-то только один раз, это не реальный вариант использования. Более реалистично, у вас, вероятно, есть функция, которая вызывается with. произвольные списки, к которым нужно время от времени добавлять. Вы правы, в этом случае было бы глупо реверсировать внутри функции. Но это не делает добавление "эффективным". Это просто означает, что вы используете неправильную структуру данных для своего сценария.

Dima 10.04.2022 12:55

@ Дима, я понимаю твою точку зрения, это правильно, я, должно быть, неправильно понял первый комментарий, твой и Луиса. Спасибо вам обоим.

AminMal 10.04.2022 13:22

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

Оттуда это довольно просто.

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

   @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), что делает все это квадратичным (фу!).

Другие вопросы по теме