리습의 개발 방법을 배우자: 함수의 구현

구현이 어느정도 명확해졌으면 주로 바텀-업 방식을 사용한다. 바텀-업은 구현 결과를 눈으로 확인하며 구현하는 장점이 있다.

다소 복잡한 구현부가 있으면 스텁 함수(stub functions)로 대체한다. 스텁 함수를 사용하는 것은 이전 포스트에서 설명하였다. 스텁 함수를 예상하는 결과로 동작하도록 하드코딩 하는 것도 좋은 트릭이다.

2014/06/20 - [Programming/Functional] - 리습의 개발 방법을 배우자: 대도 웜퍼스 게임의 설계

2014/06/24 - [Programming/Functional] - 리습의 개발 방법을 배우자: 함수와 하위 함수의 설계

이번 포스트에서는 엣지 리스트를 연관 리스트(association lists, 줄여서 alist)로 변환하는 함수를 개발한다.
엣지의 주 용도는 한 노드에 연결된 다른 노드를 찾는 역활이다.
이것을 위해서 매번 전체 엣지를 훓는 것은 비효율적이다.
이를 연관 리스트로 변환하면 한 노드에 연결된 노드의 목록을 좀 더 빨리 얻을 수 있다.
아래는 변환 전의 리스트와 변환 후의 연관 리스트의 견본이다.

• 리스트:

  '((1 . 2) (2 . 1) (2 . 3) (3 . 2))

• 연관 리스트:

  '((1 (2)) (2 (1) (3)) (3 (2)))

엣지의 단순 리스트를 연관 리스트로 변환하는 EDGES-TO-ALIST 함수를 구현한다.

아래는 이 함수의 개발 과정이다.

1. 연관 리스트의 요소 하나를 보면, 출발점과 도착점 목록으로 구성된다.

   (2 (1) (3))

   '2'는 출발점이고 '(1) (3)'은 도착점 목록이다.
   도착점 목록을 구하도록 하겠다.
2. 도착점 목록을 구할 수 있는 원시 데이타를 추출하자.
   '2'를 출발점으로하는 엣지는 구한다.
   이 엣지는 노드 '2'을 출발하여 한번에 도착가능한 노드를 포함한다.

   (direct-edges node edge-list)

   DIRECT-EDGES는 이전 포스트를 참고한다.
3. 위 결과-엣지 목록-에서 중복을 제거한다.

   (remove-duplicates (direct-edges node edge-list) :test #'equal)

   REMOVE-DUPLICATES 함수의 기본 비교 함수는 EQ이다.
   EQ는 같은 객체인지를 비교하기 때문에 엣지의 비교에는 사용할 수 없다.
   엣지을 비교하려면 EQUAL 함수을 사용해야 함으로
   키워드 매개변수 :TEST를 사용하여 EQUAL 함수를 전달한다.
4. 엣지에서 도착하는 노드를 뽑아낸다.

   (mapcar (lambda (edge) (list (cdr edge)))
           (remove-duplicates (direct-edges node edge-list)
                              :test #'equal))))

   출발점 '2'에 대한 결과는 다음과 같다.

   '((1) (3))

   여기까지 도착점 목록을 구하는 기능을 완성했다.
5. 출발점과 도착점의 목록으로 연관 리스트의 하나의 요소를 완성한다.

   (cons node
         (mapcar (lambda (edge) (list (cdr edge)))
                 (remove-duplicates (direct-edges node edge-list)
                                    :test #'equal))))

출발점 '2'에 대한 결과는 다음과 같다.

'(2 (1) (3))

6. 도시의 모든 노드에 위 기능을 적용해야한다.
   도시의 모든 노드를 구하자.

   (remove-duplicates (mapcar #'car edge-list))

   노드의 쌍을 가지는 엣지의 목록에서 첫번째 값을 모두 추출한다.
   견본 데이터라면 다름의 결과를 얻는다.

   '(1 2 3)

   이전 포스트에서 유향 그래프를 선택한 이유를 확인할 수 있다.
   코드가 명확하고 간단하다.
7. 도시의 모든 노드에 대해서 연관 리스트의 요소를 생성하는 기능을 적용한다.

   (mapcar (lambda (node)
             (cons node
                   (mapcar (lambda (edge) (list (cdr edge)))
                           (remove-duplicates (direct-edges node edge-list)
                                              :test #'equal))))
           (remove-duplicates (mapcar #'car edge-list)))

8. 위 내용을 EDGES-TO-ALIST라는 이름의 함수로 만든다.

   ;; convert a list of edges into an a alist of edges
   (defun edges-to-alist (edge-list)
     (mapcar (lambda (node)
               (cons node
                     (mapcar (lambda (edge) (list (cdr edge)))
                             (remove-duplicates (direct-edges node edge-list)
                                                :test #'equal))))
             (remove-duplicates (mapcar #'car edge-list))))