**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

Here’s an example, using FSI:‘a – the key value to find (‘a * ‘b) list – the source tuple list ‘b – the value for the key.

If we look at the source code, List.assoc is implemented as:> 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

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

**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

Here’s an example, from FSI.‘a – the first tuple element to find (‘a * ‘b) list – the soure list ‘b option – the returned value

If we look at the source code, List.try_assoc is implemented as> 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

Wow, this looks surprisingly similar to List.assoc, with the exception of the return types of None and Some(r).let rec try_assoc x l = match l with |[] -> None |((h,r)::t) -> if x = h then Some(r) else try_assoc x t

**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:

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 assq x l = match l with |[] -> not_found() |((h,r)::t) -> if PhysicalEquality x h then r else assq x t

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

Here’s an example:(‘a -> bool) – A function that evaluates the list element and returns a bool ‘a list -> the list to process Bool -> return value

List.for_all implements[<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)

Hmm, not so much fun to describe.....so on we go.let rec for_all f l1 = Microsoft.FSharp.Primitives.Basics.List.for_all f l1

**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.

Here’s an example:(‘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

List.for_all2 implements:[<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)

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!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"

## No comments:

Post a Comment