Introducing functional programming
tail recursion
fun sum [ ] = 0
| sum (x::L) = x + sum(L)
fun sum’ ([ ], a) = a
| sum’ (x::L, a) = sum’ (L, x+a)
ML syntax
- Types
- Expressions
- Declarations
- Patterns
Types
Expressions (and declarations) in ML must be well-typed, and the rules for types are syntax-directed; only well-typed expressions can be evaluated.
t ::= int
| real
| bool
| t1 * t2 * … * tk
| t1 -> t2
| t1 list
The infix “cons” operator :: combines a value and a list of values. For example, 1::[2,3]=[1,2,3].
We will write =>* for “evaluates in a finite number of steps to”.
Functions
The lines of form (* ... *) are comments and serve solely to document the intended type and specification of the function.
fun sum [ ] = 0
| sum(x::L)=x+(sumL)
Referential transparency is the property that:
Replacing a sub-expression by an “equivalent” sub-expression produces an “equivalent” expression.
Parallelism
Work & Span
Functions as values, Composition
(f o g)(x) = f(g x)
Higher-order functions
fun map f [ ] = [ ]
| map f (x::R) = (f x) :: (map f R)
map : (’a -> ’b) -> (’a list -> ’b list)
ENSURES
map f [x1, ..., xn] = [f x1, ..., f xn]
currying
For a function f with “multiple arguments” there is a corresponding function F of the “first” argument, that returns a function of the “remaining” arguments…
留下一句结语吧：这门课就这样仓促的结束了。充实，但更是空虚，因为我不知道我做的一切是否真的有意义。希望来世能体验体验 CMU 的生活，踏踏实实地学好一门课吧。
