F# Infinite Sequences

Has anyone else noticed how the Fibonacci example in the documentation for sequences is not quite top notch? First of all, it starts with 2 3 5 8 … while of course this should be 1 1 2 3 5 8 …; and then, I cannot really see any good reason why this sequence should be finite, and stop at 1000, of all places. Here is what is in the example as it stands:

let fib = Seq.unfold (fun state ->
    if (snd state > 1000) then None
    else Some(fst state + snd state, (snd state, fst state + snd state))) (1,1)

The problem with the correct starting point appears to be down to the necessary seeding of the state value. If the (1, 1) tupel is used as initial value, it cannot also be displayed as a result. The following code uses an option type for the state parameter, so that it can signify that the value is not initialised in the first call. It also returns an infinite sequence, which seems more natural.

let fib =
    let unfoldfn state =
        match state with
        | Some((preprev, prev)) -> 
            let next = preprev + prev
            Some(next, Some(prev, next))
        | None -> Some(1, Some(0, 1))
    Seq.unfold unfoldfn None

One needs to select a subset of the elements, e.g. the first n with Seq.take, to work with the elements or print them out, but the sequence will lazily evaluate an infinite number of them when requested.

printf "%A" (Seq.take 20 fib)

I only stumbled over this example because I was looking to figure out the correct way to use sequence expressions and the yield keyword to create infinite sequences, for a little algorithm I was thinking about. It turns out that Seq.unfold works pretty well, but more complex cases may be cumbersome to put into the generator function. The idea in the example is to take a list (finite as they come) and convert it into an infinite data structure (a sequence), such that the sequence returns one element of the list after the other, and after reaching the last element starts again from the first. A list like [1;2;3;4;5;6;7] would be returned as an infinite sequence [1;2;3;4;5;6;7;1;2;3;4;5;6;7;1;2;3;…]. Let us call this a round robin sequence.

Iterating over a list, biting of its head and then doing the tail recursively, is a pretty standard use case in functional programming. What can be a bit confusing is the way this fits together with a sequence expression, but the confusion subsides after trying a few permutations of the code. There are, in the end, only a handful of things to keep in mind.

• Always keep a copy of the original list, we need to get back to it after one iteration,
• Return a single element with the yield keyword,
• When doing the recursion use yield! instead of yield to add the result of the nested sequence expression.
• Make sure to be prepared when some madman passes an empty list in.

After that, the round robin code is rather self explanatory.

let round_robin lst =
    let rec inner_rr l =
        seq {
            match l with
            | [] -> 
                yield! inner_rr lst
            | h::t ->
                yield h
                yield! inner_rr t
            }
    if lst.IsEmpty then Seq.empty else inner_rr []


printf "%A" (Seq.toList (Seq.take 20 (round_robin [1;2;3;4;5;6;7])))