max-num手続きのリファクタリング

max-numをリファクリングの例があったので、要点をメモ。

;; リストから最大値を表示する手続き
(define (max-num lis)
  ;; 大きい数値を返す手続き
  (define (pick-greater a b)
	(if (> a b) a b))
  (fold pick-greater -inf.0 lis))
(print (max-num '(4 3 5 2)))

この手続きの特徴は、負の無限大「-inf.0」を初期値としてリストと比較して実現している。
リファクタリングは負の無限大ではなくcarとcdrだけで実現してみようというもの。

まずはコードから

;; リストから最大値を表示する手続き
(define (max-num lis)
  ;; 大きい数値を返す手続き
  (define (pick-greater a b)
	(if (> a b) a b))
  (fold pick-greater (car lis) (cdr lis))
(print (max-num '(4 3 5 2)))

渡されたリストの最初の要素を初期値に使う。

挙動の比較

printデバッグで結果を比較してみます。
【負の無限値】

(define (max-num lis)
  (define (pick-greater a b)
	(print a)
	(print b)
	(print "--")
	(if (> a b) a b))
  (fold pick-greater -inf.0 lis))
(max-num '(1 2 3))
;____Result_____
;1
;-inf.0
;--
;2
;1
;--
;3
;2
;--
;3

【リストの左右のポインタ値】

;; リストから最大値を表示する手続き
(define (max-num lis)
  ;; 大きい数値を返す手続き
  (define (pick-greater a b)
	(print a)
	(print b)
	(print "--")
	(if (> a b) a b))
  (fold pick-greater (car lis) (cdr lis)))
(max-num '())
;____Result_____
;2
;1
;--
;3
;2
;--
;3

初期値がリスト自身になっている分、比較数が一回少ないです。
左右のポインタをフル活用している感があって気持ちいい。

仕様を詰める

基本的に数値のリストが渡ってくるというのがこの手続きの条件ですが、空リストの場合はどうかという事が本には書いてありました。
試してみます。

【負の無限値】

(define (max-num lis)
  (define (pick-greater a b)
	(print a)
	(print b)
	(print "--")
	(if (> a b) a b))
  (fold pick-greater -inf.0 lis))
(max-num '())
;____Result_____
;-inf.0

【リストの左右のポインタ値】

;; リストから最大値を表示する手続き
(define (max-num lis)
  ;; 大きい数値を返す手続き
  (define (pick-greater a b)
	(print a)
	(print b)
	(print "--")
	(if (> a b) a b))
  (fold pick-greater (car lis) (cdr lis)))
(max-num '())
;____Result_____
;*** ERROR: pair required, but got ()
;Stack Trace:
;_______________________________________
;  0  lis
;
;    1  (max-num '())
;            At line 11 of "(stdin)"

この違いは、foldの最初の評価に絡んでいるようです。
foldはリストが空でない限り、処理を繰り返しますがfoldの初期評価で真(リストが空)になる為、最後に評価された結果(最後の値が初期値だ)である、「-inf.0」が返される。

carとcdrを利用した手続きの方はというと、foldで評価する前にcarの手続きを評価しているところでエラーになってしまっています。

結果の期待値としは両方とも、期待通りの結果ではありません。
例外処理をしてみます。*1

例外処理を含めたMax手続き

;; リストから最大値を表示する手続き
(define (max-num lis)
  ;; 大きい数値を返す手続き
  (define (pick-greater a b)
	(print a)
	(print b)
	(print "--")
	(if (> a b) a b))
  (if (null? lis)
	(print "List is Empty.")
	(fold pick-greater (car lis) (cdr lis)))
  )
(max-num '())

リストが空なら何かをするという感じです。
エラーメッセージを表示するという形にしましたが、本ではerrorという手続きでエラーを発生させているようです。
なるほど。

(error "hogehoge")

そんな感じで、foldの挙動を理解する事ができました。
サンプルは実際にやってみるに限ります。机上と体験では雲泥の差がでると感じました。*2

最後になりましたが、foldの手続きは引き渡された引数を両方とも必ず使用しなくてもいいらしいです。

*1:仕様決めの問題。

*2:私のレベルが低いという事も・・・