[Gauche][Scheme]foldの写経

fold便利やなー。

「プログラミングGauche」P.46 6.3リストの走査 より
(fold <手続き> <初期値> <リスト>)
<リスト>が要素(v0 v1 v2 ・・・vN)からなるとき、foldは次のとおりに動作します。

• まず、最初の要素v0と<初期値>を引数にして<手続き>を呼ぶ
• 次に、2番目の要素v1と上の呼び出しの結果を引数にして<手続き>を呼ぶ
• 次に、3番目の要素v2と上の呼び出しの結果を引数にして<手続き>を呼ぶ
• 以下同様に繰り返し、最後にvNとそれまでの結果を引数にして<手続き>を呼び、その結果をfoldの戻り値とする

もし<リスト>が空リストであれば、<初期値>がそのまま返されます。

以下写経的なもの

;; 引数のリストの合計を求める
(define (sum-of-numbers ls)
  (fold + 0 ls))

;; 引数のリストの積を求める
(define (product-of-numbers ls)
  (fold * 1 ls))

;; ２つの引数のうちで大きいものを返す
(define (pick-greater a b)
  (if (> a b) a b))

;; 引数のリストのうち最も大きな数値を求める
(define (max-number ls)
  (define (pick-greater a b)
    (if (> a b) a b))
  (fold pick-greater -inf.0 ls))

;; 引数のリストのうち最も小さな数値を求める
(define (min-number ls)
  (define (pick-smaller a b)
    (if (< a b) a b))
  (fold pick-smaller +inf.0 ls))


(min-number '(1 2 3 4 5 6 7 8 9 10)) ;; => 1
(max-number '(1 2 3 4 5 6 7 8 9 10)) ;; => 10
(pick-greater 1 2) ;; => 2
(pick-greater 10 5) ;; => 1-
(sum-of-numbers '(1 2 3 4 5)) ;; => 15
(product-of-numbers '(1 2 3 4 5)) ;; => 120

;; 引数のリストを全て表示する
(define (print-list ls)
  (fold (lambda (a b) (print a)) #f ls))
(print-list '(1 2 3 4 5 6))
;; => 1
;; => 2
;; => 3
;; => 4
;; => 5
;; => 6

;; 引数のリストの長さを求める
(define (length ls)
  (fold (lambda (a b) (+ b 1)) 0 ls))
(length '(1 2 3 4 5)) ;; => 5
(length '(1 2 3)) ;; => 3

;; 引数のリストのうち最も大きな数値を求める(lambda)
(define (max-number ls)
  (if (null? ls)
      (error)
      (fold (lambda (a b)
              (if (> a b) a b))
            (car ls)
            (cdr ls))))
(max-number '(1 2 3 4 5 6 5 4 3 2 1 0)) ;; => 6

;; fold関数の再定義
(define (fold2 func val ls)
  (if (null? ls)
      val
      (fold2 func (func (car ls) val) (cdr ls))))

;; fold2を使用した、引数のリストのうち最も大きな数値を求める
(define (max-num ls)
  (fold2 (lambda (a b) (if (> a b) a b)) 0 ls))

(max-num '(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1 0)) ;; => 10

追記

複数のリストに対応したもの。

• vallog: fold （複数リスト引数）