앞서, cons 를 통해 쌍을 만들고, 쌍 2개를 다시 쌍으로 만들 수 있는 쌍의 성질을 확인했다.
이처럼 어떤 연산으로 만든 물체가 다시 그 연산의 대상이 될수 있음을 '닫힘 성질을 가진다'(closure property) 라고 한다.
이러한 닫힘 성질은 계층 구조를 만들 수 있게 하기 때문에 데이터의 표현력을 더 끌어올리는 열쇠가 된다.
List
쌍으로 표현할 수 있는 데이터 구조 중 가장 쓸만한 것은 리스트이다.
Lisp 는 cons 를 연쇄적으로 겹쳐쓰지 않고 리스트를 정의할 수 있도록 특별한 문법을 지원한다.
(list a1 a2 a3 ...) 와 같이 정의할 수 있으며, 이는 (cons a1 (cons a2 (cons a3 ...))) 와 완전히 동일하다.
리스트의 마지막에는 두 번째 원소로 nil 이라는 값을 갖는다
리스트 연산
nil은 원소를 가지지 않은 차례열, 빈 리스트를 나타낸다.
Lisp 에서는 기본 프로시저 null? 을 사용할 수 있으며 nil 일 경우 false, 아닐경우 true 를 반환한다.
프로시저에 인자의 개수를 동적으로 받고 싶다면 해당 인자 앞에 . 을 붙이면 추가로 받은 원소들을 담은 리스트로 사용할 수 있다.
리스트 매핑
리스트의 모든 원소를 똑같은 방법으로 바꾸고 그 결과를 리스트로 반환하는 것은 쓸모가 많다. 이는 매핑, map 함수를 적용시키는 것과 같다.
(define (map proc items)
(if (null? items)
nil
(cons (proc (car items))
(map proc (cdr items)))))위와 같이 map 프로시저를 정의할 수 있고, (map (lambda (x) (* x x)) (list 1 3 5 7)) 과 같이 범용적으로 적용해볼 수 있다.
위에서 살펴본 List 는 닫힘 성질을 만족하는 쌍으로 만들어진 것이므로, 닫힘 성질을 만족하여 계층 구조를 이룰 수 있다.
((1, 2), 3, 4) 와 같이 3개의 원소를 같는 리스트를 정의해보자.
(define li (cons (list 1 2) (list 3 4)))car li 는 list 1 2 를 반환하고, cdar li 는 3을 cddar li 는 4를 반환하므로 ((1, 2), 3, 4) 를 나타낸다고 볼 수 있다.
위 구조는 Tree 형태로도 표현할 수 있다.
length li 의 값은 3이다. 앞의 원소가 element 라고 단정지었기 때문이다. 따라서, 트리를 순회하며 모든 리스트의 원소를 반환하는 count-leaves 를 정의해보자.
(define (count-leaves l)
(cond ((null? l) 0)
(not (pair? l)) 1
(else (+ (count-leaves (car l)) (count-leaves (cdr l))))))빈 리스트면 0, element면 1, 그게 아니면 쌍의 앞쪽과 뒤쪽의 element들의 수를 더하여 알 수 있다. (pair 는 쌍인지 아닌지를 구별해주는 기본 프로시저이다.)
위에서 볼 수 있듯, Tree 구조는 재귀적으로 모든 원소를 순회할 수 있는 특징을 갖고 있다.