F#探险之旅(五):透过F#理解函数式编程(上)

简介:

F#系列随笔索引

关于函数式编程(Functional programming,FP)
 
函数式编程(FP)是一种编程范式,它将计算过程视为函数运算,避免状态和数据的修改。与命令式编程相比,它更强调函数的运用。λ运算构建了函数式编程的基础。重要的函数式编程语言包括Lisp、Scheme、Erlang、Haskell、ML、OCaml等,微软则在2005年引入了F#。

此外,包括C/C++/C#/Python/Javascript等很多语言也提供了对FP的部分支持。由此我们可以得出一个结论,随着现实问题复杂度的增加,单一的编程范式很难满足需要了。我们需要对FP有更多的了解,问题是学习哪种语言呢?作为一个.NET程序员,我的答案是F#。使用F#,除了能借助FP的力量,最重要的一点是它跟.NET平台的无缝兼容,它可以轻松地与C#或VB.NET进行互操作,通过F#,我们手中的C#/VB.NET会变得更为强大。

本文尝试通过F#对FP的一些重要特征和属性做些介绍,包括函数(一等公民、高阶函数、柯里化、匿名函数、闭包)、避免副作用(对状态和数据的修改)、递归、惰性求值、模式匹配;然后讨论了FP对代码结构的影响。像Continuation和Monad留在以后的随笔中介绍。希望能增加您对FP的认识。

函数是一等公民(First-class citizen) 

这里的citizen也可换作object/value/entity,所谓一等公民是指那些在程序中可以无限制(相比于同一语言中的其它对象)使用的对象。在编程语言中,“函数是一等公民”意味着它可以:
1. 表示为匿名的文字值
2. 存储于变量中
3. 存储于数据结构中
4. 作为函数的参数进行传递
5. 作为函数的返回值
6. 在运行时进行构造

F#中的函数是一等公民,而在C#中,函数不是一等公民,比如我们不能把函数作为参数进行传递,也不能将其作为返回值,而对类则可以这么做。这种不同并不值得奇怪。如果我们把人类社会作为一个抽象来看,那么在它的不同实现中公民的等级也有所不同。在缅甸,和尚是一等公民,男人是二等公民,女人和尼姑是三等公民,人妖是四等公民,我们国家显然不是这样,但缅甸和中国的公民们大部分都能活得好好的。

复制代码
F# Code - First-class citizen
#light

let makeDerivative f (deltaX: float) =
fun x -> (f(x + deltaX) - f(x)) / deltaX

let cos = makeDerivative sin 0.000001

open System
let writeLine input =
print_any input
Console.WriteLine()

writeLine (cos
0.0) // ~= 1
writeLine (cos(Math.PI / 2.0)) // ~= 0

Console.Read()
复制代码


在这个例子中,makeDerivative函数的第一个参数f是一个函数,它的返回值也是函数,返回的是一个匿名函数。

高阶函数(High-level function) 

高阶函数是指那些可以接受其它函数为参数,或者把函数作为返回值的函数。上面的makeDerivative函数就是一个例子。高阶函数描述的是函数的数学概念,而“函数是一等公民”则是一个计算机科学的术语。

还记得在高中数学中学过的复合函数的概念吗?如果u(x) = x * 2,而y(u) = u + 3,那么y接受的“参数”是一个函数,而y本身也是一个函数。

函数柯里化(Currying) 

所谓柯里化,简单来说是指对于一个接受多个参数的函数,将第一个参数设为一个固定值,这样会得到一个新函数,新函数的参数是原函数第一个参数之外的函数。看下面简单的例子:

F# Code - 函数柯里化
// val add : int -> int -> int
let add a b = a + b
// val increment : (int -> int)
let increment = add 1


函数add接受两个参数,我们将第一个参数a设为固定值1,就得到新函数increment。

匿名函数(Anonymous function) 

顾名思义,我们定义了一个函数,也可以调用它,但没有为它设定一个名称,这样的函数就是匿名函数。在lambda运算中,所有函数都是匿名函数。

在F#的列表操作中,会经常用到匿名函数。

F# Code - 匿名函数
List.filter (fun i -> i % 2 = 0) [1 .. 20]


List.filter函数用于对列表进行过滤,其签名为:

Type Infomation
val it : (('a -> bool) -> 'a list -> 'a list)


第一个参数是返回bool值的函数,第二个参数是列表,返回值为使得第一个参数返回true的那些元素组成的新列表。本例中filter的第一个参数即匿名函数,使用关键字fun进行定义。本例中过滤后的新列表为:

Output
[2; 4; 6; 8; 10; 12; 14; 16; 18; 20]


此外还可以使用function关键字定义匿名函数,第二种方式还可以使用模式匹配。

闭包(Closure) 

闭包是个比较抽象的概念,先来看下面的例子吧。

复制代码
F# Code - 闭包(针对宿主函数的参数)
#light
open System

let makePower power =
let powerFn base = Math.Pow(base, power)
powerFn

let square = makePower 2.0
Console.WriteLine(square(
3.0))
复制代码


运行结果为9。我们来分析一下。makePower函数接受参数power,在其内部定义了一个函数powerFn,它接受参数base,并使用到了power的值,makePower函数将powerFn作为它的返回值。那么square也是一个函数,它相当于Math.Pow(base, power),这里的power值为2.0。问题是power不在powerFn的作用域内,调用makePower结束后,它的就不复存在,那么square到哪里去找power的值呢?如果我们这样创建一个新的函数来求数的立方值:

F# Code
let cube = makePower 3.0


那么运行时就要存储两个power的拷贝了。不仅这样,每个我们用makePower创建的函数都要使用power的一个拷贝,保存这些值的现象称为闭包。

上面的闭包保存了宿主函数的参数值。另外闭包还可以保存宿主函数的局部变量

复制代码
F# Code - 闭包(针对宿主函数的局部值)
let makeIncrementer() =
let n = ref 0

let increment() =
n := !n +
1
!n

increment

let inc1 = makeIncrementer()
let inc2 = makeIncrementer()
Console.WriteLine(inc1())
// 1
Console.WriteLine(inc1()) // 2
Console.WriteLine(inc1()) // 3
Console.WriteLine(inc2()) // 1
Console.WriteLine(inc2()) // 2
Console.WriteLine(inc2()) // 3
复制代码


这里闭包为increment保存了n的值,n是ref值,所以是可以修改的。局部变量的生命周期不再由简单的作用域来限定了,我们可以得出结论,它们不再保存在堆栈上——而是必须保存在堆上。闭包使得包内的函数可以访问作用域之外的值,当闭包应用了一个不在其作用域的值时,它会在其宿主作用域中查找。想一想,上面的makeIncrementer、n还有increment,这个小小的封闭体是不是很像面向对象中的类呢

没有副作用(Side effect) 

如果一个函数或表达式改变了某个状态,我们就说该函数或表达式产生了副作用。比如一个函数可能会修改全局/静态变量、参数,写文件,输出到控制台,或者调用其它产生副作用的函数。在纯粹的函数式编程中,函数没有副作用。

如果没有副作用,我们的程序还能干什么?在考虑这个问题前,先来想想,没有副作用后,程序会变成什么样子。此时,唯一影响函数返回值的是参数,这样对于相同的参数,它会返回相同的值,而且它对外部状态毫无影响。既然返回值与外部状态无关,单元测试时只要考虑参数就好了;在调试时则只需检查调用堆栈里的参数;如果两个函数没有数据的依赖,就不必考虑它们的调用顺序函数可以轻松地并行执行,这里没有死锁;编译器可以调整或合并表达式的求值,比如用在惰性求值这里。

没有副作用,程序的状态该如何保存呢?把函数提升为一等公民了,它就该多做点事情,我们要把状态保存在参数中。如果要保存某个状态一段时间并时不时地对其进行一些修改,可以写个递归函数

递归(Recursion) 

递归是编程中的一个非常重要的概念,它表示函数通过自身进行定义,亦即在定义处调用自身。在函数式编程中常用于表达命令式编程的循环。下面是求阶乘的函数:

复制代码
F# Code - 递归
let rec factorial x =
match x with
| x when x < 0 -> failwith "value must be greater than or equal to 0"
| 0 -> 1
| x -> x * factorial(x - 1)
复制代码


使用rec关键字定义递归函数,这里的match表示模式匹配结构。

惰性求值(Lazy evaluation) 

惰性求值又称延迟求值(Delayed evaluation),它将运算时间推迟到真正要使用运算结果的时候

在惰性求值之前,我还遇到过两个懒惰的家伙。一个是Lazy load,这个在ORM中是常见的概念:

XML Code - iBATIS.NET Lazyload


这是iBATIS.NET中的一段配置,第三个result节点的lazyLoad特性值为true,这意味着对于User类的RoleList属性来说,只有在用到它的时候才会执行SQL语句进行加载。

另一个是Lazy initialization,Singleton模式的一种实现方式用到了它:

C# Code - Singleton模式


在F#中,如果要利用延迟求值的特性,必须要显式地声明哪些表达式的求值需要延迟,这个要使用lazy关键字。如果需要对该表达式求值,则要调用Lazy模块的force函数。在调用force函数的时候,它会计算表达式的值,而所求得的值会被缓存起来,再次对表达式应用force函数时,所得的值其实是缓存中的值

复制代码
F# Code - 惰性求值
let sixtyWithSideEffect = lazy(printfn "Hello, sixty!"; 30 + 30)

print_endline
"Force value the first time:"
let actualValue1 = Lazy.force sixtyWithSideEffect

print_endline
"Force value the second time:"
let actualValue2 = Lazy.force sixtyWithSideEffect
复制代码


运行结果为:

Output
Force value the first time:
Hello, sixty!
Force value the second time:


惰性求值可以减少不必要的运算,从而带来性能上的提升;也可用于构造无穷的数据结构(如自然数序列)。

此外,我在下午1到4点还会听HitFM的Lazy afternoon :-)

模式匹配(Pattern matching) 

模式匹配不是什么新的创新的特性。事实上,它和函数式编程的关系不大。把产生模式匹配归因于函数式编程的唯一的原因是函数式语言一度提供了模式匹配,然而现在的命令式语言还做不到。模式匹配是指对于一个数据结构,检查其是否包含匹配给定模式的元素。正则表达式就是一种典型的模式匹配应用,它用于检查字符序列。

在F#中,模式匹配允许你根据标识符值的不同进行不同的运算。有点像一连串的if...else结构,也像C#中的switch,但是它更为强大和灵活。看下面Lucas序列的例子,Lucas序列定义跟Fibonacci序列一样,只不过起始值不同:

复制代码
F# Code - Lucas数
let rec luc x =
match x with
| x when x <= 0 -> failwith "value must be greater than zero"
| 1 -> 1
| 2 -> 3
| x -> luc(x - 1) + luc(x - 2)
复制代码


这里匹配的对象是x,它是一个整数,除了对基元类型匹配外,还可以对复杂类型进行匹配,下面的例子是对元组进行匹配:

复制代码
F# Code - 对元组应用模式匹配
let myOr b1 b2 =
match b1, b2 with
| true, _ -> true
| _, true -> true
| _ -> false
复制代码


而模式匹配的常见用法是对列表进行匹配:

F# Code - 对列表应用模式匹配
let rec concatenateList list =
match list with
| head :: tail -> head @ (concatenateList tail)
| [] -> []


这里的concatenateList函数可将列表的列表拼接为一个列表。

考虑到F#跟.NET平台的亲密关系,我们还可以对.NET类型进行匹配。

复制代码
F# Code - 对.NET类型应用模式匹配
let recognizeType (item : obj) =
match item with
| :? System.Int32 -> print_endline "An integer"
| :? System.Double -> print_endline "A double"
| :? System.String -> print_endline "A string"
| _ -> print_endline "Unkown type"
复制代码


看到模式匹配有多么灵活和强大了吧?

FP对代码结构的影响 

这里将从程序架构、类/接口/函数的组织、函数(或方法)的实现这三个层次来讨论。

程序架构上,FP对代码结构的影响最小,因为此时问题域本身是最重要的,我们得更多地关注层次较高的内容,比如性能、可靠性等。

类/接口/函数的组织这个层次上,OO的设计仍然不错,它可以较好地分解问题域并构建解决方案。但是在这个层次上OO有些情况下也不是那么奏效了,比如Command模式。Command模式往往表现为仅包含单一方法(比如Do或Execute)的类/接口,这只是穿上了“类”的外衣的函数。Visitor模式亦是如此。可以说在FP中,有些模式已经内置在语言中了!

函数(或方法)的实现这个层次上,FP的影响最大。此时没有“变量”了;不再需要类型注解了;控制结构表现为表达式和递归;可以定义局部/嵌套的函数……

F#系列随笔索引

参考
《Foundations of F#》 by Robert Pickering
《Expert F#》 by Don Syme , Adam Granicz , Antonio Cisternino
http://en.wikipedia.org/wiki/First-class_object
http://en.wikipedia.org/wiki/First-class_function
http://en.wikipedia.org/wiki/Currying
http://en.wikipedia.org/wiki/Side_effect_(computer_science)
http://en.wikipedia.org/wiki/Lazy_evaluation
http://en.wikipedia.org/wiki/Singleton_pattern
http://en.wikipedia.org/wiki/Pattern_matching
http://en.wikipedia.org/wiki/Anonymous_function
How does functional programming affect the structure of your code?
函数式编程另类指南
为什么函数式编程至关重要


本文转自一个程序员的自省博客园博客,原文链接:http://www.cnblogs.com/anderslly/archive/2008/10/26/fsharp-adventure-understanding-fp.html,如需转载请自行联系原作者。

目录
相关文章
|
4月前
|
Rust 安全 Go
揭秘Rust语言:为何它能让你在编程江湖中,既安全驰骋又高效超车,颠覆你的编程世界观!
【8月更文挑战第31天】Rust 是一门新兴的系统级编程语言,以其卓越的安全性、高性能和强大的并发能力著称。它通过独特的所有权和借用检查机制解决了内存安全问题,使开发者既能享受 C/C++ 的性能,又能避免常见的内存错误。Rust 支持零成本抽象,确保高级抽象不牺牲性能,同时提供模块化和并发编程支持,适用于系统应用、嵌入式设备及网络服务等多种场景。从简单的 “Hello World” 程序到复杂的系统开发,Rust 正逐渐成为现代软件开发的热门选择。
72 1
|
4月前
|
Java 开发者
那些年,我们一同踏入Java编程的大门,多态,这个充满魔法的名字,曾无数次点亮我们探索面向对象编程的热情。
那些年,我们一同踏入Java编程的大门,多态,这个充满魔法的名字,曾无数次点亮我们探索面向对象编程的热情。
49 5
|
2月前
|
自然语言处理 算法 语音技术
探索编程世界的奇妙之旅:从初学者到实践者的蜕变
【10月更文挑战第14天】探索编程世界的奇妙之旅:从初学者到实践者的蜕变
20 0
|
3月前
|
前端开发 算法 JavaScript
探索编程之海:我的技术感悟之旅
【9月更文挑战第14天】在编程的浩瀚海洋中,我是一位勇敢的探险者。每一次代码的编写,都是对未知领域的挑战。本文将分享我在技术探索中的心得体会,从初识编程的迷茫到逐渐找到自己的航线,再到不断精进技艺的过程。通过这段旅程,我深刻理解了“你必须成为你希望在世界上看到的改变”这句话的内涵,并将它融入到我的学习和实践中。让我们一起跟随这篇文章,揭开编程世界的神秘面纱,找到属于自己的航道。
44 9
|
4月前
|
Python
Python 控制结构:开启震撼编程之旅,犹如舞台上的精彩戏剧,让你的代码活起来!
【8月更文挑战第22天】Python的控制结构是编程的核心,包括条件判断(if-elif-else)和循环(for、while)。例如,可以用if-elif-else判断学生成绩等级,for循环计算1至10的总和,while循环实现猜数字游戏。此外,列表推导式等高级特性让操作更简洁高效。掌握这些结构能显著提升编程效率和代码质量。
55 1
|
6月前
|
机器学习/深度学习 人工智能 自然语言处理
探索编程世界的奇幻旅程
【6月更文挑战第18天】在数字时代的浪潮中,编程不仅是技术操作的体现,更是一种思维的展现。本文将通过一系列生动的故事和实例,揭示编程背后的逻辑美学与创造力的火花,带领读者走进编程世界的奇幻之旅。
|
7月前
|
程序员
代码与禅意:编程中的悟性之旅
【5月更文挑战第31天】在数字世界的繁花似锦中,我们常常忽略了编码背后蕴含的哲学。本文将探讨编程不仅仅是一门技术,更是一种艺术和内省的过程。从禅宗的角度出发,我们将一窥那些静谧的代码行间所折射出的深邃智慧,以及它如何影响程序员的思考方式和解决问题的策略。
|
7月前
|
Java C++ Python
编程的奇妙世界:膛目结舌的代码技巧探秘
编程的奇妙世界:膛目结舌的代码技巧探秘