scheme 에 기본적으로 존재하는 pair 자료구조를 활용해, list 자료구조를 만들 수 있다.
예를 들어, 1 2 3 4 순서의 list는 아래와 같이 표현할 수 있다.
(cons 1 (cons 2 (cons 3 (cons 4 ()))))
이때 맨 뒤의 ()는 nil이라고 하는 다른 언어의 null과 비슷한 역할을 하는 값이다. 리스트 자료구조를 활용한 연습 문제들을 풀어보자.
연습문제 2.17
(빈 리스트가 아닌) 리스트를 인자로 받아, 마지막 원소만으로 이루어진 리스트를 내놓는 last-pair 프로시저를 정의하라.
(define (last-pair li)
(if (null? (cdr li))
(list (car li))
(last-pair (cdr li))))
; 테스트
(last-pair (list 23 72 149 34))
; (34)
연습문제 2.18
리스트를 인자로 받아 그 원소들의 순서를 뒤집는 reverse 프로시저를 정의하라.
(define (reverse li)
(define (iter-reverse rev li)
(if (null? li)
rev
(iter-reverse (cons (car li) rev) (cdr li))))
(iter-reverse () li))
; 테스트
(reverse (list 1 4 9 16 25))
; (25 16 9 4 1)
연습문제 2.19
이전에 나왔던 동전 바꾸기 프로시저의 인자로 동전 종류 리스트를 받아, 다양한 종류가 주어지는 상황에서 올바른 답을 내놓을 수 있도록 프로시저를 수정하라.
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))
(define (no-more? coin-values)
(null? coin-values))
(define (except-first-denomination coin-values)
(cdr coin-values))
(define (first-denomination coin-values)
(car coin-values))
(define (cc amount coin-values)
(cond ((= amount 0) 1)
((or (< amount 0) (no-more? coin-values)) 0)
(else (+ (cc amount
(except-first-denomination coin-values))
(cc (- amount (first-denomination coin-values))
coin-values)))))
; 테스트
(cc 100 us-coins)
; 292
연습문제 2.20
프로시저의 인자로 들어오는 값들의 수가 정해지지 않았을 때, 들어오는 값들을 모아 하나의 리스트로 받을 수 있다.
이 방법을 dotted-tail notation이라고 한다.
꼬리점 문법을 사용하여 하나 이상의 정수를 인자로 받아, 첫 번째 인자가 짝수라면 짝수만, 홀수라면 홀수만 들어 있는 리스트를 리턴하는 프로시저를 작성하라.
(define (same-parity . nums)
(define (same-parity-recur rem nums)
(cond ((null? nums) ())
((= rem (remainder (car nums) 2)) (cons (car nums)
(same-parity-recur rem (cdr nums))))
(else (same-parity-recur rem (cdr nums)))))
(same-parity-recur (remainder (car nums) 2) nums))
; 테스트
(same-parity 1 2 3 4 5 6 7)
; (1 3 5 7)
(same-parity 2 3 4 5 6 7)
; (2 4 6)
연습문제 2.21
수 리스트를 인자로 받아 각 원소를 제곱한 값들로 이루어진 리스트를 리턴하는 square-list 프로시저를 2가지 방법으로 정의하라.
; 방법 1
(define (square-list items)
(if (null? items)
()
(cons (square (car items))
(square-list (cdr items)))))
(square-list (list 1 2 3 4))
; (1 4 9 16)
; 방법 2
(define (square-list items)
(map square items))
(square-list (list 1 2 3 4))
; (1 4 9 16)
연습문제 2.22
위의 square-list는 재귀 프로세스로 구현되어 있는데, 이를 반복 프로세스로 아래처럼 만들어 보았더니 리스트가 거꾸로 나왔다.
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons (square (car things)) answer))))
(iter items ()))
그 이유는 아래와 같이 things의 맨 앞에 있는 요소를 answer에 뒤에서부터 하나씩 붙여서 만들기 때문이다.
; things = (1 2 3)
; answer = ()
; things = (2 3)
; answer = (1 ()) = (1)
; things = (3)
; answer = (4 (1)) = (4 1)
; things = ()
; answer = (9 (4 1)) = (9 4 1)
그렇다면 아래와 같이 cons에서 인자의 순서를 맞바꾸면 해결될까?
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons answer (square (car things))))))
(iter items ()))
그러나 문제는 애초에 scheme 의 list가 (a (b (c ()))) 의 형태로 구성되어 있다는 점이다. 위와 같이 하게 되면, 아래와 같이 이상한 자료 구조가 나오게 된다.
; things = (1 2 3)
; answer = ()
; things = (2 3)
; answer = (() 1)
; things = (3)
; answer = ((() 1) 4)
; things = ()
; answer = (((() 1) 4) 9)
리스트를 앞에서부터 읽어서 앞에서부터 처리하려면, 재귀 프로시저로 구현하는 것이 자연스럽다.
연습문제 2.23
이번에는 리스트를 받아서 리스트를 내놓는게 아니고, 순서대로 원소에 어떤 프로시저를 적용하는 for-each 프로시저를 구현하는 문제이다.
(define (for-each proc li)
(cond ((not (null? li)) (proc (car li))
(for-each proc (cdr li)))))
(for-each (lambda (x) (newline) (display x)) (list 12 34 56))
; 12
; 34
; 56
scheme 문법에 익숙치 않아서, 차례로 두 표현식을 실행하게 하는 방법을 찾느라 시간이 좀 걸렸다.