C311 Test 1

T/F

  1. T F# is statically typed

  2. T Tuples are heterogeneously typed and can contain other tuples

  3. F [[1; 4]; [-1; 5]; [3; 4]; 5] is a valid F# list

  4. T let f x = (fun y → x * y);; is a curried function

  5. T A function with one function parameter that returns a function is order 2

  6. T let f5 a b = (a+1)::b;; can only take integers as an argument for a

  7. T The reduce function we have written is the same as the List.foldBack function.

  8. T The List.fold function is the same as List.foldBack for associative operations such as + and *

Matching (non-exhaustive)

9. a (fun a b → a*b) a. let f a b = a*b

10. c (fun b → 4*b)

b. let f a = (fun b) → a*a

11. e [2; 3; 4]

c. let f a b = a * b;; f 4;;

12. d 12

d. List.foldBack (fun a b → a*b) [3;1;4] 1

13. f 10

e. List.map (fun a → a+1) [1;2;3]

f. List.foldBack (fun x c → x+c) (List.map (fun a → a+1) [1;2;3]) 1

Short answer

Using the following definitions:

let rec map f L =
  match L with
    | [] -> []
    | h::t -> f h::map f t;;

let rec filter f L =
  match L with
    | [] -> []
    | h::t when f h -> h::filter f t
    | h::t -> filter f t;;

let rec reduce f a L =
  match L with
    | [] -> a
    | h::t -> f h (reduce f a t);;

let rec map2 f L1 L2 =
  match (L1, L2) with
    | ([], []) -> []
    | (h1::t1, h2::t2) -> (f h1 h2)::map2 f t1 t2;;

type IS = I of int | S of string;;

let m a b =
  match (a,b) with
    | (I x, I y) -> I (x*y)
    | (I x, S y) -> S y;;

let g x y = (x, y)

let h x y = y @ [x]

Give the results of the following. Some may be be errors.

14. g 2 "b"

(2, "b") // Note string constants have quotes!

15. let f a = g a 8;; f "a";;

("a", 8)

16. h [3;2] 1

error

17. map (fun a → a+1) [1;2;3;4]

[2; 3; 4; 5]

18. map2 g [1;2] ["a";"b"]

[(1, "a"); (2, "b")]

19. map2 (fun a b → (a,b)) [1;2] ["a";"b"]

[(1, "a"); (2, "b")]

20. reduce h [] [1;2;3]

[3;2;1]

21. filter (fun x → x > 3) [1;2;3;4;5]

[4; 5]

22. m (I 5) (S "a")

S "a" // Note S

23. m (I 5) (I 6)

I 30

24. m (S "a") (I 5)

error

25. Domain of g

'a → 'b // set of all generic values 'a and 'b

26. Range of g

→ 'a * 'b // set of all tuples 'a * 'b

Programming in F#

  1. Define a function count5 to count the number of 5’s in a list. For example:

count5 [] // returns 0
count5 [1;5;2;5;3;5] // returns 3
> let rec count5 L =
-  match L with
-   | [] -> 0
-   | h::t when h = 5 -> 1+count5 t
-   | h::t -> count5 t;;

val count5 : L:int list -> int

> count5 [];;
val it : int = 0
> count5 [1;5;2;5;3;5];;
val it : int = 3
  1. Given a union data type definition of:

type irs = I of int | R of double | S of string | IR of int * double | IS of int * string

Define the Imult function that multiplies two I types and returns an I type. Ignore any other combinations.

Imult (I 5) (I 4) // returns I 20

> let rec Imult i1 i2 =
-   match (i1, i2) with
-    | (I x, I y) -> I (x*y);;

val Imult : i1:irs -> i2:irs -> irs

> Imult (I 5) (I 4);;
val it : irs = I 20
  1. Using the datatype definition of Q 28, define the IxS function that given an I type and a S type returns an IS type. For example:

IxS (I 4) (S "hello") // returns IS (4, "hello")

> let IxS (I i) (S s) = IS (i, s);;

val IxS : irs -> irs -> irs

> IxS (I 4) (S "hello");;
val it : irs = IS (4,"hello")
  1. Given the following datatype definition:

type 'e mylist = NIL | CONS of 'e * 'e mylist

Define the function to find the length of a mylist. For example:

myLength (CONS (8, CONS (2, CONS (6, NIL)))) // returns 3

> let rec myLength L =
-    match L with
-      | NIL -> 0
-      | CONS (h, t) -> 1+myLength t;;

val myLength : L:'a mylist -> int

> myLength (CONS (8, CONS (2, CONS (6, NIL))));;
val it : int = 3
  1. Define the recursive rdc function that returns all but the last element of a list.

rdc [1;2;3] // returns [1;2]

> let rec rdc L =
-   match L with
-     | h::[] -> []
-     | h::t -> h::rdc t;;

val rdc : L:'a list -> 'a list

> rdc [1;2;3];;
val it : int list = [1; 2]
  1. Define a tail recursive rdc that returns all but the last element of a list.

tailRdc [] [1;2;3;4] // returns [3;2;1] (note: this will return the list in reverse order and that is OK)

> let rec tailRdc a L =
-     match L with
-       | h::[] -> a
-       | h::t -> tailRdc (h::a) t;;

val tailRdc : a:'a list -> L:'a list -> 'a list

> tailRdc [] [1;2;3;4];;
val it : int list = [3; 2; 1]