R6RS Scheme: 쌍과 리스트

Scheme에서 가장 기본적인 복합 데이터인 쌍(pair)과 그것으로 만들어지는 리스트(list)의 연산을 설명해요. cons, car, cdr에서부터 map, for-each 같은 고차 함수까지, 기본 라이브러리가 제공하는 모든 관계 프로시저를 다뤄요.

출처: 문서

본문

*쌍(pair)*은 두 필드를 가진 복합 구조인데, 역사적인 이유로 그 필드를 car 필드, cdr 필드라고 불러요. 쌍은 cons 프로시저로 만들어지고, car 필드와 cdr 필드는 각각 car와 cdr 프로시저로 접근해요.

쌍은 주로 리스트를 표현하는 데 사용돼요. 리스트는 재귀적으로 정의할 수 있는데, 빈 리스트이거나 cdr이 리스트인 쌍이에요. 더 정확히 말해, 리스트의 집합은 다음 조건을 만족하는 가장 작은 집합 X로 정의돼요:

빈 리스트는 X에 들어 있어요.
list가 X에 있으면, cdr 필드에 list를 담은 어떤 쌍도 X에 있어요.

리스트에서 연속된 쌍들의 car 필드에 든 객체들이 바로 그 리스트의 원소들이에요. 예를 들어 두 원소짜리 리스트는 car가 첫 원소이고 cdr이 (car가 두 번째 원소이고 cdr이 빈 리스트인) 쌍인 쌍이에요. 리스트의 길이는 원소의 개수인데, 이것은 쌍의 개수와 같아요.

빈 리스트는 자기만의 타입을 가진 특별한 객체예요. 그것은 쌍이 아니고, 원소가 없으며 길이가 0이에요.

Note: 위 정의들은 모든 리스트가 유한한 길이를 가지고 빈 리스트로 끝난다는 사실을 함의해요.

빈 리스트로 끝나지 않는 쌍의 체인을 *비정상 리스트(improper list)*라고 불러요. 비정상 리스트는 리스트가 아니라는 점에 주의하세요. 리스트 표기와 점 표기를 결합하면 비정상 리스트를 나타낼 수 있어요:

(a b c . d)

이것은 다음과 동등해요:

(a . (b . (c . d)))

어떤 주어진 쌍이 리스트인지 아닌지는 cdr 필드에 무엇이 저장돼 있는지에 달려 있어요.

`(pair? obj)` — procedure

obj가 쌍이면 #t를, 그렇지 않으면 #f를 반환해요.

(pair? '(a . b))        ⇒ #t
(pair? '(a b c))         ⇒ #t
(pair? '())              ⇒ #f
(pair? '#(a b))          ⇒ #f

`(cons obj1 obj2)` — procedure

car가 obj1이고 cdr이 obj2인 새로 할당된 쌍을 반환해요. 이 쌍은 eqv?의 의미에서 기존의 모든 객체와 다르다는 것이 보장돼요.

(cons 'a '())           ⇒ (a)
(cons '(a) '(b c d))    ⇒ ((a) b c d)
(cons "a" '(b c))       ⇒ ("a" b c)
(cons 'a 3)             ⇒ (a . 3)
(cons '(a b) 'c)        ⇒ ((a b) . c)

`(car pair)` — procedure

pair의 car 필드에 든 내용을 반환해요.

(car '(a b c))          ⇒ a
(car '((a) b c d))      ⇒ (a)
(car '(1 . 2))          ⇒ 1
(car '())                 &assertion exception

`(cdr pair)` — procedure

pair의 cdr 필드에 든 내용을 반환해요.

(cdr '((a) b c d))      ⇒ (b c d)
(cdr '(1 . 2))          ⇒ 2
(cdr '())                 &assertion exception

`(caar pair)`, `(cadr pair)`, …, `(cdddar pair)`, `(cddddr pair)` — procedure

이 프로시저들은 car와 cdr의 합성인데, 예를 들어 caddr는 다음과 같이 정의할 수 있어요:

(define caddr (lambda (x) (car (cdr (cdr x)))))

최대 4단계까지 임의의 합성이 제공돼요. 이런 프로시저는 모두 합쳐 스물여덟 개가 있어요.

`(null? obj)` — procedure

obj가 빈 리스트이면 #t를, 그렇지 않으면 #f를 반환해요.

`(list? obj)` — procedure

obj가 리스트이면 #t를, 그렇지 않으면 #f를 반환해요. 정의상 모든 리스트는 유한한 길이를 가지며 빈 리스트로 끝나는 쌍들의 체인이에요.

(list? '(a b c))     ⇒ #t
(list? '())           ⇒ #t
(list? '(a . b))      ⇒ #f

`(list obj ...)` — procedure

인자들의 새로 할당된 리스트를 반환해요.

(list 'a (+ 3 4) 'c)            ⇒ (a 7 c)
(list)                          ⇒ ()

`(length list)` — procedure

list의 길이를 반환해요.

(length '(a b c))               ⇒ 3
(length '(a (b) (c d e)))       ⇒ 3
(length '())                    ⇒ 0

`(append list ... obj)` — procedure

첫 번째 리스트의 원소들 뒤에 나머지 리스트들의 원소들이 이어지고, 마지막 쌍의 cdr이 obj가 되는, 아마도 비정상일 수 있는 리스트를 반환해요. obj가 리스트가 아니면 비정상 리스트가 결과로 나와요.

(append '(x) '(y))              ⇒ (x y)
(append '(a) '(b c d))          ⇒ (a b c d)
(append '(a (b)) '((c)))        ⇒ (a (b) (c))
(append '(a b) '(c . d))        ⇒ (a b c . d)
(append '() 'a)                 ⇒ a

append가 빈 체인이 아닌 쌍 체인을 만든다면 그것은 항상 새로 할당돼요. 쌍이 하나도 할당되지 않으면 obj가 그대로 반환돼요.

`(reverse list)` — procedure

list의 원소들을 역순으로 담은 새로 할당된 리스트를 반환해요.

(reverse '(a b c))              ⇒ (c b a)
(reverse '(a (b c) d (e (f))))  ⇒ ((e (f)) d (b c) a)

`(list-tail list k)` — procedure

list는 최소한 크기 k인 리스트여야 해요. list-tail 프로시저는 list의 첫 k개 원소를 생략해서 얻은 쌍들의 부분 체인을 반환해요.

(list-tail '(a b c d) 2)                 ⇒ (c d)

구현 책임: 구현은 list가 길이가 최소한 k인 쌍들의 체인인지 확인해야 해요. 그것이 이 길이를 넘어서까지 쌍들의 체인인지는 확인하지 않아도 돼요.

`(list-ref list k)` — procedure

list는 길이가 최소한 k + 1인 리스트여야 해요. list-ref 프로시저는 list의 k번째 원소를 반환해요.

(list-ref '(a b c d) 2)                 ⇒ c

구현 책임: 구현은 list가 길이가 최소한 k + 1인 쌍들의 체인인지 확인해야 해요. 그것이 이 길이를 넘어서까지 쌍들의 체인인지는 확인하지 않아도 돼요.

`(map proc list1 list2 ...)` — procedure

리스트들은 모두 같은 길이여야 해요. proc은 리스트들의 개수만큼의 인자를 받아들이고 단일 값을 반환해야 해요. proc은 어떤 리스트도 변형해서는 안 돼요.

map 프로시저는 proc을 리스트들의 원소들에 원소별로 (element-wise) 적용하고, 결과들을 순서대로 담은 리스트를 반환해요. proc은 항상 map 자신과 같은 동적 환경에서 호출돼요. proc이 리스트의 원소들에 적용되는 순서는 미지정이에요. map에서 여러 반환 값이 발생하면, 앞선 반환 값들이 만들어낸 값들은 변형되지 않아요.

(map cadr '((a b) (d e) (g h)))   ⇒ (b e h)
(map (lambda (n) (expt n n))
     '(1 2 3 4 5))                ⇒ (1 4 27 256 3125)
(map + '(1 2 3) '(4 5 6))         ⇒ (5 7 9)
(let ((count 0))
  (map (lambda (ignored)
         (set! count (+ count 1))
         count)
       '(a b)))                   ⇒ (1 2) or (2 1)

구현 책임: 구현은 리스트들이 모두 같은 길이인지 확인해야 해요. 구현은 proc에 대한 제약을, 설명된 대로 적용함으로써 수행되는 범위까지 확인해야 해요. 구현은 proc을 적용하기 전에 그것이 적절한 인자인지 확인할 수 있어요.

`(for-each proc list1 list2 ...)` — procedure

리스트들은 모두 같은 길이여야 해요. proc은 리스트들의 개수만큼의 인자를 받아들여야 해요. proc은 어떤 리스트도 변형해서는 안 돼요.

for-each 프로시저는 proc을 리스트들의 원소들에 원소별로 적용해 그 부수 효과(side effect)를 일으켜요. 적용 순서는 첫 원소부터 마지막 원소까지예요. proc은 항상 for-each 자신과 같은 동적 환경에서 호출돼요. for-each의 반환 값은 미지정이에요.

(let ((v (make-vector 5)))
  (for-each (lambda (i)
              (vector-set! v i (* i i)))
            '(0 1 2 3 4))
  v)                                ⇒ #(0 1 4 9 16)
(for-each (lambda (x) x) '(1 2 3 4)) ⇒ unspecified
(for-each even? '()) ⇒ unspecified

구현 책임: 구현은 리스트들이 모두 같은 길이인지 확인해야 해요. 구현은 proc에 대한 제약을, 설명된 대로 적용함으로써 수행되는 범위까지 확인해야 해요. 구현은 proc을 적용하기 전에 그것이 적절한 인자인지 확인할 수 있어요.

Note: for-each의 구현이 마지막 원소들에 대해 proc을 꼬리 호출(tail-call)할 수도 있고 하지 않을 수도 있어요.

더 알아보기 (Learn more)

출처: Pairs and lists - R6RS

R6RS Scheme: 쌍과 리스트