▸Goals

  • Use classical higher-order functions to navigate through data structures.
  • Deepen your understanding of datatypes with tree structures.

Requirements

▸Mission 5

Algorithms and more type structures

▸Practicing on lists

As a warm-up, some classical exercises on lists (yes, this is quite long).

StarExercise : First-order functions on lists
  • Write a function nth with type α list → int → α such that nth alist n returns the n-th element of alist (counting from 0), or fails with failwith "List too small" if n is bigger than the list.
  • Write a function rev with type α list → α list which reverses the elements of the list: rev [ 1 ; 2 ; 3 ] is [ 3 ; 2 ; 1 ].
    You need an auxiliary function with an accumulator (this is clearly the easiest way to reverse a list). If you work well, the auxiliary function should be hidden from the outside world.
  • Write a function append with type α list → α list → α list which concatenates two lists. No accumulator, this function does not exist in tail-recursive form (unless you make two passes). For example, append [ 1 ; 2 ] [ 3 ; 4 ] is [ 1 ; 2 ; 3 ; 4].
  • Write the tail-recursive variant: rev_append with the same type, but a different behaviour. rev_append l1 l2 returns a list: (reversed-l1) then (l2). For instance, rev_append [ 1 ; 2 ] [ 3 ; 4 ] is [ 2 ; 1 ; 3 ; 4]. (You can write an auxiliary function if necessary).
Exercise : Find your way in the OCaml manual
  • Search for ocaml manual using whatever search engine.
  • You should find a page entitled The OCaml system release 4.04 (the precise version number does not matter) .
  • Identify:
    • Which part explains the compiler options, the runtime options, the documentation generator, etc. Find the list of compiler options. Do not read them all!
    • Which part contains a few tutorials. Find the tutorial about objects. You'll read it this summer.
    • Which part contains the formal definition of the language: you should find the definition of expressions.
    • Which part contains the libraries. Find the standard library, in which you find the List module.
  • In the documentation of the List module, read the first paragraph and the documentation of the first block of functions (until Iterators). Almost all functions should sound familiar.
  • Finally, have a quick look at the definitions in the Pervasive module, to be found in the Core Library. All these definitions are always available by default in OCaml. Read the boolean operations.
StarStarExercise : Higher-order functions on lists
  • Remember the function map you have written in Lesson 2 (higher-order functions).
    Its type is ∀αβ. (α → β) → α list → β list. It is not tail-recursive, it does not use an accumulator.
  • Write the tail-recursive version rev_map with the same type. The function takes as an argument a list [ a ; b ; c ; ...] and returns a reversed list: [ ... ; f c ; f b ; f a ]
    You need an auxiliary function, which can be carefully hidden from the outside world.
  • Write a function iter with type ∀α. (α → unit) → α list → unit such that iter f [ a ; b ; c ; ... ] is equivalent to f a ; f b ; f c ; ... (it is a sequence). The type checker will probably infer a more polymorphic type: ∀α. (α → β) → α list → unit, that's ok.
    As an example, iter (Printf.printf "Element : %d\n%!") [ 2 ; 4 ; 6 ; 8 ] should print the elements of the list.
  • This function is not in the standard library: write print_list with type ∀α. string → (α → string) → α list → unit such that print_list sep conv alist prints the elements of the list, using conv to convert them to strings, and using sep as a separator (for example, a comma).
    print_list ", " string_of_int [ 4 ; 8 ; 99 ] 4, 8, 99
    print_list " ++ " (fun x -> x) [ "aa" ; "bb" ; "cc" ] aa ++ bb ++ cc
  • Note: to be fully compositional, print_list should return a string rather than use Printf. (Exercise to be done on your own, later).
  • Finally, we get in touch with the essence of iterators on lists: fold
    We wish to write a function fold able to add all elements of a list, or to multiply all elements, or apply any operation.
    fold (+) 0 [ 1 ; 2 ; 3 ; 4 ] 100 is the accumulator.
    fold ( * ) 1 [ 1 ; 2 ; 3 ; 4 ] 24Put the spaces around ( * ) otherwise it is considered as a comment.

    Complete this definition (keep the type annotations):
    let rec fold (op:int -> int -> int) (acu:int) = function | ...
    Test with the examples above. Make sure that the operator op is applied to the acu first, then to an element of the list (otherwise your type variables will be inverted in the next question).
  • Remove the type annotations on fold. You shoud get a polymorphic type: (α → β → α) → α → β list → α.
    (Again, you have written a polymorphic function without noticing.)
    Take the necessary time to understand this type, as well as the following examples:
    fold (fun a b -> a ^ " " ^ string_of_int b) "" [ 1 ; 2 ; 3 ; 4] Guess what is the result.
    fold (fun a b -> if a < b then b else a) 0 [ 10 ; 40 ; 20 ; 30 ] Guess.
    fold (fun a b -> b :: a) [] [ 4 ; 3 ; 2 ; 1 ] Guess.
  • In the List module, read the section about Iterators. fold is named fold_left. You use it with List.fold_left
  • Write a function exists with type (α → bool) → α list → bool such that exists pred alist returns true iff the predicate pred is true for at least one element of alist.
    Write two versions: one using fold and one writing the recursive function directly, with pattern-matching.
    exists (fun x -> x < 10) [ 20 ; 5 ; 30 ]
    exists (fun x -> x < 10) [ 20 ; 40 ; 30 ]
    exists (fun x -> x < 10) []
  • Define a composition operator ++ (to define this infix operator: let (++) f g ... ) which composes two functions (the usual composition written ∘ in maths).
    ((fun x -> x - 10) ++ abs) (-20) 10
    (abs ++ (fun x -> x - 10)) (-20) 30
  • Write the function forall, which has type (α → bool) → α list → bool which returns true iff the predicate is true for all elements of the list. Do not use fold, do not use pattern-matching, use only exists and your wits. (You may use ++ too.)
StarExercise : Association lists

A classical use of lists consists in association lists which are lists of pairs. Here is an example, indicating which people can speak japanese: let assoc1 = [ ("Lucy", true) ; ("Mike", false) ; ("Hilary", false) ; ("Donald", true) ]

  • Write a function assoc with type α → (α * β) list → β such that assoc key assoc_list returns the value associated to key in assoc_list. It fails with raise Not_found if the key is not in the list (the exception Not_found is already defined).
    assoc "Donald" assoc1 true
    assoc "Mike" assoc1 false
    assoc "donald" assoc1 Not_found
  • Write a function remove_assoc with type α → (α * β) list → (α * β) list. It removes a key from an association list. It fails with Not_found if the key is not in the list.
    Test it.

▸Trees

  • Let us define a datatype for simple binary trees:type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree
    A tree contains leaves with values of type 'a and each node has two childs (two subtrees).
  • The function max is already defined in OCaml. It is defined as: let max a b = if b > a then b else a
    What is its type?
  • Write a function depth with type 'a tree → int which returns the (maximal) depth of the tree.
    depth (Leaf 100) 0
    depth (Node (Leaf 100, Leaf 200)) 1
  • Write a function build with type int → α → α tree such that build n x builds a tree having depth n and each leaf contains the value x (you are free to build the tree as you like).
    You can now test the function depth.
  • To pretty-print the trees, you can use this function (guess how to use it by reading its type).
    let print_tree tos tree = let rec loop margin = function | Leaf x -> Printf.printf "___ %s\n%!" (tos x) | Node (a,b) -> Printf.printf "____" ; loop (margin ^ "| ") a ; Printf.printf "%s|\n%s|" margin margin ; loop (margin ^ " ") b in loop " " tree
  • StarStarWrite a function build_fold with type int → α → (α → α) → α tree such that:
    • build_fold n init f builds a tree having depth n.
    • The first (leftmost) leaf to be constructed should have value init, the second one should have value f init, the next one has value f (f init) and so on by applying f each time a leaf is constructed.
    • As an example, let tree1 = build_fold 3 10 (fun x -> x+2) builds the following tree:
      _______________ 10
   |   |   |
   |   |   |___ 12
   |   |
   |   |_______ 14
   |       |
   |       |___ 16
   |
   |___________ 18
       |   |
       |   |___ 20
       |
       |_______ 22
           |
           |___ 24
      Depth is 3, leaf numbers start at 10, and the next number is obtained by adding 2.
    • You need an auxiliary function (like loop in the print_tree example above), which returns a tree and the value of the next leaf to be built.
    • Here is another example: let tree2 = build_fold 2 "o" ( fun x -> "(" ^ x ^ ")" ) 
      ___________ o
   |   |
   |   |___ (o)
   |
   |_______ ((o))
       |
       |___ (((o)))
  • Write a function tmap with type (α → β) → α tree → β tree. From the type, you should guess what the function does.
  • Write a function tfind with type (α → bool) → α tree → α option such that tfind pred tree returns Some x iff x is the leftmost leaf in the tree that satisfies pred, or None if none can be found .
  • Write a function contains with type α → α tree → bool such that contains x tree returns true iff the tree contains a leaf with value x.
  • Write a function replace with type (α tree → bool) → α tree → α tree → α tree such that replace pred sub tree replaces all subtrees of tree that satisfy pred with the subtree sub.
    As an example, replace (fun t -> contains 14 t && depth t = 1) (Leaf 0) tree1 replaces by Leaf 0 any subtree that contains the value 14 and whose depth is 1.
    _______________ 10
   |   |   |
   |   |   |___ 12
   |   |
   |   |___ 0
   |
   |___________ 18
       |   |
       |   |___ 20
       |
       |_______ 22
           |
           |___ 24

▸Outcomes

Once the mission is completed, you must be able to:

  • Cite half a dozen classical functions on lists, give their (polymorphic) type and understand what they do.
  • Write such functions by yourself (not by heart).
  • Handle more complex datatypes, such as a tree type.