Recursion and Higher-Order Functions

• Write a function count : 'a list -> ('a -> bool) -> int which takes a list of elements, a predicate which operates on the elements, and returns the number of elements which match the predicate. For example

  # count [1;2;3;4;5] (fun x -> x > 2);;
  - : int = 3
  # count [1;2;3;4;5] (fun x -> x mod 2 == 0);;
  - : int = 2
  # count ["abc"; "defgh"; "ijklmnopq"; "rs"; "tuvwxy"; "z"] (fun x -> String.length x > 2);;
  - : int = 4
  

• What is the value of:

  count 
    [(fun x -> x mod 2 == 0);
     (fun x -> x mod 2 == 1);
     (fun x -> x == 0);
     (fun x -> true)]
    (fun p -> p 0)
  

• A set can be represented as a list with no duplicates. Write a function which takes a list and removes all duplicates. You will probably need to use the function List.mem : 'a -> 'a list -> bool from the library which checks if the given element (first argument) is a member of the given list (second argument).

  # remove_dups [1;2;3;4;5;1;2;6;2;9];;
  - : int list = [3; 4; 5; 1; 6; 2; 9]
  

• Write functions which take two sets (represented as lists without duplicates like above) and return the union, the intersection, and the difference (the set of elements in the first set but not in the second).

  # let s1 = [1;2;3;4;5;6;7];;
  val s1 : int list = [1; 2; 3; 4; 5; 6; 7]
  # let s2 = [5;6;7;8;9];;
  val s2 : int list = [5; 6; 7; 8; 9]
  # union s1 s2;;
  - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
  # intersect s1 s2;;
  - : int list = [5; 6; 7]
  # diff s1 s2;;
  - : int list = [1; 2; 3; 4]
  # diff s2 s1;;
  - : int list = [8; 9]
  

• Write a function which produces the powerset (the set of all subsets) of a set. For example,

  # powerset [1;2;3];;
  - : int list list = [[]; [3]; [2]; [2; 3]; [1]; [1; 3]; [1; 2]; [1; 2; 3]]
  

• The library definition for List includes the following functions:

  val iter : ('a -> unit) -> 'a list -> unit
  List.iter f [a1; ...; an] applies function f in turn to a1; ...;
  an. It is equivalent to begin f a1; f a2; ...; f an; () end.
  
  val map : ('a -> 'b) -> 'a list -> 'b list
  List.map f [a1; ...; an] applies function f to a1, ..., an, and builds
  the list [f a1; ...; f an] with the results returned by f. Not
  tail-recursive.
  
  val rev_map : ('a -> 'b) -> 'a list -> 'b list
  List.rev_map f l gives the same result as List.rev (List.map f l), but
  is tail-recursive and more efficient.
  
  val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
  List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn.
  
  val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
  List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b)
  ...)). Not tail-recursive.
  

  What are the values of the following expressions:
  • List.fold_left (-) 1 [2;3;4;5]
  • List.fold_right (-) [2;3;4;5] 1
  • List.fold_left (fun x y -> x * (1 + y)) 0 [1;2;3]
  • List.fold_right (fun x y -> x * (1 + y)) [1;2;3] 0
  • List.fold_left (@) [] [[1;2;3];[4;5];[6;7;8]]
  • List.fold_right (@) [[1;2;3];[4;5];[6;7;8]] []
  • List.map (fun f -> f 0) [(fun y -> y * 2); (fun y -> y + 1)]

Data Structures; Modules/Interfaces; Algorithms

Also make sure you understand how the knapsack and shortest-path algorithms work.

Practice with Extra Credit Problems

• Reversing a list
• Converting binary to decimal and back; efficient implementations
• Other implementations of queues