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

Software Development/Scala

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

루ㅌ 2021. 4. 11. 18:39

함수적 프로그램은 변수를 갱신하거나 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)으로 노출하므로 캡슐화를 위반한다.

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

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

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