[FP In Scala] 함수적 자료구조

함수적 프로그램은 변수를 갱신하거나 mutable(변이 가능)한 자료구조를 수정하는 일이 없다.

 

함수형 프로그래밍에서 사용할 수 있는 자료구조는 어떤 것일까?

 

함수적 자료구조가 무엇이고 그것을 다루는 방법에 대해 알아보자. 

 

이를 통해 함수형 프로그래밍에서 자료구조를 정의하는 방법을 소개하고 관련 기법인 패턴 부합도 설명한다.

 

1. 함수적 자료구조의 정의

함수적 자료구조: 오직 순수 함수만으로 조작되는 자료구조

순수 함수: 자료를 변경하거나 부수 효과를 수행하는 일이 없어야 한다.

 

• 함수적 자료구조는 정의에 의해 불변이(immutable). ex) 빈 목록(List()나 Nil), 정수 3이나 4
  • 3 + 4를 평가하면 3이나 4가 수정되는 일이 없다.
  • 마찬가지로 두 목록을 연결하면 목록은 변하지 않고 새로운 목록이 만들어진다.
  • 자료구조가 그런 식으로 조작된다면 -> 여분의 복사가 많이 일어나지 않을까? -> 그렇지 않다.
    • 이유는 잠시 후 설명
  • Singly Linked List: 가장 보편적인 함수적 자료구조
    • 스칼라 표준 라이브러리에 정의되어 있는 List 자료 형식의 것과 개념적으로 동일.

package ch03

// 형식 A에 대해 매개변수화된 List 자료 형식.
sealed trait List[+A]

// 빈 목록을 나타내는 List 자료 생성자.
case object Nil extends List[Nothing]

// 비지 않은 목록을 나타내는 또 다른 자료 생성자.
// 또 다른 List[A]로 Nil일 수도 있고 다른 Cons일 수도 있다.
case class Cons[+A](head:A, tail: List[A]) extends List[A]

// List 동반 객체. 목록의 생성과 조작을 위한 함수들을 담는다.
object List {
  // 패턴 부합으로 목록의 정수들을 합하는 함수  
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    // x로 시작하는 목록의 합은 x + 목록의 나머지 부분의 합       
    case Cons(x, xs) => x + sum(xs)
  }
  
  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x, xs) => x * product(xs)
  }
  // 가변 인수 함수 구문  
  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))
}

 

• Sealed trait
  • 자료 형식을 도입할 때에는 trait 키워드를 사용.
    • trait 키워드로 정의하는 특질(trait)은 하나의 추상 인터페이스.
    • 필요시 일부 메서드의 구현을 담을 수도 있다.
    • 예제에서는 trait를 이용해서 List라는 특질을 정의.
      • 이 특질에는 메서드가 하나도 없다.
    • trait 앞에 sealed를 붙이는 것은 이 특질의 모든 구현이 반드시 이 파일 안에 선언되어야 한다는 것을 의미.
      • trait 대신 asbstract class를 사용해도 된다.
• case
  • case로 시작하는 두 줄은 List의 두 가지 구현, 즉 두 가지 자료 생성자이다.
    • List가 취할 수 있는 두 가지 형태를 나타낸다.
      • List는 자료 생성자 Nil로 표기되는 빈 목록일 수 있다.
      • 자료 생성자 Cons(Construct의 줄임말)로 표기되는 비지 않은 목록일 수도 있다.
        • 비지 않은 목록은 초기 요소 head 다음에 나머지 요소들을 담은 하나의 List(tail; 빈 목록일 수도 있다)로 구성.
        • List("a", "b")와 Cons("a", Cons("b", Nil))은 같은 것을 뜻함.
• 자료 형식의 다형적 특성
  • sealed trait List 다음에 형식 매개변수 [+A]를 두고 Cons 자료 생성자 안에서 그 A 매개변수를 사용함으로써, 목록에 담긴 요소들의 형식에 대해 다형성이 적용되는 List 자료 형식이 만들어진다.
  • 하나의 동일한 정의로 Int 요소들의 목록, Double 요소들의 목록, String 요소들의 목록 등등을 사용할 수 있게 된다.
    • 형식 매개변수 A에 있는 +는 공변[covariant]을 뜻한다.
      • 공변성과 반공변성을 통칭 가변성이라고 한다. 그리고 이와 반대되는 의미로는 불변성.
        • covariant: class C[+A]
        • contravariant: class C[-A]
        • invariant: class C[A]
      • 가변성(Variance) : 특정 타입의 객체를 다른 타입의 객체로 변환할 수 있는 성격을 말한다.
      • 공변과 불변의 이해
        • Dog가 Animal의 하위형식이면 List[Dog]가 List[Animal]의 하위 형식으로 간주.
        • 예제에서 Nil이 List[Nothing]을 확장.
          • Nothing은 모든 형식의 하위형식이고 A가 공변이므로 Nil을 List[Int]나 List[Double] 등 그 어떤 형식의 목록으로도 간주할 수 있다.
        • 스칼라가 하위형식을 이용해서 자료 생성자를 부호화하는 방식에서 기인한 군더더기에 가깝다.
          • 가변 지정자를 전혀 사용하지 않고 코드를 작성하는 것도 얼마든지 가능.

// 자료 생성자의 용례 몇 가지
val ex1: List[Double]: Nil
val ex2: List[Int] = Cons(1, Nil)
val ex3: List[String] = Cons('A', Cons('B', Nil))

• case object Nil이라는 표기를 이용해 빈 List를 구축할 수 있다.
• case class Cons는 Cons(1, Nil), Cons("A", Cons("B", Nil)) 같은 표기를 통해서 임의의 길의의 단일 연결 목록을 구축할 수 있게 한다.
  • 스칼라는 임의의 case class나 case object에 대해 기본 def toString: String 메서드를 생성한다.
    • 이 메서드는 디버깅에 편리하다.
    • REPL에서 List 값들을 시험해 볼 때 출력되는 것들이 바로 이 기본 toString구현의 출력이다.
      • REPL은 toString을 이용해서 각 표현식의 결과를 출력한다.
      • Cons(1, Nil)은 "Cons(1, Nil)"로 출력
        • toString은 재귀 방식이기 때문에 긴 목록을 출력할 때 스택이 넘칠 수도 있다.
        • 따라서 기본 구현과 다른 구현을 제공하는 것이 바람직하다.
• ex2는 A 형식 매개변수를 Int로 ex3은 String으로 인스턴스화한다. ex1의 예는 Nil이 List[Double] 형식으로 인스턴스화된다는 점에서 흥미롭다. 
  
  • 빈목록은 아무 요소도 없으므로 그 어떤 형식의 목록으로도 간주할 수 있다.
• 각 자료 생성자는 sum이나 product 같은 함수들에서처럼 패턴 부합에 사용할 수 있는 패턴도 도입한다. 

2. 패턴 부합

// 패턴 부합으로 목록의 정수들을 합하는 함수
def sum(ints: List[Int]): Int = ints match {
  case Nil => 0
  // x로 시작하는 목록의 합은 x + 목록의 나머지 부분의 합
  case Cons(x, xs) => x + sum(xs)
}

def product(ds: List[Double]): Double = ds match {
  case Nil => 1.0
  case Cons(0.0, _) => 0.0
  case Cons(x, xs) => x * product(xs)
}

• object List에 속함 함수 sum과 product를 보자.
  • 이런 함수들을 List의 동반 객체(companion object)라고 부르기도 한다. 
  • 두 함수 모두 패턴 부합을 활용한다.
  • sum 함수의 정의는 빈 목록의 합이 0이라고 한다.
  • 비지 않은 목록의 합은 첫 요소 x에 나머지 요소들의 합 xs를 더한 것이다.
    • x와 xs 대신 다른 이름도 사용이 가능하다. 목록 같은 순차열을 나타내는 변수의 이름으로는 xs, ys, as, bs 등을 사용하고 그러한 순차열의 개별 요소를 나타내는 변수의 이름으로는 x, y, z, a, b 등을 사용하는 것이 관례이다.
  • product 함수의 정의에 의하면 빈 목록의 곱이 1.0이고 0.0으로 시작하는 임의의 목록의 곱은 0.0, 그렇지 않으면 첫 요소에 나머지 요소들의 곱을 곱한 것이다.
  • 이들은 재귀적인 정의임을 주목.
    • List같은 재귀적인 자료 형식(Cons 자료 생성자에서 자신을 재귀적으로 참조함을 주목할 것)을 다루는 함수들을 작성할 때엣는 이처럼 재귀적인 정의를 사용하는 경우가 많다.
• 스칼라의 동반객체
  • 자료 형식과 자료 생성자와 함께 동반 객체를 선언하는 경우가 많다. 
  • 동반 객체는 자료 형식과 같은 이름의 object로 , 자료 형식의 값들을 생성하거나 조작하는 여러 편의용 함수들을 담는 목적으로 쓰인다.
• 패턴 부합은 표현식의 구조를 따라 내려가면서 그 구조의 부분 표현식을 추출하는 복잡한 switch 문과 비슷하게 작동한다.
• 패턴 부합 구문은
  • ds 같은 표현식(대상[target], 또는 검사자[scrutinee])으로 시작
  • 그 다음에 키워드 match가 오고
  • 그 다음에 일련의 case 문들이 {}로 감싸인 형태이다.
  • 부합의 각 경우 문은 =>의 좌변에 패턴(Cons(x, xs))이 있고 그 우변에 결과(x * product(xs))가 있는 형태
  • 패턴에 부합하면 그 경우 문의 결과가 젠처 부합 표현식의 결과가 된다.
  • 패턴이 여러개 부합하면 첫음으로 부합한 경우문을 선택
• 패턴 부합의 예
  • List(1, 2, 3) match { case _ => 42}는 42
    • 임의의 표현식과 부합하는 변수 패턴 _을 사용. _대신 foo, x도 가능하지만 경우 문의 결과 안에서 그 값이 무시되는 변수를 나타낼 때에는 이처럼 _를 사용하는 것이 일반적이다.
      • _ 변수 패턴은 여러 부분을 무시하기 위해 여러번 지칭될 수 있다.
  • List(1, 2, 3) match { case Cons(h, _) => h}의 결과는 1
    • 생성자 패턴과 변수들을 함께 사용해서 대상의 부분 표현식을 묶는다(bind 또는 capture)*
  • List(1, 2, 3) match { case Cons(_, t) => t}의 결과는 List(2, 3)이다.
  • List(1, 2, 3) match { case Nil => 42}의 결과는 MatchError(실행시점) 오류이다.
    • MatchError: 부합되는 표현식의 경우 문 중 대상과 부합하는 것이 하나도 없음.
• 패턴이 표현식과 부합하는지 판정하는 규칙이 무엇일까?
  • 패턴은 3이나 "hi" 같은 리터럴(소스 코드의 고정된 값을 대표하는 용어) x나 xs 같이 소문자나 밑줄로 시작하는 식별자로 된 변수, 그리고 Cons(x, xs)나 Nil 같은 자료 생성자로 구성.
  • 변수는 모든 것에 부합, 자료 생성자는 해당 형태의 값에만 부합.
  • 패턴의 변수들을 대상의 부분 표현식들에 배정한 결과가 대상과 구조적으로 동등하다면 패턴과 대상은 부합한다.
  • 대상과 부합한 패턴 경우 문의 우변에서는 해당 지역 범위에서 그 변수들에 접근할 수 있다.

연습문제 1
val x = List(1,2,3,4,5) match {
  case Cons(x, Cons(2, Cons(4, _))) => println(x)
  case Nil => println(42)
  // 다음에 부합
  case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => println(x + y)
  case Cons(h, t) => println(h + sum(t))
  case _ => println(101)
}

• 스칼라의 가변 인수 함수
  • object List의 apply 함수는 가변 인수 함수이다. 이는 이 함수가 A 형식의 인수 0개 이상 받을 수 있음을 뜻한다.
  • 자료 형식을 만들 때에는, 자료 형식의 인스턴스를 편리하게 생성하기 위해 가변 인수 apply 메서드를 자료 형식의 동반 객체에 집어넣는 관례가 흔히 쓰인다.
    • 그런 생성 함수의 이름을 apply로 해서 동반 객체에 넣어두면 List(1, 2, 3, 4), List("a", "b")처럼 임의의 개수의 인수들을 쉼표로 구분한 구문(이를 목록 리터럴 또는 리터럴)으로 함수를 호출할 수 있다.
  • 가변 인수 함수는 요소들의 순차열을 나타내는 Seq를 생성하고 전달하기 위한 작은 구문적 겉치레일 뿐이다. 
    • Seq는 스칼라의 컬렉션 라이브러리에 있는 하나의 인터페이스로, 목록이나 대기열, 벡터 같은 순차열 비슷한 자료구조들이 구현하도록 마련된 것이다.
    • apply 안에서 인수 as는 Seq[A]에 묶인다.
    • Seq[A]에는 head와 tail이라는 함수가 있다. 
    • 특별한 형식 주해인 _*는 Seq를 가변 인수 메서드에 전달할 수 있게 한다.
      • 시퀀스 타입을 하나의 인수로 취급 하겠다고 컴파일러에게 알리는 타입 선언

3. 함수적 자료구조의 자료 공유

• 자료가 불변이라면 목록에 요소를 추가 또는 제거하는 함수는 어떻게 할까?
  • 기존 목록의 앞에 1이라는 요소를 추가하려면 Cons(1, xs)라는 새 목록을 만들면 된다. 
  • 목록은 불변이므로 xs를 실제로 복사할 필요는 없다. 그냥 재사용하면 된다. 이를 자료 공유라 한다.
  • 불변이 자료를 공유하면 함수를 좀 더 효율적으로 구현할 수 있을 때가 많다.
  • 이후의 코드가 지금 이 자료를 언제 어떻게 수정할지 걱정할 필요 없이, 항상 불변이 자료구조를 돌려주면 된다.
  • 자료가 변하거나 깨지지 않도록 방어적으로 복사본을 만들어 둘 필요가 없는 것이다.
  • 이를 두고 함수적 자료구조는 영속적이라고 말한다. 
  • 이는 자료구조에 연산이 가해져도 기존의 참조들이 결코 변하지 않음을 뜻한다.
• 연습문제 2 첫 요소를 제거하는 tail 함수
• 연습문제 3 '''List의 첫 요소를 다른 값으로 대체하는 setHead 함수

  def tail[A](l: List[A]): List[A] =
    l match {
      case Nil => sys.error("tail of empty list")
      case Cons(_,t) => t
    }

  def setHead[A](l: List[A], h: A): List[A] = l match {
    case Nil => sys.error("setHead on empty list")
    case Cons(_,t) => Cons(h,t)
  }

3.1 자료 공유의 효율성

자료 공유를 이용하면 연산을 좀 더 효율적으로 수행할 수 있는 경우가 많다.

 

• 연습문제 4 tail을 일반화해서, 목록에서 처음 n개의 요소를 제거하는 함수 drop 구현
• 연습문제 5 주어진 술어와 부합하는 List의 앞 소도들을 제거하는 함수 dropWhile을 구현

def drop[A](l:List[A], n:Int): List[A] =
    if (n <= 0) l
    else l match {
    	case Nil => Nil
        case Cons(_, t) => drop(t, n-1)
    }
    
def dropWhile[A](l: List[A], f: A => Boolean): List[A] =
    l match {
      case Cons(h,t) if f(h) => dropWhile(t, f)
      case _ => l
    }

 

 

자료 공유의 더욱 놀라운 예로, 한 목록의 모든 요소를 다른 목록의 끝에 추가하는 것.

def append[A](a1: List[A], a2: List[A]): List[A] = 
  a1 match {
    case Nil => a2
    case Cons(h, t) => Cons(h, append(t, a2))
  }

• 첫 목록이 다 소진될 때까지만 값들을 복사한다.
• 함수의 실행시간은 오직 a1의 길이에 의존한다.
• 만일 이 함수를 배열 두 개를 이용해서 구현한다면 두 배열의 모든 요소를 결과 배열에 복사해야 했을 것이다.
• 이 경우 불변이 연결 목록이 배열보다 훨씬 효율적이다.

연습문제 6 그러나 모든 것이 효율적이진 않다. 한 List의 마지막 요소를 제외한 모든 요소로 이루어진 List를 돌려주는 함수 init.

  def init[A](l: List[A]): List[A] =
    l match {
      case Nil => sys.error("init of empty list")
      case Cons(_, Nil) => Nil
      case Cons(h, t) => Cons(h, init(t))
    }

• 단일 연결 목록의 구조 때문에, Cons의 tail을 치환할 때마다 반드시 이전의 모든 Cons 객체를 복사해야 한다.
• 자료 공유를 현명하게 활용하는 방법을 찾아내는 것이 핵심이다.

3.2 고차 함수를 위한 형식 추론 개선

dropWhile 같은 고차 함수에는 흔히 익명 함수를 넘겨준다.

인수 f에 익명 함수를 지정해서 호출하기 위해서는 그 익명 함수의 인수의 형식을 명시해야 한다.

val xs List[Int] = List(1, 2, 3, 4, 5)
val ex1 = dropWhile(xs, (x: Int) => x < 4)

• ex1의 값은 List(4, 5)이다. 
• 인수들을 두 그룹으로 묶으면 둘째 인수의 함수에 Int를 받지 않아도 스칼라가 추론한다.

  def dropWhile[A](as: List[A])(f: A => Boolean): List[A] =
    as match {
      case Cons(h,t) if f(h) => dropWhile(t)(f)
      case _ => as
    }

• dropWhile(xs)는 하나의 함수를 돌려주며, 그 함수를 인수 f로 호출한다(dropwhile은 커링되었다).
  • 즉, 인수가 두 개인 함수는 인수 하나를 받고 인수가 하나인 다른 함수를 돌려주는 함수로 표현할 수 있다.
• 스칼라의 형식 추론을 돕기 위한 것

val xs List[Int] = List(1, 2, 3, 4, 5)
val ex1 = dropWhile(xs)(x => x < 4)

 

4. 목록에 대한 재귀와 고차 함수로의 일반화

  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    // x로 시작하는 목록의 합은 x + 목록의 나머지 부분의 합
    case Cons(x, xs) => x + sum(xs)
  }

  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    // 0.0의 점검을 위한 평가 단축 논리를 포함하지 않도록 단순화
    // case Cons(0.0, _) => 0.0
    case Cons(x, xs) => x * product(xs)

• 두 정의가 아주 비슷하다.
• 유일한 차이는 빈 목록일 때의 반환값과 결과를 결합하는 데 쓰이는 연산이다.
• 코드의 중복을 발견했다면 부분 표현식들을 추출해서 함수 인수로 대체함으로써 코드를 일반화하는 것이 항상 가능하다.
• 일반화된 함수는 빈 목록일 때의 반환값과 비지 않은 목록일 때 결과에 요소를 추가하는 함수를 인수로 받는다.

 
 def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
    as match {
      case Nil => z
      case Cons(x, xs) => f(x, foldRight(xs, z)(f))
    }

  def sum2(ns: List[Int]) =
    foldRight(ns, 0)((x,y) => x + y)

  def product2(ns: List[Double]) =
    foldRight(ns, 1.0)(_ * _)

• 코드의 중복을 발견했다면 부분 표현식들을 추출해서 함수 인수로 대체함으로써 코드를 일반화하는 것이 항상 가능하다.
• foldRight로 구현된 product가 0.0을 만났을 때 즉시 재귀를 멈추고 0.0을 돌려줄까?
  • 아니요. 인수 평가 때문에 목록의 끝까지 순회할 것이다.
• foldRight(List(1,2,3), Nil:List[Int])(Cons(_,_))처럼 Nil과 Cons 자체를 foldRight에 전달하면 어떻게 될까?
  • 원래 목록을 반환.
• foldRight를 이용해서 목록의 길이를 계산

  def length[A](l: List[A]): Int =
    foldRight(l, 0)((_,acc) => acc + 1)

• foldRight 구현은 꼬리 재귀가 아니므로 긴 목록에 대해서는 StackOverflowError오류가 발생한다. 꼬리 재귀적인 또 다른 일반적 목록 재귀 함수 foldLeft를 이전 장에서 논의한 기법들을 이용해서 작성.

  def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
    case Nil => z
    case Cons(h,t) => foldLeft(t, f(z,h))(f)
  }

• sum, product와 목록의 길이를 계산하는 함수를 foldLeft를 이용해 작성

  def sum(l: List[Int]) = foldLeft(l, 0)(_ + _)
  def product(l: List[Double]) = foldLeft(l, 1.0)(_ * _)

• 목록의 역을 돌려주는 함수를 작성

def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc,h) => Cons(h,acc))

• foldLeft를 foldRight를 이용해서 구현할 수 있을까? 그 반대도 가능할까?

def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B = 
  foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
  foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

• append를 foldLeft나 foldRight를 이용해서 구현

def appendViaFoldRight[A](l: List[A], r: List[A]): List[A] = 
  foldRight(l, r)(Cons(_,_))

• 목록들의 목록을 하나의 목록으로 연결하는 함수를 작성. 실행 시간은 반드시 모든 목록의 전체 길이에 선형 비례

def concat[A](l: List[List[A]]): List[A] = 
  foldRight(l, Nil:List[A])(append)

• 정수 목록의 각 요소에 1을 더해서 목록을 변환하는 함수(새 List를 돌려주는 순수 함수)

def add1(l: List[Int]): List[Int] = 
  foldRight(l, Nil:List[Int])((h,t) => Cons(h+1,t))

• List[Double]의 각 값을 String으로 변환하는 함수 d.toString 사용

def doubleToString(l: List[Double]): List[String] = 
  foldRight(l, Nil:List[String])((h,t) => Cons(h.toString,t))

• 목록의 구조를 유지하면서 목록의 각 요소를 수정하는 작업을 일반화한 함수 map 작성

def map[A,B](l: List[A])(f: A => B): List[B] = 
  foldRight(l, Nil:List[B])((h,t) => Cons(f(h),t))

• 목록에서 주어진 술어를 만족하지 않는 요소들을 제거하는 함수 filter 작성

def filter[A](l: List[A])(f: A => Boolean): List[A] = 
  foldRight(l, Nil:List[A])((h,t) => if (f(h)) Cons(h,t) else t)

• map과 비슷하되 하나의 요소가 아니라 목록을 최종 결과 목록에 삽입하는 flatMap을 작성

def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] = 
  concat(map(l)(f))

• flatMap을 이용한 filter 구현

def filterViaFlatMap[A](l: List[A])(f: A => Boolean): List[A] =
  flatMap(l)(a => if (f(a)) List(a) else Nil)

• 목록 두 개를 받아서 대응되는 요소들을 더한 값들로 이루어진 새 목록을 구축하는 함수를 작성

def addPairwise(a: List[Int], b: List[Int]): List[Int] = (a,b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(h1+h2, addPairwise(t1,t2))
}

• 함수를 정수나 덧셈에 국한되지 않도록 일반화

def zipWith[A,B,C](a: List[A], b: List[B])(f: (A,B) => C): List[C] = (a,b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(f(h1,h2), zipWith(t1,t2)(f))
}

 

표준라이브러리

• 지금까지 만든 List와 표준 라이브러리에 있는 List의 차이는 Cons를 ::이라고 부른다는 것이다.
  • ::은 오른쪽으로 연관된다.
    • 1 :: 2 :: Nil == 1 :: (2 :: Nil) == List(1, 2)

4.2 단순 구성요소들로 목록 함수를 조립할 때의 효율성 손실

List의 한 가지 문제는, 어떤 연산이나 알고리즘을 아주 범용적인 함수들로 표현할 수 있긴 하지만 그 결과로 만들어진 구현이 항상 효율적인 것은 아니다.

같은 입력을 여러 번 훑는 구현이 만들어 질 수 있다. 이른 종료를 위해서는 명시적인 재귀 루프를 작성해야 할 수 있다.

• List가 또 다른 List를 부분 순차열로서 담고 있는지 점검하는 hasSubsequence 함수를 구현하라.

// @tailrec라고 재귀 함수 앞에 붙이면 스칼라 컴파일러에 꼬리 재귀가 있으니 최적화라고 알려준다.
@annotation.tailrec
def startsWith[A](l: List[A], prefix: List[A]): Boolean = (l,prefix) match {
  case (_,Nil) => true
  case (Cons(h,t),Cons(h2,t2)) if h == h2 => startsWith(t, t2)
  case _ => false
}
@annotation.tailrec
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = sup match {
  case Nil => sub == Nil
  case _ if startsWith(sup, sub) => true
  case Cons(_,t) => hasSubsequence(t, sub)
}

5. 트리

• List는 대수적 자료 형식(algebraic data type, ADT)이라고 부르는 것의 한 예이다.
  • ADT는 하나 이상의 자료 생성자들로 이루어진 자료 형식일 뿐이다.
  • 자료 생성자들은 각각 0개 이상의 인수를 받을 수 있다.
  • 자료 형식을 해당 자료 생성자들의 합 또는 합집합이라고 부르며, 각각의 자료 생성자는 해당 인수들의 곱이라고 부른다.
  • 대수적 자료 형식이라는 이름에 걸맞게 대수학의 용어들이 쓰임을 주목

대수적 자료 형식을 다른 자료구조의 정의에 사용할 수 있다. 이진 트리 자료구조 정의.

• 트리의 노드, 잎과 가지의 개수를 세는 함수 size 작성

  def size[A](t: Tree[A]): Int = t match {
    case Leaf(_) => 1
    case Branch(l,r) => 1 + size(l) + size(r)
  }

• Tree[Int]에서 가장 큰 요소를 돌려주는 함수 maximum을 작성하라.

  def maximum(t: Tree[Int]): Int = t match {
    case Leaf(n) => n
    case Branch(l,r) => maximum(l) max maximum(r)
  }

• 트리의 뿌리에서 임임의 잎으로의 가장 긴 경로의 길이를 돌려주는 함수 depth를 작성하라.

  def depth[A](t: Tree[A]): Int = t match {
    case Leaf(_) => 0
    case Branch(l,r) => 1 + (depth(l) max depth(r))
  }

• List에 대한 함수 map과 비슷하게 트리의 각 요소를 주어진 함수로 수정하는 함수 map을 작성하라.

  def map[A,B](t: Tree[A])(f: A => B): Tree[B] = t match {
    case Leaf(a) => Leaf(f(a))
    case Branch(l,r) => Branch(map(l)(f), map(r)(f))
  }

• size와 maximum, depth, map의 유사성을 요약해서 일반화한 새 함수 fold를 작성하라.

  def fold[A,B](t: Tree[A])(f: A => B)(g: (B,B) => B): B = t match {
    case Leaf(a) => f(a)
    case Branch(l,r) => g(fold(l)(f)(g), fold(r)(f)(g))
  }

  def sizeViaFold[A](t: Tree[A]): Int =
    fold(t)(a => 1)(1 + _ + _)

  def maximumViaFold(t: Tree[Int]): Int =
    fold(t)(a => a)(_ max _)

  def depthViaFold[A](t: Tree[A]): Int =
    fold(t)(a => 0)((d1,d2) => 1 + (d1 max d2))

  def mapViaFold[A,B](t: Tree[A])(f: A => B): Tree[B] =
    fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_,_))

ADT와 캡슐화

대수적 자료 형식이 형식의 내부 표현을 공용(public)으로 노출하므로 캡슐화를 위반한다.

함수형 프로그래밍에서 캡슐화는 다르게 취급한다.

가변상태가 없기 때문에 괜찮다.

형식의 자료 생성자를 노출해도 별문제가 없는 경우가 많다.