CODEWITHSUNDEEP
pattern-matchingsmlml
Tim
Tim

Reputation: 99526

Why are the concatenation operator @ or arithmetic operators not legal pattern constructors?

In Ullman's SML book

There are some other patterns that make sense but are illegal in ML. For example, we might expect to be able to construct patterns using the concatenation operator @ or arithmetic operators.

Example 3.20: We might expect to be able to break a list into the last element and the rest of the list. For instance, we might try to compute the length of a list by

fun length(nil) = 0
| length(xs@[x]) = 1 + length(xs);
Error: non-constructor applied to argument in pattern: @
Error: unbound variable or constructor: xs

However, as we can see, the pattern xs@ [x] is not legal and triggers two error messages. The first message complains that @ is not a legal pattern constructor.

Incidentally, we get a similar pair of error messages if we try to use an arithmetic operator to construct a pattern. For instance,

fun square(0) = 0
| square(x+l) = 1 + 2*x + square(x);

is equally erroneous, even though it is based on a correct inductive definition of x^2.

Is the fact that the concatenation operator @ or arithmetic operators are not legal pattern constructors an intentional design? Why is it?

Is it also true in most other languages with pattern matching?

Upvotes: 0

Views: 104

Answers (2)

Andreas Rossberg
Andreas Rossberg

Reputation: 36118

Pattern matching can only inspect the structure of values, it cannot reverse arbitrary expressions. 5 is a value. But 3 + 2 is not, it is an expression that produces a value.

Similarly, C(x, y) is a value for any C that is a datatype constructor and any x, y that are themselves values. Lists are merely an instance of this case: :: is a datatype constructor, the list type is predefined as

datatype 'a list = nil | :: of 'a * 'a list

(And the [x,y,z] notation is just a shorthand for x :: y :: z :: nil.)

Again, x @ y is different, because @ is a function that performs a computation, not a constructor. Pattern matching can't run functions backwards.

Conceptually, values form trees, e.g., 5 :: nil is the tree whose root is the :: constructor and whose two leafs are 5 and nil. Pattern matching only describes possible destructurings of these trees, not computations on trees. The upshot is that each pattern is unambiguous and matching performance linear in the size of the pattern.

And yes, this is the case in all languages.

Upvotes: 2

Sam Westrick
Sam Westrick

Reputation: 1286

Yes, it is intentional.

@ would allow for ambiguous patterns. If you permitted it as a pattern, what should be the meaning of the following? Where do you split the input list?

fun foo (a @ b) =
  Int.max (List.length a, List.length b)

val x = foo [1,2,3,4,5]  (* ??? *)

There is a similar problem for +. A function that takes an integer as argument, and is defined over patterns x+y, could choose any two values x and y that sum to the argument, so the meaning of the pattern is ambiguous. This is further complicated by overflow issues... e.g. if you had a function fun f (x+1) = ... and then gave the minimum integer as argument to f, what should happen?

Upvotes: 1

Related Questions