F# 编程/列表
| F#：列表 |
列表是一个有序的关联值的集合，它大致相当于许多其他语言中使用的链表数据结构。F# 提供了一个模块 Microsoft.FSharp.Collections.List，用于对列表进行常见操作；此模块由 F# 自动导入，因此 List 模块已可从每个 F# 应用程序访问。
在 F# 中创建列表有很多方法，最直接的方法是用分号分隔的值序列。以下是在 fsi 中的数字列表
> let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];;
val numbers : int list
> numbers;;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
注意，列表中的所有值必须具有相同的类型
> [1; 2; 3; 4; "cat"; 6; 7];;
-------------^^^^^^
stdin(120,14): error FS0001: This expression has type
string
but is here used with type
int.
使用 :: 运算符将值添加到现有列表的开头，非常常见
> 1 :: 2 :: 3 :: [];;
val it : int list = [1; 2; 3]
- 注意：
[]是一个空列表。它本身的类型为'T list；由于它与ints 一起使用，因此它的类型为int list。
:: 运算符将项目添加到列表的开头，返回一个新的列表。它是一个右结合运算符，其类型如下
val inline (::) : 'T -> 'T list -> 'T list
此运算符实际上不会改变列表，而是创建一个全新的列表，将添加的元素放在开头。以下是在 fsi 中的示例
> let x = 1 :: 2 :: 3 :: 4 :: [];;
val x : int list
> let y = 12 :: x;;
val y : int list
> x;;
val it : int list = [1; 2; 3; 4]
> y;;
val it : int list = [12; 1; 2; 3; 4]
添加元素会创建一个新的列表，但它会重用旧列表中的节点，因此添加元素是一个非常高效的 O(1) 操作。
List 模块包含一个有用的方法 List.init，其类型为
val init : int -> (int -> 'T) -> 'T list
第一个参数是要创建的新列表的长度，第二个参数是生成列表中的项目的初始化函数。List.init 的使用方法如下
> List.init 5 (fun index -> index * 3);;
val it : int list = [0; 3; 6; 9; 12]
> List.init 5 (fun index -> (index, index * index, index * index * index));;
val it : (int * int * int) list
= [(0, 0, 0); (1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64)]
F# 会调用初始化函数 5 次，每次都使用列表中每个项目的索引，从索引 0 开始。
列表推导式是指某些语言中用于生成列表的特殊语法结构。F# 具有一个表达力强的列表推导式语法，它有两种形式：范围和生成器。
范围具有结构 [start .. end] 和 [start .. step .. end]。例如
> [1 .. 10];;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
> [1 .. 2 .. 10];;
val it : int list = [1; 3; 5; 7; 9]
> ['a' .. 's'];;
val it : char list
= ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'i'; 'j'; 'k'; 'l'; 'm'; 'n'; 'o';
'p'; 'q'; 'r'; 's']
生成器具有结构 [for x in collection do ... yield expr]，并且它们比范围灵活得多。例如
> [ for a in 1 .. 10 do
yield (a * a) ];;
val it : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]
> [ for a in 1 .. 3 do
for b in 3 .. 7 do
yield (a, b) ];;
val it : (int * int) list
= [(1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (2, 3); (2, 4); (2, 5); (2, 6);
(2, 7); (3, 3); (3, 4); (3, 5); (3, 6); (3, 7)]
> [ for a in 1 .. 100 do
if a % 3 = 0 && a % 5 = 0 then yield a];;
val it : int list = [15; 30; 45; 60; 75; 90]
可以循环遍历任何集合，而不仅仅是数字。此示例循环遍历一个 char list
> let x = [ 'a' .. 'f' ];;
val x : char list
> [for a in x do yield [a; a; a] ];;
val it : char list list
= [['a'; 'a'; 'a']; ['b'; 'b'; 'b']; ['c'; 'c'; 'c']; ['d'; 'd'; 'd'];
['e'; 'e'; 'e']; ['f'; 'f'; 'f']]
注意，yield 关键字将单个值推入列表。另一个关键字 yield! 将值的集合推入列表。yield! 关键字的用法如下
> [for a in 1 .. 5 do
yield! [ a .. a + 3 ] ];;
val it : int list
= [1; 2; 3; 4; 2; 3; 4; 5; 3; 4; 5; 6; 4; 5; 6; 7; 5; 6; 7; 8]
可以混合使用 yield 和 yield! 关键字
> [for a in 1 .. 5 do
match a with
| 3 -> yield! ["hello"; "world"]
| _ -> yield a.ToString() ];;
val it : string list = ["1"; "2"; "hello"; "world"; "4"; "5"]
上面的示例显式地使用了 yield 关键字，但是 F# 为列表推导式提供了稍微不同的基于箭头的语法
> [ for a in 1 .. 5 -> a * a];;
val it : int list = [1; 4; 9; 16; 25]
> [ for a in 1 .. 5 do
for b in 1 .. 3 -> a, b];;
val it : (int * int) list
= [(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3);
(4, 1); (4, 2); (4, 3); (5, 1); (5, 2); (5, 3)]
-> 分别相当于 yield 运算符。虽然使用 -> 表达列表推导式仍然很常见，但本书不会强调此结构，因为它已被弃用，取而代之的是 yield。
使用与创建列表相同的语法来匹配列表。以下是一个简单的程序
let rec sum total = function
| [] -> total
| hd :: tl -> sum (hd + total) tl
let main() =
let numbers = [ 1 .. 5 ]
let sumOfNumbers = sum 0 numbers
printfn "sumOfNumbers: %i" sumOfNumbers
main()
sum 方法的类型为 val sum : int -> int list -> int。它递归地枚举列表，将列表中的每个项目添加到值 total 中。该函数逐步工作，如下所示
| total | 输入 | hd :: tl | sum (hd + total) tl |
|---|---|---|---|
| 0 | [1; 2; 3; 4; 5] | 1 :: [2; 3; 4; 5] | sum (1 + 0 = 1) [2; 3; 4; 5] |
| 1 | [2; 3; 4; 5] | 2 :: [3; 4; 5] | sum (2 + 1 = 3) [3; 4; 5] |
| 3 | [3; 4; 5] | 3 :: [4; 5] | sum (3 + 3 = 6) [4; 5] |
| 6 | [4; 5] | 4 :: [5] | sum (4 + 6 = 10) [5] |
| 10 | [5] | 5 :: [] | sum (5 + 10 = 15) [] |
| 15 | [] | n/a | 返回 total |
通常，我们使用递归和模式匹配从现有列表生成新列表。反转列表是一个简单的例子
let reverse l =
let rec loop acc = function
| [] -> acc
| hd :: tl -> loop (hd :: acc) tl
loop [] l
- 注意初学者：上面看到的模式非常常见。通常，当我们遍历列表时，我们希望构建一个新的列表。为了递归地做到这一点，我们使用一个累积参数（在上面的例子中称为
acc），它在生成新列表时保存着新列表。使用嵌套函数也很常见，通常命名为innerXXXXX或loop，以便从客户端隐藏函数的实现细节（换句话说，客户端不必传递他们自己的累积参数）。
reverse 的类型为 val reverse : 'a list -> 'a list。使用方法如下
> reverse [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]
此简单函数之所以有效，是因为项目总是添加到累积参数 acc 的开头，导致一系列递归调用，如下所示
| acc | 输入 | loop (hd :: acc) tl |
|---|---|---|
| [] | [1; 2; 3; 4; 5] | loop (1 :: []) [2; 3; 4; 5] |
| [1] | [2; 3; 4; 5] | loop (2 :: [1]) [3; 4; 5] |
| [2; 1] | [3; 4; 5] | loop (3 :: [2; 1]) [4; 5] |
| [3; 2; 1] | [4; 5] | loop (4 :: [3; 2; 1]) [5] |
| [4; 3; 2; 1] | [5] | loop (5 :: [4; 3; 2; 1]) [] |
| [5; 4; 3; 2; 1] | [] | 返回 acc |
List.rev 是用于反转列表的内置函数
> List.rev [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]
通常，我们想要过滤列表以获取特定值。我们可以编写一个过滤函数，如下所示
open System
let rec filter predicate = function
| [] -> []
| hd :: tl ->
match predicate hd with
| true -> hd::filter predicate tl
| false -> filter predicate tl
let main() =
let filteredNumbers = [1 .. 10] |> filter (fun x -> x % 2 = 0)
printfn "filteredNumbers: %A" filteredNumbers
main()
filter 方法的类型为 val filter : ('a -> bool) -> 'a list -> 'a list。上面的程序输出
filteredNumbers: [2; 4; 6; 8; 10]
我们可以对上面的 filter 进行略微修改，使其尾递归
let filter predicate l =
let rec loop acc = function
| [] -> acc
| hd :: tl ->
match predicate hd with
| true -> loop (hd :: acc) tl
| false -> loop (acc) tl
List.rev (loop [] l)
- 注意：由于累积参数通常以相反的顺序构建列表，因此在从函数返回列表之前立即调用
List.rev非常常见，以便将其按正确顺序排列。
我们可以编写一个将一个列表映射到另一个列表的函数
open System
let rec map converter = function
| [] -> []
| hd :: tl -> converter hd::map converter tl
let main() =
let mappedNumbers = [1 .. 10] |> map ( fun x -> (x * x).ToString() )
printfn "mappedNumbers: %A" mappedNumbers
main()
map 的类型为 val map : ('a -> 'b) -> 'a list -> 'b list。上面的程序输出
mappedNumbers: ["1"; "4"; "9"; "16"; "25"; "36"; "49"; "64"; "81"; "100"]
一个尾递归的 map 函数可以写成
let map converter l =
let rec loop acc = function
| [] -> acc
| hd :: tl -> loop (converter hd :: acc) tl
List.rev (loop [] l)
与上面的例子类似，我们使用累加参数和逆序模式来使函数尾递归。
虽然上面已经实现了反转、过滤和映射方法，但使用 F# 的内置函数更方便
List.rev 反转列表
> List.rev [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]
List.filter 过滤列表
> [1 .. 10] |> List.filter (fun x -> x % 2 = 0);;
val it : int list = [2; 4; 6; 8; 10]
List.map 将一个列表从一种类型映射到另一种类型
> [1 .. 10] |> List.map (fun x -> (x * x).ToString());;
val it : string list
= ["1"; "4"; "9"; "16"; "25"; "36"; "49"; "64"; "81"; "100"]
List.append 的类型为
val append : 'T list -> 'T list -> 'T list
正如你所料，append 函数将一个列表追加到另一个列表。@ 操作符是一个中缀操作符，执行相同的函数
let first = [1; 2; 3;]
let second = [4; 5; 6;]
let combined1 = first @ second (* returns [1; 2; 3; 4; 5; 6] *)
let combined2 = List.append first second (* returns [1; 2; 3; 4; 5; 6] *)
由于列表是不可变的，将两个列表连接在一起需要复制所有列表元素以创建一个全新的列表。但是，由于列表是不可变的，只需要复制第一个列表的元素；第二个列表不需要复制。在内存中表示，将两个列表连接起来可以如下图所示
我们从以下开始
first = 1 :: 2 :: 3 :: [] second = 4 :: 5 :: 6 :: []
将两个列表连接起来，first @ second，得到以下结果
first = 1 :: 2 :: 3 :: []
\______ ______/
\/
combined = 1 :: 2 :: 3 :: second
(copied)
换句话说，F# 将 first 的副本附加到 second 以创建 combined 列表。这个假设可以用以下 fsi 代码验证
> let first = [1; 2; 3;]
let second = [4; 5; 6;]
let combined = first @ second
let secondHalf = List.tail (List.tail (List.tail combined));;
val first : int list
val second : int list
val combined : int list
val secondHalf : int list
> System.Object.ReferenceEquals(second, secondHalf);;
val it : bool = true
两个列表 second 和 secondHalf 在内存中实际上是同一个对象，这意味着 F# 在构建新列表 combined 时重用了 second 中的节点。
将两个列表连接起来，list1 和 list2 的空间和时间复杂度为 O(list1.Length)。
List.choose 有以下定义
val choose : ('T -> 'U option) -> 'T list -> 'U list
choose 方法很巧妙，因为它同时过滤和映射列表
> [1 .. 10] |> List.choose (fun x ->
match x % 2 with
| 0 -> Some(x, x*x, x*x*x)
| _ -> None);;
val it : (int * int * int) list
= [(2, 4, 8); (4, 16, 64); (6, 36, 216); (8, 64, 512); (10, 100, 1000)]
choose 过滤返回 Some 的项目，并将它们映射到另一个值，一步完成。
List.fold 和 List.foldBack 有以下定义
val fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
val foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State
“fold” 操作将函数应用于列表中的每个元素，将函数的结果聚合在一个累加器变量中，并将累加器作为 fold 操作的结果返回。'State 类型表示累积的值，它是计算一轮的输出，也是下一轮的输入。这个描述让 fold 操作听起来更复杂，但实现实际上非常简单
(* List.fold implementation *)
let rec fold (f : 'State -> 'T -> 'State) (seed : 'State) = function
| [] -> seed
| hd :: tl -> fold f (f seed hd) tl
(* List.foldBack implementation *)
let rec foldBack (f : 'T -> 'State -> 'State) (items : 'T list) (seed : 'State) =
match items with
| [] -> seed
| hd :: tl -> f hd (foldBack f tl seed)
fold 将函数从左到右应用于列表中的每个元素，而 foldBack 将函数从右到左应用于每个元素。让我们使用以下示例更详细地检查 fold 函数
let input = [ 2; 4; 6; 8; 10 ]
let f accumulator input = accumulator * input
let seed = 1
let output = List.fold f seed input
output 的值为 3840。此表演示了如何计算 output
| 累加器 | 输入 | f 累加器 输入 = 累加器 * 输入 |
|---|---|---|
| 1 (种子) | 2 | 1 * 2 = 2 |
| 2 | 4 | 2 * 4 = 8 |
| 8 | 6 | 8 * 6 = 48 |
| 48 | 8 | 48 * 8 = 384 |
| 384 | 10 | 384 * 10 = 3840 (返回值) |
List.fold 将一个累加器和列表中的一个项目传递给一个函数。函数的输出作为下一个项目的累加器传递。
如上所示，fold 函数从列表中的第一个项目到最后一个项目处理列表，或从左到右。正如你所料，List.foldBack 的工作方式相同，但它对列表的操作是从右到左。给定一个 fold 函数 f 和一个列表 [1; 2; 3; 4; 5]，fold 方法以以下方式转换我们的列表
fold:f (f (f (f (f (f seed 1) 2) 3) 4) 5foldBack:f 1 (f 2 (f 3(f 4(f 5 seed))))
List 模块中还有几个与折叠相关的其他函数
fold2和foldBack2：同时折叠两个列表。reduce和reduceBack：与fold和foldBack相同，只是它使用列表中的第一个（或最后一个）元素作为种子值。scan和scanBack：类似于fold和foldBack，只是它返回所有中间值作为一个列表，而不是最终累积的值。
Fold 函数非常有用
将 1 - 100 的数字加起来
let x = [ 1 .. 100 ] |> List.fold ( + ) 0 (* returns 5050 *)
在 F# 中，数学运算符与函数没有区别。如上所示，我们实际上可以将加法运算符传递给 fold 函数，因为 + 运算符的定义为 int -> int -> int。
计算阶乘
let factorial n = [ 1I .. n ] |> List.fold ( * ) 1I
let x = factorial 13I (* returns 6227020800I *)
计算总体标准差
let stddev (input : float list) =
let sampleSize = float input.Length
let mean = (input |> List.fold ( + ) 0.0) / sampleSize
let differenceOfSquares =
input |> List.fold
( fun sum item -> sum + Math.Pow(item - mean, 2.0) ) 0.0
let variance = differenceOfSquares / sampleSize
Math.Sqrt(variance)
let x = stddev [ 5.0; 6.0; 8.0; 9.0 ] (* returns 1.58113883 *)
List.find 和 List.tryfind 有以下类型
val find : ('T -> bool) -> 'T list -> 'T
val tryFind : ('T -> bool) -> 'T list -> 'T option
find 和 tryFind 方法返回列表中第一个使搜索函数返回 true 的项目。它们仅在以下方面有所不同：如果未找到满足搜索函数的项目，find 将抛出一个 KeyNotFoundException，而 tryfind 将返回 None。
这两个函数的使用方式如下
> let cities = ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"; "Fremont"];;
val cities : string list =
["Bellevue"; "Omaha"; "Lincoln"; "Papillion"; "Fremont"]
> let findStringContaining text (items : string list) =
items |> List.find(fun item -> item.Contains(text));;
val findStringContaining : string -> string list -> string
> let findStringContaining2 text (items : string list) =
items |> List.tryFind(fun item -> item.Contains(text));;
val findStringContaining2 : string -> string list -> string option
> findStringContaining "Papi" cities;;
val it : string = "Papillion"
> findStringContaining "Hastings" cities;;
System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
at Microsoft.FSharp.Collections.ListModule.find[T](FastFunc`2 predicate, FSharpList`1 list)
at <StartupCode$FSI_0007>.$FSI_0007.main@()
stopped due to error
> findStringContaining2 "Hastings" cities;;
val it : string option = None
解决方案.
编写两个函数，定义如下
val pair : 'a list -> ('a * 'a) list
val unpair : ('a * 'a) list -> 'a list
pair 函数应将列表转换为如下所示的配对列表
pair [ 1 .. 10 ] = [(1, 2); (3, 4); (5, 6); (7, 8); (9, 10)]
pair [ "one"; "two"; "three"; "four"; "five" ] = [("one", "two"); ("three", "four")]
unpair 函数应将配对列表转换为传统的列表，如下所示
unpair [(1, 2); (3, 4); (5, 6)] = [1; 2; 3; 4; 5; 6]
unpair [("one", "two"); ("three", "four")] = ["one"; "two"; "three"; "four"]
编写一个具有以下类型定义的函数
val expand : 'a list -> 'a list list
expand 函数应按如下所示展开列表
expand [ 1 .. 5 ] = [ [1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5] ]
expand [ "monkey"; "kitty"; "bunny"; "rat" ] =
[ ["monkey"; "kitty"; "bunny"; "rat"];
["kitty"; "bunny"; "rat"];
["bunny"; "rat"];
["rat"] ]
任务是计算一列整数的最大公约数。
第一步是编写一个函数，其类型应如下所示
val gcd : int -> int -> int
gcd 函数应接受两个整数并返回它们的最大公约数。提示：使用 wikipedia:Euclidean algorithm
gcd 15 25 = 5
第二步是使用 gcd 函数计算 int 列表的最大公约数。
val gcdl : int list -> int
gcdl 函数应按如下方式工作
gcdl [15; 75; 20] = 5
如果列表为空，则结果应为 0。
本练习的目标是在 F# 中实现归并排序算法来对列表进行排序。当我谈论排序时，指的是按升序排序。如果你不熟悉归并排序算法，它的工作原理如下
- 拆分：将列表分成两个大小相等的子列表
- 排序：对这些子列表进行排序
- 合并：排序的同时合并（因此得名）
请注意，该算法是递归工作的。它首先会拆分列表。下一步是对两个子列表进行排序。为此，它们将再次拆分，依此类推。这将基本上持续下去，直到原始列表被完全打乱。然后，递归将发挥其魔力，从底部组装列表。这在一开始可能看起来很混乱，但你会学到很多关于递归如何工作的知识，当涉及到多个函数时
split 函数
val split : 'a list -> 'a list * 'a list
split 函数将按如下方式工作。
split [2; 8; 5; 3] = ( [5; 2], [8; 3] )
拆分将作为元组返回。split 函数不需要对列表进行排序。
merge 函数
下一步是合并。我们现在想将拆分合并成一个排序的列表，假设两个拆分本身已经排序。merge 函数将接收两个已排序列表的元组，并递归地创建一个排序列表
val merge : 'a list * 'a list -> 'a list
示例
merge ( [2; 5], [3; 8] ) = [2; 3; 5; 8]
需要注意的是，merge 函数仅在两个拆分已经排序的情况下才会起作用。这将简化其实现。假设两个拆分都已排序，我们只需查看两个拆分的第一个元素，并比较哪个更小。为了确保这种情况，我们将编写最后一个函数。
msort 函数
你可以把它想象成一个组织算法正确执行的函数。它使用之前实现的函数，因此能够接受一个随机列表并返回排序后的列表。
val msort : 'a list -> 'a list
如何实现 msort
如果列表为空或列表只有一个元素，我们不需要对其进行任何操作，可以直接返回它，因为我们不需要排序它。
如果不是这种情况，我们需要对其应用我们的算法。首先将列表拆分成两个元素的元组，然后合并元组，同时递归地对元组的两个参数进行排序。