# 函数式编程

## 什么是函数式编程

```# let double x =
x * 2
in
List.map double [ 1; 2; 3 ];;
- : int list = [2; 4; 6]
```

`map`被称为高阶函数（higher-order function） (HOF)。高阶函数是指一个把其他函数作为参数之一的函数。

```let multiply n list =
let f x =
n * x
in
List.map f list
;;
```

```# multiply 2 [1; 2; 3];;
- : int list = [2; 4; 6]
# multiply 5 [1; 2; 3];;
- : int list = [5; 10; 15]
```

`map` 的定义在`List`模块中，离当前的代码很远。也就是说，我们把`f` 传递到一个”很久很久以前，在一个很遥远很遥远的星系“（译者：星球大战片头）中的一个模块。 代码可以传递`f`给其他模块，或者把它的引用（reference）在某个地方以便之后 再调用它。不管怎样，这个闭包保证`f`总是可以获取它定义时的环境，比如`n`

```class html_skel obj = object (self)
...
...
method save_to_channel chan =
let receiver_fn content =
output_string chan content;
true
in
```

### 部分函数应用（Partial function applications）和 currying

```let plus a b =
a + b
;;
```

1. 什么是`plus`?
2. 什么是`plus 2 3`?
3. 什么是`plus 2`?

```plus : int -> int -> int
```

```5 : int
```

```# plus 2;;
- : int -> int =
```

```# let f = plus 2;;
val f : int -> int =
# f 10;;
- : int = 12
# f 15;;
- : int = 17
# f 99;;
- : int = 101
```

```let plus 2 b =       (* 这不是真正的OCaml代码！ *)
2 + b
;;
```

```    plus : int -> int -> int
plus 2 : int -> int
plus 2 3 : int
```

```let multiply n list =
let f x =
n * x
in
List.map f list
;;
```

```let double = multiply 2;;
let triple = multiply 3;;
```

```# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]
```

```# let multiply n = List.map (( * ) n);;
val multiply : int -> int list -> int list =
# let double = multiply 2;;
val double : int list -> int list =
# let triple = multiply 3;;
val triple : int list -> int list =
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]
```

```# let plus = (+);;
val plus : int -> int -> int =
# plus 2 3;;
- : int = 5
```

```# List.map (plus 2) [1; 2; 3];;
- : int list = [3; 4; 5]
# let list_of_functions = List.map plus [1; 2; 3];;
val list_of_functions : (int -> int) list = [; ; ]
```

### Pure and impure functional programming

A pure function is one without any side-effects. A side-effect really means that the function keeps some sort of hidden state inside it. `strlen` is a good example of a pure function in C. If you call `strlen` with the same string, it always returns the same length. The output of `strlen` (the length) only depends on the inputs (the string) and nothing else. Many functions in C are, unfortunately, impure. For example, `malloc` - if you call it with the same number, it certainly won't return the same pointer to you. `malloc`, of course, relies on a huge amount of hidden internal state (objects allocated on the heap, the allocation method in use, grabbing pages from the operating system, etc.).

ML-derived languages like OCaml are "mostly pure". They allow side-effects through things like references and arrays, but by and large most of the code you'll write will be pure functional because they encourage this thinking. Haskell, another functional language, is pure functional. OCaml is therefore more practical because writing impure functions is sometimes useful.

There are various theoretical advantages of having pure functions. One advantage is that if a function is pure, then if it is called several times with the same arguments, the compiler only needs to actually call the function once. A good example in C is:

```for (i = 0; i
If naively compiled, this loop is O(n2) because `strlen (s)` is called each time and `strlen` needs to iterate over the whole of `s`. If the compiler is smart enough to work out that `strlen` is pure functional and that `s` is not updated in the loop, then it can remove the redundant extra calls to `strlen` and make the loop O(n). Do compilers really do this? In the case of `strlen` yes, in other cases, probably not.
Concentrating on writing small pure functions allows you to construct reusable code using a bottom-up approach, testing each small function as you go along. The current fashion is for carefully planning your programs using a top-down approach, but in the author's opinion this often results in projects failing.
Strictness vs laziness
C-derived and ML-derived languages are strict. Haskell and Miranda are non-strict, or lazy, languages. OCaml is strict by default but allows a lazy style of programming where it is needed.
In a strict language, arguments to functions are always evaluated first, and the results are then passed to the function. For example in a strict language, this call is always going to result in a divide-by-zero error:
give_me_a_three (1/0);;

If you've programmed in any conventional language, this is just how things work, and you'd be surprised that things could work any other way.
In a lazy language, something stranger happens. Arguments to functions are only evaluated if the function actually uses them. Remember that the `give_me_a_three` function throws away its argument and always returns a 3? Well in a lazy language, the above call would not fail because `give_me_a_three` never looks at its first argument, so the first argument is never evaluated, so the division by zero doesn't happen.
Lazy languages also let you do really odd things like defining an infinitely long list. Provided you don't actually try to iterate over the whole list this works (say, instead, that you just try to fetch the first 10 elements).
OCaml is a strict language, but has a `Lazy` module that lets you write lazy expressions. Here's an example. First we create a lazy expression for `1/0`:
# let lazy_expr = lazy (1/0);;
val lazy_expr : int lazy_t =

Notice the type of this lazy expression is `int lazy_t`.
Because `give_me_a_three` takes `'a` (any type) we can pass this lazy expression into the function:
# give_me_a_three lazy_expr;;
- : int = 3

To evaluate a lazy expression, you must use the `Lazy.force` function:
# Lazy.force lazy_expr;;
Exception: Division_by_zero.

Boxed vs. unboxed types
One term which you'll hear a lot when discussing functional languages is "boxed". I was very confused when I first heard this term, but in fact the distinction between boxed and unboxed types is quite simple if you've used C, C++ or Java before (in Perl, everything is boxed).
The way to think of a boxed object is to think of an object which has been allocated on the heap using `malloc` in C (or equivalently `new` in C++), and/or is referred to through a pointer. Take a look at this example C program:
#include

void
printit (int *ptr)
{
printf ("the number is %d\n", *ptr);
}

void
main ()
{
int a = 3;
int *p = &a;

printit (p);
}

The variable `a` is allocated on the stack, and is quite definitely unboxed.
The function `printit` takes a boxed integer and prints it.
The diagram below shows an array of unboxed (top) vs. boxed (below) integers:
boxedarray.png
No prizes for guessing that the array of unboxed integers is much faster than the array of boxed integers. In addition, because there are fewer separate allocations, garbage collection is much faster and simpler on the array of unboxed objects.
In C or C++ you should have no problems constructing either of the two types of arrays above. In Java, you have two types, `int` which is unboxed and `Integer` which is boxed, and hence considerably less efficient. In OCaml, the basic types are all unboxed.
```