The Way 2 Inner Peace.

[scheme学习笔记]递归插入排序
[scheme学习笔记]scheme中的快速排序和合并排序

[转]Scheme 之道 --- 无处不在的函数

Qians posted @ 2011年11月09日 21:16 in scheme with tags Scheme , 4386 阅读

原文链接:http://hi.baidu.com/pudding/blog/item/7029c8fc45c046fdfc037f2e.html

 

无处不在的函数

基本的函数概念

Scheme 是一门函数式语言, 因为它的函数与数据有完全平等的地位, 它可以在运行时被实时创建和修改. 也因为它的全部运行都可以用函数的方式来解释, 莫能例外.

比方说, 把 if 语句作为函数来解释? (if cond if-part else-part) 是这么一个特殊的函数: 它根据 cond 是否为真, 决定执行并返回 if-part 还是 else-part. 比如, 我可以这样写:

((if (i-am-feeling-lucky) + -) my-happyness 1)

if 函数会根据我开心与否 (i-am-feeling-lucky 是一个由我决定它的返回值的函数 :P) 返回 + 或 - 来作为对我的开心值的操作. 所谓无处不在的函数, 其意义大抵如此.

把一串操作序列当成函数呢? Scheme 是没有 "return" 的, 把一串操作序列当作一个整体, 它的返回值就是这一串序列的最后一个的返回值. 比如我们可以写

(begin (+ 1 2) (+ 3 4))

它的返回是 7.

无名的能量之源

接下来, 我们就要接触到 Scheme 的灵魂 --- Lambda. 大家可以注意到 drScheme 的图标, 那就是希腊字母 Lambda. 可以说明 Lambda 运算在 Scheme 中是多么重要.

NOTE: 这里本来应该插一点 Lambda 运算的知识的, 但是一来我自己数学就不怎么好没什么信心能讲好, 二来讲太深了也没有必要. 大家如果对 Lambda 运算的理论有兴趣的话, 可以自行 Google 相关资料.

Lambda 能够返回一个匿名的函数. 在这里需要注意两点: 第一, 我用的是 "返回" 而不是 "定义". 因为 Lambda 同样可以看成一个函数 --- 一个能够生成函数的函数. 第二, 它是匿名的, 意思是, 一个函数并不一定需要与一个名字绑定在一起, 我们有时侯需要这么干, 但也有很多时候不需要.

我们可以看一个 Lambda 函数的基本例子:

((lambda (x y) (+ x y)) 1 2)

这里描述了一个加法函数的生成和使用. (lambda (x y) (+ x y)) 中, lambda 的第一个参数说明了参数列表, 之后的描述了函数的行为. 这就生成了一个函数 , 我们再将 1 和 2 作用在这个函数上, 自然能得到结果 3.

我们先引入一个 define 的操作, define 的作用是将一个符号与一个对象绑定起来. 比如 (define name 'kyhpudding) 之后再敲入 name, 这时候 Scheme 解释器就知道如何处理它了, 它会返回一个 kyhpudding.

我们自然也可以用 define 把一个符号和函数绑定在一起, 就得到了我们常用的有名函数.

(define add
        (lambda (x y) (+ x y)))

做一个简单的替换, 上面的例子就可以写成 (add 1 2), 这样就好理解多了.

上面的写法有点晦涩, 而我们经常用到的是有名函数, 所以我们有一个简单的写法, 我们把这一类简化的写法叫 "语法糖衣". 在前面我们也遇到一例, 将 (quote x) 写成 'x 的例子. 上面的定义, 我们可以这样写

(define (add x y) (+ x y))

Lambda 运算有极其强大的能力, 上面只不过是用它来做传统的 "定义函数" 的工作. 它的能力远不止如此. 这里只是举几个小小的例子:

我们经常会需要一些用于迭代的函数, 比如这个:

(define (inc x) (+ x 1))

我们也需要减的, 乘的, 还有其他各种乱七八糟的操作, 我们需要每次迭代不是 1, 而是 2, 等等等等. 我们很自然地有这个想法: 我们写个函数来生成这类迭代函数如何? 在 Scheme 中, 利用 lambda 运算, 这是可行且非常简单的. 因为在 Scheme 中, 函数跟普通对象是有同样地位的, 而 "定义" 函数的 lambda, 其实是能够动态地为我们创造并返回函数对象的. 所以我们可以这么写:

(define (make-iterator method step)
        (lambda (x) (method x step)))

没有语法糖衣的写法是:

(define make-iterator
        (lambda (method step)
                (lambda (x) (method x step))))

这个简单的例子, 已经能够完成我们在 C 之类的语言无法完成的事情. 要生成上面的 inc 函数, 我们可以这么写:

(define inc (make-iterator + 1))

这个例子展示的是 Scheme 利用 Lambda 运算得到的能力. 利用它, 我们可以写出制造函数的函数, 或者说制造机器的机器, 这极大地扩展了这门语言的能力 . 我们在以后会有更复杂的例子.

接下来, 我们会介绍 Scheme 的一些语言特性是怎么用 Lambda 运算实现的 --- 说Scheme 的整个机制是由 Lambda 驱动的也不为过.

比如, 在 Scheme 中我们可以在任何地方定义 "局部变量", 我们可以这么写:

(let ((x 1) (y 2)) 运用这些局部变量的语句)

其实 let 也只不过是语法糖衣而已, 因为上面的写法等价于:

((lambda (x y)
         运用这些局部变量的语句)
 1 2)

一些常用的函数

虽然说这篇文章不太注重语言的实用性. 但这里还是列出我们经常用到的一些操作,这能极大地方便我们的编程, 大家也可以想想他们是怎么实现的.


- cond

相当于 C 中的 switch

(cond
 (条件1 执行体)
 (条件2 执行体)
 (else 执行体))

- 循环语句

没有循环语句...... 至少没有必要的循环语句. Scheme 认为, 任何的循环迭代都
可以用递归来实现. 我们也不用担心递归会把栈占满, 因为 Scheme 会自动处理尾递
归的情况. 一个简单的 0 到 10 迭代可以写成这样.

(define (iterate x)
        (if (= x 10)
            x
            (iterate (+ x 1))))
(iterate 0)

很明显, 当我们递归调用 iterate 的时候, 我们不必保存当前的函数环境. 因为我
们递归调用完毕后就马上返回, 而不会再使用当前的环境, 这是一给尾递归的例子.
Scheme 能自动处理类似的情况甚至做一些优化, 不会浪费多余的空间, 也不会降低
效率. 所以完全可以代替循环.

当然我们有些便于循环迭代的操作, 大家可以试试自己实现他们. (当然在解释器内
部通常不会用纯 scheme 语句实现他们). 我们最常用的是 map 操作

(map (lambda (x) (+ x 1)) '(1 2 3))

运行一下这个例子, 就能理解 map 的作用了.

- 更多的数据操作

    * cadr cddr caddr 之类, 就是 car 和 cdr 的组合, 大家可以一个个试. drScheme 支持到 cadddr...
    * append: 将两个列表拼接在一起.

Avatar_small
λ 说:
2011年11月11日 12:28

不知 Scheme 有没有 nth 和 nthcdr 。

Rrandom 说:
2011年11月11日 18:34

nth在racket的gui库中看到了.nthcdr倒是没发现..

Avatar_small
λ 说:
2011年11月12日 13:28

cddr cadr cdar 这些函数不知普遍程度怎样……不然还是用 car cdr nthcdr 嵌套使用比较好。

CLISP的也只支持到 cddddr (四层)

Avatar_small
Rrandom 说:
2011年11月12日 16:21

囧.这个自己写就好了呀.而且这个东西我觉得递归的话一次处理一两个就行了呀..不用那么多的...

reverland 说:
2012年6月19日 17:31

我这么就觉得first second更好用些……

Avatar_small
Rrandom 说:
2012年6月19日 21:43

呃.... first second就是car cdr


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter