Without using any of ( = , <= , >= , < , >, <> ), write a ML (SML; Standard Meta

Question

Without using any of ( = , <= , >= , < , >, <> ), write a ML (SML; Standard Meta Language) function that takes a list and an integer n and returns true if the list has exactly n elements and false otherwise. Use Pattern Matching.
Without using any of ( = , <= , >= , < , >, <> ), write a ML (SML; Standard Meta Language) function that takes a list and an integer n and returns true if the list has exactly n elements and false otherwise. Use Pattern Matching.
Without using any of ( = , <= , >= , < , >, <> ), write a ML (SML; Standard Meta Language) function that takes a list and an integer n and returns true if the list has exactly n elements and false otherwise. Use Pattern Matching.

Explanation / Answer

This can be rewritten using a case statement like this:

or as a lambda function:

Here, the keyword val introduces a binding of an identifier to a value, fn introduces the definition of an anonymous function, and case introduces a sequence of patterns and corresponding expressions.

Using a local function, this function can be rewritten in a more efficient tail recursive style.

(The value of a let-expression is that of the expression between in and end.) The encapsulation of an invariant-preserving tail-recursive tight loop with one or more accumulator parameters inside an invariant-free outer function, as seen here, is a common idiom in Standard ML, and appears with great frequency in SML code.

Type synonyms[edit]

A type synonym is defined with the type keyword. Here is a type synonym for points in the plane, and functions computing the distances between two points, and the area of a triangle with the given corners as per Heron's formula.

Algebraic datatypes and pattern matching[edit]

Standard ML provides strong support for algebraic datatypes. An ML datatype can be thought of as a disjoint union of tuples (or a "sum of products"). They are easy to define and easy to program with, in large part because of Standard ML's pattern matching as well as most Standard ML implementations' pattern exhaustiveness checking and pattern redundancy checking.

A datatype is defined with the datatype keyword, as in

(See above for the definition of loc.) Note: datatypes, not type synonyms, are necessary to define recursive constructors. (This is not at issue in the present example.)

Order matters in pattern matching; patterns that are textually first are tried first. Pattern matching can be syntactically embedded in function definitions as follows:

Note that subcomponents whose values are not needed in a particular computation are elided with underscores, or so-called wildcard patterns.

The so-called "clausal form" style function definition, where patterns appear immediately after the function name, is merely syntactic sugar for

Pattern exhaustiveness checking will make sure each case of the datatype has been accounted for, and will produce a warning if not. The following pattern is inexhaustive:

There is no pattern for the Triangle case in the center function. The compiler will issue a warning that the pattern is inexhaustive, and if, at runtime, a Triangle is passed to this function, the exception Match will be raised.

The set of clauses in the following function definition is exhaustive and not redundant:

If control gets past the first pattern (the Circle), we know the value must be either a Square or a Triangle. In either of those cases, we know the shape has corners, so we can return true without discriminating which case we are in.

The pattern in the second clause of the following (meaningless) function is redundant:

Any value that matches the pattern in the second clause will also match the pattern in the first clause, so the second clause is unreachable. Therefore, this definition as a whole exhibits redundancy, and causes a compile-time warning.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.