помогите переписать в функциональном стиле

Question

Я изучаю Scala как мой первый функциональный язык.В качестве одной из проблем я пытался найти функциональный способ генерации последовательности S до n мест.S определяется так, что S (1) = 1, а S (x) = количество раз, когда x появляется в последовательности.(Я не могу вспомнить, как это называется, но я видел это раньше в книгах по программированию.)

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

  S = 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7 ...

Я могу сгенерироватьэта последовательность довольно легко в Scala с использованием императивного стиля, подобного следующему:

  def genSequence(numItems: Int) = {
    require(numItems > 0, "numItems must be >= 1")
    var list: List[Int] = List(1)
    var seq_no = 2
    var no     = 2
    var no_nos = 0
    var num_made = 1

    while(num_made < numItems) {
      if(no_nos < seq_no) {
        list = list :+ no
        no_nos += 1
        num_made += 1
      } else if(no % 2 == 0) {
        no += 1
        no_nos = 0
      } else {
        no += 1
        seq_no += 1
        no_nos = 0
      }
    }
    list
  }

Но я действительно не представляю, как написать это без использования vars и цикла while.

Спасибо!

Answer 1

Ответ Павла пока приблизился, но он также неэффективен. Два flatMap с и zipWithIndex здесь излишни:)

Мое понимание необходимого вывода:

• Результаты содержат все натуральные числа (начиная с 1) хотя бы один раз
• каждое число n появляется в выходных данных (n/2) + 1 раз

Как правильно заметил Павел, решение состоит в том, чтобы начать с Stream, а затем использовать flatMap:

Stream from 1

Это генерирует Stream, потенциально бесконечную последовательность, которая производит значения только по требованию. В этом случае он генерирует 1, 2, 3, 4... вплоть до бесконечности (в теории) или Integer.MAX_VALUE (на практике)

Потоки могут быть сопоставлены, как с любой другой коллекцией. Например: (Stream from 1) map { 2 * _ } генерирует поток четных чисел.

Вы также можете использовать flatMap в потоках, что позволяет сопоставить каждый элемент ввода с нулем или несколькими элементами вывода; это ключ к решению вашей проблемы:

val strm = (Stream from 1) flatMap { n => Stream.fill(n/2 + 1)(n) }

---

Итак ... Как это работает? Для элемента 3 лямбда { n => Stream.fill(n/2 + 1)(n) } создаст выходной поток 3,3. За первые 5 целых чисел вы получите:

1 -> 1
2 -> 2, 2
3 -> 3, 3
4 -> 4, 4, 4
5 -> 5, 5, 5
etc.

и поскольку мы используем flatMap, они будут объединены, что даст:

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, ...

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

Answer 2

Следующий код создает ту же последовательность, что и ваша:

val seq = Stream.from(1)
        .flatMap(Stream.fill(2)(_))
        .zipWithIndex
        .flatMap(p => Stream.fill(p._1)(p._2))
        .tail

Однако, если вы хотите создать последовательность Голомба (которая соответствует определению, но отличается от вашейпример кода), вы можете использовать следующее:

val seq = 1 #:: a(2)
def a(n: Int): Stream[Int] = (1 + seq(n - seq(seq(n - 2) - 1) - 1)) #:: a(n + 1)

Вы можете проверить мою статью , чтобы получить больше примеров того, как работать с числовыми последовательностями в функциональном стиле.

Answer 3

Вот очень прямой «перевод» определения последовательности Голомба:

val it = Iterator.iterate((1,1,Map(1->1,2->2))){ case (n,i,m) =>
    val c = m(n)
    if (c == 1) (n+1, i+1, m + (i -> n) - n)
    else (n, i+1, m + (i -> n) + (n -> (c-1)))
}.map(_._1)

println(it.take(10).toList)

Трипел (n, i, m) содержит фактическое число n, индекс i и карту m, которая содержит частоту повторения n. Когда счетчик на карте для нашего n достигает 1, мы увеличиваем n (и можем сбросить n с карты, так как он больше не нужен), иначе мы просто уменьшаем счетчик n на карте и сохраняем n. В каждом случае мы добавляем новую пару i -> n в карту, которая будет использоваться в качестве счетчика позже (когда последующее n достигнет значения текущего i).

[Изменить]

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

import collection.immutable.Queue

val it = 1 #:: Iterator.iterate((2, 2, Queue[Int]())){
  case (n,1,q) => (n+1, q.head, q.tail + (n+1))
  case (n,c,q) => (n,c-1,q + n)
}.map(_._1).toStream

Итератор работает правильно, начиная с 2, поэтому мне пришлось добавить 1 в начале. Второй аргумент кортежа теперь является счетчиком текущего n (взятого из очереди). Текущий счетчик также может храниться в очереди, поэтому у нас есть только пара, но тогда менее понятно, что происходит из-за сложной обработки очереди:

val it = 1 #:: Iterator.iterate((2, Queue[Int](2))){
  case (n,q) if q.head == 1 => (n+1, q.tail + (n+1))
  case (n,q) => (n, ((q.head-1) +: q.tail) + n)
}.map(_._1).toStream 

Answer 4

Вот перевод вашего кода в более функциональный стиль:

def genSequence(numItems: Int): List[Int] = {
  genSequenceR(numItems, 2, 2, 0, 1, List[Int](1))
}


def genSequenceR(numItems: Int, seq_no: Int, no:Int, no_nos: Int, numMade: Int, list: List[Int]): List[Int] = {
 if(numMade < numItems){
   if(no_nos < seq_no){
     genSequenceR(numItems, seq_no, no, no_nos + 1, numMade + 1, list :+ no)
   }else if(no % 2 == 0){
     genSequenceR(numItems, seq_no, no + 1, 0, numMade, list)
   }else{
     genSequenceR(numItems, seq_no + 1, no + 1, 0, numMade, list)
   }
  }else{
    list
  }
}

genSequenceR - это рекурсивная функция, которая накапливает значения в списке и вызывает функцию с новыми значениями на основе условий.Как и цикл while, он завершается, когда numMade меньше numItems, и возвращает список genSequence.

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

Answer 5

Вот попытка Scala Tyro. Имейте в виду, я не совсем понимаю Scala, я не совсем понимаю вопрос, и я не совсем понимаю ваш алгоритм.

def genX_Ys[A](howMany : Int, ofWhat : A) : List[A] = howMany match {
    case 1 => List(ofWhat)
    case _ => ofWhat :: genX_Ys(howMany - 1, ofWhat)
}

def makeAtLeast(startingWith : List[Int], nextUp : Int, howMany : Int, minimumLength : Int) : List[Int] = {
    if (startingWith.size >= minimumLength) 
      startingWith 
    else 
      makeAtLeast(startingWith ++ genX_Ys( howMany, nextUp), 
                 nextUp +1, howMany + (if (nextUp % 2 == 1) 1 else 0), minimumLength)
}

def genSequence(numItems: Int) =  makeAtLeast(List(1), 2, 2, numItems).slice(0, numItems)

Это похоже на работу, но перечитайте предостережения выше. В частности, я уверен , есть библиотечная функция, которая выполняет genX_Ys, но я не смог ее найти.

РЕДАКТИРОВАТЬ Может быть

def genX_Ys[A](howMany : Int, ofWhat : A) : Seq[A]  = 
   (1 to howMany) map { x => ofWhat }