Pattern Matching SML?

Question

Can someone please explain the: "description of g"? How can f1 takes unit and returns an int & the rest i'm confused about too!!

(* Description of g:
 * g takes f1: unit -> int, f2: string -> int and p: pattern, and returns 
 * an int. f1 and f2 are used to specify what number to be returned for 
 * each Wildcard and Variable in p respectively. The return value is the 
 * sum of all those numbers for all the patterns wrapped in p.
 *)  

datatype pattern = Wildcard
                 | Variable of string
                 | UnitP
                 | ConstP of int
                 | TupleP of pattern list
                 | ConstructorP of string * pattern

datatype valu = Const of int
              | Unit
              | Tuple of valu list
              | Constructor of string * valu


fun g f1 f2 p =
    let
      val r = g f1 f2
    in
      case p of
           Wildcard           => f1 ()
         | Variable x         => f2 x
         | TupleP ps          => List.foldl (fn (p,i) => (r p) + i) 0 ps
         | ConstructorP (_,p) => r p
         | _                  => 0
    end

Wildcard matches everything and produces the empty list of bindings.

Variable s matches any value v and produces the one-element list holding (s,v).

UnitP matches only Unit and produces the empty list of bindings.

ConstP 17 matches only Const 17 and produces the empty list of bindings (and similarly for other integers).

TupleP ps matches a value of the form Tuple vs if ps and vs have the same length and for all i, the i-th element of ps matches the i-th element of vs. The list of bindings produced is all the lists from the nested pattern matches appended together.

ConstructorP(s1,p) matches Constructor(s2,v) if s1 and s2 are the same string (you can compare them with =) and p matches v. The list of bindings produced is the list from the nested pattern match. We call the strings s1 and s2 the constructor name.

Nothing else matches.

Simon Shine Simon Shine · Accepted Answer · 2017-01-25T14:58:02

Can someone please explain the: "description of g"? How can f1 takes unit and returns an int & the rest i'm confused about too!!

The function g has type (unit → int) → (string → int) → pattern → int, so it takes three (curried) parameters of which two are functions and one is a pattern.
The parameters f1 and f2 must either be deterministic functions that always return the same constant, or functions with side-effects that can return an arbitrary integer / string, respectively, determined by external sources.

Since the comment speaks of "what number to be returned for each Wildcard and Variable", it sounds more likely that the f1 should return different numbers at different times (and I'm not sure what number refers to in the case of f2!). One definition might be this:
```
local
    val counter = ref 0
in
    fun uniqueInt () = !counter before counter := !counter + 1
    fun uniqueString () = "s" ^ Int.toString (uniqueInt ())
end
```
Although this is just a guess. This definition only works up to Int.maxInt.
The comment describes g's return value as

[...] the sum of all those numbers for all the patterns wrapped in p.

Since the numbers are not ascribed any meaning, it doesn't seem like g serves any practical purpose but to compare the output of an arbitrarily given set of f1 and f2 against an arbitrary test that isn't given.
Catch-all patterns are often bad:
```
  ...
| _ => 0
```
Nothing else matches.
The reason is that if you extend pattern with additional types of patterns, the compiler will not notify you of a missing pattern in the function g; the catch-all will erroneously imply meaning for cases that are possibly yet undefined.

Pattern Matching SML?

1 Answers