Создать последовательность, используя предыдущие значения

Question

Я изучаю функциональное программирование на F #, и я хочу написать функцию, которая будет генерировать последовательность для меня.

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

В C # я обычно пишу что-то вроде этого:

public static IEnumerable<double> GenerateSequence(double startingValue, int n)
{
    double TransformValue(double x) => x * 0.9 + 2;

    yield return startingValue;

    var returnValue = startingValue;
    for (var i = 1; i < n; i++)
    {
        returnValue = TransformValue(returnValue);
        yield return returnValue;
    }
}

Когда я попытался перевести эту функцию на F #, я сделал это:

let GenerateSequence startingValue n =
    let transformValue x =
        x * 0.9 + 2.0

    seq {
        let rec repeatableFunction value n = 
            if n = 1 then
                transformValue value
            else 
                repeatableFunction (transformValue value) (n-1)

        yield startingValue
        for i in [1..n-1] do
            yield repeatableFunction startingValue i
    }

У этой реализации есть две очевидные проблемы.

Во-первых это потому, чтоЯ пытался избежать создания изменяемого значения (аналог переменной returnValue в реализации C #), я не использовал значения предыдущих вычислений при генерации последовательности.Это означает, что для сотого элемента последовательности мне нужно сделать дополнительно 99 вызовов функции transformValue вместо одного (как я делал в реализации C #).Это пахнет крайне плохой производительностью.

Секунда заключается в том, что вся функция не написана в соответствии с функциональным программированием.Я уверен, что есть более элегантная и компактная реализация.Я подозреваю, что Seq.fold или List.fold или что-то подобное, должно быть использовано здесь, но я все еще не могу понять, как эффективно их использовать.

---

Так что вопрос: как переписать функцию GenerateSequence на F #, чтобы она была в стиле функционального программирования и имела лучшую производительность?

Любые другие советы также приветствуются.

Answer 1

Ответ от @rmunn показывает довольно хорошее решение с использованием unfold.Я думаю, что есть два других варианта, которые стоит рассмотреть, которые на самом деле просто используют изменяемую переменную и используют рекурсивное выражение последовательности.Выбор, вероятно, зависит от личных предпочтений.Два других варианта выглядят так:

let generateSequenceMutable startingValue n = seq {
  let transformValue x = x * 0.9 + 2.0
  let mutable returnValue = startingValue
  for i in 1 .. n  do 
    yield returnValue 
    returnValue <- transformValue returnValue }

let generateSequenceRecursive startingValue n = 
  let transformValue x = x * 0.9 + 2.0
  let rec loop value i = seq {
    if i < n then
      yield value
      yield! loop (transformValue value) (i + 1) }
  loop startingValue 0

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

Если вы хотите использовать одну из этих версий и генерировать бесконечную последовательность, из которой вы можете затемВозьмите столько элементов, сколько вам нужно, вы можете просто изменить for на while в первом случае или удалить if во втором случае:

let generateSequenceMutable startingValue n = seq {
  let transformValue x = x * 0.9 + 2.0
  let mutable returnValue = startingValue
  while true do
    yield returnValue 
    returnValue <- transformValue returnValue }

let generateSequenceRecursive startingValue n = 
  let transformValue x = x * 0.9 + 2.0
  let rec loop value i = seq {
    yield value
    yield! loop (transformValue value) (i + 1) }
  loop startingValue 0

Если я писал это, явероятно, будет идти с изменяемой переменной или с unfold.Мутация может быть «обычно злой», но в данном случае это локальная изменяемая переменная, которая никоим образом не нарушает прозрачность ссылок, поэтому я не думаю, что это вредно.

Answer 2

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

Это идеальный вариантописание метода Seq.unfold.Он принимает два параметра: начальное состояние и функцию преобразования и возвращает последовательность, в которой каждое значение вычисляется из предыдущего состояния.Есть несколько тонкостей, связанных с использованием Seq.unfold, которые довольно краткая документация может объяснить не очень хорошо:

1. Seq.unfold ожидает функцию преобразования, которую яЯ буду звонить f с этого момента, чтобы вернуть опцию .Он должен вернуть None, если последовательность должна завершиться, или Some (...), если в последовательности осталось другое значение.Вы можете создавать бесконечные последовательности таким образом, если вы никогда не вернете None;бесконечные последовательности прекрасно работают, так как F # вычисляет последовательности лениво, но вам нужно быть осторожным, чтобы не зацикливаться на бесконечной последовательности.: -)

2. Seq.unfold также ожидает, что если f вернет Some (...), он вернет не только следующее значение, но и кортеж следующего значения и следующего состояния,Это показано в примере Фибоначчи в документации, где состояние фактически представляет собой кортеж текущего значения и предыдущего значения, которое будет использоваться для вычисления показанного значения next .Пример документации не очень ясен, так что вот что я думаю, это лучший пример:

   let infiniteFibonacci = (0,1) |> Seq.unfold (fun (a,b) ->
       // a is the value produced *two* iterations ago, b is previous value
       let c = a+b
       Some (c, (b,c))
   )
   infiniteFibonacci |> Seq.take 5 |> List.ofSeq // Returns [1; 2; 3; 5; 8]
   let fib = seq {
       yield 0
       yield 1
       yield! infiniteFibonacci
   }
   fib |> Seq.take 7 |> List.ofSeq // Returns [0; 1; 1; 2; 3; 5; 8]
   

И если вернуться к вашему GenerateSequence вопросу, я бы написалэто так:

let GenerateSequence startingValue n =
    let transformValue x =
        let result = x * 0.9 + 2.0
        Some (result, result)
    startingValue |> Seq.unfold transformValue |> Seq.take n

Или, если вам нужно включить начальное значение в последовательность:

let GenerateSequence startingValue n =
    let transformValue x =
        let result = x * 0.9 + 2.0
        Some (result, result)
    let rest = startingValue |> Seq.unfold transformValue |> Seq.take n
    Seq.append (Seq.singleton startingValue) rest

Разница между Seq.fold и Seq.unfold

Самый простой способ запомнить, хотите ли вы использовать Seq.fold или Seq.unfold, это спросить себя, какое из этих двух утверждений является верным:

1. У меня есть список (или массив,или последовательность) элементов, и я хочу получить одно значение результата путем многократного вычисления пары элементов в списке.Например, я хочу взять произведение всей этой серии чисел.Это операция fold : я беру длинный список и «сжимаю» его (так сказать) до единого значения.

2. У меня один стартvalue и функцию для получения значения next из значения current , и я хочу получить список (или последовательность, или массив) значений.Это операция развернуть : я беру небольшое начальное значение и «расширяю» его (так сказать) до полного списка значений.