Goals

  • Understand the bases of pattern-matching.
  • Get familiar with inner let bindings.

Requirements

➪ You have completed OCaml - Lesson 2.

Mission 3

Pattern matching, inner let

Basic pattern matching

  • At first, pattern matching looks like a standard, boring switch:
    let f x = match x with | 0 -> "zero" | 1 -> "one" | 2 -> "two" | _ -> "another number" or, equivalently, let f = function | 0 -> "zero" | 1 -> "one" | 2 -> "two" | _ -> "another number"
    • Guess the function type.
    • Try it (apply it to several values).
    • Remove, or comment out, the default case (the last one), and see if the compiler complains.
    • The order is important: try to put the default case _ not in the last position.
    This is an example of pattern-matching of integer values (nothing exceptional).
  • Write a function which pattern-matches booleans (you do not need the default case _).
  • Write a function which pattern-matches a few strings (the default case _ is mandatory).
  • This is getting interesting, you can pattern-match tuples:
    let f tup = match tup with | (0, true) -> 1 | (0, false) -> -1 | (_, false) -> 2 | (_, true) -> 3
    • Guess the function type.
    • Try it (apply it to several values).
    • The pattern _ means «anything» (here, any integer).
    • Is this pattern-matching exhaustive? (that is, all the cases are considered)?
      The OCaml compiler checks the exhaustiveness of pattern-matching.
      Besides, the compilation of pattern-matching in OCaml is efficient:
      Try it: modify the third case by: | (1, false) -> 2 and guess what the compiler says.
  • Note that the example above is equivalent to:
    let f (a,b) = match (a,b) with | (0, true) -> 1 | (0, false) -> -1 | (_, false) -> 2 | (_, true) -> 3
    Exercise : Do not confuse 'match' and 'function'
    • Does the following function confused2 have type int × bool → int?
      let confused2 (a,b) = function | (0, true) -> 1 | (n ,_) -> 10
      Apply confused2 in order to obtain 1. Try again to obtain 10.
    • Guess the types of both functions:
      let foo x y = match (x,y) with | (0,0) -> x | _ -> y let bar x y = function | (0,0) -> x | _ -> y
    • Conclusion: be careful with match and function.
  • Patterns can bind variables. Study this example carefully:
    let calc = function | (x, y, "add") -> x + y | (x, y, "sub") -> x - y | (x, y, "mul") -> x * y | (x, 0, "div") -> failwith "Division by zero." | (x, y, "div") -> x / y | _ -> failwith "Unknown operator."
    • failwith raises an exception.
    • Have you noticed the 0 in one pattern?
    • Try it: calc (110, 220, "add") and try other triples too.
    • The variables x and y in the patterns mean «anything», just like _, but makes it possible to remember the value and use it in the right-hand part x + y .
      The x in x + y is equal to the integer found in the first position of the triple, e.g. 110.
      The y is equal to the integer found in the second position of the triple, e.g. 220.
  • calc is uncurried (it takes a triple as an argument). Write the curried version of calc. You need match but you no longer need function.
Exercise : Basic pattern-matching
  • Write the boolean function xor (exclusive or) of type bool → bool → bool.
    You must use pattern-matching, with four cases.
  • Define an enumeration type : type operation = Add | Sub | Mul | Div (Yes, the names must start with a capital.)
    Rewrite the (curried) function calc so that its third argument is of type operation instead of string. (You can use enum values in patterns.)
    Here is a test: calc 4 5 Mul must return 20.
Pitfall: do not get confused by variables in patterns. See the following example.
let equal a b = match b with | a -> true | _ -> false
  • It seems that equal tests if both arguments are equal (is b = a ?)
  • However, the compiler warns about an unused case. This is strange.
  • Try it: equal 0 0 equal 0 1
    The latter does not return false, as expected.
  • This function always return true. Try to understand why.
  • The variable a in the pattern (in the match) is not the argument a of the function.
    It is considered as a fresh variable.
  • The example above is in fact equivalent to:
    let equal a b = match b with | z -> true | _ -> false
    The variable z matches anything, so the first pattern always succeeds. And the last one is always unused. The compiler was right, again.
    Since z is not used, it is also equivalent to
    let equal a b = match b with | _ -> true | _ -> false
    where the first pattern always wins (thus, the function always return true).
  • You can obtain the expected result by using a when like this:
    let equal a b = match b with | x when x = a -> true | _ -> false
    Do not use when excessively, they are ignored when checking the patterns exhaustiveness.

Sequence

  • The sequence operator is written ;
  • A sequence a ; b or a ; b has the same type than b
  • Besides, a is expected to have type unit.
  • Here is a typical example:
    let f x = Printf.printf "Calling f with value x = %d\n %!" x ; x * x + 2
    • (Try it, apply f with some value)
    • The Printf line has type unit.
    • The type of the result is the type of x * x + 2, that is int, hence f has type int → int.
  • Add a second element in the sequence, just after the Printf:
    let f x = Printf.printf "Calling f with value x = %d\n %!" x ; x + 1 ; x * x + 2
    The value of x + 1 is ignored. The compiler emits a warning.
StarExercise : Sequence
  • Write a higher-order, polymorphic function show of type (int → α) → int → α such that show f v prints a message Function called with value (here the value of v) then returns the same result as f v .
    Note that v is of type int.
    Example
    let double x = x * 2 ;; show double 100
    Function called with value 100 - : int = 200
    A message is printed, and the value 200 is returned.
  • Let us be more polymorphic: write another function pshow of type (α → string) → (α → β) → α → β
    pshow cv f v is exactly like show f v , except that we use the function cv to convert the argument v to type string. The function cv has type (α → string). (Do not try to use show, which is less generic).
    Example
    (* A function taking an int. *) let double x = x * 2 let show_double = pshow string_of_int double ;; let a = show_double 0 ;; let b = show_double 40 ;;
    Function called with value 0 Function called with value 40
    Example
    (* A function taking a pair of ints. *) let sumsquare (x,y) = x * x + y * y (* sprintf returns a string, instead of printing it. *) let string_of_pair (x,y) = Printf.sprintf "(%d, %d)" x y let show_sumsquare = pshow string_of_pair sumsquare ;; let a = show_sumsquare (1, 2) ;; let b = show_sumsquare (10, 5) ;;
    Function called with value (1, 2) Function called with value (10, 5)

    Notice that show_double has the same type than double, and show_sumsquare has the same type than sumsquare.
    Besides, both are closures.

Inner Let

You already know the top-level let.
In this chapter, we introduce another construct: let ... in ... which is an expression and thus, it can be used inside other expressions.

  • The syntax is precisely let variable = expression in expression'
  • The semantics (the meaning) of let x = expr1 in expr2 is
    • Compute the value of expr1: expr1 v
    • Return expr2, assuming that x is v that is, return expr2[x := v] (you recognize a substitution)
  • In Javascript, one would write
    Example (Javascript)
    var x = expr1 ;
    expr2
    
    The variable x exists in expr2 (and is mutable).
    Example (Ocaml)
    let x = expr1 in expr2
    The variable x exists in expr2 (and is immutable)
  • As an example, we implement the leap year algorithm (in french: bissextile) using inner lets.
    let is_leap_year n = (* Test if n is a multiple of x. *) let multiple_of x = n mod x = 0 in let is_mul4 = multiple_of 4 in let is_mul100 = multiple_of 100 in let is_mul400 = multiple_of 400 in is_mul400 || (is_mul4 && not is_mul100)
    • By the way, have you noticed that multiple_of is a closure, since it contains a variable n which is already known when the function is applied (on the contrary, x is not known until the function is applied).
    • Vocabulary: we say that x is a bound variable in multiple_of, whereas n is a free variable in multiple_of.
    • In case you wonder, is_leap_year is a function, but not a closure (it does not contain free variables).
  • Several variables can be bound at once with a let ... and ... . See the difference between:
    (* A top-level let to write our program. *) let res1 = (* A first inner let. *) let a = 10 in (* A second inner let, binding two variables at once. *) let a = 20 and b = a in (* The final result *) (a, b) and (* A top-level let to write our program. *) let res2 = (* A first inner let. *) let a = 10 in (* Two inner let (instead of one). *) let a = 20 in let b = a in (* The final result *) (a, b)

    The results are different.

    Exercise : let . . in
    Try to guess these results of:
    (* This one is a top-level let. *) let result1 = (* These are inner let. *) let a = 10 and b = 20 and c = true in let a = c and b = a and c = b in (a,b,c) let result2 = 10 + let x = 5 + 5 in let y = x * x in 2 * y let result3 = "Foo is " ^ let x = string_of_int (5*5) in x ^ " I say."
  • A let is actually a bit more general. It can bind a single, exhaustive pattern. Here are some examples:
    • A single variable is already an exhaustive pattern:
      let x = expression (nothing new)
    • A tuple of variables is an exhaustive pattern:
      let (a, b, c) = (10, 20, 30) let (a, b) = (b, a)
    • A record pattern, which we will consider later.
    • Unit is also an exhaustive pattern:
      let () = print_endline "Hello."
    • A let with unit value can be useful to gather a sequence:
      let () = print_endline "You get" ; print_endline "a shiver" ; print_endline "in the dark" ; ()
      Likewise, in Java or C, you may add brackets around a sequence of statements.
      Example (Java or C)
      { int x ;
      
        { x += 7 ;
          x = x << 8 ; }
      
        x -= 256 ;
      }
      
      The inner brackets create an inner block (only decorative in this example).
    Exercise : Compare let and match
    • Which functions are equivalent?
      let f a (b,c) = a+b+c let f a p = match p with | (b,c) -> a+b+c let f a p = let (b,c) = p in a+b+c let f a = function | (b,c) -> a+b+c let f a = fun (b,c) -> a+b+c
      Auto-check: here, functions with the same type are equivalent.
    • Rewrite this function in a much simpler way (say, one line):
      let get_triple arg = match arg with | (a, p) -> begin match p with | (b,c) -> [ a ; b ; c ] end

Expressions and definitions

An OCaml program (a module) consists of definitions and expressions.

  • Definitions include the top-level let, type definitions, module definitions, and a few other things.
    You can find the full specification of ocaml definitions in the manual (chapter 7.11, module expressions).
    So far, you mostly used let x = expression which is a (top-level) definition. See if you can find it in the specification.
  • Expressions include almost everything else:
    • Numbers, strings, characters, known as constants in the manual.
    • Lists, tuples
    • if, while, for (do not even think about using while, which is evil imperative-style)
    • let x = expression in expression
    • fun, function, match
    • begin expression end which is equivalent to (expression)
    All these are expressions, see the full specification in the manual (chapter Expressions).
    • Find the match construct.
    • Check that fun and function have very different specifications.
StarExercise : Expressions
To check that (almost) everything is an expression, complete these two toy examples, so that both functions are typeable.
You are free to imagine anything, provided it is accepted by the compiler.
let fancy1 x = begin if ... then (fun a b -> ... ) else ... end (x-1) (x+1) let fancy2 a b c = (* Remember concatenation? *) "Hello " ^ let f = if ... then match ... with | ... -> (fun x -> ... ) | ... -> (function 4 -> ... | _ -> ... ) else ... in (* Use f here *)
  • Test your function with several values.
  • Notice that fancy2 contains a lambda(fun) inside a match inside a if inside a let inside a top-level let.

Outcomes

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

  • Use pattern-matching to simplify your code.
  • Organise your code with inner let bindings.