- 2+3; val it = 5 : int - 7-4; val it = 3 : int
- 5 * 3 ; val it = 15 : int - 5 * 3 ; val it = 15 : int - 5*3; val it = 15 : int
- 6 = -1 = ; val it = 5 : int
Canonical values evaluate to themselves.
- 6; val it = 6 : int - 11; val it = 11 : int
- 2+3; 4-5; 6*7; val it = 5 : int val it = ~1 : int val it = 42 : int - ~5; (* unary negation *) val it = ~5 : int - 37 div 5; 37 mod 5; val it = 7 : int val it = 2 : int - (3+4)*2; val it = 14 : int - Int.min (2+3, 2-3); (* "min" is an operation from the "Int" module *) val it = ~1 : int - "this is a string"; val it = "this is a string" : string - size "string"; val it = 6 : int - size ""; val it = 0 : int - "abc" ^ "defg"; val it = "abcdefg" : string - #"A"; #"B"; val it = #"A" : char val it = #"B" : char - true; false; val it = true : bool val it = false : bool - not true; (* boolean negation *) val it = false : bool - not false; val it = true : bool - if true then "then" else "else"; val it = "then" : string - if false then if true then 1 else 2 else if false then 3 else 4; val it = 4 : int - if true then 2 else 37 div 0; val it = 2 : int - if false then 37 div 0 else 3; val it = 3 : int - 2=2 orelse 37 div 0 = 5; val it = true : bool - 2=0 andalso 37 div 0 = 5; val it = false : bool - 1=1; val it = true : bool - 2=4; val it = false : bool - "string" = "string"; val it = true : bool - if 1=2 then 3 else 4; val it = 4 : int - 3.14159; (* an approximation of pi *) val it = 3.14159 : real - 123.456E7; val it = 1234560000.0 : real - 1.2 + 3.4; (* '+' overloaded: int and real *) val it = 4.6 : real - 1.2 - 3.4; val it = ~2.2 : real - 1.2 * 3.4; val it = 4.08 : real - 7.2 / 4.8; val it = 1.5 : real - 3.1415926535; (* an approximation of pi *) val it = 3.1415926535 : real - 2.7182818284; val it = 2.7182818284 : real - Math.e; val it = 2.71828182846 : real - Math.cos (Math.pi/2.0); val it = 0.0 : real - Math.sqrt (49.01); val it = 7.00071424927 : real - Int.min (ceil 3.4, floor 3.4); val it = 3 : int - (); val it = () : unit
- (true, (), 1); val it = (true,(),1) : bool * unit * int - (2, "ab", 2*2, 5.0); val it = (2,"ab",4,5.0) : int * string * int * real - ( 2 ); (* No such thing as a one-tuple *) val it = 2 : int - ((())); val it = () : unit - ((2,3,4), (true,3.3)); val it = ((2,3,4),(true,3.3)) : (int * int * int) * (bool * real) - #2 ("one", 2, "three"); (* projection *) val it = 2 : int
- {abscissa=1.2, ordinate=3.2}; val it = {abscissa=1.2,ordinate=3.2} : {abscissa:real, ordinate:real} - {make="Toyota", model="Corolla", year=1986, color="silver"}; val it = {color="silver",make="Toyota",model="Corolla",year=1986} : {color:string, make:string, model:string, year:int} - {x_dim=2, y_dim=3} = {y_dim=3, x_dim=2}; (* order irrelevant *) val it = true : bool - {a = (), b = 2, c = ("s",2), d = 1}; val it = {a=(),b=2,c=("s",2),d=1} : {a:unit, b:int, c:string * int, d:int} - {a = 2.3, b = {a="s",c=45}}; val it = {a=2.3,b={a="s",c=45}} : {a:real, b:{a:string, c:int}} - {one = (2.3, "string")}; val it = {one=(2.3,"string")} : {one:real * string} - {1=(), 2=true, 3=1}; (* n-tuples are records *) val it = ((),true,1) : unit * bool * int - {1=(), 3=1, 2=true}; val it = ((),true,1) : unit * bool * int - {1=(), 3=1}; val it = {1=(),3=1} : {1:unit, 3:int} - {34564=1, b=2, b3=3, <*> =4}; val it = {34564=1,<*>=4,b=2,b3=3} : {34564:int, <*>:int, b:int, b3:int} - {1=1, 01=01, 001=001} (* Error! *) stdIn:23.5-23.10 Error: syntax error: deleting COMMA INT0 EQUALOP - #a {a=3}; (* field selection *) val it = 3 : int - # a{z=1.2, a=3, b=true, 4=()}; val it = 3 : int - #a (#b {b={a=3}}); val it = 3 : int - let val r = {r=3} in # r r end; val it = 3 : int - let val ### = 3 in # ## {## = ###} end; val it = 3 : intNumbers are allowed as labels in ML records. And these make it possible to treat tuples as as special case of records. The case where the labels are implicit with numbers in order.
- [1,2,3,4]; val it = [1,2,3,4] : int list - [true,false,false]; val it = [true,false,false] : bool list - ["a","bc","def","ghij"]; val it = ["a","bc","def","ghij"] : string list - [(8,true),(5,false)]; val it = [(8,true),(5,false)] : (int * bool) list - [1,2,3.14159,4]; (* Error! *) stdIn:17.1-17.16 Error: operator and operand don't agree [literal] operator domain: real * real list operand: real * int list in expression: 3.14159 :: 4 :: nil - 1 :: [2,3,4]; 1 :: 2 :: [3,4]; (* binary, infix "cons" op *) val it = [1,2,3,4] : int list val it = [1,2,3,4] : int list - [1,2,3] @ [4,5]; (* binary, infix append op *) val it = [1,2,3,4,5] : int list - [("abcd", 4), ("xyz", 3)]; val it = [("abcd",4),("xyz",3)] : (string * int) list - (["abcd", "xyz"], [4, 3,2,1]); val it = (["abcd","xyz"],[4,3,2,1]) : string list * int list - [[2,4,6], [2,3,5,7], [2,4,8,16,32]]; val it = [[2,4,6],[2,3,5,7],[2,4,8,16,32]] : int list listThe notation with the square brackets is just a special syntax of building up lists using the constructors
:: and nil.
- 1::2::3::4::nil; val it = [1,2,3,4] : int list - true::false::false::nil; val it = [true,false,false] : bool list - "a"::"bc"::"def"::"ghij"::nil; val it = ["a","bc","def","ghij"] : string list - (8,true)::(5,false)::nil; val it = [(8,true),(5,false)] : (int * bool) list - (2::4::6::nil) :: (2::3::5::7::nil) :: (2::4::8::16::32::nil) :: nil; val it = [[2,4,6],[2,3,5,7],[2,4,8,16,32]] : int list listIt is important in SML to distinguish constructors from ordinary functions. Constructors are the primitive functions that create new values of a data. For example, the constructors for lists are
:: and nil.
The append function @ is not a constructor
(it can be defined using :: and nil).
- val a = 2; (* Bind the value 2 to a. *) val a = 2 : int - a; (* Respond with the value of a. *) val it = 2 : int - 3*a + 4*a*a; (* Use the value of a in an expression. *) val it = 22 : int - val b = 3 * 4 + 5; val b = 17 : int - val c = 2 * b; (* Use value of b in binding of c. *) val c = 34 : int - val a = 3; (* This binding hides previous bindings. *) val a = 3 : int - a; (* Respond with value of visible binding. *) val it = 3 : int - val <=> = (~1,0,1); (* A symbolic identifier <=> *) val <=> = (~1,0,1) : int * int * int - 6*5*4; (* Expressions are really bindings to "it". *) val it = 120 : int - val c = it div (3*2); val c = 20 : int - it; val it = 120 : int - val a = 4; (* Global binding to a. *) val a = 4 : int - let val a = 5 in a+6 end; (* Local binding to a. *) val it = 11 : int - a; (* No change in a. *) val it = 4 : int - let val p = 87187 * 3797 in (p, p+2, p+4) end; val it = (331049039,331049041,331049043) : int * int * int - val pi2 = let val pi = 3.14 in 2.0 * pi end; val pi2 = 6.28 : real
- local = val pi = 3.14 = in = val pi2 = 2.0 * pi = end; val pi2 = 6.28 : real - val a = 0 and b = 1 and c = 7.8; val a = 0 : int val b = 1 : int val c = 7.8 : real - let = val c = 3 and d = 4 (* Two local, independent bindings. *) = in = (c * d) div 3 = end; val it = 4 : int - let val e = 5 and f = e+1 in e+f end; (* Error! *) stdIn:24.23 Error: unbound variable or constructor: e - let = val c = 3; val d = c+1; (* These bindings are dependent *) = in = (c * d) div 3 = end; val it = 4 : int - let = val c = 3 = in = let val d = c+1 in (c * d) div 3 end = end; val it = 4 : int
- val (fst, snd) = (4, 4.45); val fst = 4 : int val snd = 4.45 : real - val (a,b,c) = (1,3,6); (* Matching in declaration *) val a = 1 : int val b = 3 : int val c = 6 : int - val {1=a, 2=b, 3=c} = {1=1,2=3,3=6}; val a = 1 : int val b = 3 : int val c = 6 : int - val {abscissa=x, ordinate=y} = {abscissa=1.2, ordinate=3.2}; val x = 1.2 : real val y = 3.2 : real - val {abscissa=x, ordinate=y} = {ordinate=3.2, abscissa=1.2}; val x = 1.2 : real val y = 3.2 : real - val {b=x, ...} = {a=2, b="s", c=3.4, d=[1,2]}; val x = "s" : string - val {2=x, ...} = (1,2,3); val x = 2 : int - val {frac=x, ...} = Real.split 37.4321; val x = 0.4321 : real - val x = 3; val x = 3 : int - val (x,x) = (2,3); (* Error! *) stdIn:22.1-22.18 Error: duplicate variable in pattern(s): x - val (head::rest) = 3*4; (* Error! *) stdIn:1.1-2.18 Error: pattern and expression in val dec don't agree [literal] pattern: 'Z list expression: int in declaration: head :: rest = (case (3 * 4) of head :: rest => (head,rest)) - val (head::rest) = [1,2,3] @ [4,5,6]; stdIn:1.1-2.32 Warning: binding not exhaustive head :: rest = ... val head = 1 : int val rest = [2,3,4,5,6] : int list - val (head::rest) = [] @ (tl [1]); (* Runtime error! *) stdIn:23.1-23.33 Warning: binding not exhaustive head :: rest = ... uncaught exception nonexhaustive binding failure raised at: stdIn:23.1-23.33 - val (x,_,y) = (1,2,3); (* wildcard pattern *) val x = 1 : int val y = 3 : int - val (x,_,y,_) = (1,2,3,4); val x = 1 : int val y = 3 : int - val head :: _ = [1, 2, 3]; stdIn:25.1-25.26 Warning: binding not exhaustive head :: _ = ... val head = 1 : int - val x as (fst,snd) = (2, true); (* layered pattern *) val x = (2,true) : int * bool val fst = 2 : int val snd = true : bool - val list as head :: tail = [1, 2, 3]; stdIn:27.1-27.37 Warning: binding not exhaustive list as head :: tail = ... val list = [1,2,3] : int list val head = 1 : int val tail = [2,3] : int list - val (x,1) = (7,1); stdIn:28.1-28.18 Warning: binding not exhaustive (x,1) = ... val x = 7 : int - val 1 = 1; stdIn:29.1-29.10 Warning: binding not exhaustive 1 = ... - val 1 = 2; (* Runtime error! *) stdIn:30.1-30.10 Warning: binding not exhaustive 1 = ... uncaught exception nonexhaustive binding failure raised at: stdIn:30.1-30.10 - val (x,y,_)::_ = [(2,3,4),(5,6,7)]; stdIn:1.1-2.30 Warning: binding not exhaustive (x,y,_) :: _ = ... val x = 2 : int val y = 3 : intOnly certain functions, constructors, can be used in patterns.
:: is a constructor, hence it can be use in a pattern.
@ is not. Neither is +.
- (fn x => x+1); (* A function object: successor function *) val it = fn : int -> int - val f = (fn x => x+1); (* Bind f to the successor function *) val f = fn : int -> int - f; val it = fn : int -> int - f (2); (* Function application *) val it = 3 : int - f 2; (* Parens not needed, if arg a token. *) val it = 3 : int - 3 2; (* Type error! *) stdIn:18.1-18.4 Error: operator is not a function [literal] operator: int in expression: 3 2 - f (true); (* Type error! *) stdIn:1.1-2.4 Error: operator and operand don't agree [tycon mismatch] operator domain: int operand: bool in expression: f true - f 2 * 4; (* Application binds tightest. *) val it = 12 : int - (fn x => x+1) 8; (* Name not needed to apply to arg *) val it = 9 : int - val f = (fn n => n+1); (* Definition of the function f. *) val f = fn : int -> int - fun f (n) = n+1; (* Same function, alternative syntax. *) val f = fn : int -> int - fun sq (x:real) = x*x; val sq = fn : real -> real - fun abs n = if n<0 then ~n else n; val abs = fn : int -> int - [fn n=>n+1, fn m=>2*m, fn n=>n div 2]; val it = [fn,fn,fn] : (int -> int) list - (fn n=>2*n,fn r=>ceil r); val it = (fn,fn) : (int -> int) * (real -> int) - ((fn x=>x+2) 4, (fn x=>x*3) 7); val it = (6,21) : int * int - fun f(x) = x+2; fun g(x) = x*3; (* h, j use these functions. *) val f = fn : int -> int val g = fn : int -> int - (f(4), g(7)); val it = (6,21) : int * int - fun h (x) = (f x, g x); h (4); h (7); (* functions and tuples. *) val h = fn : int -> int * int val it = (6,12) : int * int val it = (9,21) : int * int - fun j (x) = [f x, g x]; j (4); j (7); (* functions and lists. *) val j = fn : int -> int list val it = [6,12] : int list val it = [9,21] : int list - #1 (fn x => x+1, fn y => y-1) 8; val it = 9 : int - val a = 1; (* SML uses static binding *) val a = 1 : int - fun f(x) = x+a; f(4); val f = fn : int -> int val it = 5 : int - val a = 3; val a = 3 : int - f(4); (* f(4) still has the value 5. *) val it = 5 : int - let val a = 1 in = let fun f(x) = x+a in = let val a = 3 in = f(4) = end = end = end; val it = 5 : int
- fun fact (n) = if n=0 then 1 else n*fact(n-1); val fact = fn : int -> int - fact (8); val it = 40320 : int - val fact' = (fn n => if n=0 then 1 else n*fact'(n-1)); (* Error! *) stdIn:15.43-15.48 Error: unbound variable or constructor: fact' - val rec fact = (fn n => if n=0 then 1 else n*fact(n-1)); val fact = fn : int -> int - fun gcd (n,m) = if m=0 then n else gcd (m,n mod m); val gcd = fn : int * int -> int - fun exp (b,n) = if n=0 then 1.0 else b * exp (b,n-1); val exp = fn : real * int -> real - fun mc91 (n) = if n>100 then n-10 else mc91 (mc91 (n+11)); (* McCarthy's 91 fun *) val mc91 = fn : int -> int - map mc91 [103, 102, 101, 100, 99, 98, 97, 96]; val it = [93,92,91,91,91,91,91,91] : int list - fun alt n = if n>100 then n-10 else 91; val alt = fn : int -> int - mc91(95)=alt(95); mc91(90)=alt(90); mc91(20)=alt(20); val it = true : bool val it = true : bool val it = true : bool - fun (* mutually recursive function definitions *) = odd (n) = if n=0 then false else even (n-1) = and = even (n) = if n=0 then true else odd (n-1); val odd = fn : int -> bool val even = fn : int -> bool - fun (* mutually recursive function definitions *) = take nil = nil | take (x::xs) = x::(skip xs) = and = skip nil = nil | skip (x::xs) = take xs; val take = fn : 'a list -> 'a list val skip = fn : 'a list -> 'a list - take [1,2,3]; skip [1,2,3,4]; val it = [1,3] : int list val it = [2,4] : int list
- fun f (x:int*int) = (#1 x) div (#2 x); val f = fn : int * int -> int - f (12,3); (* function f applied to pair (12,3) *) val it = 4 : int - val p = (12,3); (* define a pair p *) val p = (12,3) : int * int - f p; (* function f applied to pair p *) val it = 4 : int - fun f (x,y) = x div y; val f = fn : int * int -> int - fun g (x,y,z) = x+2*y*z; val g = fn : int * int * int -> int - fun h (x,y) = (x div y, x mod y); val h = fn : int * int -> int * int - fun roots (a,b,c) = = let = val d = Math.sqrt (b*b - 4.0*a*c) = in = ((~b + d) / (2.0*a), (~b - d) / (2.0*a)) = end; val roots = fn : real * real * real -> real * real - roots(1.0,2.0,~1.2); val it = (0.483239697419,~2.48323969742) : real * real - let val t =(1.0,2.0,~1.2) in roots t end; val it = (0.483239697419,~2.48323969742) : real * real - Real.fmt (StringCvt.FIX(SOME 3)) (#1 let val t =(1.0,2.0,~1.2) in roots t end); val it = "0.483" : string - fun l (x as (fst,snd)) = (x,fst div snd); (* layered patterns *) val l = fn : int * int -> (int * int) * int - fun j ((x,y), (a,b,c)) = f(x,y) - g(a,b,c); (* tuples of tuples *) val j = fn : (int * int) * (int * int * int) -> int - fun j (p,t) = f(p) - g(t); (* simpler alternative *) val j = fn : (int * int) * (int * int * int) -> int - fun = tuition {name=_, id=_, courses=nil} = 1000 | = tuition {courses=[_], ...} = 2000 | = tuition {id,...} = if id>500000 then 5000 else 4000; val tuition = fn : {courses:'a list, id:int, name:'b} -> int - val Norm's_Record = {id=123456, name="Norm dePlume", courses=["cse1001", "mth1001"]}; val Norm's_Record = {courses=["cse1001","mth1001"],id=123456,name="Norm dePlume"} : {courses:string list, id:int, name:string} - tuition Norm's_Record; val it = 4000 : int - fun sum (nil) = 0 | sum (head::tail) = head+sum(tail); val sum = fn : int list -> int - fun (* Error! *) = f (x,y) = x+y+1 | = f (x,y,z) = x+y+z+2 | = f _ = 3 ; stdIn:39.1-42.15 Error: parameter or result constraints of clauses don't agree [tycon mismatch] this clause: 'Z * 'Y * 'X -> 'W previous clauses: 'V * 'U -> 'W in declaration: f = (fn (x,y) => <exp> + <exp> + 1 | (x,y,z) => <exp> + <exp> + 2 | _ => 3) - fun f(0) = "zero" | f(_) = "nonzero"; val f = fn : int -> string - fun f(_) = "nonzero" | f(0) = "zero"; (* Error! *) stdIn:43.1-43.37 Error: match redundant _ => ... --> 0 => ... - fun h (head::rest) = head+1; stdIn:1.1-2.23 Warning: match nonexhaustive head :: rest => ... val h = fn : int list -> int - h [3,17,435]; val it = 4 : int - h (nil); (* We were warned a runtime error possible! *) uncaught exception nonexhaustive match failure raised at: stdIn:2.17 - fun f (x,y,2) = x+y+2; stdIn:1.1-2.17 Warning: match nonexhaustive (x,y,2) => ... val f = fn : int * int * int -> int - f (3,17,2); val it = 22 : int - f (1,2,3); (* Error! *) uncaught exception nonexhaustive match failure raised at: stdIn:2.12 - fun f[x,y,z] = (x,x+y+1,x+y+z+2); stdIn:1.1-46.10 Warning: match nonexhaustive x :: y :: z :: nil => ... val f = fn : int list -> int * int * int - f [1,2,3]; val it = (1,4,8) : int * int * int - f [1,2]; (* Error! *) uncaught exception nonexhaustive match failure raised at: stdIn:2.11 - let val x=0 in if x=0 then 0 else 100 div x end; val it = 0 : int - fun If (x,y,z) = if x then y else z; val If = fn : bool * 'a * 'a -> 'a - let val x=0 in If (x=0, 0, 100 div x) end; uncaught exception divide by zero raised at: <unknown file> - infix 6 or; infix 6 or - fun x or y = x orelse y; val or = fn : bool * bool -> bool - infix 7 &; infix 7 & - fun x & y = x andalso y; (* & is a symbolic identifier *) val & = fn : bool * bool -> bool
- fun id x = x; val id = fn : 'a -> 'a - (id 1, id "two"); val it = (1,"two") : int * string - fun fst (x,y) = x; val fst = fn : 'a * 'b -> 'a - fun snd (x,y) = y; val snd = fn : 'a * 'b -> 'b - fst (1,"two"); val it = 1 : int - fst ([true, false], 3.14159); val it = [true,false] : bool list - fst (1,"two") + snd ((1,2), hd [1,2,3]); val it = 2 : int - nil; val it = [] : 'a list - null; val it = fn : 'a list -> bool - hd; val it = fn : 'a list -> 'a - tl; val it = fn : 'a list -> 'a list - fun switch (x,y) = (y,x); val switch = fn : 'a * 'b -> 'b * 'a - switch (2, "abc"); val it = ("abc",2) : string * int - switch (2,3.14159); val it = (3.14159,2) : real * int - #2 (switch ([6,9], (fn x =>x))); val it = [6,9] : int list - fun null (nil) = true | null (_::_) = false; val null = fn : 'a list -> bool - fun length (x) = = if null x then 0 else length (tl x) + 1; val length = fn : 'a list -> int
- fun member (x, nil) = false | member (x, y::ys) = x=y orelse member (x,ys); val member = fn : ''a * ''a list -> bool - member ("me", ["you", "them", "me", "us"]); val it = true : bool - member ("me", ["you", "them", "us"]); val it = false : bool - fun insert (x, nil) = [x] = | insert (x,y::ys) = if x<y then x::y::ys else y :: insert (x,ys); val insert = fn : int * int list -> int list - insert (5, [1,2,3,4,6,7,8,9]); val it = [1,2,3,4,5,6,7,8,9] : int list - fun merge (xs,nil) = xs = | merge (nil,ys) = ys = | merge (x::xs,y::ys) = if x<y then x :: merge(xs,y::ys) else y :: merge(x::xs,ys); val merge = fn : int list * int list -> int list - merge ([1,2,3,4,5,100,102,104,106], [~1,4,10, 20,21,22,105,200]); val it = [~1,1,2,3,4,4,5,10,20,21,22,100,...] : int list
- local = fun rotate nil = nil | rotate (x::xs) = xs@[x] = in = fun boundaries l = ListPair.zip (l, rotate l) = end; val boundaries = fn : 'a list -> ('a * 'a) list - boundaries nil; stdIn:18.1-18.15 Warning: type vars not generalized because of value restriction are instantiated to dummy types (X1,X2,...) val it = [] : (?.X1 * ?.X1) list - boundaries [1]; val it = [(1,1)] : (int * int) list - boundaries [1,2,3,4,3,2,1]; val it = [(1,2),(2,3),(3,4),(4,3),(3,2),(2,1),(1,1)] : (int * int) list
- fun apply3 (f) = f(3); val apply3 = fn : (int -> 'a) -> 'a - fun fact (n) = if n=0 then 1 else n*fact(n-1); val fact = fn : int -> int - apply3 (fact); val it = 6 : int - apply3 (fn x => x+16); val it = 19 : int - apply3 (fn x => ({a=x}, true)); val it = ({a=3},true) : {a:int} * bool - fun min_2 (f,g,x) = Int.min (f x, g x); val min_2 = fn : ('a -> int) * ('a -> int) * 'a -> int - fun com_2 (h,f,g,x) = h (f x, g x); val com_2 = fn : ('a * 'b -> 'c) * ('d -> 'a) * ('d -> 'b) * 'd -> 'c - fun min_2 (f,g,x) = com_2 (Int.min, f, g, x); val min_2 = fn : ('a -> int) * ('a -> int) * 'a -> int
The key to functional programming is combining functions with other functions. What are the correct building blocks? Look for what is important---reoccuring patterns.
- fun = incr (nil) = nil | = incr (h::t) = (h+1) :: incr (t); val incr = fn : int list -> int list - fun = half (nil) = nil | = half (h::t) = (h/2.0) :: half (t); val half = fn : real list -> real list - val f = (fn x=>x+1); val f = fn : int -> int - fun = incr (f,nil) = nil | = incr (f,h::t) = f(h) :: incr (f,t); val incr = fn : ('a -> 'b) * 'a list -> 'b list - fun = map (f,nil) = nil | = map (f,h::t) = f(h) :: map (f,t); val map = fn : ('a -> 'b) * 'a list -> 'b list - map (fn x=>x+1, [1,2,3,4,5]); (* "map" sucessor func to list *) val it = [2,3,4,5,6] : int list - fun incr (list) = map (fn x=>x+1, list); val incr = fn : int list -> int list - incr [1,2,3,4,5]; (* new incr behaves as before *) val it = [2,3,4,5,6] : int list - map (fn x=>x/2.0, [2.0, 3.0, 4.0]); val it = [1.0,1.5,2.0] : real list - fun half (list) = map (fn x=>x/2.0, list); val half = fn : real list -> real list - half [2.0, 3.0, 4.0]; val it = [1.0,1.5,2.0] : real list - fun = gt0 (nil) = nil | = gt0 (h::t) = if h>0 then h::gt0(t) else gt0(t); val gt0 = fn : int list -> int list - fun = eqsq (nil) = nil | = eqsq (h::t) = if h*h=h then h::eqsq(t) else eqsq(t); val eqsq = fn : int list -> int list - fun filter (f,l) = = if null l = then [] = else if f(hd l) = then (hd l)::(filter (f, tl l)) = else filter (f, tl l); val filter = fn : ('a -> bool) * 'a list -> 'a list - fun = filter (f,nil) = nil | = filter (f,head::tail) = = if f(head) = then head::(filter (f, tail)) = else filter (f, tail); val filter = fn : ('a -> bool) * 'a list -> 'a list - filter ((fn x => x>0), [~1,0,1]); val it = [1] : int list - filter ((fn x => x*x=x), [~1,0,1]); val it = [0,1] : int list
- fun table (a, n, dx, F:real->real) = = if n<0 then nil else (a, F a) :: table (a+dx, n-1, dx, F); val table = fn : real * int * real * (real -> real) -> (real * real) list - table (0.0, 4, Math.pi/4.0, Math.sin); val it = [(0.0,0.0),(0.785398163397,0.707106781187),(1.57079632679,1.0), (2.35619449019,0.707106781187),(3.14159265359,0.0)] : (real * real) list - fun trapezoid (a, n, dx, F) = = if n<=0 then 0.0 else dx*(F(a)+F(a+dx))/2.0 + trapezoid (a+dx, n-1, dx, F); val trapezoid = fn : real * int * real * (real -> real) -> real - trapezoid (0.0, 4, Math.pi/4.0, Math.sin); val it = 1.89611889794 : real - trapezoid (0.0, 400, Math.pi/400.0, Math.sin); val it = 1.99998971915 : real - ~(Math.cos (Math.pi)) - ~(Math.cos (0.0)); (* integral of sin is -cos *) val it = 2.0 : real
- Int.fmt StringCvt.HEX 1200; (* format an integer *) val it = "4b0" : string - (Int.fmt StringCvt.HEX) 1200; (* application is left associative *) val it = "4b0" : string - Int.fmt StringCvt.HEX; (* function to format an integer *) val it = fn : int -> string - Int.fmt; (* notice that "->" is right associative *) val it = fn : StringCvt.radix -> int -> string - StringCvt.padLeft #" " 8 (Int.fmt StringCvt.HEX 1200); val it = " 4b0" : string - StringCvt.padLeft #" " 8; val it = fn : string -> string - StringCvt.padLeft #" "; val it = fn : int -> string -> string - StringCvt.padLeft; val it = fn : char -> int -> string -> string - val min = (fn x => fn y => Int.min (x,y)); val min = fn : int -> int -> int - fun min x = (fn y => Int.min (x,y)); val min = fn : int -> int -> int - fun min x y = Int.min (x,y); val min = fn : int -> int -> int"blob" "blob" is now easy to understand -- function, argument, function application. Now we have "blob" "blob" "blob" and this looks odd at first. Of course, it is really ("blob" "blob") "blob" which is clearly two function applications. But we have something completely different from ordinary imperative langauges here: ("blob" "blob") is an expressions that must evaluate to a function. In order for it to be applied to an argument it must be a function. Happily, the basic rewriting rules (replacing equals by equals) still holds. We will be able to define functions fun f pat pat = splat , and then f blob blob can be replaced by splat.
(Unfortunately value polymorphism gets in the way of the main point that fun and val are all the same. See Types and Type Checking by McQueen.)
- val const7 = (fn x => fn y => 7); (* Several ways to define the same thing ... *) val const7 = fn : 'a -> 'b -> int - fun const7 x = (fn y => 7); val const7 = fn : 'a -> 'b -> int - fun const7 x y = 7; val const7 = fn : 'a -> 'b -> int - fun const7 _ _ = 7; val const7 = fn : 'a -> 'b -> int - Compiler.Control.valueRestrictionTopWarn := false; val it = () : unit - const7 (); const7 nil; const7 3; const7 "a"; (* Think of these as functions: 'a->int *) val it = fn : ?.X1 -> int val it = fn : ?.X1 -> int val it = fn : ?.X1 -> int val it = fn : ?.X1 -> int - const7 nil "abc"; val it = 7 : int - const7 nil 3.4; val it = 7 : int - const7 () "abc"; val it = 7 : int - const7 () 3.4; val it = 7 : int - const7 "xyz" [1,2]; val it = 7 : int - fun const x = (fn _ => x); val const = fn : 'a -> 'b -> 'a - fun const x _ = x; val const = fn : 'a -> 'b -> 'a - const nil "abc"; val it = [] : ?.X1 list - const nil 3.4; val it = [] : ?.X1 list - const () "abc"; val it = () : unit - const () 3.4; val it = () : unit - const "xyz" [1,2]; val it = "xyz" : string
- fun f (x) = (fn (y,z) => if x=0 then y+z else x*(y+z)); val f = fn : int -> int * int -> int - f (2); val it = fn : int * int -> int - f (2) (5,8); val it = 26 : int - f (0) (5,8); val it = 13 : int - fun f (x) (y,z) = if x=0 then y+z else x*(y+z); val f = fn : int -> int * int -> int
Here is a function to determine arithmetic sequences from geometric sequences. It returns the sequence, ie., the function from natural numbers to integers that generates each element of the sequence.
- fun sequence (x as a::b::c::_) = = let = val ab = b-a and bc = c-b = val r1 = b div a and r2 = c div b; = fun guess n = List.nth (x, n) = fun arith 0 = a | arith n = arith (n-1) + ab; = fun geom 0 = a | geom n = geom (n-1) * r1; = in = if ab=bc then arith else if r1=r2 then geom else guess = end; stdIn:13.1-22.4 Warning: match nonexhaustive x as a :: b :: c :: _ => ... val sequence = fn : int list -> int -> int - val f = sequence [4,5,6,7,8,9]; val f = fn : int -> int - f 3; f 4; f 5; f 6; val it = 7 : int val it = 8 : int val it = 9 : int val it = 10 : int - val f = sequence [1,2,4,8,16]; val f = fn : int -> int - f 3; f 4; f 5; f 6; val it = 8 : int val it = 16 : int val it = 32 : int val it = 64 : int
Higher-order functions, polymorphism and lists go together well.
- fun map f nil = nil | map f (x::xs) = (f x)::(map f xs); val map = fn : ('a -> 'b) -> 'a list -> 'b list - fun filter p nil = nil | filter p (x::xs) = if p x then x::(filter p xs) else filter p xs; val filter = fn : ('a -> bool) -> 'a list -> 'a list - fun exists p nil = false | exists p (x::xs) = (p x) orelse (exists p xs); val exists = fn : ('a -> bool) -> 'a list -> bool - fun all p nil = true | all p (x::xs) = (p x) andalso (all p xs); val all = fn : ('a -> bool) -> 'a list -> bool - fun all p xs = not (exists (not o p) xs); val all = fn : ('a -> bool) -> 'a list -> bool - fun fold f ie nil = ie = | fold f ie (x::xs) = f (x, fold f ie xs); val fold = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b - fold (op +) 0 [1,2,3,4,5,6,7,8,9]; val it = 45 : int - fold (op ^) "" ["a","bc","def","","ghij"]; val it = "abcdefghij" : string - foldr (op @) nil [[1],[2,3],[4,5,6],[],[7,8,9,0]]; (* foldr predefined *) val it = [1,2,3,4,5,6,7,8,9,0] : int list - fun revf f ie l = = if null(l) = then ie = else revf f (tl l) (f (hd l, ie)); val revf = fn : ('a * 'a list -> 'a list) -> 'a list -> 'a list -> 'a list - fun revf f ie nil = ie = | revf f ie (y::ys) = revf f (f (y,ie)) ys; val revf = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b - revf (op +) 0 [1,2,3,4,5,6,7,8,9]; val it = 45 : int - revf (op ^) "" ["a","bc","def","","ghij"]; val it = "ghijdefbca" : string - foldl (op @) nil [[1],[2,3],[4,5,6],[],[7,8,9,0]]; (* foldl predefined *) val it = [7,8,9,0,4,5,6,2,3,1] : int listComposition is another example of a higher-order function.
- fun comp (f,g) = (fn x => f (g (x))); val comp = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b - fun comp (f,g) (x) = f(g(x)); val comp = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b - val f = comp (Math.sin, Math.cos); val f = fn : real -> real - val g = Math.sin o Math.cos; (* Composition "o" is predefined *) val g = fn : real -> real - f(0.25); val it = 0.824270418114 : real - g(0.25); val it = 0.824270418114 : realThe functions twin and fourtimes are defined using composition.
- local = fun search (n,i) = i*i<=n andalso (n mod i = 0 orelse search (n,i+1)); = in = fun composite n = search (n,2); (* search for a divisor *) = fun prime n = not (composite n) = end; val composite = fn : int -> bool val prime = fn : int -> bool - prime 3797; val it = true : bool - prime 87187; val it = true : bool - prime (87187 * 3797); val it = false : bool - composite (87187 * 3797); val it = true : bool - prime 99989; val it = true : bool - prime 99991; val it = true : bool - local = fun pair p = (p, p+2); = fun both_prime (p,q) = prime p andalso prime q; = in = val twin = both_prime o pair = end; val twin = fn : int -> bool - twin 99719; val it = true : bool - twin 99989; val it = true : bool - val times = (fn x => (fn y => x * y)); val times = fn : int -> int -> int - fun times x = (fn y => x * y); val times = fn : int -> int -> int - fun times x y = x*y; val times = fn : int -> int -> int - times 3 4; val it = 12 : int - times 2; (* Partial application *) val it = fn : int -> int - val twice = times 2; (* Func twice define w/o using vars *) val twice = fn : int -> int - twice 5; (* Example use of twice. *) val it = 10 : int - val fourtimes = twice o twice; (* Defined w/o vars *) val fourtimes = fn : int -> int - fourtimes 5; (* Example use of fourtimes. *) val it = 20 : int - times; val it = fn : int -> int -> int - op *; val it = fn : int * int -> int - val hex = Int.fmt StringCvt.HEX; (* Convert int to hex string *) val hex = fn : int -> string - val pad8 = StringCvt.padLeft #" " 8; (* Pad left with blanks *) val pad8 = fn : string -> string - fun format n = pad8 (hex n); val format = fn : int -> string - val format = pad8 o hex; (* predefined, binary, infix "o" *) val format = fn : int -> string - val curry = (fn f => (fn a => fn b => f(a,b))); val curry = fn : ('a * 'b -> 'c) -> 'a -> 'b -> 'c - fun curry (f) (a) (b) = f(a,b); val curry = fn : ('a * 'b -> 'c) -> 'a -> 'b -> 'c - fun plus (x,y) = x + y; val plus = fn : int * int -> int - val curryplus = curry plus; val curryplus = fn : int -> int -> int - val curryplus = curry (op +); (* "op" keyword turns off infix *) val curryplus = fn : int -> int -> int - val successor = curryplus 1; val successor = fn : int -> int - val succ = plus 1; (* type error! *) stdIn:54.1-54.18 Error: operator and operand don't agree [literal] operator domain: int * int operand: int in expression: plus 1 - val succ = (fn x => plus (1,x)); val succ = fn : int -> int - Compiler.Control.valueRestrictionTopWarn := false; val it = () : unit - val len = List.foldl (fn (_,n) => n+1) 0; val len = fn : ?.X1 list -> int - fun len l = List.foldl (fn (_,n) => n+1) 0; (* eta expansion *) val len = fn : 'a -> 'b list -> int - fun uncurry f (a,b) = f a b; val uncurry = fn : ('a -> 'b -> 'c) -> 'a * 'b -> 'cFunctions that return functions allow the programmer to combine functions to make new functions. Higher-order utility functions capture the common patterns and can be specialized to perform customized operations.
- fun map f nil = nil = | map f (x::xs) = (f x) :: map f xs; val map = fn : ('a -> 'b) -> 'a list -> 'b list - map real; val it = fn : int list -> real list - map real [1,2,3,4,5,6]; val it = [1.0,2.0,3.0,4.0,5.0,6.0] : real list - fun f g (x,y) = (x,g(y)); val f = fn : ('a -> 'b) -> 'c * 'a -> 'c * 'b - map (f (fn x=>x+1)) [("a",1),("b",2),("c",2)]; val it = [("a",2),("b",3),("c",3)] : (string * int) list - fun = filter f (nil) = nil | = filter f (head::tail) = = if f(head) then head::(filter f tail) else filter f tail; val filter = fn : ('a -> bool) -> 'a list -> 'a list - filter (fn x => x>0 andalso x*x=x); val it = fn : int list -> int list - filter Real.>; val it = fn : (real * real) list -> (real * real) list - filter Real.> [(1.0,2.0),(2.0,1.0),(Math.pi,Math.e)]; val it = [(2.0,1.0),(3.14159265359,2.71828182846)] : (real * real) list - filter Real.< [(1.0,2.0),(2.0,1.0),(Math.pi,Math.e)]; val it = [(1.0,2.0)] : (real * real) list - fun merge p (xs,nil) = xs = | merge p (nil,ys) = ys = | merge p (x::xs,y::ys) = = if p(x,y) then x :: merge p (xs,y::ys) else y :: merge p (x::xs,ys); val merge = fn : ('a * 'a -> bool) -> 'a list * 'a list -> 'a list - merge Real.>; val it = fn : real list * real list -> real list - merge Int.<; val it = fn : int list * int list -> int list - merge Int.< ([1,2,3,99,100],[1,2,3,49,50]); val it = [1,1,2,2,3,3,49,50,99,100] : int list - merge Int.> (rev [1,2,3,99,100], rev [1,2,3,49,50]); val it = [100,99,50,49,3,3,2,2,1,1] : int list
- datatype color = Red | Blue | Green; datatype color = Blue | Green | Red - Blue; Red; Green; val it = Blue : color val it = Red : color val it = Green : color - datatype bool = true | false; datatype bool = false | true - fun not (true) = false | not (false) = true; val not = fn : bool -> bool - datatype numbs = i of int | r of real; datatype numbs = i of int | r of real - [i 3, r 3.4, i 5, i 9, r 5.4]; val it = [i 3,r 3.4,i 5,i 9,r 5.4] : numbs list - fun isum nil = 0 = | isum ((i n)::rest) = n+(isum rest) | isum (_::rest) = isum (rest); val isum = fn : numbs list -> int - datatype shape = Rectangle of real*real | Circle of real | Line of (real*real)list = | Spline of (real*real)list; datatype shape = Circle of real | Line of (real * real) list | Rectangle of real * real | Spline of (real * real) list - Circle (1.2); Circle (3.4); val it = Circle 1.2 : shape val it = Circle 3.4 : shape - Rectangle (4.3, 1.9); Rectangle (40.3, ~8.345); val it = Rectangle (4.3,1.9) : shape val it = Rectangle (40.3,~8.345) : shape - Line [(1.1, 2.2)]; Line []; val it = Line [(1.1,2.2)] : shape val it = Line [] : shape - datatype ilist = inil | cons of int * ilist; datatype ilist = cons of int * ilist | inil - datatype itree = empty | node of int * itree * itree; datatype itree = empty | node of int * itree * itree - datatype = stmt = Assign | Block of block = and = block = Begin of stmt list; datatype stmt = Assign | Block of block datatype block = Begin of stmt list - Assign; val it = Assign : stmt - Block (Begin [Assign]); Block (Begin [Assign, Assign]); val it = Block (Begin [Assign]) : stmt val it = Block (Begin [Assign,Assign]) : stmt - datatype 'a option = NONE | SOME of 'a; (* predefined in structure Option *) datatype 'a option = NONE | SOME of 'a - datatype 'a glist = gnil | cons of 'a * 'a glist; datatype 'a glist = cons of 'a * 'a glist | gnil - datatype 'a binary_tree = empty | node of 'a * 'a binary_tree * 'a binary_tree; datatype 'a binary_tree = empty | node of 'a * 'a binary_tree * 'a binary_tree - datatype ('a,'b) union =InLeft of 'a | InRight of 'b; datatype ('a,'b) union = InLeft of 'a | InRight of 'b - InLeft(3); InRight (true); InLeft("s"); val it = InLeft 3 : (int,'a) union val it = InRight true : ('a,bool) union val it = InLeft "s" : (string,'a) union - [InLeft(3), InRight (true)]; val it = [InLeft 3,InRight true] : (int,bool) union list - [InLeft(3), InRight (true), InLeft("s")]; (* type error *) stdIn:40.1-40.41 Error: operator and operand don't agree [literal] operator domain: (int,'Z) union * (int,'Z) union list operand: (int,'Z) union * (string,bool) union list in expression: InLeft 3 :: InRight true :: InLeft "s" :: nil