Generate sequence using previous values

Question

I'm learning functional programming with F#, and I want to write a function that will generate a sequence for me.

There is a some predetermined function for transforming a value, and in the function I need to write there should be two inputs - the starting value and the length of the sequence. Sequence starts with the initial value, and each following item is a result of applying the transforming function to the previous value in the sequence.

In C# I would normally write something like that:

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;
    }
}

As I tried to translate this function to F#, I made this:

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
    }

There are two obvious problems with this implementation.

First is that because I tried to avoid making a mutable value (analogy of returnValue variable in C# implementation), I didn't reuse values of former computations while generating sequence. This means that for the 100th element of the sequence I have to make additional 99 calls of the transformValue function instead of just one (as I did in C# implementation). This reeks with extremely bad performance.

Second is that the whole function does not seem to be written in accordance with Functional Programming. I am pretty sure that there are more elegant and compact implementation. I suspect that Seq.fold or List.fold or something like that should have been used here, but I'm still not able to grasp how to effectively use them.

---

So the question is: how to re-write the GenerateSequence function in F# so it would be in Functional Programming style and have a better performance?

Any other advice would also be welcomed.

Answer 1

The answer from @rmunn shows a rather nice solution using unfold. I think there are other two options worth considering, which are actually just using a mutable variable and using a recursive sequence expression. The choice is probably a matter of personal preference. The two other options look like this:

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

I modified your logic slightly so that I do not have to yield twice - I just do one more step of the iteration and yield before updating the value. This makes the generateSequenceMutable function quite straightforward and easy to understand. The generateSequenceRecursive implements the same logic using recursion and is also fairly nice, but I find it a bit less clear.

If you wanted to use one of these versions and generate an infinite sequence from which you can then take as many elements as you need, you can just change for to while in the first case or remove the if in the second case:

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

If I was writing this, I'd probably go either with the mutable variable or with unfold. Mutation may be "generally evil" but in this case, it is a localized mutable variable that is not breaking referential transparency in any way, so I don't think it's harmful.