数学思维引导的函数式编程深度解析

需积分: 9 196 浏览量更新于2024-07-16 收藏 3.36MB PDF 举报

《函数式编程的科学》是一本深入浅出的教程，由 Sergei Winitzki 博士编著，于 2019 年出版。本书旨在帮助程序员掌握数学思维在类型和代码理解中的应用，特别强调与软件实践的直接相关性。内容主要针对中高级读者，需要具备高中代数水平的数学背景，因为书中会涉及复杂的概念，需要读者长时间集中精力和付出努力去学习。书中的科学方法论介绍了函数式编程的核心理念，如纯函数（pure functions）、无副作用（statelessness）、不可变数据（immutability）以及高阶函数（higher-order functions）。作者通过丰富的例子，使用 Scala 这一现代编程语言来演示这些概念，使得理论知识与实践操作相结合，帮助读者更好地理解和掌握函数式编程的精髓。书中还包含了对函数式编程范式的详细解释，比如引用透明性（referential transparency）、模式匹配（pattern matching）以及函数组合（function composition），这些都是函数式编程语言如 Haskell、Erlang 或 Lisp 的基石。此外，作者还强调了函数式编程在并发、错误处理和可维护性方面的优势，这些都是现代软件开发中日益重要的议题。版权方面，本书遵循 GNU 自由文档许可证（GNU Free Documentation License, Version 1.2 或更高版本），允许在指定条件下复制、分发和修改，具体内容在附录 F - GNU自由文档许可证中详述。作者提供了源代码（包括 LyX 文档、LaTeX 源码、图形文件和构建脚本）的透明副本，以及一个带有完整颜色链接的 PDF 版本，可以在 GitHub 上获取，并提供了详细的编译指南。《函数式编程的科学》不仅是一本技术手册，更是一本引导程序员建立严谨逻辑思考和实践技能的工具书，对于希望深入理解并应用于实际项目的开发者来说，是一本不可或缺的参考书籍。通过阅读和实践书中的内容，读者将能够提升自己的编程素养，更好地应对复杂软件系统的设计和维护挑战。

1 Mathematical formulas as code. I.

Nameless functions

1.1 Translating mathematics into code

1.1.1 First examples

We begin by writing Scala c ode for some computational tasks.

Example

1.1.1.1: Factorial of 10 Find the product of integers from 1 to 10 (the factorial of 10).

First, we write a mathematical formula for the result:

k=1

k .

We can then write Scala code in a way that resembles this formula:

scala> (1 to 10).product

res0: Int = 3628800

The Scala interpreter indicate s that the result is the value 3628800 of type Int. To deﬁne a name for

this value, we use the “

val” syntax:

scala> val fac10 = (1 to 10).product

fac10: Int = 3628800

scala> fac10 == 3628800

res1: Boolean = true

The code (1 to 10).product is an expression, which means that (1) the code can be evaluated

(e.g. using the Scala interpreter) and yields a value, and (2) the code can be inserted as a part of

a larger expression. For example, we could write

scala> 100 + (1 to 10).product + 100

res0: Int = 3629000

Example 1.1. 1.2: Factorial as a function Deﬁne a function that takes an integer n and computes the

factorial of n.

A mathematica l formula for this function can be written as

f (n) =

k=1

k .

The corresponding Scala code is

def f(n:Int) = (1 to n).product

In Scala’s def syntax, we need to specify the type of a function’s argument; in this case, we write

n:Int. In the usual mathematical notation, types of arguments are either not written at all, or written

separately from the formula:

f (n) =

k=1

k, ∀n ∈ N .

1.1 Translating mathematics into code

This indicates that n must be from the set of non-negative integers (denoted by N in mathematics).

This is similar to specifying the type

Int in the Scala code. So, the argument’s type in the code

speciﬁes the domain of a function.

Having deﬁned the function f, we can now a p ply it to an integer argument:

scala> f(10)

res6: Int = 3628800

It is a n error to apply f to a non-integer value, e.g. to a string:

scala> f("abc")

<console>:13: error: type mismatch;

found : String("abc")

required: Int

f("abc")

1.1.2 Nameless functions

The formula and the code, as written above, both involve naming the function as “ f ”. Sometimes a

function does not really need a name, – for instance, if the function is used only once. “Nameless”

mathematical functions are denoted using the symbol 7→ (pronounced “mapped to”) like this:

x 7→



some formula



So the mathematical notation for the nameless factorial function is

n 7→

k=1

k .

This reads as “a function that map s n to the p roduct of all k where k goes from 1 to n”. The Scala

expression implementing this mathematical formula is

(n: Int) => (1 to n).product

This expression shows Scala’s syntax for a nameless function. Here,

n: Int

is the function’s argument, while

(1 to n).product

is the function’s body. The arrow symbol => separates the argument from the body.

Functions in Scala (whether named or nameless) are treated as values, which means that we can

also d eﬁne a Scala value as

scala> val fac = (n: Int) => (1 to n).product

fac: Int => Int = <function1>

We see that the value fac has the type Int => Int, which means that the function takes an integer

(

Int) argument and returns an integer result v alue. What is the value of the function fac itself ? As

we have just seen, the Scala interpreter prints <function1> as the “value” of fac. An alternative Scala

interpreter

called ammonite prints something like this,

scala@ val fac = (n: Int) => (1 to n).product

fac: Int => Int = ammonite.$sess.cmd0$$$Lambda$1675/2107543287@1e44b638

This book uses the symbol → for sym bolic calculations and => for S cala code. Several programming languages, such as

OCaml and Haskell, use the notat ion -> for the function arrow.

https://ammonite.io/

1 Mathematical formulas as code. I. Nameless functions

This seems to indicate some identifying number, or perhaps a memory location.

One may imagine that a “function value” represents a b lock of compiled code , — code that will

actually run and evaluate the function’s body when the function is applied to its a rgument.

Once d eﬁned, a function can be applied to an argument like this:

scala> fac(10)

res1: Int = 3628800

However, functions can be used without naming them. We can directly apply a nameless factorial

function to an integer argument 10 instead of writing fac(10):

scala> ((n: Int) => (1 to n).product)(10)

res2: Int = 3628800

One would not often write code like this because there is no adva nta ge in creating a nameless func-

tion and then applying it right away to an argument. This is so because we can e v aluate the expres-

sion

((n: Int) => (1 to n).product)(10)

by substituting 10 instead of n in the function body, which gives us

(1 to 10).product

If a na meless function uses the argument several times, for example

((n: Int) => n*n*n + n*n)(12345)

it is still better to substitute the argument and to eliminate the na meless function. We could write

12345*12345*12345 + 12345*12345

but, of course, it is better to avoid repeating the v alue 12345. To achieve that, we may deﬁne n as a

value in an expression block like this:

scala> { val n = 12345; n*n*n + n*n }

res3: Int = 322687002

Deﬁned in this way, the value n is visible only within the expression block. Outside the block,

another value named n could be deﬁned independently of this n. For this reason, the deﬁnition of n

is called a locally scoped deﬁnition.

Nameless functions are convenient when they are themselves arguments of other functions, as we

will see next.

Example 1.1.2.1: prime numbers Deﬁne a function that takes an integer argument n and determines

whether n is a prime number.

A simple mathematical formula for this function can be written as

is_prime (n) = ∀k ∈ [2, n −1] : n , 0 mod k . (1.1)

This formula has two clea rly separated parts: ﬁrst, a range of integers from 2 to n −1, and second,

a requirement that all these integers should satisfy a given condition, n , 0 mod k. Formula (1.1) is

translated into Sca la code as

def is_prime(n: Int) = (2 to n-1).forall(k => n % k != 0)

In this code , the two parts of the mathematical formula are implemented in a way that is closely

similar to the mathematical notation, except for the arrow after k.

We can now apply the function is_prime to some integer values:

scala> is_prime(12)

res3: Boolean = false

scala> is_prime(13)

res4: Boolean = true

1.1 Translating mathematics into code

As we can see from the output above, the function is_prime returns a value of type Boolean. Therefore,

the function is_prime has type

Int => Boolean.

A function that returns a Boolean value is called a predicate.

In Scala, it is optional – but strongly recommended – to specify the return type of named functions.

The required syntax looks like this,

def is_prime(n: Int): Boolean = (2 to n-1).forall(k => n % k != 0)

However, we do not need to specify the type Int for the argument k of the nameless function k =>

n % k != 0. The Scala compiler knows that k is going to iterate over the integer elements of the range

(2 to n-1), which effective ly forces k to be of type

Int.

1.1.3 Nameless functions and bound variables

The code for is_prime differs from the mathematical formula (

1.1) in two ways.

One difference is that the interval [2, n −1] is in front of forall. Another is that the Scala c ode uses

a nameless function (k

=> n % k != 0), while Eq. (1.1) does not seem to involve any functions.

To understand the ﬁrst d ifference, we need to keep in mind that the Scala syntax such as (2 to

n-1).forall(k => ...) means to apply a function called forall to two arguments: the ﬁrst argument is

the range (2 to n-1), and the sec ond argument is the nameless function (k

=> ...). In Scala, the inﬁx

syntax x.f(z), or equivalently x f z, means that a function f is applied to its t w o arguments, x and z.

In the ordinary mathematical notation, this would be f (x, z). Inﬁx notation is often e asier to read

and is widely used, e.g. when we write x + y rather than something like plus(x, y ).

A single-argument function could be also deﬁned with inﬁx notation, and then the syntax is x

.f,

as in the expression (1 to n)

.product we ha v e seen before.

The inﬁx methods .product and .forall are already provided in the Scala standard library, so it is

natural to use them. If we want to avoid the inﬁx syntax, we could deﬁne a f unction for_all with

two arguments and write code like this,

for_all(2 to n-1, k => n % k != 0)

This would have brought the syntax somewhat closer to

the formula (1.1).

However, there still remains the sec ond difference: The symbol k is used as an argument of a

nameless function (k

=> n % k != 0) in the Scala code, – while the mathematical formula

∀k ∈ [2, n − 1] : n , 0 mod k (1.2)

does not seem to use any functions but deﬁnes the symbol k that goes over the range [2, n −1]. The

variable k is then used for writing the predicate n , 0 mod k.

Let us investigate the role of k more closely. The mathematical variab le k is actually deﬁned only

inside the expression “∀k : .. .” and makes no sense outside that expression. This becomes clear by

looking at Eq. (

1.1): The variable k is not present in the left-hand side and could not possibly be

used there. The name “k” is deﬁned only in the right-hand side, where it is ﬁrst mentioned as the

arbitrary element k ∈ [2, n −1] and then used in the sub- expression “... mod k”.

So, the mathematical notation in Eq. (

1.2) says two things: First, we use the name k for integers

from 2 to n −1. Second, for each of those k we evaluate the expression n , 0 mod k, which can be

viewed as a ce rtain given function of k that returns a

Boolean v alue. Translating the mathematical

notation into code, it is therefore natural to use the nameless function

k 7→ n , 0 mod k

and to write Scala code applying this nameless function to each element of the range [2, n −1] and

checking that all result values be true:

(2 to n-1).forall(k => n % k != 0)

Just as the mathematical notation d eﬁnes the variable k

only in the right-hand side of Eq. (1.1), the argument k of

the nameless Scala function k => n % k != 0 is deﬁned only within tha t function’s body and cannot

be used in any code outside the expression n % k != 0.

1 Mathematical formulas as code. I. Nameless functions

Variable s that are deﬁned only inside an expression and are invisible outside are c alled bound

variables , or “variables bound in an expression”. Variables that are used in an expression but are

deﬁned outside it are called free variables, or “variables occurring free in an expression”. These

concepts apply equally well to mathematical formulas a nd to Sc ala code. For example, in the ma th-

ematical expression k → n , 0 mod k (which is a nameless function), the variable k is bound (it is

deﬁned only within that expression) but the variable n is free (it is deﬁned outside that ex p ression).

The main difference between free and bound variables is that bound variables can be locally re-

named at will, unlike free variables. To see this, consider that we could rename k to z and write

instead of Eq. (

1.1) a n equivalent deﬁnition

is_prime (n) = ∀z ∈ [2, n −1] : n , 0 mod z ,

or in Scala code,

(2 to n-1).forall(z => n % z != 0)

The argument z in the nameless function z => n % z != 0

may be renamed without changing the result of the entire

program. No code outside that function needs to be changed a fter renaming z. But the value n is

deﬁned outside and cannot be renamed “locally” ( i. e. only within the sub-expression). If we wanted

to rename n in the sub- expression z

=> n % z != 0, we would also need to change every place in the

code that deﬁnes and uses n outside that expression, or else the program would become incorrect.

Mathematical formulas use bound variables in various constructions such as ∀k : p(k), ∃k : p(k),

k=a

f (k),

dk, lim

n→∞

f (n), and argmax

f (k). When translating mathematical expressions

into code, we nee d to recognize the presence of bound variables, which the mathematical notation

does not make quite so explicit. For each bound variable, we need to create a nameless function

whose argument is that variab le , e.g. k

=>p(k) or k=>f(k) for the examples just shown. Only then will

our code correctly reproduce the behavior of bound variables in mathematical expressions.

As an example, the mathematical formula ∀k ∈ [1, n] : p (k) has a bound variable k and is trans-

lated into Scala code as

(1 to n).forall(k => p(k))

At this point we can apply a simpliﬁcation trick to this code . The nameless function k → p(k) does

exactly the same thing as the (named) function p: It takes an argument, which we may call k, and

returns p(k). So, we can simplify the Scala code above to

(1 to n).forall(p)

The simpliﬁcation of x → f (x) to just f is a lwa ys possible for functions f of a single a rgument.

1.2 Aggregating data from sequences

Consider the task of counting how many even numbers there are in a given list L of integers. For

example, the list [5, 6, 7, 8, 9] contains two even numbers: 6 and 8.

A mathematica l formula for this task can be written like this,

count_even (L) =

k ∈L

is_even (k) ,

is_even (k) =











1 if k = 0 mod 2

0 otherwise

Here we deﬁned a helper function is_even in order to write more easily a formula for count_even. In

mathematics, complicated formulas are often split into simpler parts by deﬁning helper expressions.

Certain features of Scala allow programmers t o write code that looks like f(x) but actually involves additional implicit or

default arguments of the function f, or an implicit type conversion for its argument x. In those cases, replacing the code

=> f(x) by f will fail to compile. But these complications do not arise when working with simple functions.

剩余319页未读，继续阅读

qq_35245476

粉丝: 0
资源: 3

数学思维引导的函数式编程深度解析

Functional Programming pdf 2018

函数式编程概要

理解函数式编程

函数式编程

Javascript函数式编程简单介绍

函数式编程中的Swift与Swift中的函数式编程

Java8函数式编程1

F#编程科学：连接函数式编程与.NET世界的桥梁

函数式编程入门探索

OCaml函数式编程自动分级练习语料库介绍

最新资源