cdr 하나를 바꾸면 그곳에 닿는 모든 경로의 모양이 달라진다.
파괴적 append를 수행하고 붙인 꼬리의 별칭을 관찰하며 순환을 만들고 같은 객체를 영원히 따라가지 않도록 고유 pair만 셉니다.
변경과 정체성은 append와 순회 같은 익숙한 리스트 연산의 의미를 어떻게 바꿀까요?
- 올바른 가변 리스트의 마지막 pair 찾기
- 기존 cdr 하나를 바꾸어 append! 구현하기
- 오른쪽 리스트로 들어가는 별칭이 결과와 계속 공유됨을 관찰하기
- proper list로 출력하지 않고 유한한 순환 만들기
- 명시적인 seen 객체 집합으로 고유 pair 세기
append!는 왼쪽 리스트를 다시 만들지 않습니다. 마지막 pair를 찾아 그 pair의 cdr이 right를 가리키게 합니다. 원래 left 이름은 이제 합쳐진 체인을 보고 right는 c에서 시작하는 공유 꼬리를 계속 가리킵니다. eq? 결과가 그 정체성 관계를 직접 드러냅니다.
순환 예제는 마지막 cdr을 첫 pair로 되돌립니다. 보통 재귀 리스트 순회는 빈 리스트에 닿지 못합니다. count-unique-pairs는 내려가기 전에 모든 pair 정체성을 기록하고 memq가 이미 본 pair를 찾으면 0을 더합니다. 프로그램은 프린터가 순환을 끝없이 펼치게 하지 않고 eq?로 순환을 보고합니다.
- 출력
- —
- 값
- —
- 진단
- —
파괴적 append 프로그램은 ((a b c d) (c d) #t)를 반환합니다. 순환 프로그램은 (3 #t)를 반환합니다.
b pair를 right에 연결하는 set-cdr! 하나를 찾고 공유 꼬리에 닿는 이름 세 개를 비교하세요. 순환 실행에서는 마지막 연결이 첫 pair로 돌아가는 지점과 다시 내려가지 않게 하는 각 memq 성공을 찾으세요.
프로그램을 수정하고 결과를 비교해 보세요.
마지막 pair 하나만 공유하는 리스트 두 개를 만들고 두 리스트를 모두 담은 구조의 고유 pair를 세세요. 순진한 재귀 pair 수와 비교하세요.
힌트 보기
car와 cdr을 내려가기 전에 pair 정체성을 기록하세요. 같은 할당은 출력 내용 대신 pair 정체성으로 확인합니다.