Tag Archives: F#

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.

Records with Functions and Parameters

In my last post, we saw how you could use records in a way which was object-like in nature. In this post, I want to expand on that post, showing how to use functions as members which take parameters. As this is more complicated, I will use a simpler record type which only has one member. The code is:

open System.IO
open System.Globalization

type DateTimeStringPainter =
    { ShowString: System.DateTime -> System.String; }


let culture = CultureInfo.CurrentCulture
let flag = "F"

let strFunctionGiveFormatter fmt dtFunctionFormatString =
    {ShowString = (fun dtStruct -> dtFunctionFormatString fmt dtStruct);}

let fnCreateFunctionToPrintDTString fmtter formatFlag =
    strFunctionGiveFormatter fmtter (fun formatProvider dateTimeStruct -> dateTimeStruct.ToString(formatFlag, formatProvider))
    
let createRecordDateTimeStringPainter = fnCreateFunctionToPrintDTString culture flag

printfn "%s" (createRecordDateTimeStringPainter.ShowString(System.DateTime.Now))

//printfn "%s" (System.DateTime.Now.ToString("F", culture))

printfn "\nPress any key to kill ..."
System.Console.ReadKey() |> ignore 

The code above creates a function which will output a date to the console. Note that this could be done with 1 line of code (see line 20). But be cool – it’s demonstration code!

The custom type, DateTimeStringPainter, requires the implementation of a method which takes a DateTime value as a parameter and gives a string result (line 5).

In line 11, I have defined the implementation of the ShowString function. It takes the DateTime parameter dtStruct. Notice on the right hand side, there are 3 items dtFunctionFormatString, fmt and dtStruct. As you will see, that is a function, dtFunctionFormatString, which takes 2 parameters fmt and dtStruct. That function gives us the string we require to meet the implementation requirements of ShowString.

Lines 13 – 14 show the rest of the story. On line 14, strFunctionGiveFormatter is called, passing to it a formatter and a function. Recall from line 10 that strFunctionGiveFormatter takes variables of those two types. The function is declared “in-line” and passed to strFunctionGiveFormatter on line 14.

Going back to line 11 quickly, dtFunctionFormatString takes two parameters. It gets its DateTime parementer from the left hand side of ShowString (dtStruct), and it gets its other parameter from the incoming parameter fmt. And that is the core thing to understand in this example.

Line 16 shows an identifier being bound to the fnCreateFunctionToPrintDTString function, with an IFormatter object and a format flag passed in as parameters. And line 18 sees ShowString actually being called, with a DateTime instance being passed in (i.e. which goes to the left hand side of ShowString on line 11).

And that is how you pass around functions with parameters to a record which has a function as one of its members.

Using Records like Objects (F#)

Records are an F# thing. And the concept which I will set out in the example below took me a while to get my head around (the syntax). But it’s really very simple.

Records can have functions as their fields. The following example involves the use of a custom type (NamerRecord). NamerRecord is a record with 2 functions as its fields.

  1. First off, I will create/initialise a NamerRecord record with a name (line 19). At that point, neither of the record’s functions have been called.
  2. Then, I’ll call the record’s SayName function (line 22).
  3. Then I will change the name of the record (line 23),
  4. Following which, I will call the SayName function again (line 24).
open System.Drawing

// a NamerRecord record that will act as our object
type NamerRecord =
    { Rename: string -> unit;
      SayName: unit -> unit }

//  This identifier (aNameThing) has the type "string -> NamerRecord". 
//  We pass in a string and end up with a NamerRecord.
//  It's a functional programming thing. Functions can be values. 
let aNameThing initialName =    
    let currentName = ref initialName
    {   Rename = 
            fun newName -> currentName := newName;
        SayName = 
            fun() -> printf "%s\n" !currentName; }

//  This is the instantiation of our NamerRecord type
let dave = aNameThing "Bobby Sixkiller"

//  call the functions defined in the NamerRecord type
dave.SayName()
dave.Rename("Vince Black (aka Reno Raines)")
dave.SayName()

printf "\n\n"
System.Console.ReadKey() |> ignore

We’re getting object-like behaviour out of a record:

In my next post, I’ll take this a bit further to confuse you even more!