首页 > 代码库 > 我以为的函数式编程

我以为的函数式编程

函数式编程

函数式编程(functional programming)的思想相对于命令式编程(imperative programming),告诉计算机你要什么而不是告诉它要怎么做,举个例子:

(defun fun(x)
   (list ‘a (expt (car x) 2)))

这是函数是编程,而

(defun imp (x)
   (let* ((y (car x))
         (z (expt y 2)))
     (list ‘a z)))
是命令式编程,结果一样,但思想不同。

函数式编程还要尽量避免对函数的参数进行修改,避免所谓副作用(side effect),除了某些地方要利用它的情况除外。
C语言只能返回一个值,所以有时候要用指针或引用传递参数作为返回值;而lisp可以返回多个值

由底向上

bottom-up programming相对于自上而下、分治的编程风格,优点:利用clisp交互式的编程环境,可以写完一个模块就马上进行测试;一些实用函数(utility function)还可以在今后的项目中使用,随着写的程序越多,这些实用函数就越显出价值,你的工具越丰富,程序就越简洁紧凑,磨刀不误砍柴工。

抽象

要写实用函数就需要培养抽象能力,发现相似程序共同的结构/pattern,比如经常要写类似这样的递归:
求类表的长度

(defun len(lst)
   (if (null lst)
       0
       (+ 1 (len (cdr lst)))))
判断列表lst中所有元素是否都被fn函数判断为真:
(defun all(fn lst)
   (if (null lst)
       t
       (and (funcall fn (car lst)) (all fn (cdr lst)))))

(其实clisp中以上这两个例子都已经有内置函数了,叫length和every)
它们结构相似,可以写一个更通用的函数来实现这种递归结构的函数的功能:

(defun rec(joiner end base)
   (labels ((inner-rec (lst)
      (if (null lst)
          (if (functionp end) (funcall end) end)
          (funcall joiner
                   (if (functionp base)(funcall base (car lst)) base)
                   (inner-rec (cdr lst))))))
      #‘inner-rec))

定义的函数rec的返回值也是一个函数,这个返回的函数拥有递归的结构,可以实现上面len和all两个例子的功能:

(setf all2 (rec #‘(lambda(x y)(and x y)) t #‘oddp))
(funcall all2 ‘(1 2 3));相当于(all #‘oddp ‘(1 2 3))

(setf len2 (rec #‘+ 0 1))
(funcall len2 ‘(1 2 3));相当于(len ‘(1 2 3))

(setf copy (rec #‘cons nil #‘identity));生成一个用于复制列表的函数copy

(setf has-number (rec #‘(lambda(x y)(or x y)) nil #‘numberp));has-number判断列表是否含有数字

...

think recursively

作者在书中大量使用递归,尽管有时效率并不高,他认为递归让代码优雅。第一遍先用递归写,代码完成后再尽量改成尾递归,这样编译器(应该说是reader)会把尾递归优化成效率较高的迭代


我以为的函数式编程