Latest update Dec 11, 2011
To prevent spambots from collecting mail addresses, all mail addresses on this page have the "@" replaced by "#".
let upchar c = match c with | 'a' -> 'A' | 'b' -> 'B' | 'c' -> 'C' | c -> c let rec upstring s = match s with | "" -> "" | s -> (upchar (s.[0])).ToString() + upstring (s.[1 .. String.Length s]) let upstring = String.map upchar
let squares n = let rec sqlocal i n = if i > n then [] else i*i :: squares (i+1) n in sqlocal 1 n let squares n = [ for i in 1 .. n -> i*i ]
let list_match pat l = match l with | [] -> [] | x::xs -> let rec test pat l = match (pat,l) with | ([],s) -> true | (p:pat,x:xs) when p = x -> test pat xs | _ -> false in test pat s :: list_match pat xs match : 'a list -> 'a list -> bool list let matchall pat = match pat >> List.fold (||) false
let rec foldBack1 f l = match l with | [] -> failwith "Applying foldBack1 to empty list" | [x] -> x | x::xs -> f x (foldBack1 f xs) let rec fold1 f l = match l with | [] -> failwith "Applying fold1 to empty list" | x::xs -> List.fold f x xs
// "Vanilla" recursive function for the sequence let rec f n = match n with | 1 -> 1 | n when n % 2 = 0 -> f (n/2) | _ -> f(3*n+1) // Version with accumulating argument, returning the number of calls. Call // with f2 1 n let rec f2 count n = match n with | 1 -> count | n when n % 2 = 0 -> f2 (count + 1) (n/2) | _ -> f2 (count + 1) (3*n+1) // Version with mutable ref cell let count = ref 1 let rec f3 n = match n with | 1 -> !count | n when n % 2 = 0 -> count := !count + 1; f3 (n/2) | _ -> count := !count + 1; f3 (3*n+1) // Computing the sequence as a list let rec f4 n = match n with | 1 -> [1] | n when n % 2 = 0 -> n :: f4 (n/2) | _ -> n :: f4 (3*n+1)
let sroot a eps = let rec new x = let newx = 0.5*(x + a/x) in if abs (x - newx) < eps then newx else new newx in new a
let newrap f f' a eps = let rec new x = let newx = x - f x/f' x in if abs (x - newx) < eps then newx else new newx in new a : float
let iter f test x = let rec new x = let xnew = f x in if test x xnew then xnew else new xnew in new x let newrap2 f f' a eps = iter (fun x -> x - f x/f' x) (fun x xnew -> abs (x - xnew) < eps) a : float
// A function "isprime" that tests, given a list l of previous primes, whether // i is prime or not let rec isprime i l = match l with | [] -> true | head :: tail -> if i % head = 0 then false else isprime i tail // The prime sieve function. The local function lsieve recursively builds the // list of discovered primes, and tests the next candidate against this list. let sieve n = let rec lsieve i l n = if i = n then l else if isprime i l then lsieve (i+1) (i::l) n else lsieve (i+1) l n in lsieve 3 [2] n
type Vec5 = V2 of float * float | V3 of float * float * float | V4 of float * float * float * float | V5 of float * float * float * float * float let vlen vec = match vec with | V2 (x,y) -> sqrt (x**2 + y**2) | V3 (x,y,z) -> sqrt (x**2 + y**2 + z**2) | V4 (x,y,z,u) -> sqrt (x**2 + y**2 + z**2 + u**2) | V5 (x,y,z,u,v) -> sqrt (x**2 + y**2 + z**2 + u**2 + v**2) let vadd v1 v2 = match (v1,v2) with | (V2 (x1,y1),V2 (x2,y2)) -> V2 (x1+x2,y1+ny2) | (V3 (x1,y1,z1),V3 (x2,y2,z2)) -> V3 (x1+x2,y1+y2,z1+z2) | (V4 (x1,y1,z1,u1),V4 (x2,y2,z2,u2)) -> V4 (x1+x2,y1+y2,z1+z2,u1+u2) | (V5 (x1,y1,z1,u1,v1),V5 (x2,y2,z2,u2,v2)) -> V5 (x1+x2,y1+y2,z1+z2,u1+u2,v1,v2) | _ -> failwith "Attempt to add vectors of different dimensionality"
// We represent internal nodes and leaves by the same kind of node. Leaves // contain the empty list. type VarTree<'a> = VNode of 'a * (VarTree<'a> list) let treeMap f (VNode (x,l)) = VNode (f x) (List.map (treeMap f) l) let fanout_sum (VNode (x,l)) = List.length l + List.sum (List.map fanout_sum l) let no_nodes (VNode (x,l)) = 1 + List.sum (List.map no_nodes l) let average_fanout t = float (fanout_sum t)/float (no_nodes t)
let f x y = x + y let g (x,y) = x + yConsider f first. We have identifiers f, x, y. First, choose one distinct type variable for each identifier:
f : 'a x : 'b y : 'cWe also have
(+) : 'n -> 'n -> 'n, 'n numerical typeFrom the LHS f x y, we obtain
'a = 'b -> 'c -> 'dsince f is a function applied to x and y, and thus the argument types of f must match with the types of x, y. Furthermore, the type of the LHS is 'd. From the RHS, we have
'b = 'n 'c = 'n 'd = 'nsince x and y are arguments to +, and the type of x + y must be the same as the type for f x y. There is no more information to guide the choice of 'n: thus, it defaults to int:
'n = intThis yields
'b = int 'c = int 'd = intand since f : 'b -> 'c -> 'd we obtain the answer
f : int -> int -> int
g : 'b * 'c -> 'd x : 'b y : 'cAs for f, we obtain
'b = int 'c = int 'd = intand the final result is
g : int * int -> int
let rec map f l = match l with | [] -> [] | head :: tail -> f head :: map f tailWe know beforehand:
[] : 'a list (first occurrence) [] : 'b list (second occurrence) (::) : 'c -> 'c list -> 'c list (first occurrence) (::) : 'd -> 'd list -> 'd list (second occurrence) 1 : int (+) : 'n -> 'n -> 'n, 'n numerical typeNote that we must use different type variables for the different occurrences of [] and (::), since they may assume different typings in different places. As usual, we assign one distinct type variable to each identifier in the function declaration:
map : 'e f : 'f l : 'g head : 'h tail : 'iLets, start with the LHS, We immediately obtain
map : 'f -> 'g -> 'j map f l : 'jNow consider the RHS (the match expression). Since l is matched with [] (first occurrence), we obtain
'g = 'a listFurthermore, well-typedness of head :: tail demands
'h = 'c 'i = 'c listSince l can match head :: tail, we also have
'c list = 'a listwhich implies
'c = 'aSumming up so far, we have the following typings (to be further refined):
map : 'f -> 'a list -> 'j f : 'f l : 'a list head : 'a tail : 'a listNow consider the results of the match expression, [] (second occurrence) and f head :: map f tail. From f head we obtain
'f = 'a -> 'k 'k = 'dFor map f tail, the types for f and tail already match the argument types of map. We have map f tail : 'j, which yields
'j = 'd listFinally, since the types of [] and f head :: map f tail must match the type of map f l, we have
'b list = 'd list 'd list = 'd listwhich is satisfied exactly when 'b = 'd. Now all expressions have been checked for correct typings, and we obtain the following typing for map:
map : ('a -> 'd) -> 'a list -> 'd listSince we were careful in each step not to introduce more constraints than necessary on the typings, this is a most general typing for map.
let rec take n l = match (n,l) with (_,[]) -> failwith "List too short" (0,_) -> [] (_,x::xs) -> x :: take (n-1) xsWe know beforehand:
[] : 'a list (first occurrence) [] : 'b list (second occurrence) (::) : 'c -> 'c list -> 'c list (first occurrence) (::) : 'd -> 'd list -> 'd list (second occurrence) failwith : string -> 'e "List too short" : string 0 : int (-) : 'n -> 'n -> 'n, 'n numerical type 1 : intWe assign unique type variables as typings for the different identifiers:
take : 'f n : 'g l : 'h x : 'i xs : 'jfrom LHS (take n l) we have
'f = 'g -> 'h -> 'k take n l : 'kFrom the RHS (match expression), we have, from the possible matchings of (n,l):
'g = int (since n can match 0) 'h = 'a list (since l can match first occurrence of []) 'h = 'c list (since l can match x::xs)The two latter equalities also imply
'c = 'aFrom well-typing of x::xs we obtain
'i = 'c 'j = 'c listSumming up, we now have
take : int -> 'a list -> 'k n : int l : 'a list x : 'a xs : 'a listNow consider the results of the match: failwith "List too short", [] (second occurrence), and x :: take (n-1) xs. They must be well-typed, and their types must all match 'k, the type of take n l. We have:
failwith "List too short" : 'e [] : 'b list (second occurrence) x :: take (n-1) xs : 'd listfrom which we obtain
'k = 'e = 'b list = 'd listWell-typing of x :: take (n-1) xs demands
'd = 'a (x first argument to ::) 'd list = 'd list (take (n-1) xs second argument to ::) 'n = int (n-1 first argument to take) 'a list = 'a list (xs second argument to take) 'n = int (n first argument to -) int = int (1 second argument to -)Summing up, we now have the typing
take : int -> 'a list -> 'a listSince we now have checked that all subexpressions are well-typed, this is a correct typing of take, and it is also its most general type (by a similar argument as for map).