Exercise : Lists.
  • Write a function switch with type α list → α list which switches the 1st and 2nd elements of the list, the 3rd and 4th elements, the 5th and 6th elements, and so on.
    switch [] []
    switch [1] [1]
    switch [1 ; 2] [2 ; 1]
    switch [1 ; 2 ; 3] [2 ; 1 ; 3]
    switch [1 ; 2 ; 3 ; 4] [2 ; 1 ; 4 ; 3]
    switch [1 ; 2 ; 3 ; 4 ; 5] [2 ; 1 ; 4 ; 3 ; 5]
    switch [1 ; 2 ; 3 ; 4 ; 5 ; 6] [2 ; 1 ; 4 ; 3 ; 6 ; 5]
  • Write a function unpair with type (α × α) list → α list which returns all elements of a list of pairs.
    unpair [] []
    unpair [ (3,4) ] [3 ; 4]
    unpair [ (3,4) ; (10,11) ] [3 ; 4 ; 10 ; 11]
    unpair [ (3,4) ; (10,11) ; (20,30) ] [3 ; 4 ; 10 ; 11 ; 20 ; 30]
  • Write a function remove_succ with type int list → int list which removes all elements x if the following element is x+1.
    remove_succ [] []
    remove_succ [ 10 ] [ 10 ]
    remove_succ [ 10 ; 20 ] [ 10 ; 20 ]
    remove_succ [ 10 ; 20 ; 21 ] [ 10 ; 21 ]
    remove_succ [ 10 ; 20 ; 21 ; 22 ; 23 ; 24; 100 ; 101 ; 110 ] [ 10 ; 24 ; 101 ; 110 ]
    remove_succ [ 20 ; 21 ; 22 ; 21 ; 22 ; 23 ] [ 22 ; 23 ]
  • Write a function combine with type α list → β list → (α × β) list which makes a list of pairs from two lists having the same size. Raise an exception with failwith if the lists have different sizes.
    combine [ 10 ; 20 ; 30 ] [ 4 ; 5 ; 6 ] [ (10, 4) ; (20, 5) ; (30, 6) ]
    combine [ 10 ; 20 ; 30 ] [ 4 ; 5 ; 6 ; 9 ] Failure "..."
  • Write a function keep with type α list → bool list → α list taking two lists of the same length and which keeps only the elements of the first list for which the corresponding boolean is true in the second list. It fails if the lists have different lengths.
    keep [ 1 ; 2 ; 3 ; 4 ; 5 ] [ true ; true ; false ; false ; false ] [ 1 ; 2 ]
    keep [ 1 ; 2 ; 3 ; 4 ; 5 ] [ false ; false ; false ; false ; false ] []
    keep [ 1 ; 2 ; 3 ; 4 ; 5 ] [ false ; true ; false ; true ; false ] [ 2 ; 4 ]
  • Write a function map2 with type (α → β → γ) → α list → β list → γ list which takes a two-argument function and two lists of the same length, and applies the function with one argument taken from each list. It fails if the lists have different lengths.
    map2 (-) [ 100 ; 200 ; 300] [ 1 ; 2 ; 3 ] [99 ; 198 ; 297]
    map2 (fun a b -> a ^ string_of_int b) [ "AA" ; "BB" ] [ 20 ; 30 ] [ "AA20" ; "BB30" ]
  • Write a function interleave with type α list → α list → α list which builds a new list by taking alternatively an element from each list. It does not fail if the lists have different sizes.
    interleave [ 10 ] [ 1 ; 2 ; 3 ; 4 ] [10 ; 1 ; 2 ; 3 ; 4]
    interleave [ 10 ; 20 ; 30 ; 40 ] [ 1 ; 2 ; 3 ; 4 ; 5 ] [10 ; 1 ; 20 ; 2 ; 30 ; 3 ; 40 ; 4 ; 5]
    interleave [] [ 1 ; 2 ; 3 ; 4 ; 5 ] [1 ; 2 ; 3 ; 4 ; 5]
Exercise : Variants.
  • Copy the following type definition: type bool3 = BTrue | BFalse | Unknown , which represents a boolean value and a third case indicating that the value is not known.
  • Write the function and3, which is a logical AND for bool3 values.
    and3 BTrue Unknown Unknown
    and3 BFalse Unknown BFalse
  • Similarly, write the not3 function.
  • Copy type instruction = Plus of int | Mul of int
  • Write a function apply_instructions with type int → instruction list → int such that apply_instructions n l applies the instructions in l starting from value n.
    apply_instructions 100 [] 100
    apply_instructions 100 [ Plus 5 ] 105
    apply_instructions 100 [ Plus 1 ; Mul 3 ] 303
    apply_instructions 100 [ Plus 1 ; Mul 3 ; Plus 10 ] 313
  • Write a function to_funlist with type instruction list → (int → int) list which maps a list of instructions to a list of the corresponding functions. (We write the functions using the lambda-calculus notations.)
    to_funlist [ Plus 4 ] [ λx.(x + 4) ] (a singleton list)
    to_funlist [ Mul 3 ; Plus 1 ] [ λx.(x × 3) ; λx.(x + 1)) ] (a two-element list)
    List.map (fun f -> f 100) (to_funlist [ Mul 3 ; Plus 1 ]) [ 300 ; 101 ]
  • Write to_fun with type instruction list → int → int which builds a function of type int → int by composing the functions returned by to_funlist so that the final function returns the same values than apply_instructions.
    to_fun [] 100 100
    to_fun [ Plus 5 ] 100 105
    to_fun [ Plus 1 ; Mul 3 ] 100 303
    to_fun [ Plus 1 ; Mul 3 ; Plus 10 ] 100 313
  • Write a function compact with type instruction list → instruction list which takes a list of instructions and returns a simplified (but equivalent) list. For example, [ Plus 10 ; Plus 20 ; ... ] can be simplified into [ Plus 30 ; ... ]. You do not need to switch Plus and Mul operations.
    compact [ Mul 3 ; Mul 100 ; Plus 50 ; Plus 10 ] [ Mul 300 ; Plus 60 ]
  • Write a function to_string with type string → instruction list → string which pretty-prints the operations as follows:
    to_string "x" [ Plus 5 ] "x + 5"
    to_string "y" [ Plus 1 ; Mul 3 ] "(y + 1) * 3"
    to_string "u" [ Plus 1 ; Mul 3 ; Plus 10 ] "(u + 1) * 3 + 10"
  • Copy type 'a element = Single of 'a | Pair of 'a * 'a type 'a fonct = One_arg of ('a -> 'a) | Two_args of ('a -> 'a -> 'a)
  • Write a function count_elements with type α element list → int which counts the number of elements in the list (pairs count for two).
  • Write a function apply_list with type α fonct list → α element list → α list which takes a list of fonct and a list of element having the same size, and applies each function of the first list to the corresponding element in the second list. Two_args functions must be applied to Pairs, otherwise it is an error (raise an exception). Similarly, One_arg functions must be applied to Singles.
    apply_list [] [] []
    apply_list [ Two_args (+) ; One_arg abs ] [ Pair (100,50) ; Single (-99) ] [ 150 ; 99 ]
    apply_list [ Two_args (+) ; One_arg abs ] [ Single (-99) ; Pair (100,50) ] Failure "Two arg function applied to a single."
  • Write a function partial_apply with type α → α fonct list → (α → α) list which takes a value x and a list of fonct and returns a list of functions. One_arg functions are returned untouched, and Two_arg functions are partially applied with x.
    partial_apply 10 [] []
    partial_apply 99 [ Two_args (+) ; One_arg abs ] [ λu.(99 + u) ; abs ]
    let pl = partial_apply true [ One_arg not ; Two_args (&&) ] [ not ; λb.(true && b) ]
    List.map (fun f -> f false) pl [ true ; false ]
Exercise : Records.
  • Copy the following type definition: type people = { name: string ; age: int }
  • Write a function mk_people_list : int → people list which creates a list of "Johns" as follows:
    mk_people_list 0 []
    mk_people_list 1 [ { name = "John-1" ; age = 10 } ]
    mk_people_list 2 [ { name = "John-2" ; age = 20 } ; { name = "John-1" ; age = 10 } ]
    mk_people_list n n Johns, such that the age of John-k is k*10.
  • Write a function age_most : (int → int → bool) → people → people list → people such that age_most cmp guy list returns the people in the list whose age is the highest, when comparing ages with cmp. cmp a b returns true iff a is higher than b (according to whatever order). guy is used as a starting reference point.
    age_most (<) { name = "Max" ; age = 100 } [] { name = "Max" ; age = 100 }
    age_most (<) { name = "Max" ; age = 100 } (mk_people_list 8) { name = "John-1" ; age = 10 }
    age_most (>) { name = "Max" ; age = 100 } (mk_people_list 8) ..returns {Max}
    age_most (>) { name = "Max" ; age = 0 } (mk_people_list 8) ..returns {John-8}
  • We consider authors contributing to a wiki. Some of them are identified, some of them are anonymous.
    type author = Anonymous | Someone of people
    A contribution can be of different nature (different types α): text, images, movies, ...
    type 'a contribution = { date: float ; author: author ; content: 'a }
    let mike = { name = "Mike" ; age = 30 } let rihanna = { name = "Rihanna" ; age = 28 } let test_contr = [ { date = 100.0 ; author = Anonymous ; content = "afoo1" } ; { date = 90.0 ; author = Someone mike ; content = "bar1" } ; { date = 105.0 ; author = Anonymous ; content = "afoo2" } ; { date = 107.0 ; author = Someone rihanna ; content ="bar2" } ; { date = 102.0 ; author = Someone mike ; content = "bar3" } ]
  • Write a function filter_contributions : α contribution list → α contribution list which keeps only contributions by identified people.
    filter_contributions test_contr only Mike and Rihanna.
  • Write a function map_contributions : (α → β) → α contribution list → β contribution list such that map_contributions f l creates a list similar to l, but all the contents have been mapped by f.
    map_contributions String.length test_contr like test_contr, but content is an int (4 or 5).
  • Write a function latest : α contribution list → α contribution option which returns the latest contribution (with the greatest date): Some contrib or returns None if there is no contribution.
    latest [] None
    latest test_contr Some { date = 107. ; author = Someone { name = "Rihanna" ; age = 28 } ; content = "bar2" }
  • Write a function contents_of : people → α contribution list → α list which returns a list of all the contents provided by the given people.
    contents_of mike test_contr [ "bar1" ; "bar3" ]
    contents_of rihanna test_contr [ "bar2" ]
    contents_of { name = "Mike" ; age = 50 } test_contr []