(* this program is in response to George White's question about  *)
(* mixing types.  US Postal Codes are integers and Canadian ones *)
(* are strings.  Define a postal code to be "special" if it is   *)
(* American and prime or if it is Canadian and a palindrome.     *)
(* Write a function that is true of special codes and false of   *)
(* all others.  *)

(*  The solution is to define a type POSTAL_CODE which is the disjoint *)
(*  union of types string and integer. In order to do this we must     *)
(*  define two constructors -- a special kind of function -- one that  *)
(*  converts  strings to POSTAL_CODE and one that converts integer to  *)
(*  POSTAL_CODE.  What's special about the constructors is that they   *)
(*  "tag along" with the value they're applied to and can be picked    *)
(*  off later in pattern matching in order to recover the original     *)
(*  string or integer.   *)


datatype POSTAL_CODE = US of int  | CDN of string;


(*  First we need a primality testing function (type= int -> bool) *)
(* We'll directly implement the definition  *)
(* prime x = "for all Y between" 2 and (SQRT X), "can't evenly divide X by Y" *)

(* Auxiliary functions:  *)
(*    " can't evenly divide X by Y"  *)
(*         has type int *int -> bool *)
(*    "FOR ALL Y between Arg1, Arg2, Arg3  *)
(*         has type int*real*(int*int -> bool) -> bool  *)
(*         but it's only defined in the context of a particular X *)

fun can't_evenly_divide (X,Y) = (X mod Y) <> 0;

fun prime X =
let fun for_all_Y_between (Arg1,Arg2,Arg3) =
        if Arg1 > floor(Arg2)
        then true
        else if Arg3 (X,Arg1)
             then for_all_Y_between(1+Arg1,Arg2,Arg3)
             else false
in
  for_all_Y_between (2,sqrt(real(X)),can't_evenly_divide)
end
;

(* Similarly we'll directly implement the definition of a palindrome  *)
(* There are many definitions of palindrome -- I'll use the easiest because  *)
(* it illustrates an interesting feature of ML's built-in equality predicate *)
(* X is a palindrome = X = (reverse X)  *)

fun reverse [] = []
 |  reverse (head::tail) = (reverse tail) @ [head]
;

fun palindrome_for_lists X = (X = (reverse X));

val palindrome = palindrome_for_lists o explode;

(* the interesting point is the type of palindrome_for_lists -- look  *)
(* carefully and you'll see it's  ''a list -> bool.  ''a means  *)
(* any EQUALITY TYPE (but not any type whatsoever - for example you could  *)
(* not pass a list of functions to palindrome_for_lists  because there is  *)
(* no way to check for equality of functions).  Most types that don't involve *)
(* functions are EQUALITY types, including user defined types.  For example,  *)
(* our POSTAL_CODE is an equality type: ML treats to constants of this type   *)
(* as equal if they have the same constructor applied to equal values.  *)

(* With all these functions defined, SPECIAL is a piece of cake *)

fun special (US  code) = prime code
 |  special (CDN code) = palindrome code
;

(* Here's how this is used, and how postal codes are built out of integers  *)
(* and reals.  *)

val c1 = (US 78731);
val c2 = (CDN "K1N N1K"); (* sorry George, no legal Canadian code is a  *)
                          (* palindrome because letters & digits alternate *)

(* here's a function that takes in a string and converts to  *)
(* a postal code  (i.e. detects if the string consists only of digits and *)
(* if so make it  *)

exception not_a_number;

(* the following function assumes the string has been transformed into  *)
(* a list of characters with the low order digits at the HEAD of the list *)

fun convert     []      = 0
 |  convert ("0"::tail) =     10* convert tail
 |  convert ("1"::tail) = 1 + 10*(convert tail)
 |  convert ("2"::tail) = 2 + 10*(convert tail)
 |  convert ("3"::tail) = 3 + 10*(convert tail)
 |  convert ("4"::tail) = 4 + 10*(convert tail)
 |  convert ("5"::tail) = 5 + 10*(convert tail)
 |  convert ("6"::tail) = 6 + 10*(convert tail)
 |  convert ("7"::tail) = 7 + 10*(convert tail)
 |  convert ("8"::tail) = 8 + 10*(convert tail)
 |  convert ("9"::tail) = 9 + 10*(convert tail)
 |  convert     _       = raise not_a_number;

                              
fun convert_string_to_postal_code s =
     US (convert (reverse (explode s)))
     handle not_a_number => (CDN s)
;

(* and to abbreviate that terribly long name.. *)

val pc = convert_string_to_postal_code;

(* just to illustrate the equality type business... *)

val c3 = (pc "78731");

val c3equalsc1 = c3 = c1;
val c3equalsc2 = c3 = c2;