リストの各要素に手続きを適用する


Tags: R6RS, リスト

リストの各要素に手続きを適用し、その結果をリストとして受け取るには map 手続きを使う。

(import (rnrs))

(map (lambda (x) (* x 2)) '(1 2 3 4 5)) ; => (2 4 6 8 10)

map に渡した手続きの適用順序は規定されていないため、副作用のある手続きを使うと意図しない結果になることがある。

(import (rnrs))

(map display '(1 2 3 4 5)) ; 表示順序は処理系依存

このような用途には for-each を使う。このとき手続きの戻り値は単純に無視される。

(import (rnrs))

(for-each display '(1 2 3 4 5)) ; -> 12345

リストの各要素について二項演算 ⊕ を畳み込む手続き fold-left, fold-right がある。 fold-left は (... (((0 ⊕ a1) ⊕ a2) ⊕ a3) ...) のように左側から畳み込み、 fold-right は (a1 ⊕ (a2 ⊕ (a3 ⊕ (... (an ⊕ 0) ...)))) のように右側から畳み込む(Cf. http://foldl.com http://foldr.com )。

例えば a ⊕ b := cons(b, a) と定義すると fold-left ⊕ '() は reverse と等価になり、 a ⊕ b := b + 10 * a とすると fold-left ⊕ 0 は十進数の各桁の数値を要素として持つリストを数値に変換する計算になる。 ⊕ := cons とすると fold-right ⊕ は append になる。

(import (rnrs))

(fold-left (lambda (a b) (cons b a)) '() '(1 2 3 4 5)) ; => (5 4 3 2 1)
(fold-left (lambda (a b) (+ b (* 10 a))) 0 '(1 2 3 4 5)) ; => 12345

(fold-right cons '(4 5) '(1 2 3)) ; => (1 2 3 4 5)

⊕ に結合律が成り立つとき fold-left ⊕ と fold-right ⊕ は同じ結果を返す。ただし、多くの場合 fold-left, fold-right は下のように定義されているため(簡単のために一引数の場合を示す)、 fold-left では末尾呼び出しの最適化が働き、より効率よく動作することが多い。

(import (rnrs base))

(define (fold-left kons knil xs)
  (if (null? xs)
      seed
      (fold-left kons (kons knil (car xs)) (cdr xs))))

(define (fold-right kons knil xs)
  (if (null? xs)
      seed
      (kons (car xs) (fold-right kons knil (cdr xs)))))