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.

Answer 2

Your description of the problem was excellent: "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."

That is a perfect description of the Seq.unfold method. It takes two parameters: the initial state and a transformation function, and returns a sequence where each value is calculated from the previous state. There are a few subtleties involved in using Seq.unfold which the rather terse documentation may not explain very well:

1. Seq.unfold expects the transformation function, which I'll call f from now on, to return an option. It should return None if the sequence should end, or Some (...) if there's another value left in the sequence. You can create infinite sequences this way if you never return None; infinite sequences are perfectly fine since F# evaluates sequences lazily, but you do need to be careful not to ever loop over the entirely of an infinite sequence. :-)

2. Seq.unfold also expects that if f returns Some (...), it will return not just the next value, but a tuple of the next value and the next state. This is shown in the Fibonacci example in the documentation, where the state is actually a tuple of the current value and the previous value, which will be used to calculate the next value shown. The documentation example doesn't make that very clear, so here's what I think is a better example:

   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]
   

And to get back to your GenerateSequence question, I would write it like this:

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

Or if you need to include the starting value in the sequence:

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

The difference between Seq.fold and Seq.unfold

The easiest way to remember whether you want to use Seq.fold or Seq.unfold is to ask yourself which of these two statements is true:

1. I have a list (or array, or sequence) of items, and I want to produce a single result value by running a calculation repeatedly on pairs of items in the list. For example, I want to take the product of this whole series of numbers. This is a fold operation: I take a long list and "compress" it (so to speak) until it's a single value.

2. I have a single starting value and a function to produce the next value from the current value, and I want to end up with a list (or sequence, or array) of values. This is an unfold operation: I take a small starting value and "expand" it (so to speak) until it's a whole list of values.