F# 探险之旅-透过 F# 理解函数式编程

来源:http://www.chinese-glasses.com 作者:Web前端 人气:192 发布时间:2020-04-22
摘要:时间: 2019-09-20阅读: 137标签: 编程 F#探险之旅-选择不同的开发方式 F#探险之旅-函数式编程(上) F#探险之旅-函数式编程(中) F#探险之旅-函数式编程(下) F#探险之旅-命令式编

时间: 2019-09-20阅读: 137标签: 编程

在学习 Haskell 之前,作者一直使用主流语言,如 Java、C 和 C++——现在他仍然喜欢它们。那么,一个命令式开发人员如何转变成了一个 Haskell 开发者?他将在本文中将对此做出解释——尤其是对那些在函数式编程方面经验较少的开发人员。


本文最初发布于 Mario Morgenthum 的个人博客,由 InfoQ 中文站翻译并分享。

列表(List)是函数式编程(FP)的基础。事实上,FP的重要代表Lisp的名字即源自“List Processing”,它的发明者John McCarthy)于1960年发表的论文向我们展示了,在只给定几个简单的操作符和一个表示函数的记号的基础上,如何构造出一个完整的编程语言,他的主要思想之一是用一种简单的数据结构列表来表示代码和数据。

首先,我将通过对一些主题的讨论比较函数式编程和面向对象编程,因为它是最流行的范式。在第一个代码示例中,我将简要介绍 Haskell 的语法,因为我将在本文中使用它。

链表(Linked list)是Lisp的主要数据结构之一,并且Lisp的源代码本身也由列表构成。F#中的列表类型表示为链表,它与C#中的数组、泛型List<T>类型有着明显的不同。链表可以用下面的图表示:

控制流

图片 1

控制流描述你如何告诉程序做什么——形成算法。基本控制元素有以下三种:

首先我们来看一下FP中列表的基本操作(其中的代码都由F#实现)。

顺序——顺序执行代码

列表的基本操作

重复——重复执行代码

cons:它是“construct”的缩写,用于构造列表,意即将一个元素添加到列表的开头。我们先约定空表表示为[],在此基础上再约定操作符“::”表示cons操作,这样我们就可以构造任意的列表了。如:

选择——根据条件将代码划分成分支

列表的cons操作
let emptyList = [] // []
let oneItem = 3 :: [] // [3]
let twoItems = 2 :: oneItem // [2; 3]
let threeItems = 1 :: twoItems // [1; 2; 3]

面向对象编程

可以看到这里是如何通过“cons”操作来一步一步构造列表的。

顺序是语句逐行执行

car:它表示“Contents of the Address part of the Register”,意即列表的第一个元素。F#中使用List模块的hd(Head)函数来执行car操作:

重复是循环,如 for 或 while 语句,或递归

列表的car操作
let stringList = ["No "; "one "; "really "; "listens to "; "anyone else."]
List.hd stringList // "No "

选择是 if … else 或 switch 语句

cdr:它表示“Contents of the Decrement part of the Register”,意即列表中第一个元素之外的元素。F#中使用List模块的tl(Tail)函数来执行cdr操作:

下面这个简单的例子使用 Java 实现文本居中显示。该文本是作为一个字符串数组传入的。每一行是这个数组的一个元素:

列表的cdr操作
let stringList = ["No "; "one "; "really "; "listens to "; "anyone else."]
List.tl stringList // ["one "; "really "; "listens to "; "anyone else."]
void alignCenter(String[] text){ int maxLength = 0; for (String line : text) { if (line.length()  maxLength) { maxLength = line.length(); } } for (int i = 0; i  text.length; ++i) { int spaceCount = (maxLength - text[i].length()) / 2; StringBuilder builder = new StringBuilder(); for (int j = 0; j  spaceCount; ++j) { builder.append(' '); } builder.append(text[i]); text[i] = builder.toString(); }}

有了这三种基本操作,其它的操作都可以推导出来了。比如:

函数式编程

concat:该操作用于连接两个列表。在F#用“@”操作符执行该操作。

顺序是链式调用

let list1 = [2; 3; 4]
let list2 = [5; 6; 7]
let largeList = list1 @ list2
print_any largeList // [2; 3; 4; 5; 6; 7]

重复是递归

length:该检查列表的元素数量,在F#中使用List模块的length函数:

选择是模式匹配,或 case … of 或 if … else 表达式

let list1 = [2; 3; 4]
List.length list1  // 3

下面是同一个例子的 Haskell 实现,展示模式匹配和递归的用法:

nth:该操作返回列表的第n个元素,在F#中使用List模块的nth函数:

alignCenter :: [String] - [String]alignCenter xs = alignCenter' maxLength xs where maxLength = maximum (map length xs)alignCenter' :: Int - [String] - [String]alignCenter' _ [] = []alignCenter' n (x:xs) = (replicate spaceCount ' ' ++ x) : alignCenter' n xs where spaceCount = div (n - length x) 2
let list1 = [2; 3; 4]
List.nth list1 2  // 4

下面是一个没有使用递归的简化版本,使用了 map 和 lambda 函数:

这里代码用来获取list1中的索引(基于0)为2的元素,返回4。

alignCenter :: [String] - [String]alignCenter xs = map (x - replicate (div (n - length x) 2) ' ' ++ x) xs where n = maximum (map length xs)

现在再来看看List模块还有哪些重要的函数:

Haskell 简介

List模块(Microsoft.FSharp.Collections.List)的函数

函数的第一行是签名。签名 alignCenter :: [String] - [String] 告诉我们这是一个名为 alignCenter 的函数,其输入是一个字符串列表,输出是一个新字符串列表(从左往右读)。

List.rev:很明显,它可以翻转一个列表。要注意的是该函数会创建整个列表的一个副本,所以要注意性能问题。

第一个函数确定字符串列表中最长的行,并调用第二个函数。我们通过一个简单的表达式 maximum (map length xs) 终止第一个循环。那么它是如何工作的?让我们看下涉及到的所有函数的签名。

List.zip:该函数的签名为a’ list -> b’ list -> (a’ * b’) list,将两个列表打包为一个元组的列表:

length :: [a] - Intmap :: (a - b) - [a] - [b]maximum :: [a] - a
print_any(List.zip [1; 2] ["one"; "two"]) // [(1, "one"); (2, "two")]

length 函数的输入是一个任意类型的列表,输出是一个 Int 值。类型签名中的所有小写类型都是类型变量,类似于 Java 中 List里的 T。我认为函数的功能非常明了。

List.exists:该函数的签名类型为(a’ -> bool) -> a’ list -> ‘a,顾名思义,它用于检查列表是否包含了满足指定谓词函数的元素。

map 函数接收两个参数,第一个是 a - b 类型的函数,第二个是 [a],返回值是 [b]。 那么,“它接收一个函数作为参数”是什么意思呢?是的,这是真的。你可以将函数作为参数传递,不过不能是函数指针(如 C 语言中),也不能是方法引用(如 Java 语言中),要是作为第一类值的真正函数。以函数为参数或返回新函数作为结果的函数称为高阶函数。那么,这个函数是干什么用的呢?它将 [a] 的每个元素传递给 a - b 函数,后者将 a 转换为 b,并把它们汇集到一个新列表 [b] 中。

List.find:该函数的签名类型为(a’ -> bool) -> a’ list -> ‘a,可以看到它接受两个参数,第一个参数是谓词函数,第二个参数及传入的列表。可以这么理解,find函数对列表的元素逐一检查,看是否满足上面所说的谓词函数,如果找到了,返回该元素的值,否则抛出异常。

现在让我们解析下类型变量 map length xs,其中,xs 是 [String] 类型。

let result =  List.find (fun i -> i * i = 64) [1..10]
print_int result // 8
map :: (String - Int) - [String] - [Int]

这里检查[1..10]中的每个数字,返回8。但如果找不到任何元素满足的话,会抛出KeyNotFoundException,这时可以使用tryfind,这个类似于C#中TryParse方法。

你需要知道 String 是 [Char] 类型的同义词,表示字符列表。这就是为什么它兼容 length 函数。表达式 map length [“Hello”, “World!”] 会被解析成 [5, 6]。我们感兴趣的是列表中最长字符串的长度,因此,我们将结果列表传给 maximum,它会返回列表中长度最大的元素,即 6。

List.filter:该函数接受的参数与find函数类似,不过它的功能是对列表的元素进行过滤,将所有满足谓词函数的元素构造为一个列表返回:

我们看下第二个函数:

let list3 = List.filter (fun i -> i % 2 = 0) [1..20]
print_any list3 // [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]
alignCenter' :: Int - [String] - [String]

另外,还有功能强大的聚合函数(Aggregate Operators),即iter、map和fold。(事实上,F#中的Set、Seq、Option和Array模块都支持这三种操作)

你可能已经注意到函数名末尾的’。没有什么特别的,它只是 Haskell 中一个有效的标识符字符,因为它在数学中是一个常用符号,表示与先前标识符相关的名称。该函数是递归的,我们遍历文本的每一行,进行转换,并将转换后的行放在所有剩余元素的递归调用之前。

List.iter:该函数将枚举列表中的每个元素,并将每个元素应用于指定的函数,如:

alignCenter’ _[] =[] 这行代码是递归基本型。它的意思是:如果第二个参数是空列表,那么返回一个空列表,因为没有什么可做。在这种情况下,我们对第一个参数的值不感兴趣,所以我们不需要为它命名而只需要以 _ 表示。

List.iter (fun i -> printfn "List contains %d" i) [1..5]

以下几行代码就完成了整个工作:

输出结果为:

alignCenter' n (x:xs) = (replicate spaceCount ' ' ++ x) : alignCenter' n xs where spaceCount = div (n - length x) 2
List contains 1
List contains 2
List contains 3
List contains 4
List contains 5

我们将第一个参数绑定到 n,将第二个参数(一个列表)与模式 (x:xs) 进行匹配,这意味着:将列表的第一个元素绑定到 x,其余所有元素绑定到 xs。我们会根据需要复制空格,将它们与当前元素 x 串在一起,并在所有剩余的元素 xs 递归调用的结果列表前加上:。就这些。

List.map:map函数用将列表转换为另一个列表。它的签名类型为:

在递归操作(reduction step)之前声明递归的结束条件(base case)非常重要,因为编译器自顶向下运行,并采用它找到的第一个匹配模式。

(‘a –> ‘b) –> ‘a list –> ‘b list

小结

看看这个效果图就容易理解了,对第一个列表的元素逐一应用函数,从而得到一个新的列表:
图片 2

与相同代码的 OOP 版本相比,我们使用模式匹配和抽象函数节省了大量代码。好了,现在你可能会抱怨:“嗯,你只是把整个代码隐藏在库函数里了,比如 replicate、map 和 maximum”——我告诉你:“是的,当然!因为我不需要成千上万次地重复编写同样的 for 循环!”老实说,Java 代码可以使用 leftPad之类的东西来复制空格,但它是一个非常具体的函数,专门用于填充字符串,没有其他用途。

let x = List.map (fun i -> i * (-1)) [1..5]
printfn "%A" x // [-1; -2; -3; -4; -5]

在函数式编程中,你能够以一种简单的方式抽象常见的循环用例来执行映射、过滤、折叠和展开等任务。在 OOP 中,如果没有大量的样板代码(如后台 接口和内置语法糖),你将无法实现这样优雅的解决方案。

List.fold:在这三个函数中,fold最为强大,不过也最为复杂。它的功能可以理解为:假定我们有三个值,初始值baseValue,函数fun,列表list,逐一访问list中的每个元素,对其应用函数fun,将fun的执行结果累加到baseValue,fold将baseValue的最终值返回。在逐一访问列表时,可以采用从左到右或从右向左的方式,所以fold函数有两个实现:fold_left和fold_right。

概 念

let accumulate acc x = acc + x
let totalList = List.fold_left accumulate 0 [1..100]
printfn "1+2+..+100 = %d" totalList // 5050

这些概念描述了构建应用程序的基本思想。代码、数据及其交互在各自的范式中是如何表示的?

这里baseValue是0,函数是accumulate,列表是[1..100],最终结果为5050。

面向对象编程

列表与模式匹配和递归的结合

面向对象编程引入了接口、类、继承和对象的概念。对象包含数据字段和方法代码,这些方法通过操作字段来更改对象状态。

初学列表时,容易像C#中的集合类型那样去看待它。最近学习了一下Haskell),为它的纯粹和优雅所折服,其中的列表部分大量使用了模式匹配和递归,这个过程也让我重新理解了列表。相比于F#的List模块,Haskell)提供了额外的列表操作函数,这里我想通过在F#中实现这些函数来看看如何结合使用列表与模式匹配和递归。

函数式编程

take:接受两个参数,一个数字,一个列表,用于从列表开头获取指定个数的元素组成的新列表:

函数式编程的核心是函数。与 OOP 中的方法相比,你能用它做的事情更多:

let rec take (count: int) (l: 'a list) =
    match l with
    | _ when count <= 0 -> []
    | [] -> []
    | x :: xs -> x :: take (count - 1) xs

let list1 = [1; 2; 3; 4; 5]
print_any(take 0 list1) // []
print_any(take 1 list1) // [1]
print_any(take 3 list1) // [1; 2; 3]

把函数传递给其他函数

这里同时使用了递归和模式匹配,如果count小于等于0,返回空列表;否则返回从开头计数的指定个数的元素。

将新函数作为函数的求值结果返回

drop:该函数也接受两个参数,从列表开头移除指定个数的元素,将剩下的元素组成的列表返回:

本文由10bet发布于Web前端,转载请注明出处:F# 探险之旅-透过 F# 理解函数式编程

关键词:

最火资讯