(loop (print (eval (read))))

;;닭집을 차리기 위한 여정

루프의 컨벤션

SICP 2장을 죽 읽다보면 map을 이용한 리스트 조작이 나오고, 또 이를 재귀적으로 적용하여 우리가 흔히 얘기하는 이중 루프 (혹은 겹친 루프) 를 만들어 내는 예제나 연습문제가 많이 나온다.

은근하게도, 하나의 컨벤션이 제시되는데 바로 flatmap 이다.

아래는 바로 대표적인 예를 보여주는 연습문제 n-queens problem 이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(define (n-queens n)
  (define (iter m)
    (if (zero? m)
        '(())
        (filter (λ (queens)
                  (let* ([current-queen (car queens)]
                         [rest-queens (cdr queens)]
                         [indexed-rest-queens (map cons rest-queens (range 1 (length queens)))])
                    (not
                     (ormap (λ (indexed-queen)
                              (ormap (λ (current-queen-attack-range)
                                       (= (car indexed-queen) current-queen-attack-range))
                                     (list current-queen
                                           (+ current-queen (cdr indexed-queen)) ;; current-queen 과의 거리 +
                                           (- current-queen (cdr indexed-queen))))) ;; current-queen 과의 거리 - 
                            indexed-rest-queens))))
                (append-map (λ (result)
                              (map (λ (current)
                                     (cons current result))
                                   (range 1 (add1 n))))
                            (iter (sub1 m))))))
  (iter n))

plt-racket 에서의 flatmap 은 append-map이다. 참고로, clojure 에서는 mapcat

처음 SICP 를 볼때는 아무 생각없이 flatmap 을 썼었는데, 사실 이 flatmap 이 이런 쓰임새로 활용될 때에는 머릿속에 잘 그려지지 않는다고 생각한다. 해서, flatmap 의 동작을 설명하는 코드를 짜 보았다.

먼저 flatmap 은 apply-append-map 과 같다. 위에서 append-map 으로 시작하는 코드를 다음과 같이 바꿔도 동작할 것이다.

1
2
3
4
5
6
7
(apply append
    (map
     (λ (result)
           (map (λ (current)
                  (cons current result))
                (range 1 (add1 n))))
         (iter (sub1 m))))

이는 사실 모든 원소에 함수롤 적용한 결과로부터 얻은 리스트들을 다시 하나의 리스트들로 모은다는 뜻이다. 따라서 reduce-by-append 와 같다.

1
2
3
4
5
6
7
8
(foldr append
       '()
       (map
        (λ (result)
              (map (λ (current)
                     (cons current result))
                   (range 1 (add1 n))))
            (iter (sub1 m))))

이렇게 해놓고 나니, flatmap 이 어떻게 동작할 지, 머릿속에 분명하게 그려진다. 다시 flatmap 을 써야지.

요즘 SICP 스터디를 다시 하면서 요런코드들을 자바나 자바스크립트로 써보고 있는데, 특히 자바의 경우는 java8 이후로 람다와 스트림을 지원해서 어느정도 용이하게 작성하는게 가능해졌다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Main {
    public static void main(String[] args) {
        System.out.println(nQueens(5));
    }
    public static List<List<Integer>> nQueens(Integer n) {
        return nQueens(n, n);
    }
    
    public static List<List<Integer>> nQueens(Integer n, Integer m) {
        if (m.equals(0)) {
            List<List<Integer>> lst = new LinkedList<>();
            lst.add(new LinkedList<>());
            return lst;
        } else {
            return nQueens(n, m - 1).stream()
                    .flatMap(result ->
                                    IntStream.range(1, n + 1)
                                            .boxed()
                                            .map(current -> {
                                                List<Integer> lst = new LinkedList<>(result);
                                                lst.add(0, current);
                                                return lst;
                                            })
                    )
                    .filter(queens -> {
                        int currentQueen = queens.get(0);
                        
                        boolean isSafe = true;
                        for (int i = 1; i < queens.size(); i++) {
                            Integer queen = queens.get(i);
                            if (currentQueen == queen ||
                                    currentQueen + i == queen ||
                                    currentQueen - i == queen)
                                isSafe = false;
                        }
                        return isSafe;
                    })            
                    .collect(Collectors.toList());
        }
    }
}

요즘엔 자바를 쓰면서도 그다지 불편하지 않아서 참 다행이라는 생각이 든다.
하지만 점점 돈은 안되는 느낌이다. 슬프다..