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:

- a function; and
- 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:

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

**. So, the first time it is called, the first item in the returned tuple will be the first item in the sequence which**

*the next state value*`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:

`divideByTwo`

processed the parameter, generating an option with the tuple (10, 5);`unfold`

took the 10 from that tuple and placed it as the first item in the sequence that it is building;`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:

F_{n} = F_{n-1} + F_{n-2}

with the seed values

F_{0} = 0, F_{1} = 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:

- Note how the function never returns
`None`

. As it is non-terminating in nature, it will always return`Some`

. - 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.
- 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. - 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.

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.

You’re most welcome. Glad I helped.

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?

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.