Seq.Unfold Explained in Simple Methodical Terms

On a reasonably thorough search of textbooks and the Internet, I am left dissatisfied with explanations of F#’s Seq.unfold function. It is a bit of a tricky one. But it should not be made harder by insufficient explanation. So I am going to attempt a more didactic approach, breaking it right down, rather than just throwing a Fibonacci example at the reader (that will come later).

Let’s get formal for a second. The Microsoft documentation is here. Have a quick read of that small page and then I will elaborate, in my own words.

The Ingredients

A call to unfold typically looks something like (without the huge gap after the first parameter):

Seq.unfold calculateElementAndPrimeNext            10 
                    (*1 function*)          (*2 state value*)

So, the ingredients (parameters) are:

  1. a function; and
  2. state value.

The function is an element generator. That is, it takes any type of parameter and generates the sequence, element by element. Each time the function is invoked, it returns an option type. That type can be either None or Some(x) where x is a value of any type and the Some constructor must contain a tuple.

That function is repeatedly invoked until finally None is returned. I think the tricky part about unfold is understanding how that generated element comes from the return type of the function. I will endeavour to clarify that by using a really simple example, first up.

The Generator Function

In preparation for our examination of unfold, I am going to present the generator function to be passed to unfold for our first example. That function is:

let divideByTwo x =
    let limit = 0.1
    let n = x - (x / 2.0)
    if n > limit then
        Some(x,n)
    else
        None

Now let’s just call that function manually, passing it a floating point value of 8.0 and examine what is returned:

Option

Figure 1

We can see there that there is a tuple of {8,4} that is returned. Looking at the function, we can see that it will half the incoming parameter and return a tuple comprising of it’s incoming parameter and that halved value. If, however, that halved value is less than 0.1, None is returned. I think you can see where I am going with this. If we can keep calling that function, by halving the incoming parameter each time, eventually it will reach a state where None is returned.

Back to our big picture, the return type of the function for unfold is an option tuple. As you can see, that matches what divideByTwo returns. The tuple consists of the next element of the sequence and the next state value. So, the first time it is called, the first item in the returned tuple will be the first item in the sequence which unfold is in the process of generating. And the second item in the tuple will be what is passed to the generating function on its next (second) invocation. And so on until None is returned. When that is returned, the sequence is “closed off” and complete.

Simple Example

With our generator function in hand, we are now ready to test drive the Seq.unfold method and see what it can do for us. To that end, the following code shows the generator function and the initial state (10.0) being passed to the unfold function:

let divideByTwo x =
    let limit = 0.1
    let n = x - (x / 2.0)
    if n > limit then
        Some(x,n)
    else
        None

let newSequence = Seq.unfold divideByTwo 10.0 // pass function and initial state to unfold

let printResults x =
    printf "%f - " x |> ignore
    
Seq.iter printResults newSequence

System.Console.ReadLine() |> ignore //  keep window open

unfold is called on line 9 and the remaining code after that just iterates through the newly created sequence and prints to the console. You should see something like:

10.000000 – 5.000000 – 2.500000 – 1.250000 – 0.625000 – 0.312500 –

Let’s just run through an invocation of the generator function to see how unfold works. One important thing to understand is that you only need to pass in the initial state parameter once. In the case of our example, we passed in 10.0. Then, this happened:

  1. divideByTwo processed the parameter, generating an option with the tuple (10, 5);
  2. unfold took the 10 from that tuple and placed it as the first item in the sequence that it is building;
  3. unfold took the 5 from that tuple and invoked divideByTwo again with 5 as the parameter.

This cycle continues until divideByTwo is passed a value which returns less than 0.1 when halved. And at that point, each item passed to divideByTwo is added to the sequence, except for the last one. The last one (0.15625) is not added because None was returned when that value was passed to divideByTwo.

So, a key point to understand is that a state parameter is only added to the new sequence when an tuple is returned by the generator function. I deliberately broke out the generator function into a separate function, because it is easier to study and debug that way. Once you understand what is going on, you can use an embedded lambda to unfold the sequence:

let newSequence = 
    10.0 |> //  pipe the float "state" parameter to unfold as the second parameter         
    Seq.unfold 
        (fun x -> 
             let limit = 0.1
             let n = x - (x / 2.0)
             if n > limit then
                Some(x,n)
             else
                None)

Now, take a breather. I’m even going to include a ruled line here to close off this section. Because next up we’ll look at the Fibonacci sequence and how unfold lends itself as an ideal way to implement that sequence.


Fibonacci

Now we’re ready to look at a slightly more difficult example of using unfold to generate the Fibonacci sequence. The interesting thing about this sequence is that it is non-terminating. unfold can be used to generate a non-terminating sequence, but your computer will eventually run out of memory. So, it is also possible to terminate it outside of the unfold function itself. You will see that in this example.

Quick Side-Bar: the algorithm for Fibonacci numbers is defined by the recurrence relation:
Fn = Fn-1 + Fn-2
with the seed values
F0 = 0, F1 = 1.

The actual function which implements the above algorithm and which will be our generating function is:

let fibonacciGenerator (newItemToBeAdded, nextItemToBeAdded) =
    Some(newItemToBeAdded, (nextItemToBeAdded, newItemToBeAdded + nextItemToBeAdded))

There are a couple of things I would like to note about the function:

  1. Note how the function never returns None. As it is non-terminating in nature, it will always return Some.
  2. This time, the parameter for the function is a tuple. That makes no difference. The key thing is that the return type is an option tuple.
  3. As with the previous example, the item which will be added to the sequence for that particular invocation of the generator function will be the newItemToBeAdded parameter. That is, the value which is the left hand value of the returning option tuple.
  4. As per the algorithm for Fibonacci, the item which will be added in the next invocation of it will be nextItemToBeAdded and that will be coupled with the sum of newItemToBeAdded and nextItemToBeAdded, which will be the next item after that.

With all that analysis done, we are ready to build the Fibonacci sequence:

open System

let fibonacciGenerator (newItemToBeAdded, nextItemToBeAdded) =
    Some(newItemToBeAdded, (nextItemToBeAdded, newItemToBeAdded + nextItemToBeAdded))
 
let fibonacci = 
    Seq.unfold fibonacciGenerator (0, 1)

let first20FibonacciNumbers =
    fibonacci
    |> Seq.take 20
     
first20FibonacciNumbers |> Seq.iter (fun x -> printf "%i" x)  

Console.ReadKey() |> ignore //  keep window open

The initial state value passed to unfold is {0,1}. From that first invocation of the generator function, we can deduce that 0 will be added to the sequence, 1 will be the next item and 1 will also be the third item in the sequence (i.e. newItemToBeAdded + nextItemToBeAdded = 1 + 0 ). Note that I have dealt with the non-terminating aspect of the pattern by using Seq.take to take the first 20 numbers from the sequence. You should see:

0 – 1 – 1 – 2 – 3 – 5 – 8 – 13 – 21 – 34 – 55 – 89 – 144 – 233 – 377 – 610 – 987 – 1597 – 2584 – 4181 –

The reason we are able to take the first 20 is that unfold is lazily evaluated (I think – please correct me if I am wrong). So when only 20 items are requested, the generator function will only be invoked 20 times.

And for completeness, the version using a lambda:

open System

let fibonacci (a,b) =
    Seq.unfold
        (fun (newItemToBeAdded, nextItemToBeAdded) -> Some(newItemToBeAdded, (nextItemToBeAdded, newItemToBeAdded + nextItemToBeAdded))) (a,b)

let first20FibonacciNumbers =
    fibonacci (0,1)
    |> Seq.take 20
 
first20FibonacciNumbers |> Seq.iter (fun x -> printf "%i - " x)  

Console.ReadKey() |> ignore //  keep window open

Very important. Very powerful. Very cool.

I hope this has made learning about Seq.unfold much easier for people looking to learn about it. Me sleep now.

Edit

Note, as mentioned above, the pure Fibonacci equation is non-terminating. Hence, the call to |> Seq.take 20. However, for the purposes of illustration, we can create a variation of the Fibonacci sequence which does have a base case which will terminate after the 20th number is reached (4181). Here is what that would look like:

let fibonacciGeneratorOf20 (newItemToBeAdded, nextItemToBeAdded) =
    if newItemToBeAdded < 4182 then
        Some(newItemToBeAdded, (nextItemToBeAdded, newItemToBeAdded + nextItemToBeAdded))
    else
        None
  
let fibonacci = 
    Seq.unfold fibonacciGeneratorOf20 (0, 1)
 
let first20FibonacciNumbers =
    fibonacci

Note how there is no longer a call to take 20, as this is now built into the fibonacciGeneratorOf20 function.

  1. Hi David,

    Thanks for explaining clearly what msdn over two pages fails to tell in their seq.unfold references : That the first tuple element is added to the sequence and the second element is the input for the next iteration.

  2. You’re most welcome. Glad I helped.

  3. This was helpful, however I’m not clear on the later fibonacci example terminates because there’s no place where it returns an explicit ‘None’. I’m trying to find way to eliminate (where possible) the if X Some else None construct when using Seq.unfold and your example avoids it but how?

  4. Hi Hugh, I’ve added an Edit at the end of the post which is hopefully helpful. Obviously, it does not help eliminate the if .. else. But it does explain how the call to “take 20” is how it avoids it.

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>