CODEWITHSUNDEEP
pattern-matchingsml
Har
Har

Reputation: 3908

SML: how are constructors and functions distinguished?

I have the following two "functions": is_three and SOME

fun is_three(number) =
    case numbers of
        3 => true
       | _ => false

When I write in the following two statements I get this:

is_three; 
val it = fn : int -> bool
SOME;
val it = fn : 'a -> 'a option

from the surface they both seem to be functions which return values. However if i try using is_three in a case statement I get the following:

stdIn:20.9-20.19 Error: non-constructor applied to argument in pattern: is_three

 fun are_threes(numbers) =
     case numbers of
         [] => true
       | is_three(x)::xs => true andalso are_threes(xs)
  1. how can the case statement distinguish whats a constructor and whats a function
  2. Why are functions not allowed in case statements?

Upvotes: 1

Views: 1908

Answers (2)

John Coleman
John Coleman

Reputation: 51998

1) Since a function call is not a valid pattern, there is nothing to distinguish. While it is true that in something like

val x = FOO y

it is not possible without further context to tell if FOO y is a function or a datatype constructor (although naming conventions would suggest the latter), in the context of pattern matching, there is no possible ambiguity. FOO y is a valid pattern if FOO is a datatype constructor but not if FOO is a function.

2) As to why, suppose that you could have functions appearing in patterns. Say you had the following two functions

fun square x = x*x
fun cube x = x*x*x

What if you could define a function like this:

fun f (square x) = x+1
|   f (cube x) = x+2
|   f _ = 3

What should f 64 be? 64 is square 8 so should it be 8+1 = 9? Or should it be 4+2 = 6 since cube 4 = 64? In any event -- how is the compiler supposed to recognize an instance of such a pattern? In general, even if a function g is computable, it might be undecidable if a given value is in the range of g. Furthermore, note that recovering x = 4 from the value 64 with pattern-matching against the "pattern" cube x would require inverting the function cube. It is too much to expect the compiler to invert arbitrary functions, especially since it is generally impossible.

In a sense, a weak form of the sort of thing you are talking about was implemented in Haskell in the form of n+k patterns . These were considered by many to be a bad idea and were eventually dropped from the language.

Upvotes: 2

Justin Raymond
Justin Raymond

Reputation: 3558

The language specification makes a distinction between functions and constructors. So even though the type of a constructors may look like functions, there are different rules for how constructors and functions may be used. Constructors may be used in case expressions, functions cannot.

The reason for this at a language design level is that constructors and functions are different concepts. Constructors are the "introduction form" of data types and pattern-matches are the "elimination form" of data types. That is, constructors are how we create values, pattern-matching is how we "use up" values. For example, we use [] and :: to construct a list of values. To use the list of values, we pattern-match on the list to extract the head and the tail. In contrast, a function is a relation between inputs and outputs that may or may not contain constructors and pattern-matches.

The second question is a more difficult to answer. First of it is not entirely clear what you mean in your example | is_three(x)::xs => true andalso are_threes(xs). Presumably you meant match x::xs with numbers and succeed if is_three(x). Under this interpretation, the pattern match you wrote is incomplete (what happens when is_three is false?). The function can already be expressed quite concisely as expressed as

 fun are_threes(numbers) =
 case numbers of
     [] => true
   | x::xs => is_three(x) andalso are_threes(xs)

There is a language extension in Haskell called view patterns, which lets you write functions in patterns.

Upvotes: 2

Related Questions