The function

`product`

once again runs into troubles with the value restriction. If one of the parameters is an empty list, the F# system won't recognize the result as a simple data value, so it will complain. The only way around it is to use type annotations, as noted in the comments after both versions of the function.

let rec duple n x =

if n = 0 then [] else x :: (duple (n - 1) x)

// invert would probably accept a list of real pairs in F#

let invert lp =

let invpair p =

match p with

[] -> []

| (a :: b :: []) -> [b; a]

| _ -> failwith "invalid list" in

List.map invpair lp

let rec filter_in p lst =

match lst with

[] -> []

| (x :: rl) when p x -> x :: (filter_in p rl)

| (_ :: rl) -> filter_in p rl

let rec every p lst =

match lst with

[] -> true

| (x :: rl) when p x -> every p rl

| _ -> false

let every2 p lst =

List.fold_left (fun b x -> b && p x) true lst

let rec exists p lst =

match lst with

[] -> false

| (x :: rl) when p x -> true

| (_ :: rl) -> exists p rl

// It's not possible to return numbers and booleans, so we could

// use an algebraic data type, or int option, which seems better

let vector_index p (v:'a array) =

let rec search i =

if i = v.Length then None

elif p v.(i) then Some i

else search (i + 1) in

search 0

// the test given can't be easily expressed in F#

// also: fragile for negative n

let rec list_set lst n x =

match (lst, n) with

([], _) -> []

| (elt :: rl, 0) -> x :: rl

| (elt :: rl, i) -> elt :: (list_set rl (n - 1) x)

// value restriction troubles: any empty list gives an error

let rec product l1 l2 =

match (l1, l2) with

(_, []) -> []

| ([], _) -> []

| (x :: rl1, _) -> (List.map (fun e -> (x, e)) l2) @ (product rl1 l2)

// value restriction troubles: any empty list gives an error

let product2 l1 l2 =

List.concat (List.map (fun x -> List.map (fun e -> (x, e)) l2) l1)

(*

To call product with an empty list as argument, you must annotate its type:

> product [1; 2; 3] ([] : int list);;

val it : (int * int) list = []

*)

// once again, this function makes less sense in F# than in Scheme

let down lst =

List.map (fun x -> [x]) lst

// explicitly recursive version:

let rec down2 lst =

match lst with [] -> [] | (x::rl) -> [x] :: (down2 rl)

// scheme version

(*

(define down

(lambda (lst)

(if (null? lst)

'()

(cons (list (car lst))

(down (cdr lst))))))

*)

// more type inference nuances: these types must be written down

let vector_append_list (v:'a array) (lst:'a list) =

let rec copy src dst i =

if i = 0 then ()

else (dst.(i-1) <- src.(i-1); copy src dst (i-1)) in

let rec copy_list_to_vector ls vc i =

match ls with

[] -> ()

| (x :: rls) -> (vc.(i) <- x;

copy_list_to_vector rls vc (i + 1)) in

let newv = Array.create (v.Length + lst.Length) 0 in

(copy v newv v.Length;

copy_list_to_vector lst newv v.Length;

newv)

## No comments:

Post a Comment