ML

These two days I learn how to program with ML that is a functional programming language, quite different from what I have known.

Data types supported: int, real, bool, char #”a”, string “a”, list[, , , ] “::, nil, @”, tuple().

Two ways for programming:

(1) binding symbols: val ……;

(2) define functions: fun …….
1. simple function definitions:

fun function_name parameter = expression;
2. A binding allows us to refer an item to a symbolic name.

val symbolic_name = expression;

3. While a tuple() allows its components to be of mixed types and is of fixed length, a list[] must have identical typed components and may be of any length.
4. A function of more than one argument may be implemented as a function of a tuple or a “curried” function. (After H B Curry).

fun add(x,y)=x+y:int;

fun add x y = x+y:int; The type of this function is int->(int->int). It is a function which takes an integer and returns a function from an integer to an integer.

5. About list:

Usually a list is expressed as h::t, where h is the first element of the list. The common operators are :: and @, both of which are used to construct functions.

6. Map

fun map f nil = nil

| map f (h::t) = (f h)::(map f t);

For example, val doublist= map (fn x=>2*x);

7. Reduce takes a binary function (a function with two inputs) a base value and a list. It applys the function repeatedly down the list.
fun reduce f b nil = b

| reduce f b (h::t) = f(h,reduce f b t);
For example, val flatten = reduce (fn(a,b)=>a@b) nil;

8. Zip can be used to apply a binary function (one with two inputs) to the corresponding elements of two lists.

fun zip f nil nil = nil

| zip f (h::t) (i::u) = f(h, i) ::zip f t u;

9. Filter takes a predicate (a function which returns true or false) and a list. It returns the list with only those items for which the predicate s true.

fun filter f nil = nil

| filter f (h::t) = if f h then h::filter f t else filter f t;

10. other common functions:

fun member x nil = false

| member x (h::t) = x=h orelse member x t;

————————————————

fun fst(a,_) = a; (* Also try #1 *)

————————————————
fun snd(_,b) = b; (* Try #2 *)

10. Nested definitions: let … in … end

fun sort nil = nil : int list

| sort(h::t) = let

fun insert(i,nil) = [i]

| insert(i,h::t) = if i > h then i::h::t else h::insert(i,t)

in insert(h, sort t) end;

——————————————————————–

fun rev l = let

fun reva(nil,acc) = acc

| reva(h::t,acc) = reva(t,h::acc)

in reva(l,nil) end;

—————————————————————————
fun power(x,0) = 1

| power(x,n) = let

fun even n = (n mod 2) = 0 val s = power(x, n div 2)

in if even x then s*s else x*s*s end;

—————————————————————–

fun minmax [x] = (x, x)

| minmax(h::t) = let

val (mn, mx) = minmax t

in (min(h,mn),max(h,mx)) end;