3장 리스트 처리

1장에서 우리는 개미 수열의 각 줄을 문자열로 보았다. 덕분에 2장에서 정규표현식을 이용하여 개미 수열의 다음 줄을 계산할 수 있었다. 하지만 더 일반적으로 보자면 각 줄을 숫자 리스트라고 보는 것이 타당할 것 같다. 말하자면 next()의 시그너처1를 다음처럼 보자는 얘기다.

List<Integer> next(List<Integer> ns)

이 장에서는 개미 수열의 다음 줄을 계산하는 next()의 동작을 하나하나 따져보고 리스트 처리라는 관점에서 다시 구현해 볼 것이다.

next()가 하는 일

2장의 정규표현식은 잊고 다시 1장의 끝에서 막 리팩터링한 next()가 하는 일을 하나씩 따져보자. next()는 여전히 여러가지 일을 한꺼번에 하고 있다.

  • 루프 - 당연하게도 반복문을 포함하고 있다. 숫자를 하나씩 끝까지 읽어야 한다.
  • 카운트 - 같은 숫자의 반복 횟수를 카운트한다.
  • 비교 - 새로 읽은 숫자가 현재 카운트 중인 숫자와 같은지 비교한다.
  • 문자열 생성 - 반복된 숫자의 갯수와 그 숫자를 이용하여 결과 문자열을 누적 생성한다.

각각의 일은 대수롭지 않지만 이런 일들을 한꺼번에, 그것도 서로 뒤엉킨 체로 처리한다는 점이 문제다. (애초에 ant()가 분리되기 전에는 전체를 감싸는 루프가 하나 더 있었다.)

Java #3 - 리스트 처리

next()를 리스트를 처리하는 함수로 본다면 다음과 같이 단계를 나누어 볼 수 있다. 예를 들어, [1,3,1,1,2,2,2,1]를 입력으로 가정해 보자.2

  1. 리스트를 같은 숫자들의 그룹으로 나눈다. [1,3,1,1,2,2,2,1] → [[1],[3],[1,1],[2,2,2],[1]]
  2. 각 그룹을 길이와 그룹의 숫자의 리스트로 바꾼다. → [[1,1],[1,3],[2,1],[3,2],[1,1]]
  3. 리스트의 리스트를 다시 하나의 리스트로 이어붙인다. → [1,1,1,3,2,1,3,2,1,1]

각 단계를 도와주는 함수들이 이미 있다면, 다시 말해 이번에도 Wishful Thinking을 적용해 본다면 어떨까? 다음의 함수들이 있다면 next()를 구현하기 더 수월할 것이다.

List<List<A>> group(List<A> as)
as의 요소들을 이어진 같은 요소들끼리 그룹을 만든다.3
List<B> map(Function<A,B> f, List<A> as)
as의 요소들을 f를 이용하여 B로 만든다.
List<A> concat(List<List<A>> ass)
ass의 요소들(리스트)을 이어붙여서 하나의 리스트를 만든다.

이런 함수들만 있다면 next()를 구현하는 것은 너무나 간단한 일이다. map()의 인자는 2장의 replace()처럼 함수를 인자로 받는 고차 함수다. 이 경우는 group()으로 나누어진 각 그룹을 처리할 함수를 넘겨주면 되는데, 그룹(리스트)의 길이와 그룹의 값으로 이루어진 리스트를 반환하는 함수여야 한다.

group/map/concat을 이용하는 next() (Java)
  private static List<Integer> next(List<Integer> ns) {
    return concat(map(g -> asList(g.size(), g.get(0)), group(ns)));
  }

리스트 처리 함수들

우리가 있었으면 하고 바랐던 세 함수 중에서 map()과 concat()은 구현하기 어렵지 않다. 리스트의 각 요소들을 결과 리스트에 적절히 추가하기만 하면 된다.

리스트 처리 함수 - map과 concat (Java)
  public static <A, B> List<B> map(Function<A, B> f, List<A> as) {
    List<B> bs = new ArrayList<>();
    for (A a : as) {
      bs.add(f.apply(a));
    }
    return bs;
  }

  public static <A> List<A> concat(List<List<A>> ass) {
    List<A> list = new ArrayList<>();
    for (List<A> as : ass) {
      list.addAll(as);
    }
    return list;
  }

그런데 group()은 중첩된 리스트를 생성해야 하므로 상대적으로 복잡하다.

리스트 처리 함수 - group (Java)
  public static <A> List<List<A>> group(List<A> as) {
    List<List<A>> ass = new ArrayList<>();
    List<A> g = null;
    for (A a : as) {
      if (g == null || !g.get(0).equals(a)) {
        g = new ArrayList<>();
        ass.add(g);
      }
      g.add(a);
    }
    return ass;
  }

group()의 구현을 보면 개미 수열의 next()에 포함될 로직과 비슷하다. 하지만 일반화되었다는 점이 다르다. 이제 group()은 그 자체로 다른 문제에 재사용될 수 있다.4

정규표현식의 replace()와 마찬가지로 이번 장에서 정의한 group(), map(), concat()은 개미 수열 문제에 국한되지 않으며 일반적인 리스트 처리에 사용할 수 있다. 각 함수의 시그너처에 타입 파라미터가 있다는 점만 보아도 알 수 있다.

App-specific General
ant() group()
next() map()
  concat()

함수형 프로그래밍

이 장에서 맞보기로 보여준 몇 개의 리스트 처리 함수들은 함수형 프로그래밍(Functional Programming)에서는 매우 일반화된 유틸리티 함수다. 특히 map()으로 대표되는 가장 큰 특징은 “함수형 자료 구조”와 “고차 함수”의 활용이다.5 현대적 언어라고 할 수 있는 거의 모든 언어들은 이미 이같은 함수형 프로그래밍의 요소들을 포함하고 있거나 포함하는 방향으로 발전하고 있다. Java나 JavaScript도 이런 트렌드를 거스르지 않는다. 게다가 이미 함수형 스타일을 사용할 수 있게 도와주는 라이브러리들도 많다.6 함수형 스타일의 라이브러리는 기본적으로 제공하는 유틸리티의 추상 수준이 매우 높기 때문에 이번 장의 next()에서 본 것처럼 간결한 코드를 얻을 수 있다. 물론 적절한 추상화를 통해 간결해진 코드는 오류가 개입될 여지도 매우 적다.

1장의 Haskell 코드에서 ant 함수의 정의를 다시 살펴보자.

ant = iterate (group >=> sequence [length, head]) [1]

여기서 group >=> sequence [length, head] 부분이 Java나 JavaScript로 작성했을 때 다음 줄을 계산하는 next()에 해당한다.

이런! 벌써 Haskell과 거의 유사한 수준의 구현을 얻게 되었다. 사실 이번 장에서 리스트 처리 함수를 이용하여 작성된 next()는 함수형 프로그래밍 스타일을 따른 것이고, Haskell은 함수형 프로그래밍 언어의 대표 격이라서 두 코드가 유사할 수 밖에 없다. 그러나 결정적인 차이는 아직 남아있으니 여기서 멈추지 말기를 바란다.

Up next

4장 이터레이터