Data Types

In MiniML: bool, int option, int list

datatype shape = Circle of real * real * real

Recursive Types

  • Context-free Grammar
  • Inductive (leaves are just ints)

Using Abstraction

Fold is your friend! fold takes a list, state (accumulator), and a folder.

internal function loop.

base case: empty list

induction step: apply folder to (head, state), and recursively call loop on the tail

map:

Generative Datatypes

Pattern Matching

like switches except not just on ints (or enums)

can be:

case s
  of x => e1 (* any subject matches this pattern *)
   | _ => e2 (* same as x but discarded *)
   | 3 => e3 (* matches when s = 3 *)
   | (p1, p2, pn) => e4 (* provided s is a tuple
                         * and the correct arity
                         * (guaranteed already by
                         *  the type checker)
                         * pn can be a pattern
                         *)
   | C y => e5 (* Matches Constructor AND
                * y can be a tuple, constructor,
                * record, etc.
                *)

Quirks

case s
  of (1, 2) => e1
   | (1, 3) => e2

A naive compiler would ask “Is the 1st element 1?” twice. In general, this is NP complete.

Infeasible/Silly

case s
  of x => e1
   | 3 => e2

x will always match

fun diff(nil, y) = y(1)
  | diff(x, nil) = x(1)

Overlapping (nil, nil) so y(1) will never be executed.

Questions?

case s
  of Cons(x)      => e (* 1-tuple = variable *)
   | Cons(y, nil) => e (* redundant *)

One cannot call functions ins a pattern, or match on the value of a ref. However, SML lists can be deconstructed using :: as in the following:

case s
  of []         => e (* empty list *)
   | hd :: tail => e (* non-empty list *)

Example

case s : (bool * intlist)
  of (true, _)            => p1
   | (false, nil)         => p2
   | (false, Cons(x,Nil)) => p3
   | (false, Cons(y,z))   => p4

Is the order of matching important?

If the ordering is right to left, then the correct match will not happen until both arguments are matched (since _ is the wildcard)

Are p3, p4 redundant?

No, because p3 is more specific but overlapping. It matches specifically Nil while p4’s last argument matches anything and assigns the value to y

Is case s of x => e | 3 => e redundant?

Yes, because x will always match because of ordering and 3 will never

Advertisements