Categories
Tech

F# Friday – Array.splitAt

Array.splitAt splits an array into two parts at the index you specify. The first part ends just before the element at the given index; the second part starts with the element at the given index. Some examples will help:

Some Examples

The most obvious use case is bisecting an array, i.e., splitting it into two (nearly) equal parts. To do that, half the length, and use it as your splitting index:

let xs = [|1;2;3;4;5;6|]
let mid = xs.Length / 2 // 3
let left, right = xs |> Array.splitAt mid
// val left : int [] = [|1; 2; 3|]
// val right : int [] = [|4; 5; 6|]

But what happens if your array contains an odd number of elements? No sweat! Because of the way integer division works, the quotient length ÷ 2 is truncated. In other words, the left array will always have one less element than the right array:

let xs = [|1;2;3;4;5|]
let mid = xs.Length / 2 // 2
let left, right = xs |> Array.splitAt mid
// val left : int [] = [|1; 2|]
// val right : int [] = [|3; 4; 5|]

Of course, you don’t have to cut the thing in half. You can split it anywhere:

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 1
// val left : int [] = [|1|]
// val right : int [] = [|2; 3; 4; 5|]

Or …

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 4
// val left : int [] = [|1; 2; 3; 4|]
// val right : int [] = [|5|]

What happens if you split at index 0?

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 0
// val left : int [] = [||]
// val right : int [] = [|1; 2; 3; 4; 5|]

Ah, the left array is empty! That’s because Array.splitAt starts the right array at the given index. There’s nothing before the given index, so the only thing left to return for left is an empty array.

The reverse happens if you split at the length: The right array is empty while the left array contains the entire input array:

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 5
// val left : int [] = [|1; 2; 3; 4; 5|]
// val right : int [] = [||]

But what happens if you try to split at an index greater than the length?

let xs = [|1;2;3;4;5|]
let left, right = xs |> Array.splitAt 6
// System.InvalidOperationException: The input sequence has an insufficient number of elements.
//    at Microsoft.FSharp.Collections.ArrayModule.SplitAt[T](Int32 index, T[] array)
//    at <StartupCode$FSI_0063>.$FSI_0063.main@()

Oops! Well, I guess you shouldn’t do that. So then, just be sure to split at an index that is no greater than the length of the array. You likewise get an exception if you attempt to split at a negative index value.

Merge Sort with Array.splitAt

You can use Array.splitAt in performing a merge sort. Array.splitAt is, admittedly, a pretty small piece of the puzzle. Merge sort is a divide-and-conquer algorithm, and Array.splitAt just performs the divide part. Nevertheless it comes in handy for that part.

Speaking of which, start by using Array.splitAt to define a bisect function that splits an array in half:

let bisect xs =
    let mid = (xs |> Array.length) / 2
    xs |> Array.splitAt mid

A merge sort breaks an array down into single-element (or empty) arrays and then puts them back together, sorting the elements of each block as it combines them. Start with the merge function that puts the blocks back together after you’ve broken them down:

let merge left right =
    let rec mergeWith l r acc =
        match l, r with
        // If either side is empty, just add
        // the non-empty side to the accumulator.
        | ([||], a) | (a, [||]) ->
            Array.append acc a

        // Compare the head elements, and add
        // the lesser head value to the
        // accumulator. Then call recursively.
        | _ ->
            let lh = l |> Array.head
            let rh = r |> Array.head
            let next, l', r' =
                if lh < rh
                then lh, l |> Array.tail, r
                else rh, l, r |> Array.tail
            Array.append acc [|next|]
            |> mergeWith l' r'
        
    [||] |> mergeWith left right

Now mergeSort can use bisect and merge to break down the array and then merge it back together:

let rec mergeSort =
    function
    | [||] -> [||]
    | [|x|] -> [|x|]
    | xs -> 
        let l, r = bisect xs
        merge (mergeSort l) (mergeSort r)
    
let xs = [|43; 48; 3; 23; 28; 6; 25; 43; 16|]
let sorted = mergeSort xs
// val sorted : int [] = 
//   [|3; 6; 16; 23; 25; 28; 43; 43; 48|]

A quick announcement: I’ve got some instructional material to develop. Unfortunately it’s going to take up a fair amount of my time. This is probably the last F# Friday post for a little while, but I hope to pick back up in a month or two.

Categories
Tech

F# Friday – Seq.groupBy

Sometimes you have a collection of items that you want to group according to some common property or key. Seq.groupBy can do that job for you. It takes that collection and returns a sequence of pairs. The first element of each pair is the grouping key; the second is the sequence of all the items that fall into that group.

That’s a little hard to follow. So what’s it useful for?

Well, maybe you need to group a list of names by initial. No sweat:

let names = 
    seq [ "Rehoboam"
          "Abijah"
          "Asa"
          "Jehoshaphat"
          "Jehoram"
          "Ahaziah" ]

let groupedByInitial =
    names
    |> Seq.groupBy (fun s -> s.[0])
// val groupedByInitial : seq<char * seq<string>> =
//   seq [ ('R', seq ["Rehoboam"])
//         ('A', seq ["Abijah"; "Asa"; "Ahaziah"])
//         ('J', seq ["Jehoshaphat"; "Jehoram"]) ]

And of course, if you want to sort those groups, throw in a call to Seq.sortBy to sort by the first element in the tuple:

let groupedByInitialAndSorted =
    names
    |> Seq.groupBy (fun s -> s.[0])
    |> Seq.sortBy fst
// val groupedByInitialAndSorted : seq<char * seq<string>> =
//   seq [ ('A', seq ["Abijah"; "Asa"; "Ahaziah"])
//         ('J', seq ["Jehoshaphat"; "Jehoram"])
//         ('R', seq ["Rehoboam"]) ]

Another example: Maybe you want to group some test scores according to grade. That is, all the students who scored in the 90s are grouped together, then all those scoring in the 80s, and so on:

type TestScore =
    { Name : string
      Score : int }

let grades = 
    seq [
        { Name = "Anna"; Score = 74 }
        { Name = "Andy"; Score = 76 }
        { Name = "Brenda"; Score = 70 }
        { Name = "Bobby"; Score = 90 }
        { Name = "Charlotte"; Score = 98 }
        { Name = "Chuck"; Score = 83 }
        { Name = "Deborah"; Score = 88 }
        { Name = "Dan"; Score = 66 }
        { Name = "Ellie"; Score = 80 }
        { Name = "Ed"; Score = 61 }
        { Name = "Frannie"; Score = 89 }
        { Name = "Frank"; Score = 96 }
    ]

let grouped = 
    grades
    |> Seq.groupBy (fun s -> s.Score / 10 * 10)
// val grouped : seq<int * seq<TestScore>> =
//   seq [
//     (70, seq [ {Name = "Anna"; Score = 74}
//                {Name = "Andy"; Score = 76}
//                {Name = "Brenda"; Score = 70} ] )
//     (90, seq [ {Name = "Bobby"; Score = 90}
//                {Name = "Charlotte"; Score = 98}
//                {Name = "Frank"; Score = 96} ] )
//     (80, seq [ {Name = "Chuck"; Score = 83}
//                {Name = "Deborah"; Score = 88}
//                {Name = "Ellie"; Score = 80}
//                {Name = "Frannie"; Score = 89} ] )
//     (60, seq [ {Name = "Dan"; Score = 66}
//                {Name = "Ed"; Score = 61} ] )
//   ]

You can take it another couple of steps to produce a histogram by counting the number of students in each group and sorting by the group key (i.e., grade level):

let histogram = 
    grouped
    |> Seq.map (fun pair -> 
                    let score = fst pair
                    let count = snd pair
                                |> Seq.length
                    score, count)
    |> Seq.sort
    |> Seq.rev
// val histogram : seq<int * int> =
//   seq [(90, 3); (80, 4); (70, 3); (60, 2)]

One more example, and this one has a little pitfall in it. I borrowed this one from one of Steven Proctor’s Ruby Tuesday posts. You can find anagrams in a list of words by sorting the characters in each word and grouping on that:

let anagrams =
    seq ["tar"; "rat"; "bar"; "rob"; "art"; "orb"]
    |> Seq.groupBy (fun word -> word |> Seq.sort)
// val anagrams : seq<seq<char> * seq<string>> =
//   seq [
//     (seq ['a'; 'r'; 't'], seq ["tar"])
//     (seq ['a'; 'r'; 't'], seq ["rat"])
//     (seq ['a'; 'b'; 'r'], seq ["bar"])
//     (seq ['b'; 'o'; 'r'], seq ["rob"])
//     (seq ['a'; 'r'; 't'], seq ["art"])
//     (seq ['b'; 'o'; 'r'], seq ["orb"])
//   ]

Well, that’s not what I expected. I expected “rat,” “tar,” and “art” to be grouped together, but they’re not. Thanks to the good folks on Stack Overflow, I know what the problem is now: seq is just an alias for a .NET IEnumerable. IEnumerables are not structurally equivalent. That is, two IEnumerable instances are not compared according to their contents. They are compared according to reference value. In other words, if two IEnumerables are not the very same instance, they are not equal.

In order to get Mr. Proctor’s example to work in F#, you have to add one more step to convert the grouping key, currently a seq, to something that is a type that supports structural equivalence, such as an array:

let anagrams =
    seq ["tar"; "rat"; "bar"; "rob"; "art"; "orb"]
    |> Seq.groupBy (fun word -> word 
                                |> Seq.sort 
                                |> Seq.toArray)
// val anagrams : seq<char [] * seq<string>> =
//   seq [
//       ([|'a'; 'r'; 't'|], seq ["tar"; "rat"; "art"])
//       ([|'a'; 'b'; 'r'|], seq ["bar"])
//       ([|'b'; 'o'; 'r'|], seq ["rob"; "orb"])
//   ]

Now, that’s better.

Categories
Tech

F# Friday – Code That Looks Like Math

Something that F# and most other modern languages allow these days is variable names that contain what you might think of as non-traditional characters from the Unicode character set, e.g., Greek symbols such as π and τ. If you’re a C programmer, you have to settle for spelling out the name of the character:

const double PI = 3.141592654;
double delta = x1 - x2;

But that’s OK, right? What’s the difference, really? The value π is one thing: it’s a universally recognized constant. But even with the example delta above, don’t you want to name it something more descriptive, like marginOfError anyway?

Well, yes, many times instead of using the characters verbatim from your physics textbook …

let f = m * a

… you spell it out so that the code is clearer:

let force = mass * acceleration

Likewise, even though F# allows you to write the following:

let ω = 2.0 * Math.PI * f

… it’s probably better practice to write …

let angularVelocity = 2.0 * Math.PI * frequency

What’s the point of this post then? Sure, you can use “special” characters in variable names, but so far, I’ve discouraged you from doing it!

Nevertheless there are times when it is appropriate. If you are coding up an algorithm that consists of a series of well-known equations in a certain field of study, and the more your code looks like those equations, the easier it is to check it against the literature.

Consider the following—a series of values and equations for converting latitude and longitude to universal polar stereographic (UPS) coordinates, a way of representing coordinates at the earth’s poles:

Values and equations for converting geodetic coordinates (latitude and longitude) into universal polar stereographic (UPS) coordinates
Converting Latitude and Longitude to Universal Polar Stereographic (UPS) Coordinates

UPS coordinates consist of a hemisphere—either northern or southern—and two distance components, easting and northing, both in meters:

type Hemisphere = Northern | Southern
type UpdCoord =
    { Hemisphere : Hemisphere
      Easting : float
      Northing : float }

Now compare the code below to the equations from the literature above:

let latLonToUps (lat : float) (lon : float) =
    let hemisphere =
        if lat < 0.0
        then Southern
        else Northern

    let Ï• = abs lat
    let λ = lon

    let π = Math.PI

    let FN = 2000000.0
    let FE = 2000000.0

    let a = 6378137.0
    let f = 1.0 / 298.257223563

    let e_2 = f * (2.0 - f)
    let e = sqrt e_2
    let eOver2 = e / 2.0
    let Câ‚’ = ((2.0 * a) / sqrt (1.0 - e_2)) *
             (((1.0 - e) / (1.0 + e)) ** eOver2)
    let kâ‚’ = 0.994
    let πOver4 = π / 4.0
    
    let esinϕ = e * (sin ϕ)
    let Ï•Over2 = Ï• / 2.0

    let tanZOver2 = 
        (((1.0 + esinϕ) / (1.0 - esinϕ)) ** eOver2) *
        tan (Ï€Over4 - Ï•Over2)
    let R = kâ‚’ * Câ‚’ * tanZOver2
    let Rcosλ = R * (cos λ)
    let Rsinλ = R * (sin λ)

    let N = match hemisphere with
            | Northern -> FN - Rcosλ
            | Southern -> FN + Rcosλ
    let E = FE + Rsinλ

    { Hemisphere = hemisphere
      Easting = E
      Northing = N }

It’s not perfect: you still cannot set numerators above denominators, for instance. But isn’t that easier to compare to the literature than if we had to write out RsinLambda or eSinPhi?

(Note: UPS coordinates are only valid for latitudes near the poles. For simplicity, the code above does not check to make sure that the input latitude falls within those bounds. I mean, it’s complex enough as it is for the sake of exemplifying the point of this post.)

(Note: I’m aware that some of the characters in the code don’t show up correctly on all browsers, e.g., the subscript “O” and perhaps the φ. I’m working to correct that. Nevertheless you should be able to use such symbols in your source code.)

One final example of something that F# allows you to do that no other language to my knowledge allows: using single-quote marks in variable names. Why would you ever want to do such a thing? One example is derivatives. In calculus, a prime (′) indicates a first derivative, and a double prime (″) indicates the second derivative. The following is how you could represent kinematics calculations:

let x = x0 + (v * t) + (0.5 * a * (t ** 2.0))
let x' = v + (a * t)
let x'' = a

Another case I’ve seen is when you have a value or function that is closely associated with another value/function in some obvious way. If they are in close proximity to each other, it doesn’t make sense to come up with wholly different names. Consider this factorial function:

let factorial n =
    let rec factorial' n acc =
        if n <= 0 
        then acc
        else factorial' (n - 1) (n * acc)
    
    factorial' n 1

The inner function does the work. The outer function is just an interface to the inner function. All the factorial does is to make the initial call factorial' with a little bit of setup. The factorial function is a nice interface for the user of the function; the factorial' name indicates to developers that it is doing the heavy lifting.

Categories
Tech

F# Friday – Array.last and Array.tryLast

Last week, we looked at List.tryHead. If you don’t need the first item in a list, but rather the last item, the counterpart of List.head is List.last. Likewise, the counterpart of List.tryHead is List.tryLast.

Recall the code example from last week:

type Salesman = { Name : string
                  Sales : decimal }
 
let findTopSalesman salesmen =
    salesmen
    |> List.filter (fun s -> s.Sales >= 10000M)
    |> List.sortBy (fun s -> -s.Sales) // descending
    |> List.tryHead

let sales =
    [
        { Name = "Joe Bob"; Sales = 9500M }
        { Name = "Sally Jane"; Sales = 18500M }
        { Name = "Betty Lou"; Sales = 11800M }
        { Name = "Sammy Joe"; Sales = 6500M }
    ]
 
let top = findTopSalesman sales
// val top : Salesman option = 
//   Some {Name = "Sally Jane";
//         Sales = 18500M;}

The List.sortBy call (highlighted above) sorts the sales records in a descending fashion so that the first record would be the top salesman. What if it makes more sense to you to sort the records in an ascending fashion and take the last record? With List.tryLast, you can:

type Salesman = { Name : string
                  Sales : decimal }
 
let findTopSalesman salesmen =
    salesmen
    |> List.filter (fun s -> s.Sales >= 10000M)
    |> List.sortBy (fun s -> s.Sales) // ascending
    |> List.tryLast

let sales =
    [
        { Name = "Joe Bob"; Sales = 9500M }
        { Name = "Sally Jane"; Sales = 18500M }
        { Name = "Betty Lou"; Sales = 11800M }
        { Name = "Sammy Joe"; Sales = 6500M }
    ]
 
let top = findTopSalesman sales
// val top : Salesman option = 
//   Some {Name = "Sally Jane";
//         Sales = 18500M;}

This is a trivial example: I mean, you can sort the records however you wish; they’re your records! But what if you receive the recordset from elsewhere—an API that is outside your control, for instance—and it is already sorted in an ascending fashion. It is probably better to accept the recordset as is and just take the last item rather than to sort it again. Which brings me to another couple of other points …

This post claims to be about Array.last and Array.tryLast. Why all the talk about List.tryLast?

First, one of the things the F# team did in F# 4.0 was to normalize the sequential collections modules. Now just about any function available in one sequential collection module is available in them all. That is, if there’s a List.last, for example, then there’s also a Seq.last and an Array.last.

Second, I want to point out a potential pitfall of using last and tryLast. Both the size and type of the collection can affect the performance of your program or even crash it.

Arrays give you O(1) access to their elements. (In case you’re not familiar with it, that’s called “Big O notation.” It’s a way of expressing how long an algorithm takes to execute.) That is, arrays give you nearly instant access to any element—first, last, somewhere in the middle—doesn’t matter.

Lists and sequences, on the other hand, give you O(n) access to their elements. That is, the more items in the list/sequence, the longer it takes to get to the one you want because the machine always has to start at the first element and iterate through every single one until it gets to the one you want. No big deal if there are only 100 elements, but if there are 10,000,000 elements, fetching the last element will take a while.

Furthermore, sequences can be infinite. If you call Seq.last or Seq.tryLast on an infinite sequence, your program will crash:

let init n = n + 1
// This sequence starts at one and just keeps going
let ns = Seq.initInfinite init
let notGood = ns |> Seq.last
// Unhandled Exception: System.InvalidOperationException: 
//   Enumeration based on System.Int32 exceeded 
//   System.Int32.MaxValue.

You don’t have to eschew last and tryLast. Just take into account what kind of collection you’re calling them on. Array.last and Array.tryLast are perfectly safe. (Well, do remember that Array.last throws an exception if the array is empty, but with regard to performance, they’re fine.) But before you call last or tryLast on a list or a sequence, make sure you know how big it is, or you could, as they say, shoot yourself in the foot.

Categories
Tech

F# Friday – List.tryHead

Sometimes you need to get the first element of a list. No problem: List.head to the rescue, right? But what happens when you call List.head on an empty list?

let xs : int list = []
let h = xs |> List.head
// System.ArgumentException: The input list was empty.

Well that’s not good. You could get around that little wart with this:

let xs : int list = []
let h = if xs |> List.isEmpty 
        then -1
        else xs |> List.head
// val h : int = -1

That’s not great. Alternatively, there’s this:

let xs : int list = []
let h = match xs with
        | h :: _ -> h
        | [] -> -1
// val h : int = -1

Yeah, I’m not wild about those options either.

Speaking of options, what if you had a method that returns a None if you ask for the head of an empty list? If the list is not empty, it could return a Some containing the value of the head element. Another new method in F# 4.0 is List.tryHead, and it does just that.

let empty : int list = []
let nonempty = [9..17]

let nuthin = empty |> List.tryHead
// val nuthin : int option = None

let sumthin = nonempty |> List.tryHead
// val sumthin : int option = Some 9

Now you can use defaultArg on the result of a call to List.tryHead in order to return a default value in the event of an empty list:

let empty : int list = []
let nonempty = [9..17]

let head = defaultArg (List.tryHead nonempty) -1
// val head : int = 9

let fallback = defaultArg (List.tryHead empty) -1
// val fallback : int = -1

Now when might you actually use something like this? Perhaps you want to determine the top salesman each day, but only if the salesman has reached a certain threshold, say, $10,000. You can filter out the salesmen who don’t reach the threshold, sort the list of salesmen according to end-of-day sales totals, and then try to take the head element. If no one makes the cut, then the filter operation returns an empty list, which ultimately yields a None.

type Salesman = { Name : string
                  Sales : decimal }

let findTopSalesman salesmen =
    salesmen
    |> List.filter (fun s -> s.Sales >= 10000M)
    |> List.sortBy (fun s -> -s.Sales) // descending
    |> List.tryHead

So then, if Monday’s sales are as follows, then no one gets the prize because no one has broken $10,000:

let monday = 
    [
        { Name = "Joe Bob"; Sales = 9500M }
        { Name = "Sally Jane"; Sales = 8500M }
        { Name = "Betty Lou"; Sales = 9800M }
        { Name = "Sammy Joe"; Sales = 6500M }
    ]

let mondayTop = findTopSalesman monday
// val mondayTop : Salesman option = None

On Tuesday, though, there are two contenders. Alas, there can be only one winner, and Sally Jane (who, ironically, is from British Columbia) takes the prize:

let tuesday =
    [
        { Name = "Joe Bob"; Sales = 9500M }
        { Name = "Sally Jane"; Sales = 18500M }
        { Name = "Betty Lou"; Sales = 11800M }
        { Name = "Sammy Joe"; Sales = 6500M }
    ]

let tuesdayTop = findTopSalesman tuesday
// val tuesdayTop : Salesman option = 
//   Some {Name = "Sally Jane"; Sales = 18500M;}
Categories
Tech

F# Friday – Seq.choose

Filtering over a sequence of values omits values that do not meet certain criteria. Mapping over a sequence of values transforms each value into another value. What if you could do both at the same time—filter out unwanted values, but transform the ones that are left? You can with Seq.choose.

Whereas Seq.filter takes a predicate—a function that takes a value and returns a Boolean—Seq.choose takes a function that takes a value and returns an Option. If that Option is None, then Seq.choose discards it. If it is Some, then Seq.choose extracts the value from the Some and returns it as the next element in the output sequence.

let f = fun n -> match n % 2 with
                 | 0 -> Some (n * n)
                 | _ -> None
let squaredEvens = seq [4..7]
                   |> Seq.choose f
// val squaredEvens : seq<int> = seq [16; 36]

The following graphic illustrates what is going on:

Seq.choose takes a function that may perform a transform on its input that returns an option: Either a Some containing the transformed value or otherwise a None. The resulting sequence only retains the Some values; Seq.choose filters out the None values.
Choosing Items from a Sequence

OK, so Seq.choose performs a filter and a map all in one. Why not just call Seq.filter and then Seq.map? One example I’ve seen is when you’re pattern matching and destructuring and then only using one/some of the potential match cases. Perhaps you have a discriminated union representing orders that were either fulfilled or cancelled before fulfillment:

type Order =
| Fulfilled of id : string * total : decimal
| Cancelled of id : string * total : decimal

You’d like to know how many dollars you “lost” in cancelled orders. Use Seq.choose to extract the dollar value of each cancelled order, and then sum them:

let orders = [
    Fulfilled ("fef3356074b4", 28.50m)
    Fulfilled ("2605c9988f1d", 88.25m)
    Cancelled ("94edac47971f", 22.01m)
    Fulfilled ("2a1ff57b8f46", 39.30m)
    Fulfilled ("9ee0a3e3da3a", 27.97m)
    Cancelled ("db5dc439ad93", 99.49m)
    Fulfilled ("08d58811ed36", 53.72m)
    Cancelled ("63ebd07475ca", 93.66m)
    Cancelled ("12d16ae9c112",  7.79m)
    Fulfilled ("c5ecedaedb0e", 87.21m)
]

let cancelledDollars = 
    orders 
    |> Seq.choose (function
                   | Cancelled (_, dollars) -> 
                        Some dollars 
                   | _ -> None)
    |> Seq.sum
// val cancelledDollars : decimal = 222.95M
Categories
Tech

F# Friday – The Seq.chunkBySize Function

Another module function new with F# 4.0 is Seq.chunkBySize (so new, in fact, that there is not even a hint of it on MSDN as of this writing, and hence the Github link). Seq.chunkBySize groups a sequence’s elements into arrays (chunks) of a given size.

To take an example, if you have a sequence of twelve elements and call Seq.chunkBySize to turn it into groups of three, you’ll get a sequence of four arrays, each three elements in size:

let xs = seq [1..12]
let chunked = xs |> Seq.chunkBySize 3
// val chunked : seq<int []> =
//   seq [[|1; 2; 3|]; [|4; 5; 6|]; 
//        [|7; 8; 9|]; [|10; 11; 12|]]

What happens if you use a chunk size that does not divide evenly into the size of your input sequence? No sweat! The last array just contains any remaining elements, however many they may be:

let xs = seq [1..10]
let chunked = xs |> Seq.chunkBySize 3
// val chunked : seq<int []> =
//   seq [[|1; 2; 3|]; [|4; 5; 6|]; 
//        [|7; 8; 9|]; [|10|]]

Where is this useful? Well, you can take my paging example from my F# Friday post on Seq.skip and make it slightly clearer without the (page - 1) * perPage arithmetic:

type Book = 
    { Title : string
      Author : string }

let books = 
    seq [
        { Title = "Wuthering Heights"
          Author = "Emily Bronte" }
        { Title = "Jane Eyre"
          Author = "Charlotte Bronte" }
        { Title = "Agnes Grey"
          Author = "Anne Bronte" }
        { Title = "The Scarlet Letter"
          Author = "Nathaniel Hawthorne" }
        { Title = "Silas Marner"
          Author = "George Eliot" }
        { Title = "1984"
          Author = "George Orwell" }
        { Title = "Billy Budd"
          Author = "Herman Melville" }
        { Title = "Moby Dick"
          Author = "Herman Melville" }
        { Title = "The Great Gatsby"
          Author = "F. Scott Fitzgerald" }
        { Title = "Tom Sawyer"
          Author = "Mark Twain" }
    ]

let perPage = 3
let page = 3
let records = 
    books
    |> Seq.chunkBySize perPage
    |> Seq.skip (page - 1)
    |> Seq.head

// val records : Book [] =
//   [|{Title = "Billy Budd";
//      Author = "Herman Melville";}; 
//     {Title = "Moby Dick";
//      Author = "Herman Melville";};
//     {Title = "The Great Gatsby";
//      Author = "F. Scott Fitzgerald";}|]

This time, instead of having to calculate the number of elements to skip in order to skip n pages, you first use Seq.chunkBySize to turn the sequence into a paged recordset; each “page” is n records long. Then skip page - 1 pages in order to get to the page of records you want. Finally, calling Seq.head is necessary because, remember, Seq.chunkBySize turns a flat sequence into a sequence of arrays.

One final note: the Array and List modules also contain a chunkBySize function in F# 4.0.

Categories
Tech

F# Friday – The Seq.distinct Function

Today’s F# Friday is a simple one: Seq.distinct. Seq.distinct removes any duplicate members of a sequence, leaving only unique values.

One way to remove duplicates is to turn your sequence into a set with Set.ofSeq:

let noDupes = seq [3;5;6;3;3;7;1;1;7;3;2;7]
              |> Set.ofSeq
// val noDupes : Set<int> = 
//   set [1; 2; 3; 5; 6; 7]

That’s fine if you don’t care about preserving the order of the items in the input sequence.

But if you do want to preserve the order, Seq.distinct is the ticket:

let noDupesOrdered =
    seq [3;5;6;3;3;7;1;1;7;3;2;7]
    |> Seq.distinct
// val noDupesOrdered : seq<int> = 
//   seq [3; 5; 6; 7; 1; 2]
Categories
Tech

F# Friday – The Seq.skipWhile Function

Just as the analog to Seq.take is Seq.skip, the analog to Seq.takeWhile is Seq.skipWhile. That is, when you don’t care so much about skipping a certain number of items, but rather a certain kind of items.

Seq.skipWhile starts at the beginning of the sequence and applies a predicate to each item, one by one. It does not start returning items in a new sequence until it reaches an item that does not meet the predicate. Then it stops checking elements against the predicate and returns every item in the sequence from that point on:

Seq.skipWhile skips items at the beginning of a sequence until it reaches an item that does not meet the given predicate.
Skipping Items in a Sequence While a Predicate Holds

Assume you have the same temperature sensor as the one in my post on Seq.takeWhile. This time, instead of once per minute, assume that it feeds you temperature readings once per second. Add to that the idea that the sensor has a few seconds of boot-up time in which it sends you -1000.0—the indication that the current reading is invalid—until it has fully booted and can start sending good temperature data.

type Reading = {
    Temperature : float
    Timestamp : DateTime
}

let readings = 
    seq [
        { Temperature = -1000.0
          Timestamp = DateTime(2015, 07, 19, 10, 0, 0) }
        { Temperature = -1000.0
          Timestamp = DateTime(2015, 07, 19, 10, 0, 1) }
        { Temperature = -1000.0
          Timestamp = DateTime(2015, 07, 19, 10, 0, 2) }
        { Temperature = -1000.0
          Timestamp = DateTime(2015, 07, 19, 10, 0, 3) }
        { Temperature = -1000.0
          Timestamp = DateTime(2015, 07, 19, 10, 0, 4) }
        { Temperature = -1000.0
          Timestamp = DateTime(2015, 07, 19, 10, 0, 5) }
        { Temperature = 90.1
          Timestamp = DateTime(2015, 07, 19, 10, 0, 6) }
        { Temperature = 90.2
          Timestamp = DateTime(2015, 07, 19, 10, 0, 7) }
        { Temperature = 90.2
          Timestamp = DateTime(2015, 07, 19, 10, 0, 8) }
        { Temperature = 90.1
          Timestamp = DateTime(2015, 07, 19, 10, 0, 9) }
        { Temperature = 90.3
          Timestamp = DateTime(2015, 07, 19, 10, 0, 10) }
    ]

To skip all readings until the thermometer starts returning valid data, use Seq.skipWhile:

let valid = 
    readings
    |> Seq.skipWhile (fun r -> r.Temperature = -1000.0)

// val valid: seq<Reading> =
//  [{Temperature = 90.1;
//    Timestamp = 7/19/2015 10:00:06 AM};
//   {Temperature = 90.2;
//    Timestamp = 7/19/2015 10:00:07 AM};
//   {Temperature = 90.2;
//    Timestamp = 7/19/2015 10:00:08 AM};
//   {Temperature = 90.1;
//    Timestamp = 7/19/2015 10:00:09 AM};
//   {Temperature = 90.3;
//    Timestamp = 7/19/2015 10:00:10 AM}]

Finally, even though Seq.skip throws an exception if you ask it to skip more elements than the sequence contains, Seq.skipWhile does not balk if it never reaches an element that fails to meet the predicate. You just get an empty sequence:

let none = seq [1;3;4;7]
           |> Seq.skipWhile (fun n -> n < 10)
// val none : seq<int> = seq []

As of F# 4.0, there are versions of skipWhile in the Array and List modules, but as of this writing, the documentation at MSDN does not yet include them.

Categories
Tech

F# Friday – The Seq.skip Function

The opposite of Seq.take is Seq.skip. Seq.skip, as the name suggests, skips the first n items of the sequence and returns a new sequence that starts with element n + 1:

let xs = seq [1..10]
let skipped5 = xs |> Seq.skip 5
// val skipped5 : seq<int> =
//   [6; 7; 8; 9; 10]

One of most obvious applications of Seq.skip is to pair it with Seq.take or Seq.truncate to page through a set of records. Perhaps you have a list of books:

type Book = 
    { Title : string
      Author : string }

let books = 
    seq [
        { Title = "Wuthering Heights"
          Author = "Emily Bronte" }
        { Title = "Jane Eyre"
          Author = "Charlotte Bronte" }
        { Title = "Agnes Grey"
          Author = "Anne Bronte" }
        { Title = "The Scarlet Letter"
          Author = "Nathaniel Hawthorne" }
        { Title = "Silas Marner"
          Author = "George Eliot" }
        { Title = "1984"
          Author = "George Orwell" }
        { Title = "Billy Budd"
          Author = "Herman Melville" }
        { Title = "Moby Dick"
          Author = "Herman Melville" }
        { Title = "The Great Gatsby"
          Author = "F. Scott Fitzgerald" }
        { Title = "Tom Sawyer"
          Author = "Mark Twain" }
    ]

If each page shows three books, and the user wants to see the records on page three, skip the first two pages’ worth of records, and take the next three records:

let perPage = 3
let page = 3
let records = 
    books
    |> Seq.skip ((page - 1) * perPage)
    |> Seq.take perPage

// val records : seq<Book> =
//   [{Title = "Billy Budd";
//     Author = "Herman Melville";};
//    {Title = "Moby Dick";
//     Author = "Herman Melville";};
//    {Title = "The Great Gatsby";
//     Author = "F. Scott Fitzgerald";}]

Unfortunately, like Seq.take, if you ask the sequence for more elements than it contains, it throws an exception:

let oops = seq [1..5]
           |> Seq.skip 6 
           |> printfn "%A"
// System.InvalidOperationException: 
//   The input sequence has an insufficient
//   number of elements.