[모던 자바 인 액션] 19장. 함수형 프로그래밍 기법 (2)

19.3 스트림과 게으른 평가

스트림은 한 번만 소비할 수 있다는 제약이 있어서 재귀적으로 정의할 수 없다.

이 제약 때문에 발생하는 문제들을 살펴보자.

19.3.1 자기 정의 스트림

다음은 소수를 생성하는 예제 코드이다.

public static Stream<Integer> primes(int n) {
  return Stream iterate(2, i -> i + 1)
    .filter(MyMathUtil::isPrime)
    .limit(n);
}

public static boolean isPrime(int candidate) {
  int candidateRoot = (int) Math.sqrt((double) candidate);
  return IntStream.rangeClosed(2, candidateRoot)
    .noneMatch(i -> candidate % i == 0);
}

후보 수로 정확히 나누어 떨어지는지 매번 모든 수를 반복 확인한다.

또한 합성 수(소수로 나눌 수 있는 수)는 제외할 수 있다.

다음은 합성수를 제외하는 과정이다.

1. 소수를 선택할 숫자 스트림이 필요하다.
2. 스트림에서 첫 번째 수(스트림의 head)를 가져온다. 이 숫자는 소수다.
3. 이제 스트림의 tail에서 가져온 수로 나누어떨어지는 모든 수를 걸러 제외시킨다.
4. 이렇게 남은 숫자만 포함하는 새로운 스트림에서 소수를 찾는다. 1부터 재귀적으로 호출한다.

1단계 : 스트림 숫자 얻기

static Intstream numbers() {
  return Intstream.iterate(2, n -> n +1);
}

2단계 : 머리 획득

Static int head(IntStream numbers) {
  return numbers.findFirst().getAsInt();
}

3단계 : 꼬리 필터링

Static IntStraem tail(IntStream numbers) {
  return numbers.skip(1);
}

IntStream numbers = numbers();
int head = head(numbers);
IntStream filtered = tail(numbers).filter(n -> n % head != 0);

4단계 : 재귀적으로 소수 스트림 생성

static IntStream primes(IntStream numbers) {
  int head = head(numbers);
  return intStream.concat(
    IntStream.of(head),
    primes(tail(numbers).filter(n -> n % head != 0)
  );
}

나쁜 소식

4 단계 코드를 실행하면 에러가 발생한다. 앞서 스트림을 머리와 꼬리로 분리하면서 최종연산인 findFirst와 skip을 사용했다. 최종연산을 호출하면 스트림은 완전히 소비된다.

 

게으른 평가

더 심각한 문제가 있다. IntStream.concat은 두 개의 스트림 인스턴스를 인수로 받는다. 두 번째 인수가 primes를 직접 재귀적으로 호출하면서 무한 재귀에 빠진다.

이 문제를 해결하기 위해서는 primes를 게으르게 평가해야한다.

19.3.2 게으른 리스트 만들기

스트림에 일련의 연산을 적용하면 연산이 수행되지 않고 일단 저장된다. 스트림에 최종 연산을 적용해서 실제 계산을 해야하는 상황에서만 연산이 이루어진다.

게으른 특성으로 연산별로 스트림을 탐색할 필요 없이 한번에 여러 연산을 처리할 수 있다.

LinkedList의 요소는 메모리에 존재한다. 하지만 LazyList의 요소는 Function이 요청해야 생성된다.

기본적인 연결 리스트

interface MyList<T> {
  T head();
  
  MyList<T> tail();
  
  dafault boolean isEmpty() {
    return true;
  }
}
  
class MyLinkedList<T> implements MyList<T> {
  private final T head;
  private final MyList<T> tail;
  public MyLinkedList(T head, MyList<T> tail) {
    this.head = head;
    this.tail = tail;
  }
  
  public T head() {
    return head;
  }
    
  public MyList<T> tail() {
    return tail;
  }
    
  public boolean isEmpty() {
    return false;
  }
}
  
class Empty<T> implements MyList<T> {
  public T head() {
    throw new UnSupportedOperationException();
  }
   
  public MyList<T> tail() {
    throw new UnSupportedOperationException();
  }
}
...
MyList<Integer> I = new MyLinkedList<>(5, new MyLinkedList<>(10, new Empty()));

기본적인 게으른 리스트

class LazyList<T> implements MyList<T> {
  final T head;
  final Supplier<MyList<T>> tail;
  public MyLinkedList(T head, Supplier<MyList<T>> tail) {
    this.head = head;
    this.tail = tail;
  }    
  public T head() {
    return head;
  }
    
  public MyList<T> tail() {
    return tail.get();
  }
    
  public boolean isEmpty() {
    return false;
  }
}

이제 연속적인 숫자의 다음 요소를 만드는 LazyList의 생성자에 tail 인수로 Supplier를 전달하는 방식으로 n으로 시작하는 무한히 게으른 리스트를 만들 수 있다.

public static LazyList<Integer> from(int n) {
  return new LazyList<Integer>(n, () -> from(n+1));
}

게으른 필터 구현

public MyList<T> filter(Predicate<T> p) {
  return isEmpty() ? 
    this : p.test(head()) ?
      new LazyList<>(head(), () -> tail().filter(p)) : tail.filter(p);
}

재귀적으로 호출

static <T> void printAll(MyList<T> list) {
  if (list.isEmpty())
    return;
  System.out.println(list.head());
  printAll(list.tail());
}

---

19.4 패턴 매칭

패턴 매칭은 함수형 프로그래밍을 구분하는 또 하나의 중요한 특징이다.

19.4.1 방문자 디자인 패턴

방문자 디자인 패턴을 사용하면 자료형을 언랩할 수 있으며, 특정 데이터 형식을 '방문'하는 알고리즘을 캡슐화할 수 있다.

방문자 클래스는 지정된 데이터 형식의 인스턴스를 입력으로 받고, 인스턴스의 모든 멤버에 접근한다.

class BinOp extends Expr {
  ...
  public Expr accept(SimpiftExprVisitor v) {
    return v.visit(this);
  }
}

public class SimpiftExprVisitor {
   ...
   public Expr visit(BinOp e) {
     if("+".equal(e.opname) && e.right instanceof Number && ...) {
       return e.left;
     }
     return e;
   }
 }

19.4.2 패턴 매칭의 힘

자바는 패턴 매칭을 지원하지 않지만 스칼라 언어에서는 패턴 매칭을 사용해 간결하고 명확한 코드를 구현할 수 있다.

def simplifyExpression(expr: Expr): Expr = expr match {
  case BinOp("+", e, Number(0)) => e  //0 더하기
  case BinOp("*", e, Number(1)) => e  //1 곱하기
  case BinOp("/", e, Number(1)) => e  //1 나누기
  case _ => expr //expr을 단순화할 수 없다.
}

패턴 매칭을 지원하는 언어의 가장 큰 실용적인 장점은 커다란 switch 문이나 if-then-else 문을 피할 수 있다는 것이다.

 

자바로 패턴 매칭 흉내내기

def simplifyExpression(expr: Expr): Expr = expr match {
  case BinOp("+", e, Number(0)) => e  //0 더하기
  ...

위 스칼라 코드는 expr이 BinOp인지 확인하고 expr에서 세 컴포넌트(opname, left, right)를 추출한 다음에 각각의 컴포넌트에 패턴 매칭을 시도한다. 즉 스칼라의 패턴매칭은 다수준이다.

자바 8의 람다를 이용한 패턴 매칭 흉내 내기는 단일 수준의 패턴 매칭만 지원한다.

먼저 규칙을 정하자. 람다를 이용하며 코드에 if-then-else가 없어야 한다.

myIf(conditition, () -> e1, () -> e2);

static <T> T myIf(boolean b, Supplier<T> truecase, Supplier<T> falsecase) {
  return b ? truecase.get() : falsecase:get();
}

BinOp와 Number 두 서브클래스를 포함하는 Expr 클래스의 패턴 매칭 값으로 돌아와서 patternMatchExpr이라는 메서드를 정의할 수 있다.

interface TriFunction<S, T, U, R> {
  R apply(S s, T t, U u);
}

static <T> T patternMatchExpr(
    Expr e,
    TriFunction<String, Expr, Expr, T> binopcase,
    Function<Integer, T> numcase,
    Supplier<T> defaultCase) {
  return
    (e instanceof Binop) ? 
      binopcase.apply(((BinOp)e).opname, ((BinOp)e).left,((Binop)e).right) : 
    (e instanceof Number) ?
      numcase.apply(((NUmber)e).val) : defaultcase.get();
}

다음 코드를 살펴보자.

patternMatchExpr(e, (op, 1, r) -> {return binopcode;},
  (n) -> {return numcode;},
  () -> {return defaultcode;});

e가 BinOp인지(식별자 Op, l, r로 BinOp에 접근할 수 있는 binopcode를 실행)

아니면 Number인지(n 값에 접근할 수 있는 numCode를 실행) 확인한다.

둘다 아닐 경우 실행되는 defaultCode도 존재한다.

 

다음으로 patternMatchExpr을 이용해서 덧셈과 곱셈 표현식을 단순화하는 방법이다.

public static Expr simplify(Expr e) {
  TriFunction<String, Expr, Expr, Expr> binopcase =
    (opname, left, right) -> {
      if ("+".equals(opname)) {
        if (left instanceof Number && ((Number) left).val == 0) {
          return right;
        }
        if (right instanceof Number && ((Number) right).val == 0) {
          return left;
        }
      }
      if ("*".equals(opname)) {
        if (left instanceof Number && ((Number) left).val == 1) {
          return right;
        }
        if (right instanceof Number && ((Number) right).val == 1) {
          return left;
        }
      }
      return new BinOp(opname, left, right);
    };
  Function<Integer, Expr> numcase = val -> new Number(val); //숫자 처리
  Supplier<Expr> defaultcase = () -> new Number(0);
  
  return patternMatchExpr(e, binopcase, numcase, defaultcase);
}
...
Expr e = new BinOp("+", new Number(5), new Number(0));
Expr match = simplify(e);