Walking the F# List namespace - Post #3

This will probably be my last series on examining the source behind the List namespace. Only because I was running out of interesting functions that have interesting implementations, or functions that I feel I could adequately explain. And frankly, writing that List.filter actually imlements List.filter from another namespace is not too interesting. So, I took a look inside list.fs to find some interesting implementations and found a few more functions to walk through. List.assoc: List.assoc is roughly equivalent to a hashtable or dictionary lookup in c#, except the list is a list of tuples. (Also, I’m not sure if there are any index optimizations either.) Throws a not_found() exception if the key is not found. The signature for List.assoc is ‘a -> (‘a * ‘b) list -> ‘b

‘a – the key value to find
(‘a * ‘b) list – the source tuple list
‘b – the value for the key.

Here’s an example, using FSI:

> let list = [for x in 1 to 50000 -> (x,x*x)];;
val list : (int * int) list
>let findSquare s = List.assoc s list;;
val findSquare : int -> int
> findSquare 14513;;
val it : int = 210627169

If we look at the source code, List.assoc is implemented as:

let rec assoc x l =
match l with
|[] -> not_found()
|((h,r)::t) -> if x = h then r else assoc x t

The interesting code block with this function is the ((h,r)::t) syntax. The syntax of (h,r) is breaking up the tuple in the first element on the list, with h getting the key and r getting the value. If the key matches the passed in value, then return r. Also, if the list is empty ([]), then raise the not_found() exception. (I didn’t go into any detail about the rec or match, I describe them in further detail in my previous posts.) The documentation for List.assoc suggests we use List.try_assoc. So, lets try. List.try_assoc: essentially the same as List.assoc, with two main differences. First, try_assoc, will not throw a not_found() exception if the key is not found. Second, try_assoc returns an option type. When using F# code from other .Net languages, the empty option type (None) is equalivant to the null value. To create a value of the option type, you need to use Some or None. The signature for List.try_assoc is: ‘a -> (‘a * ‘b) list -> ‘b option

‘a – the first tuple element to find
(‘a * ‘b) list – the soure list
‘b option – the returned value

Here’s an example, from FSI.

> let list = [for x in 1 to 50000 -> (x,x*x)];;
val list : (int * int) list
> findSquare 50001;;
val it : int option = None
>findSquare 23;;
val it : int option = Some 529

If we look at the source code, List.try_assoc is implemented as

let rec try_assoc x l =
match l with
|[] -> None
|((h,r)::t) -> if x = h then Some(r) else try_assoc x t

Wow, this looks surprisingly similar to List.assoc, with the exception of the return types of None and Some(r). List.assq: List.assq is almost like List.assoc, except is used the PhysicalEquality operator. PhysicalEquality is defined in as “Reference/physical equality. True if boxed versions of the inputs are reference-equal, OR if both are value types and the implementation of Object.Equals for the type of the first argument returns true on the boxed versions of the inputs.” as defined in: http://research.microsoft.com/fsharp/manual/FSharp.Core/Microsoft.FSharp.Core.LanguagePrimitives.html So, generally speaking, List.assq does reference equality on values on the stack, whereas value equality compares values on the heap. I posted a question on an implementation of PhysicalEquality here (Kudos to zakaluka!) Anyway here’s how List.assq is implemented:

let rec assq x l =
match l with
|[] -> not_found()
|((h,r)::t) -> if PhysicalEquality x h then r else assq x t

List.try_assq is exactly the same as List.try_assoc, except the return type is an option type. Here’s the implementation:

let rec try_assq x l =
match l with
|[] -> None
|((h,r)::t) -> if PhysicalEquality x h then Some(r) else try_assq x t

List.for_all: Returns true if all the elements in the list satisfy the given predicate, false if one fails. The list elements are anded together, visualized as p iO && p i1 && .. p iN. The signature for list.for_all is (‘a -> bool) -> ‘a list -> bool

(‘a -> bool) – A function that evaluates the list element and returns a bool
‘a list -> the list to process
Bool -> return value

Here’s an example:

[<Test>]
member t.For_allExample () =
let list1 = [0 .. +2 .. 20]
let list2 = [1 .. 10]
let evens = List.for_all (fun x -> x % 2 = 0) list1
let notevens = List.for_all (fun x -> x % 2 = 0) list2
Assert.IsTrue(evens)
Assert.IsFalse(notevens)

List.for_all implements

let rec for_all f l1 = Microsoft.FSharp.Primitives.Basics.List.for_all f l1

Hmm, not so much fun to describe.....so on we go. List.for_all2: Returns true if all the elements in two lists satisfy the given predicate, false if one fails. The lists must have the same length. The signature for list.for_all2 signature is (‘a -> ‘b -> bool) -> ‘a list -> ‘b list -> bool.

(‘a -> ‘b -> bool) – A function that takes an element from the first list and the second list and returns a bool
‘a list – the first list
‘b list – the second list
Bool -> the return value

Here’s an example:

[<Test>]
member t.For_all2Example () =
let list1 = [0 .. +2 .. 20]
let list2 = [20 .. +2 .. 40]
let list3 = [1 .. 10]
let evens = List.for_all2 (fun x y -> x % 2 = 0 && y % 2 = 0 ) list1 list2
let notevens = List.for_all2 (fun x y -> x % 2 = 0 && y % 2 = 0) list2 list3
Assert.IsTrue(evens)
Assert.IsFalse(notevens)

List.for_all2 implements:

let rec for_all2 f l1 l2 =
match l1,l2 with
|[],[] -> true
|(h1::t1),(h2::t2) -> f h1 h2 && for_all2 f t1 t2
|_ -> invalid_arg "for_all2"

This recursive function is interesting, in particular the line (h1::t1),(h2::t2) -> f h1 h2 && for_all2 f t1 t2. The function aggregates the results of the function and the list elements!