<a href="http://www.cnblogs.com/anderslly/archive/2008/10/archive/2008/10/08/fs-posts-indices.html" target="_blank">F#系列随笔索引</a>
链表（Linked list）是Lisp的主要数据结构之一，并且Lisp的源代码本身也由列表构成。F#中的列表类型表示为链表，它与C#中的数组、泛型List<T>类型有着明显的不同。链表可以用下面的图表示：
首先我们来看一下FP中列表的基本操作（其中的代码都由F#实现）。
列表的基本操作
cons：它是“construct”的缩写，用于构造列表，意即将一个元素添加到列表的开头。我们先约定空表表示为[]，在此基础上再约定操作符“::”表示cons操作，这样我们就可以构造任意的列表了。如：
可以看到这里是如何通过“cons”操作来一步一步构造列表的。
car：它表示“Contents of the Address part of the Register”，意即列表的第一个元素。F#中使用List模块的hd（Head）函数来执行car操作：
cdr：它表示“Contents of the Decrement part of the Register”，意即列表中第一个元素之外的元素。F#中使用List模块的tl（Tail）函数来执行cdr操作：
有了这三种基本操作，其它的操作都可以推导出来了。比如：
concat：该操作用于连接两个列表。在F#用“@”操作符执行该操作。
length：该检查列表的元素数量，在F#中使用List模块的length函数：
nth：该操作返回列表的第n个元素，在F#中使用List模块的nth函数：
这里代码用来获取list1中的索引（基于0）为2的元素，返回4。
现在再来看看List模块还有哪些重要的函数：
List模块（Microsoft.FSharp.Collections.List）的函数
List.rev：很明显，它可以翻转一个列表。要注意的是该函数会创建整个列表的一个副本，所以要注意性能问题。
List.zip：该函数的签名为a’ list -> b’ list -> (a’ * b’) list，将两个列表打包为一个元组的列表：
List.exists：该函数的签名类型为(a’ -> bool) -> a’ list -> ‘a，顾名思义，它用于检查列表是否包含了满足指定谓词函数的元素。
List.find：该函数的签名类型为(a’ -> bool) -> a’ list -> ‘a，可以看到它接受两个参数，第一个参数是谓词函数，第二个参数及传入的列表。可以这么理解，find函数对列表的元素逐一检查，看是否满足上面所说的谓词函数，如果找到了，返回该元素的值，否则抛出异常。
这里检查[1..10]中的每个数字，返回8。但如果找不到任何元素满足的话，会抛出KeyNotFoundException，这时可以使用tryfind，这个类似于C#中TryParse方法。
List.filter：该函数接受的参数与find函数类似，不过它的功能是对列表的元素进行过滤，将所有满足谓词函数的元素构造为一个列表返回：
另外，还有功能强大的聚合函数（Aggregate Operators），即iter、map和fold。（事实上，F#中的Set、Seq、Option和Array模块都支持这三种操作）
List.iter：该函数将枚举列表中的每个元素，并将每个元素应用于指定的函数，如：
输出结果为：
List.map：map函数用将列表转换为另一个列表。它的签名类型为：
看看这个效果图就容易理解了，对第一个列表的元素逐一应用函数，从而得到一个新的列表：
List.fold：在这三个函数中，fold最为强大，不过也最为复杂。它的功能可以理解为：假定我们有三个值，初始值baseValue，函数fun，列表list，逐一访问list中的每个元素，对其应用函数fun，将fun的执行结果累加到baseValue，fold将baseValue的最终值返回。在逐一访问列表时，可以采用从左到右或从右向左的方式，所以fold函数有两个实现：fold_left和fold_right。
这里baseValue是0，函数是accumulate，列表是[1..100]，最终结果为5050。
列表与模式匹配和递归的结合
take：接受两个参数，一个数字，一个列表，用于从列表开头获取指定个数的元素组成的新列表：
这里同时使用了递归和模式匹配，如果count小于等于0，返回空列表；否则返回从开头计数的指定个数的元素。
drop：该函数也接受两个参数，从列表开头移除指定个数的元素，将剩下的元素组成的列表返回：
如果count小于等于0，返回原列表；否则移除指定个数的元素。这里使用了head和tail，这样代码的可读性会更好。
通过take和drop函数，我们可以看到，首先得把列表理解为链表，然后在此基础上应用递归和模式匹配，就可以完成很多复杂的操作。
小结
本文介绍了函数式编程（FP）中的列表操作。首先是函数式编程中列表的三种基本操作，在此基础上我们可以推导出其它的各种操作；随后介绍了F#中List模块中的重要函数；最后通过两个自定义函数来展示如何结合使用列表、递归和模式匹配。顺便提一句，强烈建议你学习一下Haskell来了解FP的基本思想，在F#中很容易就能使用命令式编程的方式编写程序，这种灵活性往往使人偏离FP，尤其是在初学FP时。这就像我们学习英语的过程，想象一下，如果把你空投到美国（或其它英语国家），你的英语的进步是不是会快得多？
参考：
本文转自一个程序员的自省博客园博客，原文链接：http://www.cnblogs.com/anderslly/archive/2008/11/03/fsharp-adventure-fp-list-processing.html，如需转载请自行联系原作者。