Programming in Scala 스터디 정리 - 16장. 리스트

Programming in Sala 책으로 스칼라 스터디하면서 정리했던 내용이다. 지금은 3판 번역본도 나왔지만, 약간 앞서서 스터디를 시작해서 2판으로 진행했다.

16장

리스트 리터럴

• 리스트는 변경 불가능
• 리스트 구조는 재귀적(연결 리스트)

val num = List(1,2,3,4)
val diag3 = List(
  List(1,0,0),
  List(0,1,0),
  List(0,0,1)
)
val empty = List()

리스트 타입

• 리스트는 균일 : 리스트에 속한 모든 원소의 타입은 동일
• 리스트 타입은 공변적 : S가 T의 서브타입이면, List[S]도 List[T]의 서브타입
• 빈 리스트의 타입 : List[Nothing]

// Nothing은 모든 타입의 서브타입이므로, List[Nothing] 타입은 List[String]의 서브타입
val xs: List[String] = List()

리스트 생성

• Nil 과 :: 사용

val nums = 1 :: (2 :: (3 :: (4 :: Nil)))
val diag3 = (1 :: (0 :: (0 :: Nil))) ::
            (0 :: (1 :: (0 :: Nil))) ::
            (0 :: (0 :: (1 :: Nil))) :: Nil
val empty = Nil

• 콜론으로 끝나기 때문에 :: 연산자는 오른쪽 결합 법칙 적용

val num = 1 :: 2 :: 3 :: 4 :: Nil

리스트 기본 연산

• head : 첫번째 원소 반환
• tail : 첫번째 원소 제외한 나머지 원소로 이루어진 리스트 반환
• isEmpty : 리스트가 비었으면 true
• 빈 리스트에 head, tail 호출 시 NoSuchElementException 발생

리스트 패턴

• List(...) 패턴

val fruit = List("apples", "oranges", "pears")
val List(a, b, c) = fruit
// a: String = apples
// b: String = oranges
// c: String = pears

• :: 와 Nil 패턴

val fruit = List("apples", "oranges", "pears")
val a :: b :: rest = fruit
// a: String = apples
// b: String = oranges
// rest: List[String] = List(pears)

List 클래스 1차 메소드(함수를 인자로 받지 않는 메소드)

두 리스트 연결 :::

• xs ::: ys : xs의 모든 원소 뒤에 ys의 모든 원소가 있는 새로운 리스트
• 오른쪽으로 결합 : xs ::: ys ::: zs 는 xs ::: (ys ::: zs) 와 같음

분할 정복 원칙

def append[T](xs: List[T], ys: List[T]): List[T] =
  xs match {  // 분할 부분 : 2개로 분할(첫번째 원소, 나머지 원소들)
    case List() => ys
    case x :: xs1 => x :: append(xs1, ys)   // 정복 부분 : 나머지 원소들에 대한 연산
  }

리스트 길이 length

List(1,2,3).length // 3

리스트 양 끝 init, last

• init : 마지막 원소를 제외한 모든 원소
• last : 마지막 원소
• 빈 리스트에서 호출하면 NoSuchElementException 발생
• 전체 리스트를 순회해야해서 비효율적임

리스트 뒤집기 reverse

• 뒤집힌 새로운 리스트를 반환
• reverse는 자기 자신의 역 : xs.reverse.reverse == xs

접두사와 접미사 drop, take, splitAt

• xs take n : xs 리스트의 처음부터 n번째까지 원소를 반환
• xs drop n : 첫번째에서 n번째까지 원소를 제외한 xs 리스트의 모든 원소를 반환
• xs splitAt n : (xs take n, xs drop n) 리스트를 두번 순회하지 않음

원소 선택 apply, indices

• apply : 인덱스로 원소 선택
• xs apply n == xs(n) == (xs drop n).head. 인덱스 n에 비례한 시간이 걸려 잘 사용하지 않음
• indices : 유효한 모든 인덱스의 리스트 반환(Range())

리스트의 리스트를 한 리스트로 flatten

List(List(1,2), List(3), List(), List(4, 5)).flatten
// List(1,2,3,4,5)

두 리스트를 순서쌍으로 묶기 zip, unzip

• xs zip ys : xs 리스트와 ys리스트의 원소들의 순서쌍 리스트를 만들고, 길이가 긴쪽의 남는 원소를 버린다.
• xs.zipWithIndex : xs 리스트의 각 원소를 그 인덱스와 함께 순서쌍으로 묶은 리스트를 만든다.
• xs.unzip : 튜플의 리스트를 리스트의 튜플로 나눈다

리스트 출력 toString, mkString

• toString : 리스트에 대한 표준 문자열 표현 List( ... )
• xs mkString (pre, sep, post)
  • pre : 제일 앞에 출력할 접두사
  • sep : 원소 사이에 출력할 분리 문자
  • post : 제일 뒤에 출력할 접미사
• xs mkString sep == xs mkString ("", sep, "")
• xs mkString == xs mkString ""
• addString : 생성한 문자열을 결과로 반환하지 않고 StringBuilder 객체에 추가

val buf = new StringBuilder
abcde addString (buf, "(", ";", ")")

• mkString과 addString은 다른 모든 컬렉션에서도 사용 가능(Traversable로부터 상속한 메소드)

리스트 변환 iterator, toArray, copyToArray

• 리스트 <-> 배열 변환 : toArray, toList

val arr = abcde.toArray // 배열로 변환
arr.toList              // 리스트로 변환

• copyToArray : 리스트 원소를 어떤 배열의 특정 지점부터 연속으로 복사

xs copyToArray (arr, start) // xs 의 모든 원소를 arr의 start 지점에 복사

• iterator

val it = abcde.iterator
it.next

예제

// 병합 정렬
def msort[T](less: (T, T) => Boolean)(xs: List[T]): List[T] = {
  def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
    case (Nil, _) => ys
    case (_, Nil) => xs
    case (x :: xs1, y :: ys1) =>
      if (less(x, y)) x :: merge(xs1, ys)
      else y :: merge(xs, ys1)
  }
  val n = xs.length / 2
  if (n == 0) xs
  else {
    val (ys, zs) = xs splitAt n
    merge(msort(less)(ys), msort(less)(zs))
  }
}

List 클래스의 고차 메소드

리스트 매핑

• xs map f : xs 리스트의 모든 원소에 함수 f를 적용해서 나온 결과 값의 리스트를 반환

List(1, 2, 3) map (_ + 1) // List(2, 3, 4)

• flatMap : 원소의 리스트를 반환하는 함수를 받아, 모든 원소에 적용해서 나온 모든 리스트를 연결한 단일 리스트를 반환한다.

words map (_.toList)      // List(List(...), List(...))
words flatMap (_.toList)  // List( ... )

• foreach : 프로시저를 받아 모든 원소에 적용한다.

var sum = 0
List(1,2,3,4,5) foreach (sum += _)
sum // 15

리스트 걸러내기

• xs filter p : T => Boolean 타입의 술어 함수 p를 받아 원소 x중에 p(x) == true 인 원소의 리스트를 만든다.

List(1,2,3,4,5) filter (_ % 2 == 0) // List(2, 4)

• partition : filter와 같지만, true인 원소와 false인 원소들의 리스트를 한 쌍으로 만든다.

List(1,2,3,4,5) partition (_ % 2 == 0) // (List(2, 4),List(1,3,5))

• find : 술어 함수를 만족하는 첫번째 원소를 반환

List(1,2,3,4,5) find (_ % 2 == 0) // Some(2)
List(1,2,3,4,5) find (_ <= 0)     // None

• takeWhile : 술어를 만족하는 가장 긴 접두사를 반환

List(1,2,3,-4,5) span (_ > 0)  // List(1,2,3)

• dropWhile : 술어를 만족하는 가장 긴 접두사를 제거

List(1,2,3,-4,5) span (_ > 0)  // List(-4,5)

• span : takeWhile과 dropWhile결과를 순서쌍으로 반환. 한번만 순회한다.

List(1,2,3,-4,5) span (_ > 0)  // (List(1,2,3),List(-4,5))

리스트 전체에 대한 술어

• xs forall p : 리스트의 모든 원소가 p를 만족하면 true
• xs exists p : 리스트에서 p를 만족하는 원소가 하나라도 있으면 true

리스트 폴드

• (z /: xs) (op) : 왼쪽으로 편향된 연산 트리
• (xs :\ z) (op) : 오른쪽으로 편향된 연산 트리
  • z : 시작값
  • xs : 대상 리스트
  • op : 이항 연산자

def reverseLeft[T](xs: List[T]) =
  (List[T]() /: xs) { (ys, y) => y :: ys}

리스트 정렬

• xs sortWith before : 두 원소를 비교할 수 있는 함수 before를 사용하여 xs를 정렬
  • before : x before y가 true 이면 x가 y 앞에 위치
  • 병합 정렬 수행

List 객체의 메소드

원소로 리스트 만들기

• List.apply(...) == List(...)

List.apply(1,2,3) // List(1,2,3)

수의 범위를 리스트로 만들기

• List.range(from, until) : until을 제외한 범위 리스트

List.range(1,5) // List(1,2,3,4)

• List.range(from, until, increment) : increment 만큼 증가하는 리스트

균일 리스트 만들기

• List.fill(n)(v) : v를 n번 반복한 리스트

List.fill(5)('a')     // List(a,a,a,a,a)
// 인자 갯수를 추가하면 다차원 리스트 생성
List.fill(2,3)('b')   // List(List(b,b,b),List(b,b,b))

함수 도표화

• List.tabulate : 함수로 계산한 원소의 리스트 생성

List.tabulate(5)(n => n * n)  // List(0, 1, 4, 9, 16)

리스트 연결

• List.concat

List.concat(List('a','b'), List('c'))   // List(a,b,c)

여러 리스트 처리

• 튜플의 zipped 메소드는 여러 리스트에서 동작하는 공통 연산을 일반화

(List(10, 20), List(3, 4, 5)).zipped.map(_ * _)       // List(30, 80)

(List("abc","de"), List(3,2)).zipped.forall(_.length == _)    // true

(List("abc","de"), List(3,2)).zipped.exists(_.length != _)    // false

스칼라의 타입 추론 알고리즘

• 지역적 흐름 기반 타입 추론 방식

// abcde 의 타입으로 부터 메소드에 적용할 인자의 타입 추론
abcde sortWith (_ > _)    // (Char, Char) => Boolean

msort(_ > _)(abcde)         // 비교 함수를 인자로 넘길때 타입을 알 수 없음
msort[Char](_ > _)(abcde)   // 타입인자를 전달하여 추론 가능 (Char, Char) => Boolean
msortSwapped(abcde)(_ > _)  // 이미 알려진 첫번째 파라미터 목록 값의 타입을 참고하여 추론 가능

(xss :\ List[T]()) (_ ::: _)  // 연산 타입 추론 : (List[T], List[T]) => List[T]
(xss :\ List()) (_ ::: _)     // 연산 타입 추론 : (List[T], List[Nothing]) => List[Nothing]