Exercise 3 - Lists

Documentation and user's manual

Table of contents

OCaml programs

Exercise 3 - Lists

Specification of the type  t list

This type gives each list of elements of A a representation (or a unique representation if and only if  t  gives each element of A a unique representation). It is equipped with these five functions: These constructors: The basic constructor  empty_list  constructs the representation of the empty list. The inductive constructor  cons_list  constructs a (or the) representation of the list whose first element is x and whose rest is lx given a pair (x,lx) where x is an element of A and lx is a list of elements of A. The predicate function  is_empty_list  checks whether a list of elements of A is empty. The accessors  head  and  tail  access the first element and the rest of a non-empty list of elements of A. The interface definition of the module (i.e. the content of the  List_1.mli  file) shows the types of these five functions: val empty_list : unit -> 'a list val cons_list : 'a * 'a list -> 'a list val is_empty_list : 'a list -> bool val head : 'a list -> 'a val tail : 'a list -> 'a list It also indicates that these functions are polymorphic:  t  can be any type, which is expressed by the type variable  'a .

Use lists.   For each of the following specifications of functional values write a recursive definition that meets the specification:

1

Name:  length . Type:  a list -> int . Computes the length of a list. Examples: [ ]  ->  0 [1 ; 2 ; 3]  ->  3 ["" ; ""]  ->  2 [[ ]]  ->  1

2

Name:  is_member . Type:  a * 'a list -> bool . Tests whether x is a member of the list lx given the pair (x, lx). Examples: (`a`, [ ])  ->  false (3, [2 ; 2])  ->  false ("", ["" ; "la" ; ""])  ->  true

3

Name:  map_twice . Type:   . Computes the list of twice each element in a list of integers. Examples: [ ]  ->  [ ] [0 ; 0 ; -5 ; 3 ; 1]  ->  [0 ; 0 ; -10 ; 6 ; 2]

4

Name:  less_than . Type:  int -> int list . Computes the strictly decreasing list of the non-negative integers less than an integer. Examples: 0  ->  [ ] 5  ->  [4 ; 3 ; 2 ; 1 ; 0]

5

Name:  even_only . Type:  int list -> int list . Computes the sublist of the even numbers in a list of integers. Examples: [ ]  ->  [ ] [3 ; 5]  ->  [ ] [2 ; 2]  ->  [2 ; 2] [-3 ; 0 ; -3]  ->  [0]

6

Name:  map_length . Type:  'a list list -> int list . Computes the list of the lengths of the elements in a list of lists. Examples: [ ]  ->  [ ] [[1] ; [ ]]  ->  [1 ; 0] [[1 ; 2] ; [3]]  ->  [2 ; 1] [[[ ]]]  ->  [1]

7

Name:  combine . Type:  'a list * 'b list -> ('a * 'b) list . Transforms a pair of lists having the same length into a list of pairs. Examples: ([ ], [ ])  ->  [ ] ([0 ; 2], [1 ; 3])  ->  [(0, 1) ; (2, 3)]

8

Name:  split . Type:  ('a * 'b) list -> 'a list * 'b list . Transforms a list of pairs into a pair of lists. Examples: [ ]  ->  ([ ], [ ]) [(0, 1) ; (2, 3)]  ->  ([0 ; 2], [1 ; 3])

9

Name:  insert . Type:  'a * 'a list -> 'a list . Order-preserving insertion of a value into an increasing list (according to  < ). Examples: ("yes", [ ])  ->  ["yes"] (7, [2 ; 3 ; 3 ; 6 ; 8])  ->  [2; 3; 3; 6; 7; 8]

10

Name:  sort . Type:  'a list -> 'a list . Sorts a list in increasing order (according to  < ).

Exercise 3 - Lists

Documentation and user's manual

Table of contents

OCaml programs