Sequence comprehensions

Before digging deeper into advanced language-oriented features of F#, I'll need to do a small digression and talk about sequence comprehensions. This is a language construct that allows us to generate sequences, lists and arrays of data in F# and as we will see later it can be generalized to allow solving several related problems. Anyway, let's first look at an example that filters an F# list:


> let people = [ ("Joe", 55); ("John", 32); ("Jane", 24); ("Jimmy", 42) ];;
val people : (string * int) list
> [ for (name, age) in people
when age <>
-> name ];;
val it : string list = ["Jane"]

In this example we first declared a list with some data and then used a sequence expression, wrapped between square brackets [ and ], to select only some elements from the list. The use of square brackets indicate that the result should be an F# list (you can also use [| .. |] to get an array or seq { .. } to get a sequence as I'll show later). The code inside the comprehension can contain most of the ordinary F# expressions, but in this example I used one extension, the when .. -> construct, which can be used for typical filtering and projection operations. The same code can be written like this:


> [ for (name, age) in people do
if (age <>
yield name ];;
val it : string list = ["Jane"]

In this example, we used an ordinary for .. do loop (in the previous example the do keyword was missing and we used if .. then condition instead of when. Finally, returning a value from a sequence comprehension can be done using the yield construct. The point of this example is to demonstrate that the code inside the comprehension is not limited to some specific set of expressions and can, in fact, contain very complex F# code. I will demonstrate the flexibility of sequence comprehensions in one more example - the code will generate all possible words (of specified length) that can be generated using the given alphabet:


> let rec generateWords letters start len =
seq { for l in letters do
let word = (start ^ l)
if len = 1 then
yield word
if len > 1 then
yield! generateWords letters word (len-1) }
val generateWords : #seq -> string -> int -> seq
> generateWords ["a"; "b"; "c"] "" 4;;
val it : seq = seq ["aaaa"; "aaab"; "aaac"; "aaba"; ...]

This example introduces two interesting constructs. First of all, we're using seq { .. } expression to build the sequence, which is a lazy data structure, meaning that the code will be evaluated on demand. When you ask for the next element, it will continue evaluating until it reaches yield construct, which returns a word and then it will block again (until you ask for the next element). The second interesting fact is that the code is recursive - the generateWord function calls itself using yield! construct, which first computes the elements from the given sequence and then continues with evaluation of the remaining elements in the current comprehension.

Continue