与命令式编程相比,函数式编程需要对软件架构有不同的思考方式。业务的第一个顺序是停止思考基于语句的编程,开始思考基于表达式的编程。这意味着从定义系统和从什么中可以得到什么的角度来思考,而不是顺序因果。它将自然地导致从不可变对象的角度来思考,而不是我们都习惯的(大部分是无意识的)可变编程。基于表达式的编程和不可变对象对一个成功的函数式程序员以及我们在函数式编程语言中思考算法的容易程度有着直接的影响。
什么使祈使句成为祈使句?早些时候我写道:
“在计算机科学中,命令式编程是一种编程范式,它用改变程序状态的语句来描述计算……命令式程序定义了计算机要执行的命令序列。”【26】
前面引用的是关键词“语句”。“在计算机编程中,语句是命令式编程语言中最小的独立元素……[语句]不返回结果,只执行它们的副作用。”【27】显然,在现代命令式语言中,语句也可以返回值,但它们不必*。*
相反,“面向表达式的编程语言是这样一种编程语言,其中每个(或几乎每个)构造都是一个表达式,从而产生一个值……所有函数式编程语言都是基于表达式的。”【28】
一个语句隐含地说“相信我,做这件事,我声称这是正确的事情”,而一个表达式说“这是一种获得特定结果的方法。”我们可以从前面的例子中看出区别。
一个 C# 语句:
p.Offset(11, 12);
一个 F# 的表达:
let p2 = p.Offset 11 12
中定义的类。NET 框架,F#必须允许基于语句的编程,因此允许void
返回类型。这打开了可变函数的潘多拉盒子;为什么要调用一个不返回任何东西的函数,除非它有副作用?因此,例如,在 C#中,我们经常编写带有void
返回类型的方法:
public void PrintSomething(string s)
{
Console.WriteLine(s);
}
因为 F#是一种不纯的语言,需要支持 void 返回才能使用。NET 框架等势在必行。NET 语言,我们也可以用 F# (FSI 控制台)编写:
let PrintSomething s =
printfn "%s" s
();;
val PrintSomething : s:string -> unit
我们被告知这是一个函数,它接受一个字符串并返回一个“单位”,F#的单词“void”副作用是一些东西被发射到控制台窗口(它的状态改变)。人们应该尽量避免编写返回“单位”的函数,因为这意味着函数有副作用。有完全合理的理由,比如将数据保存到数据库,但这当然是一个副作用!
“在计算机编程中,急切评估或贪婪评估是大多数传统编程语言使用的评估策略。在急切求值中,一旦表达式绑定到变量,就会立即被求值。急切求值的另一种方法是懒惰求值,即只在计算依赖表达式时才计算表达式。命令式编程语言的执行顺序由源代码组织隐式定义,几乎总是使用急切的评估。”【29】
在基于语句和基于表达式的编程中,语句的行为不同。在基于语句的语言中,至少在一个小的上下文中,例如一个块,在没有其他控制逻辑的情况下,语句按照它们被定义的顺序依次执行*。另一方面,像 F#这样不纯的基于表达式的语言允许在表达式中嵌入语句。在这种情况下,嵌入式语句将在计算表达式时执行,无论何时。这往往一开始很难让人头脑清醒,导致一些有趣的行为。例如,假设您有一个函数,它打印一些东西并返回一个文本(FSI 控制台):*
> let printAndReturn =
printfn "Hi!"
5;;
Hi!
val printAndReturn : int = 5
> printAndReturn;;
val it : int = 5
注意怎么*嗨!*立即发出—默认情况下,F#执行“急切”的表达式求值。此外,当我们稍后调用函数时,由于表达式已经被求值,嵌入其中的printfn
语句将不会执行,*嗨!*不再发射。
相反(FSI 控制台):
> let Adding a b =
printfn "Adding %d %d" a b
a+b
;;
val Adding : a:int -> b:int -> int
> Adding 1 2;;
Adding 1 2
val it : int = 3
> Adding 3 4;;
Adding 3 4
val it : int = 7
在这里,Adding
只有在提供了参数后才能被评估。因此,每次我们在呼叫站点使用Adding 1 2
或Adding 3 4
进行评估时,都会收到控制台消息添加……。
表达式中嵌入的语句会导致很多混乱,例如在使用printfn
进行调试时。表达式将尽快求值,不一定按照您期望的顺序,尤其是来自命令式、基于语句的编程语言。
基于表达式的编程还有其他细微差别。对于表情有两种基本的评价策略:渴望和懒惰。假设您想根据某个值是真还是假来评估某个表达式:
> let Add a b =
printfn "Computing a + b"
a + b
let Subtract a b =
printfn "Computing a - b"
a – b
let Compute operation sum difference =
match operation with
| "Add" -> sum
| "Subtract" -> difference
| _ -> 0
Compute "Add" (Add 1 2) (Subtract 5 4)
;;
Computing a + b
Computing a - b
val Add : a:int -> b:int -> int
val Subtract : a:int -> b:int -> int
val Compute : operation:string -> sum:int -> difference:int -> int
val it : int = 3
注意表达式(Add 1 2)
和(Subtract 5 4)
是如何计算的,不管我们想要哪个表达式结果。这可能会影响性能,因此,我们希望显式使用惰性表达式求值,这将在下一节中讨论。
“在编程语言理论中,惰性求值(或按需要调用)是一种求值策略,它将表达式的求值延迟到需要它的值时(非严格求值),并且还避免了重复求值……延迟求值的优点是能够创建可计算的无限列表,而没有无限循环或大小问题干扰计算。”【30】
请注意,lazy evaluation 是作为 lambda 演算的一部分引入的,如果您还记得的话,它是函数式编程的基础,因此 F#采用了一种急切的评估方案是很有趣的。然而,它确实支持显式的惰性评估。F#所基于的 ML 语言家族,历史上默认使用热切求值,因为它的属性更容易证明,性能更可预测。在 F#工作之前的 Haskell.NET 实验中,唐·赛姆和西蒙·佩顿-琼斯遇到了很多困难,他们试图在默认的基础上很好地实现懒惰。NET 的根本渴望的方法,他们基本上放弃了,转而转向了一种与. NET 有着相同渴望偏见的语言
让我们稍微修改一下前面的例子,通过使用“懒惰”类型【31】来改变我们对计算的调用方式:
let Compute operation sum difference =
match operation with
| "Add" -> sum
| "Subtract" -> difference
| _ -> lazy 0
let result = Compute "Add" (lazy (Add 1 2)) (lazy (Subtract 5 4))
;;
val Add : a:int -> b:int -> int
val Subtract : a:int -> b:int -> int
val Compute :
operation:string -> sum:Lazy<int> -> difference:Lazy<int> -> Lazy<int>
val result : Lazy<int> = Value is not created.
> result.Force();;
Computing a + b
val it : int = 3
现在注意,当我们强制表达式求值时,只对表达式(Add 1 2)
求值!顺便说一下,还要注意表达式0
在 match 语句中是如何被“懒求值”的;我们必须在所有返回值中保持类型一致性。
函数式编程要求您了解表达式的计算时间,记住这一点,考虑何时需要显式使用惰性计算来提高代码的性能。请注意,一些函数式编程语言,如 Haskell,默认情况下使用“惰性评估”。
- 命令式编程基于语句。
- 函数编程是基于表达式的。
- 避免返回单位(“无效”)的函数,因为这是一个严重的迹象,表明你没有以“函数式”的方式编码,你的函数有副作用。
- 表达式在 F#中“急切”求值,因此出于性能原因,您可能需要明确指示编译器您想要惰性求值。
学习如何在一个不变的世界中思考是非常困难的。日常生活中的事情是多变的。当我们开车去某个地方时,我们会打开发动机。当我们到达目的地时,我们关掉发动机。我们显然正在改变汽车的状态。我们不“复制”汽车,所以我们现在有一辆汽车发动机关闭,另一辆“相同”的汽车,但发动机打开!我们生活在一个有状态的世界中,我们世界中事物的基本特征之一就是它们的状态。
另一方面,数学和逻辑主要处理不可变的东西,所以函数式编程可以受益于更接近数学和逻辑的自然工作方式。数据库设计和数字逻辑设计的重要领域也使用不可变的定义。不变性给了我们从编译时角度来推理程序行为的巨大能力——潜在地知道并且能够证明程序是正确的能力。毕竟,对世界的科学理解主要基于数学。拥有科学的理解,就是能够用输入来解释输出,没有魔法或者没有根据的假设,就像函数式编程一样。开发程序或科学理论的大部分工作是形式化——与其说是用语法编写代码,不如说是从模糊的理解到清晰的理解。
转换到不变性的概念在精神上可能很困难,但是在编写功能代码时,有一些具体的结构性事情可以做,这有助于使不变性更加自动化。这些是:
- 通过将关联显式创建为映射来减少封装。
- 创建只做一件事的小函数。
从不变性的角度思考意味着改变你对封装的看法。通常,我们使用封装在一个保护伞下收集许多不同的概念或属性。在命令式编程中,这通常看似合理,但最终会导致纠缠和复杂性。在函数式编程环境中,封装看似相关但实际上不同的概念会在给定的类型中产生撤销“噪音”,并使其难以处理不可变的对象。相反,我们需要做的是把这些联系分开,用不同的物体把它们联系起来。在其他积极效果中,这使得处理类型变得更加容易,因为类型不包括属于“有”关系的属性。一个类型应该总是确切地表达它是什么(也就是说定义了什么它),而不是它有什么(也就是说有什么东西与之相关联)。
“什么定义了一个对象”的概念在数据库设计和唯一键的概念中有其等价性——给定一个表,每个记录由使该记录唯一的字段来定义。是的,可能还有其他属性,但突出的一点是,您总是可以通过其唯一键来识别唯一记录。表中的其他字段不能这样做。这有助于我们识别函数式编程中的核心类型。
数据库体系结构的另一个关键方面是通过使用外键将关联表示为单独的表。当减少封装时,考虑如何在数据库中表示类。您需要哪些单独的表,它们是如何关联的?完成本练习后,您就可以在 F#中正确实现类型了。
好的数据库架构的另一个关键方面是规范化,特别是不重复相同的数据。我们也将使用这个实践作为创建更好的 F#代码的指南。
接下来,我们将举一个例子,看看我们如何将这种新的思维方式与 C#类的一个非常必要的实现联系起来User
:
public class User
{
private List<string> roles = new List<string>();
private byte[] passwordHash;
public string Username { get; set; }
public string EmailAddress { get; set; }
public string PasswordHash
{
get { return Encoding.UTF8.GetString(passwordHash); }
}
public void AddRole(string roleName)
{
roles.Add(roleName);
}
public void RemoveRole(string roleName)
{
roles.Remove(roleName);
}
public void SetPassword(string newPassword, HashAlgorithm hashAlgo)
{
byte[] bytes = Encoding.UTF8.GetBytes(newPassword);
passwordHash = hashAlgo.ComputeHash(bytes);
}
}
// Example usage:
User user = new User();
user.SetPassword("Foobar", new SHA1Managed());
Console.WriteLine("Password Hash: " + user.PasswordHash);
这个简单的类用于以典型的命令式风格说明可变性和副作用。这个类需要一些修改才能成为一组行为良好的 F#类型和函数。注意,即使在术语类型和函数的使用中,我们也是如何将一个类的属性分解成它们的组成部分的。如果在 F#中实现为一个不可变的对象,它将需要克隆所有的属性,包括角色的集合。当用户的配置改变时,这是我们想要优化的。
如果我们应用“像设计数据库一样设计一个类”的原则,我们可以得出结论:
- 用户是由用户名和密码或电子邮件和密码的组合定义的*,因此属性用户名、电子邮件和密码是一个自然的分组。附加角色集合不是定义用户的特征,应该从定义
User
的类型中移除。* ** 角色也可以被认为是外键关联,这进一步激发了它应该是自己的“第一类”类型以及需要一个单独的类型来管理用户和角色之间的关联的想法。* 这也通过消除许多用户之间角色名称的重复来“标准化”数据。*
*我们现在可以在 F#中定义我们的类型,从User
开始:
type User =
{
username : string;
emailAddress : string;
passwordHash : byte[];
}
// Example Instantiation:
let u =
{
username = "Marc";
emailAddress = "marc.clifton@gmail.com";
passwordHash = null;
}
我们还需要一个简单的UserRole
类型:
type UserRole =
{
rolename : string;
}
最后,将用户与角色列表相关联的类型:
type UserRoles =
{
user : User;
roles : List<Role>;
}
我们现在可以用几个角色实例化一个用户,例如:
let u =
{
username = "Marc";
emailAddress = "marc.clifton@gmail.com";
passwordHash = null;
}
let role1 = {rolename = "Administrator"}
let role2 = {rolename = "SuperUser"}
let marc = {user = u; roles = [role1; role2]}
请注意,通过降低 C# User
类中说明的封装复杂性,我们创建了三种不同的类型。诚然,没有什么能阻止我们用命令式语言做这件事;只是我们在处理类时通常会被复杂性所吸引。我们在这里创建的类型是更简单的结构组成,这最终有助于能够用这些更简单的结构做更多的事情。使用这些新类型,我们接下来将探索在不可变的上下文中对这些类型进行操作的“功能”方式。
-
通过解耦类型的隐式关联来降低对象的复杂性。
-
要做到这一点,请从规范化关系数据库体系结构的角度来考虑:
-
创建小类型(记录),因为这些类型更容易与其他类型(记录)关联。
我们再来看看 C#中的SetPassword
方法:
public void SetPassword(string newPassword, HashAlgorithm hashAlgo)
{
byte[] bytes = Encoding.UTF8.GetBytes(newPassword);
passwordHash = hashAlgo.ComputeHash(bytes);
}
这个方法非常简单,但是从函数式编程的角度来看,它有几个问题:
- 编码协议被硬编码到方法体中——任何使用此方法的人都不能更改编码协议。
- 调用方法时必须知道哈希算法。
- 该方法不返回哈希密码;相反,它将内部字段设置为结果哈希值,这是一个副作用。
- 如果不从整个类派生,就不能扩展此方法,例如添加密码盐。
- 因为程序员没有指定这个方法是虚拟的,所以这个方法实际上不能被覆盖,迫使程序员采取更激烈的措施来创建期望的函数。因此,编写的代码不太可扩展,下一个程序员创建的任何变通办法都可能导致代码重复,如果程序员更改原始方法,就会引入潜在的错误,并导致代码变得脆弱。
当然,最后一点可以通过更好的面向对象设计来轻松解决,当然也有可能写出糟糕的功能程序;然而,函数式编程倾向于促进“只做一件事”的思想。因此,我们将SetPassword
方法分解为两个函数。
对于下面的例子,我们需要包括几个。NET 命名空间:
open System.Security.Cryptography
open System.Text
我们仍然可以将编码函数定义为:
let encodeUTF8 password = Encoding.UTF8.GetBytes(password : string)
哈希计算算法如下(一种方法是):
let getHash hashAlgo bytes = (hashAlgo : HashAlgorithm).ComputeHash(bytes : byte[])
因为我们使用的. NET 基类(HashAlgorithm
)有许多重载的Compute
方法,所以我们必须为包含Compute
方法和参数类型的类指定类型信息。
定义该函数的另一种方法是在getHash
方法的参数中指定所需的类型:
let getHash (hashAlgo : HashAlgorithm) (bytes : byte[]) = hashAlgo.ComputeHash(bytes)
第二种形式允许编译器选择正确的Compute
方法,因为它已经知道hashAlgo
的类型和bytes
的类型。
通过将 C#方法分成两个更简单的函数,我们正朝着处理更多核心行为的方向发展,让程序员能够改变程序的行为,而不会遇到我之前列出的问题。
我们可以定义第三个函数,在给定密码的情况下,计算密码散列:
let pwdHash pwd = getHash (new SHA1Managed()) (encodeUTF8 pwd)
我们这样使用它(FSI 控制台):
> pwdHash "abc";;
val it : byte [] =
[|169uy; 153uy; 62uy; 54uy; 71uy; 6uy; 129uy; 106uy; 186uy; 62uy; 37uy;
113uy; 120uy; 80uy; 194uy; 108uy; 156uy; 208uy; 216uy; 157uy|]
这不仅是一个相当丑陋的 F#函数,而且它仍然有一种命令式的“感觉”。更实用的方法是使用功能流水线。
- 创建只做一件事的函数。
- 更小的函数更容易组合(下一节将详细介绍)。
- 较小的函数使您更容易更改应用的行为,而不会破坏代码的其他部分。
虽然即使在命令式语言中,编写较小的函数也可以被认为是一种口头禅,但归根结底,所有这些小函数仍然必须放在一起,才能做更大的事情。命令式编程促进了“序列”的紧密耦合,并要求所有信息现在都可用,以便执行指令序列。
函数式编程有几种不同的方式来组合所有这些小函数:
- 函数流水线:通过提供第一个值,一个函数的结果值直接馈入下一个函数,产生最终值。
- 部分应用:创建一个函数,将它的一些初始参数绑定到值,允许后面提供其余的参数。
- 函数组合:创建一个由其他几个函数组成的函数,其中,类似于流水线操作,一个函数的结果值提供下一个函数的第一个参数。
函数式编程的一个重要特征是函数流水线的思想。管道操作符|>
是 F#中最重要的操作符之一【32】管道操作符“可以被认为是通过一系列函数来传递一个参数。”【33】嵌套函数调用可能难以读取。带有 n 级的函数管道为嵌套的一系列函数调用 n 级深度提供了一种简单的、从左到右可读的替代语法。
如果我们使用管道操作符|>
重写前面的 F#代码,代码将变得更易读:
let pwdHash pwd = pwd |> encodeUTF8 |> getHash(new SHA1Managed())
这里我们告诉编译器:
- 创建一个名为
pwdHash
的函数,该函数接受一个参数,该参数被推断为字符串。 - 调用
encodeUTF8
功能,传递密码。 - 评估与参数
new SHA1Managed()
一起传递给功能GetHash
。
在计算机科学中,部分应用(或部分函数应用)是指将一个函数的多个参数固定下来,产生另一个较小的函数的过程【34】(“Arity”表示函数接受的参数个数。)
我们可以通过推迟哈希算法来进一步“功能化”前面的代码,只需创建一个部分应用:
let pwdHash2 pwd = pwd |> encodeUTF8 |> getHash2
这里,我们定义了一个函数,它接受密码,但返回一个期望提供哈希算法的函数。但是,这也需要我们切换getHash
函数的参数顺序,这也是我之前称之为getHash2
的原因(后面会有更多介绍):
let getHash2 (bytes : byte[]) (hashAlgo : HashAlgorithm) = hashAlgo.ComputeHash(bytes)
为什么呢?因为我们提供了管道中的第一个参数,并期望调用方稍后提供第二个参数,即哈希算法。
在pwdHash2
函数中,我们将密码参数“管道”到字节编码器中,然后将结果编码的byte[ ]
值“管道”到getHash2
函数中,该函数返回一个期望编码算法的函数,并返回一个编码值的byte[ ]
。
我们这样使用它(FSI 控制台):
> let myEncPwd2 = ("abc" |> pwdHash2)(new SHA1Managed());;
val myEncpwd2 : byte [] =
[|169uy; 153uy; 62uy; 54uy; 71uy; 6uy; 129uy; 106uy; 186uy; 62uy; 37uy;
113uy; 120uy; 80uy; 194uy; 108uy; 156uy; 208uy; 216uy; 157uy|]
观察我们是如何创建部分应用pwdHash2
的,在评估时,它用 UTF8 编码来编码我们的密码,但是让我们推迟选择实际的哈希算法。我们通过输入原始密码字符串来分配编码密码,通过提供哈希算法对象来完成函数应用。
这个的语法有点乱,因为我们在混合。NET 对象,而不是使用纯 F#函数。然而,我相信这代表了在用 F#编程时您将处理的真实世界,所以我宁愿说明这个语法,而不是一个纯 F#实现。这都是函数式思考的一部分,但是要意识到你仍然必须使用不支持功能流水线和迎合的命令式框架。
- 编写函数时,考虑哪些参数最有可能被部分应用,并将这些参数放在第一位。
- 如果程序员没有按照您想要的顺序提供参数,请编写一个函数来翻转参数,您可以使用它来创建部分应用函数。
我们现在可以考虑如何添加不同的行为,例如,在密码中添加一些“盐”。这进一步说明了我们的应用的行为是如何通过简单、可组合的函数而被轻松改变的。首先,让我们这样来看编码函数:
let myEncPwd2 = ("abc" |> encodeUTF8 |> getHash2)(new SHA1Managed())
在将结果传递给getHash2
函数之前,我们将附加一个编码的盐:
let mySaltedPassword = (("abc" |> encodeUTF8, "salt" |> encodeUTF8) ||> Array.append |> getHash2)(new SHA1Managed())
注意||>
操作员。这个运算符接受一个元组,并将其传递给一个接受两个参数的函数。元组由密码和salt
构成:
("abc" |> encodeUTF8, "salt" |> encodeUTF8)
接下来,它被输入到Array.append
功能中:
let mySaltedPassword = ("abc" |> encodeUTF8, "salt" |> encodeUTF8) ||> Array.append
然后,结果通过管道传送到带有所需散列编码器的getHash2
函数。如果你好奇的话,还有三重管道操作符|||>
,它接受三个值的元组,并将其传递给一个接受三个参数的函数。
流水线要求提供输入值来“初始化”管道。例如,这个函数:
encodeUTF8 pwd
使用流水线技术重写为:
pwd |> encodeUTF8
然而,我们可能不知道这个值,这就是使用>>
运算符的函数组合的作用。前面使用的例子:
let myEncPwd2 = ("abc" |> encodeUTF8 |> getHash2)(new SHA1Managed())
无需abc
初始值即可改写:
let encodeUTF8 password = Encoding.UTF8.GetBytes(password : string)
let getHash (hashAlgo : HashAlgorithm) (bytes : byte[]) = hashAlgo.ComputeHash(bytes)
let pwdEncoder = encodeUTF8 >> getHash(new SHA1Managed())
这里我们创建了一个函数pwdEncoder
,它是encoder
和hashing
函数的组合。我们这样使用它(FSI 控制台):
> pwdEncoder "abc";;
val it : byte [] =
[|169uy; 153uy; 62uy; 54uy; 71uy; 6uy; 129uy; 106uy; 186uy; 62uy; 37uy;
113uy; 120uy; 80uy; 194uy; 108uy; 156uy; 208uy; 216uy; 157uy|]
或者像这样:
“abc” |> pwdEncoder
- 为了利用函数组合,最好有只取一个参数的函数。
- 您在组合中的函数很可能是部分函数应用!
函数组合,顾名思义,就是本身就是函数的函数组合。一级函数是一种价值,但价值一般不是函数。例如,我不会写:
let array1 = [|1;2;3|]
let array2 = [|4;5;6|]
let array3 = array1 >> Array.append array2
编译器抱怨它期望array1
是一个函数,但实际上它是一个int[ ]
;换句话说,字面意思。
然而,我们可以写道:
let t1 = encodeUTF8 >> Array.append (encodeUTF8 "salt")
> “abc” |> t1;;
val it : byte [] = [|115uy; 97uy; 108uy; 116uy; 97uy; 98uy; 99uy|]
我们能够做到这一点是因为encodeUTF8
是一个函数,而不是一个文字,我们可以在任何需要值的地方使用函数。一旦我们为函数t1
提供了初始文字值 abc ,则t1
进行评估,将“abc” |> encodeUTF8
的结果传递给Array.append
函数,该函数已经接收到评估encodeUTF8
“salt”
得到的值作为其第一参数。
考虑这个部分函数应用,其中我们不提供编码的盐参数:
let t1 = encodeUTF8 >> Array.append
其可以如下使用:
("abc" |> t1) (encodeUTF8 "salt")
// - or –
(encodeUTF8 "salt") |> ("abc" |> t1)
请注意,我们是如何将流水线操作(从初始值开始)与函数组合(对值进行编码并将结果传递给 append 函数的部分应用的函数)相结合的。)知道您使用的是文字还是“函数作为值”非常重要,因为这将指导您如何使用函数流水线和函数组合。
理解部分应用和流水线之间的交互也很重要,因为这可能会产生意想不到的后果。
给定(FSI 控制台):
let encodeUTF8 (password :string) = Encoding.UTF8.GetBytes(password)
let getHash (hashAlgo : HashAlgorithm) (bytes : byte[]) = hashAlgo.ComputeHash(bytes)
> ((encodeUTF8 "abc", encodeUTF8 "salt") ||> Array.append) |> getHash(new SHA1Managed());;
val it : byte [] =
[|153uy; 25uy; 141uy; 252uy; 72uy; 224uy; 52uy; 198uy; 99uy; 86uy; 24uy;
63uy; 133uy; 78uy; 179uy; 34uy; 246uy; 7uy; 193uy; 221uy|]
这里,getHash(new SHA1Managed())
返回部分应用函数,第一个参数是“固定的”或“绑定的”提供了第一个参数后,剩下byte[ ]
参数由管道提供。
将此与以下内容进行比较:
> ((encodeUTF8 "abc", encodeUTF8 "salt") ||> Array.append) |> getHash;;
((encodeUTF8 "abc", encodeUTF8 "salt") ||> Array.append) |> getHash;;
------------------------------------------------------------^^^^^^^
stdin(134,61): error FS0001: The type 'byte []' is not compatible with the type 'HashAlgorithm'
在这里我们可以清楚地看到,流水线试图提供第一个参数,但是由于getHash
是一个部分应用,其中没有提供任何参数,它会因类型不匹配而失败,因为流水线试图提供第一个参数,类型为HashAlgorithm
,带有byte[ ]
!
一个正确的用法是这样的:
(new SHA1Managed(), ((encodeUTF8 "abc", encodeUTF8 "salt") ||> Array.append)) ||> getHash;
从前面的代码中可以清楚地看到,部分应用getHash(new SHA1Managed())
优先于管道操作符。当我们没有正确创建分部函数应用时,我们能够在编码过程中识别出这个问题,因为getHash
函数有不同类型的参数,编译器或 IDE 告诉我们有问题。然而,如果参数是相同的类型,我们可以很容易地创建仅在运行时发现的计算错误。我们可以用下面的代码(FSI 控制台)更清楚地说明这一点:
let Sub x y = x - y;;
val Sub : x:int -> y:int -> int
> Sub 5 3;;
val it : int = 2 // We expect 5 – 3 = 2
> let t = 5 |> Sub;; // Here we create a partial application “Sub 5”
val t : (int -> int)
> t 3;; // And we expect that t(3) = (Sub 5)(3) = 2
val it : int = 2
> let t = 5 |> Sub 3;; // But what does this do? Do we expect this to = 2 ???
val t : int = -2 // This is 3 – 5 !!!
因为 F#是从左到右求值的,所以在代码5 |> Sub 3
中把5
赋值给x
似乎是合乎逻辑的,导致部分函数应用Sub 5
,然后把3
作为y
参数应用,导致2
的答案。事实并非如此!如果我们想要这个行为,我们需要指定5 |> Sub
首先通过在表达式中加上括号来计算:
> let t = (5 |> Sub) 3;;
val t : int = 2
这里我们清楚地看到部分应用Sub 3
优先,使得 3 为x
,5 为y
。
前面的代码仍然没有实现我们想要实现的目标:
- 我们希望能够指定要在实际哈希函数之外使用的编码器和哈希算法,换句话说,我们希望抽象出应用可能想要使用的实际编码器和哈希算法。
- 我们希望能够干净地追加字节流,这样我们就可以使用密码和 salt。
使用我们所学的关于函数组合、部分函数应用和函数流水线的所有知识,我们现在准备好构建一个更加简洁的实现,展示(希望)F#和函数编程的独特特性。
我们从接口到。NET 应用编程接口:
let encodeUTF8 password = Encoding.UTF8.GetBytes(password : string)
let getHash (hashAlgo : HashAlgorithm) (bytes : byte[]) = hashAlgo.ComputeHash(bytes)
接下来,我们想推广追加字节数组的思想,所以我们将编写一个通用的“编码字符串和追加”函数:
let encodeStringAndAppendFunction (f : string -> byte []) = f >> Array.append
我称之为encodeStringAndAppendFunction
的原因是,当给定一个将字符串转换为字节[ ]的编码算法时,它会返回一个部分函数应用——只提供了Array.append
函数的第一个参数。
这允许我们将编码和追加操作链接在一起。我们可以在单独的let
语句中做到这一点,以最后的“追加一个空数组”结束
let a = "abc" |> encodeStringAndAppendFunction encodeUTF8
let b = ("salt" |> encodeStringAndAppendFunction encodeUTF8) >> a
let c = [||] |> b
或者我们可以将整个表达式内联:
let encoded = [||] |>
("abc" |> encodeStringAndAppendFunction encodeUTF8 <<
("salt" |> encodeStringAndAppendFunction encodeUTF8))
重要提示:请注意,我使用的是从右向左的合成运算符<<
。这是因为我希望将我的 salt 附加到我的密码中,因此 salt 必须是Array.append
函数的第二个参数。
出于我们的目的,我们将创建一个简单编码密码和 salt 的函数:
let encodePwdAndSalt encoder pwd salt =
((encoder, pwd) ||> encodeStringAndAppendFunction <<
((encoder, salt) ||> encodeStringAndAppendFunction))
在这里,我们使用双管运算符提供编码器和密码,然后用 salt 再次应用它,创建一个函数组合,当我们在空数组中进行管道操作时,该函数组合会进行评估,接下来我们将看到这一点。
这个函数的好处是,它提供了一个清晰的模板,说明如何用额外的字符串扩展函数,我们可能希望在对字节[ ]进行哈希运算之前将这些字符串添加到字节[]中。稍后,在关于递归的讨论中,我们将进一步推广这一点。
然后,我们创建一个函数,其参数经过精心安排,适合部分函数应用:
- 因为对于一组密码和 salt,编码器和哈希算法可能不会变化,所以我们希望这些是第一个参数。
- 此外,编码器和哈希算法总是“在一起”,所以我们可以将它们指定为元组,而不是以 curried 形式(用空格分隔)。
let createHash (encoder, hasher) pwd salt =
[||] |> encodePwdAndSalt encoder pwd salt |> getHash (hasher)
我们可以直接使用这个功能(FSI 控制台):
> createHash (encodeUTF8, (new SHA1Managed())) "abc" "salt";;
val it : byte [] =
[|153uy; 25uy; 141uy; 252uy; 72uy; 224uy; 52uy; 198uy; 99uy; 86uy; 24uy;
63uy; 133uy; 78uy; 179uy; 34uy; 246uy; 7uy; 193uy; 221uy|]
但是因为我已经明智地将编码器-哈希器元组放在第一位,所以我可以用不同的编码和哈希算法创建部分函数应用(FSI 控制台):
// Create a UTF32 encoder.
let encodeUTF32 password = Encoding.UTF32.GetBytes(password : string)
// Here’s my UTF8, SHA1 encoder-hasher.
let UTF8SHA1HashFunction = createHash (encodeUTF8, (new SHA1Managed()))
// Here’s my UTF32, SHA256 encoder-hasher.
let UTF32SHA256HashFunction = createHash (encodeUTF32, (new SHA256Managed()))
;;
val encodeUTF32 : password:string -> byte []
val UTF8SHA1HashFunction : (string -> string -> byte [])
val UTF32SHA256HashFunction : (string -> string -> byte [])
我们现在有了一个非常灵活的系统,可以使用不同的编码和哈希方法对加盐密码进行哈希处理,使用部分应用来创建一个可重复使用的哈希函数。
// Now let’s create a couple hashes using our different partial applications:
let hashedPassword1 = UTF8SHA1HashFunction "abc" "salt"
let hashedPassword2 = UTF32SHA256HashFunction "abc" "salt"
;;
// And here are the results:
val hashedPassword1 : byte [] =
[|153uy; 25uy; 141uy; 252uy; 72uy; 224uy; 52uy; 198uy; 99uy; 86uy; 24uy;
63uy; 133uy; 78uy; 179uy; 34uy; 246uy; 7uy; 193uy; 221uy|]
val hashedPassword2 : byte [] =
[|130uy; 93uy; 100uy; 179uy; 200uy; 148uy; 12uy; 22uy; 159uy; 233uy; 81uy;
22uy; 180uy; 27uy; 241uy; 140uy; 151uy; 56uy; 7uy; 210uy; 55uy; 254uy; 5uy;
115uy; 8uy; 86uy; 11uy; 242uy; 12uy; 71uy; 131uy; 171uy|]
- 包起来。NET 函数,以便您可以使用部分应用构造。
- 将不变参数放在函数的第一位,以便函数适合部分应用。
- 部分应用非常强大,允许您创建揭示有用模式的函数组合,为您创建健壮应用提供进一步抽象的线索。
- 局部应用是函数式编程的“重用”策略之一。这个策略的代码。
- 不是重复,而是让你的功能尽可能小!
在命令式语言中,我们经常(不再像以前那样频繁,但您仍然可以看到)编写这样的迭代(C#):
int sum = 0;
for (int i = 0; i < 10; i++)
{
sum += i;
}
Console.WriteLine(sum); // 45
随着 lambda 表达式的出现,我们可以编写(C#):
int sum = 0;
Array.ForEach(Enumerable.Range(0, 10).ToArray(), n => sum += n);
Console.WriteLine(sum);
或者,如果您希望实现扩展方法:
public static class EntensionMethods
{
public static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
{
foreach (T element in source) action(element);
}
}
// ...
int sum = 0;
Enumerable.Range(0, 10).ForEach(n => sum += n);
Console.WriteLine(sum);
所有这些 C#例子都需要可变性 sum 的值是递增的,并且是计算表达式的副作用。
F#中使用递归来避免可变性。是的,我们可以用 F# as (FSI 控制台)编写这个例子:
> let summer =
let mutable sum = 0
for i in 1 .. 10 do
sum <- sum + i
sum
;;
val summer : int = 55
请注意,我们必须明确声明总和是可变的。
相反,使用迭代的“函数式编程”方式是使用递归(FSI 控制台):
> let rec rec_summer n acc =
match n with
| 0 -> acc
| _ -> rec_summer (n-1) (acc+n)
rec_summer 9 0;;
val rec_summer : n:int -> acc:int -> int
val it : int = 45
这是尾部递归的一个例子。“在计算机科学中,尾调用是发生在另一个过程内部作为其最终动作的子程序调用;它可能会产生一个返回值,然后由调用过程立即返回。然后,呼叫站点被称为处于尾部位置,即在呼叫过程结束时。如果子例程执行的任何调用(最终可能导致该子例程在调用链中再次被调用)处于尾部位置,则这种子例程被称为尾部递归,这是递归的一种特殊情况。尾部调用不必是递归的——可以是对另一个函数的调用——但是尾部递归特别有用,并且在实现中通常更容易处理...尾部调用很重要,因为它们无需向调用堆栈添加新的堆栈帧就可以实现...[I]在函数式编程语言中,尾调用消除通常由语言标准保证,这种保证允许使用递归,特别是尾递归来代替循环。”【35】
命令式编程有两点让尾部递归变得困难:
- 如何将循环转换成尾部递归?
- 你怎么知道你已经正确地实现了尾部递归?
人们可以大致将尾部递归分为两类:
- 其中“累加器”需要通过递归进行线程化。
- 那些不需要累加器就能对列表进行操作的。
前面的示例说明了如何通过递归手动线程化累加器。F#列表类有许多功能可以自动为您完成这项工作。例如,人们通常会写(FSI 控制台):
> let sumList list = List.fold (fun acc elem -> acc + elem) 0 list
sumList [1..9];;
val sumList : list:int list -> int
val it : int = 45
或者:
> let sumList2 list = List.reduce (fun acc elem -> acc + elem) list
sumList2 [1..9];;
val sumList2 : list:int list -> int
val it : int = 45
这些示例利用了List.fold
【36】和List.reduce
【37】功能。然而实际上,有时需要多个累加器,或者出于某种原因,对列表中每个项目的操作可能需要手动尾部递归实现。
第二种操作,在不需要累加器的情况下对一个列表进行操作,通常使用列表的“头”和“尾”。例如,简单地打印列表中的数字,我们使用 match 语句来测试空列表;否则我们使用语法hd :: tl
来提取列表的头部和列表的剩余部分,即尾部(FSI 控制台):
> let rec printList list =
match list with
| [] -> ()
| hd :: tl ->
printfn "%i" hd
printList tl
printList [1..3];;
1
2
3
另外,请注意,由于这个函数有副作用(它只是向控制台打印数字),当列表为空时,我们返回的是单位,用“()”表示。
“‘尾部递归’是一个特殊的递归函数,在递归调用后不[包括]任何其他执行,这意味着没有‘挂起操作’。””【38】
如果我们使用 dotPeek 对前一个函数生成的 IL 进行反编译,我们会看到它被实现为带有while (true)
循环的迭代:
internal class printList : FSharpFunc<FSharpList<int>, Unit>
{
internal printList()
{
}
public override Unit Invoke(FSharpList<int> list)
{
while (true)
{
if (fsharpList1.get_TailOrNull() != null)
{
// ...
}
else
break;
}
return (Unit) null;
}
}
如果我们有一个待定的操作(这里是通过最后打印头部创建的):
let rec printListNoTail list =
match list with
| [] -> ()
| hd :: tl ->
printListNoTail tl
printfn "%i" hd
除了以相反的顺序打印列表之外,我们从反编译代码中注意到,编译器已经将其实现为递归调用:
internal class printListNoTail : FSharpFunc<FSharpList<int>, Unit>
{
internal printListNoTail()
{
}
public override Unit Invoke(FSharpList<int> list)
{
// ...
this.Invoke(tailOrNull);
return // ... ;
}
}
这不是期望的实现,因为它容易受到堆栈溢出的影响,并且由于将发生的所有堆栈推送和展开,性能将会很差。
为了实现尾部递归,递归调用必须是函数代码分支中的最后一个操作,或者必须不返回任何内容(单元)或值。有时这可能很难实现,这就是延续传递风格(CPS)的有趣主题。你可以在http://codebetter . com/matthewpodwysocki/2008/08/13/recursing on-recursion-continuation-passing/上阅读更多关于 CPS 的内容。我们将在第三章中更多地了解 CPS。
for
和while
语句的主要目的是独立于正在处理的数据迭代固定次数,或者永远执行一个过程(或者通常在应用的生命周期内)。F#提供了三种不同的循环结构:
例如,这两种结构都更有意义:
for i = 1 to 10 do
printfn "%d" i
for i in 1..10 do
printfn "%d" i
与递归实现相比:
let rec print n limit =
match n with
| q when q > limit -> ()
| q ->
printfn "%d" q
print (q+1) limit
print 1 10
有了递归实现,它在做什么和什么时候做变得更加清楚,但是回答“这个循环迭代了多少次”这个问题变得更加困难然而,除了固定次数的迭代(与数据无关),人们应该仔细考虑使用递归比迭代的优势。
递归的优点是更具数学表现力——它确切地声明了什么条件导致递归调用,以及它确切地声明了什么结束了递归调用。它还明确说明了在递归期间和结束时执行什么计算。由于这个原因,递归实际上比迭代更容易理解,迭代中可能嵌入了控制逻辑,如返回或中断,以及多个退出进程。使用递归,这些行为几乎总是被放在递归调用之外,或者非常明确,通常是通过递归调用线程化状态。
人们可能认为迭代的另一个好的用例是使用命令式集合。例如,这个数据读取器看起来非常适合用 F# while…do
构造来实现:
open System
open System.Data
open System.Data.SqlClient
let openConnection name =
let connection = new SqlConnection()
let connectionString = "data source=localhost;initial catalog=" + name + ";integrated security=SSPI"
connection.ConnectionString <- connectionString
connection.Open()
connection
let createReader (connection : SqlConnection) sql =
let command = connection.CreateCommand()
command.CommandText <- sql
command.ExecuteReader()
let showDataIter (reader : SqlDataReader) =
while reader.Read() do
let id = Convert.ToInt32(reader.["BusinessEntityID"])
let fname = reader.["FirstName"].ToString()
let lname = reader.["LastName"].ToString()
printfn "%d %s %s" id fname lname
reader.Close()
let db = openConnection "AdventureWorks2008"
let sql =
"select top 5 BusinessEntityID, FirstName, LastName from Person.Person order by FirstName"
createReader db sql |> showDataIter
然而,用递归也同样容易实现,在作者看来,递归有很好的明确性,特别是在关闭阅读器方面,否则程序员可能会忘记这一点(在 F#实现中仍然会忘记,但我认为它确实使它更加明确):
// Replacing only showDataIter:
let showDataRec (reader : SqlDataReader) =
let rec showData (reader : SqlDataReader) =
match reader.Read() with
| true ->
let id = Convert.ToInt32(reader.["BusinessEntityID"])
let fname = reader.["FirstName"].ToString()
let lname = reader.["LastName"].ToString()
printfn "%d %s %s" id fname lname
showData reader
| false -> reader.Close()
showData reader
createReader db sql |> showDataRec
接下来,我们将使用数据库阅读器示例来处理集合。
- 学习
Collections.List
模块、【42】中的函数,因为这些函数将大大减少您必须自己编写的递归代码量。 - 当思考递归时,问问你自己,“我需要在这个过程中使用一个累加器吗?”这会影响递归函数的签名。
- 确保递归函数做的最后一件事是调用自己——不应该有任何挂起的操作。否则,编译器不会将递归实现为循环,并且您将招致函数调用和堆栈使用的开销,并可能导致堆栈溢出。
- 所谓尾部递归并不是因为处理列表时的
head :: tail
语法,而是因为递归调用在函数的“尾部位置”。【43】
为了确保程序员不会意外地变异一个集合,F#提供了一个完全独立的集合实现。在 C#中,我们有System.Collections
和System.Collections.Generic
名称空间。F#给了我们Microsoft.FSharp.Collections
【44】命名空间,实现了不可变的List
、Array
、seq
、Map
和Set
集合。
构建项目列表时,使用“cons”(prepend)::
运算符时,新项目总是首先出现。原因想一想就明白了。给定一个列表:
let list = [1; 2; 3]
let list2 = list :: 4 // Not a valid operation!
如果我们将一个项目添加到这个列表中,我们将修改当前列表:条目3
的“下一个项目”将需要修改,现在链接到项目4
。
相反,我们必须写:
let list = [1; 2; 3]
let list2 = 4 :: list
这样就保证了list
不会变异。为了将一个项目添加到列表中,我们必须使用串联运算符(@
)并将我们的新项目放入第二个列表中:
let list = [1; 2; 3]
let list2 = list @ [4]
当来自System.Collections.Generic
命名空间中的可变集合类时,这可能有点令人困惑,在这里我们可以随意地直接对列表进行操作。
让我们看看如何使用我之前创建的查询来创建记录列表。记录如下:
type Person =
{
PersonID: int;
FirstName: string;
LastName: string;
}
我们将首先查看上一节中读取人员数据的迭代代码。
let createPersonListIter (reader : SqlDataReader) =
let mutable list = []
while reader.Read() do
let id = Convert.ToInt32(reader.["BusinessEntityID"])
let fname = reader.["FirstName"].ToString()
let lname = reader.["LastName"].ToString()
let person = {PersonID = id; FirstName = fname; LastName = lname}
list <- person :: list
reader.Close()
list
let db = openConnection "AdventureWorks2008"
let sql = "select top 5 BusinessEntityID, FirstName, LastName from Person.Person order by FirstName"
let people = createReader db sql |> createPersonListIter
请注意,在前面的代码中,当我们使用迭代时,列表变量必须是可变的。迭代需要不断预挂起(我们也可以使用串联)带有新项目的列表,并更新保存列表的变量,迫使我们使用可变列表变量。这是函数式编程的代码味道。
解决这个问题的唯一方法是递归,我们正在构建的列表通过递归调用进行线程化:
let createPersonListRec (reader : SqlDataReader) =
let list = []
let rec getData (reader : SqlDataReader) list =
match reader.Read() with
| true ->
let id = Convert.ToInt32(reader.["BusinessEntityID"])
let fname = reader.["FirstName"].ToString()
let lname = reader.["LastName"].ToString()
let person = {PersonID = id; FirstName = fname; LastName = lname}
getData reader (person :: list)
| false ->
reader.Close()
list
getData reader list
let db = openConnection "AdventureWorks2008"
let sql = "select top 5 BusinessEntityID, FirstName, LastName from Person.Person order by FirstName"
let people = createReader db sql |> createPersonListRec
这里我们看到了为什么在函数式编程语言中工作时递归如此重要——它允许我们通过遍历递归函数调用来保留不可变的行为,这样每个新的调用实际上都是一个新的列表。习惯于以不可变的方式构建集合可能需要一些时间,递归在这个过程中起着重要的作用。我强烈建议您从您最喜欢的命令式语言中提取一些简单的迭代代码样本,并练习以不可变的递归方式重写它们。
使用不可变的集合需要一定程度的脑力体操。递归是程序员工具包中管理集合的基本工具之一。其他工具包项是对集合的三个基本操作:map
、reduce
(相当于其他一些语言中的“折叠”)、filter
。【45】
Map
对每个项目应用一个函数,并返回每个函数调用的结果列表。Reduce
累计应用两个参数,使得结果是由提供的函数确定的单个值。Filter
返回由测试函数限定的列表,返回真或假。
在命令式编程中,我们总是隐式地执行这些操作。对于函数式编程,集合类提供了实现映射、减少和过滤行为的特定函数。随着 C# 3.0 的出现,我们也有了这些功能,可以分别作为Select
、Aggregate
和Where
实现IEnumerable
的任何集合使用,例如,您可能已经在 LINQ 表达式中使用了它们。
不管你对它们的熟悉程度如何。NET 语言中,您应该花时间根据这三种行为模式来考虑您的列表操作。您将经常看到它们使用流水线技术结合起来返回复杂的计算结果。
使用从这个 SQL 查询返回的数据(我删除了“前 5 名”):
let sql = "select BusinessEntityID, FirstName, LastName from Person.Person order by FirstName"
我们可以看到如何应用过滤、映射和其他一些列表操作:
let selectNames = createReader db sql
|> createPersonListRec
|> List.filter (fun r -> r.LastName.StartsWith("Cl"))
|> List.map (fun r -> r.LastName + ", " + r.FirstName)
|> List.sort
|> Seq.distinct
|> List.ofSeq
下面我们将流水线化几个操作:
- 只过滤以 Cl 开头的姓氏。
- 将记录映射到逗号分隔的姓氏、名字字符串。
- 按结果字符串排序。
- 仅选择唯一的名称。
- 将序列转换回列表。
这很好地说明了 F#的可读性和简洁性。
- 递归是处理不可变集合的关键工具。
- 学习 F#集合类提供的映射、约简和过滤函数。
只要你充分表达了你在做什么,读者就不必担心你在做什么。命令式代码的问题是“什么”经常在“如何”中丢失,函数式编程可以帮助揭示这一点。
使用Collection
功能,如iter
—使用 lambda 表达式!
即使您必须编写一个导致突变或副作用的函数,并且理想情况下您不需要返回任何东西,也要考虑您可能想要返回什么,以便您可以利用函数流水线。通常,只需返回传递给函数的相同参数。但是,由于您不知道调用者将如何使用您的函数,所以请对“函数式”进行编程,以便调用者不受您的函数实现的限制。**