前一篇:Common Lisp 學習:基礎篇
輔助函式和累加器變數
reverse 是 Common Lisp 的內建函式,作用是將一個列表(List)反轉:
USER(1): (reverse ‘(1 2 3 4))(4 3 2 1)USER(2): (reverse ’(1 (a b) (c d) 4))(4 (c d) (a b) 1)USER(3): (reverse nil)NIL
我們也可以很容易地實現自己的 reverse 函式,但是要提高效率並非易事,參考上一節的範例,我們可以實現一個簡單的 reverse 函式:
(defun my-reverse (L) (if (null L) nil (my-append (my-reverse (cdr L)) (cons (car L) nil))))
注意到上面的遞迴呼叫到了上一節的 my-append 函式來實現。但是這樣呼叫效率是低下並且很耗費記憶體的。
首先我們來追蹤外層的 my-reverse 函式:
CL-USER> (trace my-reverse)(MY-REVERSE)CL-USER> (my-reverse ‘(1 2 3 4)) 0: (MY-REVERSE (1 2 3 4)) 1: (MY-REVERSE (2 3 4)) 2: (MY-REVERSE (3 4)) 3: (MY-REVERSE (4)) 4: (MY-REVERSE NIL) 4: MY-REVERSE returned NIL 3: MY-REVERSE returned (4)2: MY-REVERSE returned (4 3)1: MY-REVERSE returned (4 3 2)0: MY-REVERSE returned (4 3 2 1)(4 3 2 1)
然後追蹤裡層的 my-append 函式:
CL-USER> (trace my-append)(MY-APPEND)CL-USER> (my-reverse ’(1 2 3 4)) 0: (MY-REVERSE (1 2 3 4)) 1: (MY-REVERSE (2 3 4)) 2: (MY-REVERSE (3 4)) 3: (MY-REVERSE (4)) 4: (MY-REVERSE NIL) 4: MY-REVERSE returned NIL 4: (MY-APPEND NIL (4)) 4: MY-APPEND returned (4) 3: MY-REVERSE returned (4) 3: (MY-APPEND (4) (3)) 4: (MY-APPEND NIL (3)) 4: MY-APPEND returned (3) 3: MY-APPEND returned (4 3) 2: MY-REVERSE returned (4 3) 2: (MY-APPEND (4 3) (2)) 3: (MY-APPEND (3) (2)) 4: (MY-APPEND NIL (2)) 4: MY-APPEND returned (2) 3: MY-APPEND returned (3 2) 2: MY-APPEND returned (4 3 2) 1: MY-REVERSE returned (4 3 2) 1: (MY-APPEND (4 3 2) (1)) 2: (MY-APPEND (3 2) (1)) 3: (MY-APPEND (2) (1)) 4: (MY-APPEND NIL (1)) 4: MY-APPEND returned (1) 3: MY-APPEND returned (2 1)2: MY-APPEND returned (3 2 1)1: MY-APPEND returned (4 3 2 1)0: MY-REVERSE returned (4 3 2 1)(4 3 2 1)
可以看到相當的繁瑣,我們要透過
輔助函式和累加器
變數構建效率更高的版本:
(defun my-reverse2-aux (L A) (if (null L) A (my-reverse2-aux (cdr L) (cons (car L) A))))(defun my-reverse2 (L) (my-reverse2-aux L nil))
階乘
我們用輔助函式的形式重寫階乘函式:
(defun my-factorial2-aux (N A) (if (= N 1) A (my-factorial2-aux (- N 1) (* N A))))(defun my-factorial2 (N) (my-factorial2-aux N 1))
尾部遞迴
遞迴函式通常易於思考它是如何實現的,可是缺點是執行緩慢。下面我們來用尾部遞迴的方式實現三個函式:
1:計算累加, 1+2+…+N :
(defun fast-triangular-aux (N A) (if (= N 1) A (fast-triangular-aux (- N 1) (+ N A))))(defun fast-triangular (N) (fast-triangular-aux N 1))
2:計算次方 B^E :
(defun fast-power-aux (B E A) (if (zerop E) A (fast-power-aux B (- E 1) (* B A))))(defun fast-power (B E) (fast-power-aux B E 1))
3:計算列表長度:
(defun fast-list-length-aux (L A) (if (null L) A (fast-list-length-aux (cdr L) (+ 1 A))))(defun fast-list-length (L) (fast-list-length-aux L 0))
函式作為物件
有時候,我們需要傳遞多次相同的物件。例如,我們定義一個函式:
(defun my-double (x) (* 2 x))USER(11): (my-double (my-double (my-double (my-double 5))))80
然而,這樣做很笨拙,還不能只管的表示出轉換了多少次。我們來構建一個遞迴函式:
(defun repeat-transformation (F N X) (if (zerop N) X (repeat-transformation F (- N 1) (funcall F X))))
我們來測試以下,重複4次 9 * 2:
(repeat-transformation (function my-double) 4 9)144
高階函式
剛才的函式不僅能進行數學執行,還可以處理列表,比如:
(defun prepend-blah (L) (cons ‘blah L))(repeat-transformation (function prepend-blah) 4 nil)(BLAH BLAH BLAH BLAH)
又或者,獲取列表中的第七個元素:
(car (repeat-transformation (function cdr) 6 ’(a b c d e f g h i j)))G
Lambda表示式
(repeat-transformation #‘(lambda (x) (* 3 x)) 5 2)486
下面我們來構建一個函式 apply-func-list,這個函式有兩個入參,第一個入參是帶有一系列函式的列表,第二個入參為一個物件。例如:
(apply-func-list (list #’my-double #‘list-length #’rest) ‘(1 2 3))
等價於
(my-double (list-length (rest ’(1 2 3))))
具體的函式如下:
(defun apply-func-list (L X) (if (null L) X (funcall (car L) (apply-func-list (cdr L) X))))
用幾個例子測試以下:
(apply-func-list (list #‘(lambda (N) (* 10 N)) #’fourth) ‘(10 20 30 40 50))400(apply-func-list (list #’third #‘second) ’((1 2) (3 4 5) (6)))5(apply-func-list (list #‘(lambda (N) (- 10 N)) #’list-length) ‘(a b c d e f))4(apply-func-list (list #’list #‘list) ’blah)((BLAH))
迭代列表
(defun double-list-elements (L) (if (null L) nil (cons (my-double (car L)) (double-list-elements (cdr L)))))(defun reverse-list-elements (L) (if (null L) nil (cons (reverse (car L)) (reverse-list-elements (cdr L)))))
可以將上面兩個函式整合成一個:
(defun mapfirst (F L) (if (null L) nil (cons (funcall F (car L)) (mapfirst F (cdr L)))))
執行:
(mapfirst #‘my-double ’(1 2 3 4 5))(2 4 6 8 10)(mapfirst #‘reverse ’((1 2 3) (a b c) (4 5 6) (d e f)))((3 2 1) (C B A) (6 5 4) (F E D))
當然,也可以透過 lambda 傳入函式:
(mapfirst #‘(lambda (x) (* x x)) ’(1 2 3 4 5))(1 4 9 16 25)(mapfirst #‘butlast ’((1 2 3) (a b c) (4 5 6) (d e f)))((1 2) (A B) (4 5) (D E))
事實上,由於高階函式太常用了,Common Lisp 已經內建了這樣的函式,稱為 mapcar:
(mapcar #‘(lambda (x) (* x x)) ’(1 2 3 4 5))(1 4 9 16 25)(mapcar #‘butlast ’((1 2 3) (a b c) (4 5 6) (d e f)))((1 2) (A B) (4 5) (D E))
尋找迭代 find-if
(find-if #‘evenp ’(1 2 3 4 5))2(find-if #‘(lambda (X) (not (null X))) ’(nil nil (1 2 3) (4 5)))(1 2 3)(find-if #‘(lambda (X) (>= (list-length X) 3)) ’((1 2) (3 4) (5 6 7) (a b c d)))(5 6 7)(find-if #‘(lambda (X) (evenp (list-length X))) ’((1) (2 3 4) (5 6)))(5 6)(find-if #‘(lambda (X) (zerop (rem X 3))) ’(1 2 3 4 5 6 7))3
過濾迭代 filter
remove-if 是 Common Lisp 內建的過濾器:
(remove-if #‘(lambda (X) (< (list-length X) 3)) ’((1 2 3) (1 2) nil (1 2 3 4)))((1 2 3) (1 2 3 4))(remove-if #‘(lambda (X) (zerop (rem X 2))) ’(1 2 3 4 5 6 7 ))(1 3 5 7)
返回多個值的函式
CL-USER> (floor 17 5)32CL-USER> (floor -17 5)-43CL-USER> (let ((x (floor 17 5))) x)3CL-USER> (multiple-value-bind (x y) (floor 17 5) (+ x y))5