EOPL - 1.2.4 - Some Exercises - 1.15

These are F# solutions to Exercise 1.15. In some places the functions proposed in the exercise are not completely suited to a ML language, so I made notes in the comments, but otherwise there is little that is exciting about these functions. I did alternative versions in some cases, even though the whole point of this exercise (and the rest from Section 1.2) is to write recursive functions to get a feel for them.

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)