！我的圈子函数式编程の道已经建立，对 FP 感兴趣的人可以加入，共同探讨这一古老的新事物！
引用
写在前面的话：Scheme、函数式编程(FP) 已入门者无须阅读。
这是我很久以前在自己写的一篇文章，现在又拿出来，是为了在 JavaEye 上造势，让访客们看一看 Scheme & 函数式编程世界的精彩（如果还不知道什么的 FP 的话）——当然，我绝对没有要贬低其它语言（除了 Java）的意思，事实上我最喜欢的语言之一就是文中提到的 C。好了，不罗嗦了，让我们一起来推开 Scheme 那道门吧。造势之后，我会写文章，结束关于函数式编程语言效率问题的讨论，值得期待哦~~
PS: 文中的 C、Java 代码可能不可以运行，它们只是用来说明问题的。
剧本：《古老，但很神奇》
人物：XX大学计算机系的社友 Go4——8呆，F1，老农和小四。
时间：“晚汇报”时间…
（老农在计算机系混的时间不短了，可惜技术一直没长进——连打电脑游戏都“不上档次”（小四语）。这不，昨天打 CS 又被 F1 欺负了，现在正郁闷着呢。）
老农（上网无聊中）：这年头，电脑好的人就是吃香啊~~（旁白）俺编程也差，游戏也差，废啦~~有了，上 CSDN.net，找点文章进修一下。
F1：老农，怎么样，CS 技术不行啊！好好练吧！
小四（推推眼镜）：老农伯伯！算了吧，我看你还是把编程学学好吧，哈哈，你那本《数据结构》好像还是新的吧？
（老农翻着 CSDN 上最新的 Blog 文章，忽然眼睛一亮。）
小四：嘿，发现什么了？
老农（连忙把 Firefox 最小化）：没什么，又不是黄网激动什么？！
老农（旁白）：不错，就用这篇文章 K.O.他们。
老农（满脸堆笑）：嘿，你们仨过来，我在网上发现一道数据结构方面的面试题目，想不想试试？
（正在上铺捧着 SIC P发呆的8呆忽然从发呆状态切换到亢奋状态，人啊~~）
8呆：少废话，快说！
老农（奸笑中）：设计一个函数 visit_tail，要求通过一次遍历找到链表中倒数第n个节点，然后从它开始用函数 func 例遍后面的所有链表元素，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。还有，为了简化问题，可以不给出链表的其它操作函数，比方说内存分配。
8呆（再次切换回发呆状态）：无聊…这也配叫题目…
老农（怒）：那你做啊！
（8呆在他的 SICP 上写了点什么，然后很潇洒地离开了寝室）
老农（专向另两个人）：既然他不参加，那我们三个比吧。
小四、F1（信心实足）：那现在开始计时吧。
…………
（老农把刚才背下来的代码改了改，花了3分钟抄在终端里）
老农（觉得时机移到）：我好了，你们呢？
小四（大喊）：解决解决！
F1：恩，我也好了，只是还没做单元测试。
（老农、小四（旁白）：我说你是编程还是写软件啊~~）
（3个人凑在老农的电脑上开始比拼）
老农：你们看，我是用 C 写的，已经测试过的。思想是，用两根指针，第一根先出发，相距 n 步后第二根出发。然后同时步进，直到第一根指针达到末尾，然后用 func() 函数对第二个指针开始的子链表进行例遍。
（小四和 F1 仔细一看，大笑不止。老农的代码如下（注释是笔者所加，其实是F1和小四看到各句时的反应）：）
typedef struct{ //哟，终于不用struct Node了，
int data;
Node * next;
} Node;
Node * visit_tail(iNode * head,int n,void (* func)(int cur)){
//K&R 时代的函数指针，见到老佛爷啦！！Node *pfirst;
Node *psecond; //吓，终于用到匈牙利命名法了（老农：#!?%）
pfirst=head;
for(counter=0;counter<n;counter++){
if(pfirst->next)
pfirst=pfirst->next;
else
return NULL; //什么破编程风格，真实版初学者啊
}
psecond=head;
while(pfirst!=NULL) {
pfirst=pfirst->next;
psecond=psecond->next;
}
for(int i=0;i < n; i++)
(* func)(psecond.data);
psecond=psecond->next;
}
} //靠，一个函数解决所有问题，高耦合啊！
老农（再怒）：小四少罗嗦！你的呢！拿出来啊？！
小四：在这儿，好好学学吧！
（大家一看，小四也用了 C，但…好漂亮啊。代码如下（注释是小四的解释）：）
typedef T int
//没有 C++ 一样“泛型”！
typedef struct {
T data;
Node * next;
} Node;
typedef struct {
Node * pre;
Node * curr; //当前结点与 List 绑定，不但可以分步例遍，还能保证正确初始化
} List;
void init_curr (List * l) {
l->curr = l->pre; //什么叫“编程风格”，知道不？！
}
void visit (List *l, void (* func)(T data)) {
while (l-curr) { //少用 !=NULL，这可是《The C Programing Language》上说的！
(* func)(l-curr->data);
l-curr = l->curr->next;
}
} //使用内联结点的公用访问函数，降低耦合
void index (List * l, int n) {
if (n) return NULL; //结点下标从1开始
init_curr(l);
if (n > 0) {
for (int i = 0; i < n; i++) {
curr = l->curr->next;
}
} //小四（自我陶醉）：漂亮啊
if (n < 0) {
tmp = l->curr;
for (int i = 0; i < n; i++) {
tmp = tmp->next;
}
while (tmp) {
l->curr = l->curr->next;
tmp = tmp->next;
}
}
return l->curr; //方便用户，增强鲁棒性能
}
void visit_tail (List * l, int n, void (* func)(T data)) {
index(l, -n);
visit(l, func);
} //多清爽
老农（口吐白沫）：我的挽回面子计划就这么，完了…
小四（偷笑）：你还是面对现实吧…
F1：小四你先别得意，我的你们还没拜读过呢！
（大家跑到 F1 电脑前一看，先是被长度吓了一跳，然后，无语。）
package datastruct.fifi.com.baidu.hi; //加入我的数据结构Java包
//当然只有包内成员才能创建Node对象
protected class Node {
private Object data; //多态性，让你们的 typedef 去死吧！
private Node next;
//构造函数
Node (Object data) {
this.data = data;
}
//获取下一个元素
public Node next () {
return this.next;
}
//变换下一个元素，用户不能调用
protected void setNext (Node o) {
this.next = o;
}
//取数据
public Object getData () {
return this.data;
}
//换数据
public void setData (Object data) {
this.data = data;
}
//根据Effective Java的最高指导，要重写toString()方法
public String toString () {
return this.data.toString();
}
}
//自定义异常类，数据结构下标越界
public class IndexOutOfRangeException extend IndexOutOfBoundsException {
public IndexOutOfRangeException (int lower, int upper, int index) {
super("Lower: " + lower +", Upper: " + upper + ", index: " + index);
}
}
//用于被继承的访问类
public class Visitor {
public operation (Object o) { //访问操作
System.out.println(o);
}
}
public class List {
private Node preFix;
private Node current;
private int size;
List () {
current = preFix = new Node();
size = 0;
}
//定位函数
private void index (int i) throws IndexOutOfRangeException {
if (i > size || i < -size-1) {
thows new IndexOutOfRangeException(0, size+1, i);
}
this.init();
if (i >= 0) {
for (int j=0; j < i; j++) {
current = current.next();
}
}
if (i < 0) {
i = - i - 1;
for (int j=0; j < i; j++) {
current = current.next();
}
}
}
//基本访问函数,需要一个继承自Visitor类的访问工具
public visit (Visitor v) {
while (current != null) { //Java拒绝看不懂的 while(curr) ！
v.operation (current.data());
current = current.next();
}
}
//访问后n个元素
public visitTail (Visitor v, int n) {
this.index(-n);
this.visit(v);
}
}
小四：靠！过分了！Java真是让程序员远离算法的祸首啊！爱好算法的人千万离它远些！
老农：反正我的“扬眉吐气”计划是泡汤了，你们想怎么讨论就怎么讨论吧。。。
小四：>_< 。。。
F1：we 得意。
（3人正在争执着，忽然门“吱”的一声（什么破门）开了，8呆走了进来。）
8呆：吵什么呢，比完了没？我是第一吧？
F1、小四、老农：什么啊，你不是自顾自走了啦？！
8呆（诧异）：我走之前已经写好啦。
（8呆拿来他的 SICP，递给三人。只见上面写了两行 Scheme 代码：）
(define (list-visit-tail func n l)
(map func (list-tail l (- (length l) n))))
（编辑公曰：上面这段 Scheme 代码滴意思斯酱紫滴：先定义一个名为 list-visit-tail 的过程，然后用内置宏 list-tail 取 list 的后 n 位组成 list 返回，再用操作 map 进行例遍。过程 map 是列表基础操作，实现也就3行；它不改变列表本身，而是返回操作后的列表。不改变状态是函数式编程的精髓。）
（完）
结语：
这个题目其实对于任何函数式编程语言来说都是一两句话。Scheme、Haskell它们都来自于世界上第二古老的语言 Lisp，但它们的思想博大精深——基于 lambda 演算理论的函数式编程，古老，但很神奇。
参考资料：
老农说的“这篇文章”：
一次遍历找链表倒数第n个节点
8呆的书SICP：
Structure and Interpretation of Computer Programs
命令式语言的劣势：
为何 Java（以及很多其他编程语言）令人不爽
函数式语言的优势：
为什么函数式编程至关重要？
Scheme 入门推荐书：
Teach Yourself Scheme in Fixnum Days
如果你还没学过编程的话：
How to Design Programs
如果你对函数式编程语言的效率有疑虑：
函数式语言：我的性能没问题
（一）
其它有关 Scheme 的东东详见：我的 Scheme 学习笔记 (
1 2 3 4 5)
（官网可能暂时关闭）
分享到：
相关推荐
沙画，作为一种古老而又现代的艺术形式，以其独特的魅力迅速吸引了幼儿的注意力。它不仅能够激发孩子们的想象力和创造力，同时还能培养他们的艺术鉴赏能力。在大班美术教学中引入沙画，是教育者不断寻求创新与突破的...
课件的设计从一个古老但充满传奇色彩的历史故事开始——马拉松长跑的起源。通过这个故事，孩子们不仅了解了信息传递的历史背景，而且也感受到了信息传递对于历史进程的深远影响。古代希腊士兵菲迪皮达斯在战争胜利后...
在IT领域，DOS（Disk Operating System）是一个古老但至关重要的操作系统，它是个人计算机早期广泛使用的命令行界面。"神奇的DOS程序.rar"这个压缩包文件，显然包含了一些能够带给我们惊喜和回忆的DOS应用程序。让...
从古老的算盘到现代化的电子计算器，计算器的形态和功能经历了翻天覆地的变化。电子计算器不仅体积小、携带方便，而且计算功能日益强大，能够处理各种复杂的数学问题。科学计算器的出现，更是将数学计算能力推向了一...
在青岛崂山的群山之中，有一棵古老的圆柏树，它的存在，不仅仅是一个植物个体，更是一个历史的见证者，生命奇迹的讲述者。这棵被冠以“神奇”的圆柏，历经了两千年的岁月沧桑，依旧挺立在崂山之巅，它的故事，就如同...
幻方，又称“魔方”或“纵横图”，是一种古老的数学游戏，起源于中国的洛书，距今已有数千年的历史。这种游戏的核心是将一系列数字按照特定规则填入一个正方形格子中，使得每行、每列以及对角线上的数字之和都相等。...
当你松开腰带，神奇的事情发生了——无论观众如何尝试，都无法像你一样让铅笔被腰带牢牢套住，铅笔总是会在腰带拉直后滑到外面去。这就是这个游戏的神秘之处，也是其吸引人的地方。 揭秘这个游戏的关键在于拓扑学的...
汉字，作为世界上最为古老的文字之一，其发展史就像一幅宏伟的画卷，描绘了中华民族几千年的文化脉络和历史变迁。 文档开头提及了关于汉字起源的多种传说，展现了古人对汉字产生的浪漫想象。结绳记事虽是简化了复杂...
它为我们提供了一种独特的视角，帮助我们在不断演变的网络威胁环境中，运用古老的智慧来构建和维护更加坚固的安全防线。通过阅读这本书，读者不仅可以学习到密码学的基本原理，还能掌握一套实战性强、富有创新的安全...
从古老的羊皮卷轴到现代的电子书，书籍的发展历程映射出人类文明进步的轨迹。《神奇的书》这篇文稿，通过两个不同的视角，向我们展示了书籍演变的过去和未来，同时强调了书籍在教育和生活中的核心地位。通过小学生王...
这种古老的计算方式虽然比手工计算便捷，但仍要求人们付出努力和时间来学习和练习。到了17世纪，西方的计算工具开始崛起，纳皮尔算筹和奥却德的圆柱型对数计算尺等工具的发明，极大地简化了数学中的复杂计算，尤其是...
关于圣诞节和圣诞老人的神奇传说，这是一个深深植根于西方文化中的传统，承载着欢乐、爱与给予的精神。圣诞老人的形象源于多个历史人物和神话故事的融合，他的故事跨越了千年的时空，从古老的北欧神话到现代的节日...
【中医-砭石的神奇养生功效】 中医理论中，砭石是一种古老的医疗工具，源于石器时代，被誉为中医六大医术之一。它以其独特的物理性质对人体产生诸多益处，包括按摩、热疗、生物学作用以及其他多种健康效益。下面将...
8. **注意事项**：尽管数字能量学提供了理解生活的新视角，但其科学性仍有争议。在运用数字能量学时，应保持理性，避免盲目迷信，同时结合实际生活经验进行判断。 通过以上解析，我们可以理解数字能量学不仅是古代...
筹策作为一种古老的计算方式，其简单实用的特点，让古代数学家们能够以较低的工具成本完成复杂的数学运算。随后，算盘的出现将计算效率推向了一个新的高度，尤其是在商业交易和日常生活中，其独特的计算方式体现了...
然而，纸张作为一种古老而又实用的材料，在我们的生活中仍然扮演着重要的角色。在教科版二年级上册科学第二单元《2.4神奇的纸》这一课中，学生们将会通过一系列精彩的实验和活动，学习到纸的形状与功能之间的奇妙...
"幻方 C++" 是一个涉及编程语言C++与古典数学概念的主题，主要探讨如何用C++实现一种古老的数学游戏或挑战，即构建幻方。幻方是一种将数字填入正方形格子中，使得每行、每列以及对角线上的数字之和都相等的数阵。在...
1. **七巧板教学**：七巧板是一种古老的智力玩具，由七个不同的形状组成，可用于拼接各种图形。在这个教案中，它被用来培养学生的观察力、动手能力和创新思维。 2. **活动目的**：通过七巧板的教学，目标是让学生...
汇编语言是一种古老的编程语言，但它在计算机领域中仍然占据着不可替代的位置。在如今这个以高级语言为开发主流的时代，汇编语言的低级特性，即直接与硬件交互的能力，让它在某些场合中显得尤为珍贵。尤其是当提及在...
汉字，作为世界上最古老的文字之一，其发展历程充满了神奇和智慧。2019-2020学年高中语文第三课探讨了汉字的简化和规范这一重要主题。汉字的简化与规范是中国汉字文化发展的重要里程碑，旨在提高书写效率，便于大众...