3주간 꾸역꾸역 16장 리스트를 정리해보았습니다. 정리를 해도 역시나 볼때마다 새롭네요. (–_–) 이하 편의상 음슴체로 갑니다.

16 Working with Lists

16.1 List literals

리스트 리터럴의 예

val fruit = List("apples", "oranges", "pears")
val nums = List(1, 2, 3, 4)
val diag3 = List(
  List(1, 0, 0),  
  List(0, 1, 0),  
  List(0, 0, 1),  
)  
val empty = List()

리스트가 array와 다른 점 – 1) 리스트는 Immutable 함. 2) 재귀적 구조를 가질 수 있음. (예. Linked List)

16.2 The List type

리스트는 동질성을 띔, 모든 리스트의 요소들은 같은 타입임.

List[T] – 타입 T 요소를 가지는 리스트 타입.

Scala에서 리스트 타입은 공변함(covariant) – 즉 S와 T 각 한 쌍의 타입에 대해, S가 T의 하위타입이면 List[S]도 List[T]의 하위타입이 됨. (예. List[String]은 List[Object]의 하위타입)

빈 리스트 타입은 List[Nothing]. Scala에서 모든 타입 T에 대해 List[Nothing]은 List[T]의 하위 타입. 따라서, 다음과 같은 코드도 허용됨.

val xs: List[String] = List()

16.3 Constructing lists

모든 리스트는 Nil과 ::(cons라 발음)의 빌딩 블럭으로 만들 수 있음. Nil은 공백 리스트. 중위표기 연산자(infix operator)인 ::는 전방에서 리스트를 확장함.

x::xs – 첫째 요소가 x이고 이어지는 요소가 xs인 리스트

따라서, 이전 리스트는 다음과 같이 정의될 수 있음.

val fruit = "apples" :: ("oranges" :: ("pears" :: 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

16. 4 Basic operations on lists

리스트 연산은 다음의 3가지 용어로 설명될 수 있음.

head – 리스트의 첫째 요소를 반환
tail – 첫째를 제외한 모든 요소들의 리스트를 반환
isEmpty – 비어있는 리스트인 경우 true를 반환

이런 연산은 List클래스의 메소드로 정의되어 있음 (이상 API 참조). 몇 가지 예는 아래와 같음.

empty.isEmpty       returns true
fruit.isEmtpy       returns false 
fruit.head          returns "apples"
fruit.tail.head     returns "apples"
diag3.head          returns List(1,0,0)

head와 tail 메소드는 빈 리스트가 아닌 경우에만 정의됨.

Nil.head    // java.util.NoSuchElementException: head of empty list

리스트가 어떻게 처리될 수 있는지에 대한 예제로 리스트 요소들을 오름차순으로 정렬해 봄.

가장 간단한 방법은 삽입 정렬(insertion sort)임.

삽입 정렬 – x::xs 리스트를 정렬하기 위해, 나머지 xs를 정렬하고, 첫째 요소 x를 결과의 오른쪽 위치에 삽입하는 방법. 빈 리스트 정렬할 경우는 빈 리스트를 얻게 됨.

def isort(xs: List[Int]): List[Int] =
  if (xs.isEmpty) Nil
  else insert(xs.head, isort(xs.tail))
      
def insert(x: Int, xs: List[Int]): List[Int] =
  if (xs.isEmpty || x <= xs.head) x :: xs
  else xs.head :: insert(x, xs.tail)

16.5 List patterns

패턴 매칭을 사용해 리스트를 분리할 수 있음.

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

리스트의 길이를 모를 경우에는 ::를 사용해서 매칭 – a :: b :: rest (a와 b 그리고 2개 이상의 리스트는 rest로 매칭)

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

List 패턴 매칭에 대해

List(…) 이나 :: 도 패턴임. List(…)는 라이브러리에 정의된 extractor 패턴의 인스턴스임 (26장에서 설명). cons 패턴인 x::xs은 중위 연산 (infix operation) 패턴의 특이한 경우임. 중위 연산도 메소드 호출과 동일함. p op q 는 op(p, q)와 같은데, 생성자 패턴처럼 다뤄지는 거임. x::xs는 ::(x, xs)처럼 다룸. 즉 ::라는 이름의 클래스가 있다는 것을 알 수 있음. 실제 빈 리스트를 만드는 scala.::라는 이름을 지닌 클래스가 있음. Scala에서 ::가 두 개 존재함 – 하나는 scala 패키지 내에 클래스로 있고, 또 하나는 List 클래스 내에 메소드로 있음. 이상, 22장에서 List 클래스가 어떻게 구현되었는지를 살펴볼 것임.

패턴 매칭으로 기본 메소드로(head, tail 그리고 isEmpty 등)로 작성된 코드를 대체할 수 있음.

def isort(xs: List[Int]): List[Int] = xs match {
  case List() => List()
  case x :: xs1 => insert(x, isort(xs1))
}
  
def insert(x: Int, xs: List[Int]): List[Int] = xs match {
  case List() => List(x)
  case y :: ys => if (x <= y) x :: xs
      else y :: insert(x, ys)
}

위와 같이 패턴 매칭으로 좀 더 간결하고 분명한 코드를 작성할 수 있음.

16.6 First-order methods on class List

리스트 클래스의 일차 메소드에 대해 설명하겠음.

일차(first-order)라는 것은 어떤 함수도 인자로 취하지 않는다는 것을 말함.

Concatenating two lists

:::로 두 개의 리스트 연결함. xs ::: ys는 xs 다음에 ys가 오는 새 리스트를 만듦.

List(1, 2) ::: List(3, 4, 5)    // List(1, 2, 3, 4, 5)
List() ::: List(1, 2, 3)        // List(1, 2, 3)
List(1, 2, 3) ::: List(4)        // List(1, 2, 3, 4)

xs ::: ys ::: zs는 xs ::: (ys :::zs)로 해석됨.

The Divide and Conquer principle

Concatenation(:::)은 직접 구현할 수도 있음. append라고 부르고 리스트 클래스 외부에 정의해 보겠음. 연결할 두 개의 리스트를 매개변수로 받아야 하고 리스트는 임의의 요소를 지님. 따라서, 다음과 같음.

def append[T](xs: List[T], ys: List[T]): List[T]

append를 구현하기 위해 리스트와 같은 재귀적 데이터 구조를 이용하는 프로그램의 설계원리인 “분할정복(divide and conquer)”을 기억해보는 것이 좋음.

Divide and conquer (분할 정복)

리스트에 대한 대부분의 알고리즘은 먼저 입력 리스트를 패턴 매칭을 사용해 단순한 case들로 쪼개며, 이를 분할(divide)이라고 함. 그리고 각 case에 대한 결과를 구성함. 결과가 빈 리스트가 아닐 경우, 어떤 부분은 같은 알고리즘의 재귀적 호출로 인해 구성하는데, 이를 정복(conquer)이라고 함.

구현할 append 메소드에 이 원리를 적용하기 위해, 매치할 리스트를 결정해야 함. 경우의 수가 2가지 뿐이므로 단순한 편임.

정복 단계에서는 두 입력 리스트의 모든 요소들로 이루어지는 리스트를 만들어야 함.

리스트는 뒤에서 앞쪽으로 만들어지므로, ys는 그대로 남겨두지만 xs는 분해되어 ys에 앞에 삽입될 필요가 있음. 따라서,xs가 패턴매칭의 집중 대상이 됨.

리스트에서 가장 흔한 패턴 매칭은 비어 있지 않은 리스트로부터 빈 리스트를 구별해내는 것임.

이상, append 메소드는 다음과 같은 형식임.

def append[T](xs: List[T], ys: List[T]): List[T] =
  xs match {
      case List() => // ??
      case x :: xs1 => // ??
  }

??을 채우기 위해, 먼저 xs가 빈 리스트인 경우, 연결 결과로 두 번째 리스트를 넘겨주게 됨.

case List() => ys

다음으로 머리 x 와 꼬리 xs1로 이뤄지는 입력 리스트 xs가 오는 경우, 결과 역시 비어있지 않은 리스트임.

비어있지 않은 리스트를 구성하기 위해서는 리스트의 머리와 꼬리가 무엇인지 알아야 함. 머리는 x라는 걸 이미 알고 있고, 꼬리는 첫 번째 리스트의 나머지 xs1와 두 번째 리스트인 ys로 구성됨.

따라서 ?? 구현이 완료된 모습은 다음과 같음.

def append[T](xs: List[T], ys: List[T]): List[T] =
  xs match {
      case List() => ys
      case x :: xs1 => x :: append(xs1, ys)
  }

Taking the length of a list: length

length는 리스트의 길이는 계산함.

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

Accessing the end of a list: init and last

last는 리스트의 마지막 요소를 반환, init은 리스트의 첫째 요소를 반환.

val abcde = List('a', 'b', 'c', 'd', 'e')
abcde.last       // e 
abcde.init       // List(a, b, c, d)

head와 tail처럼 빈 리스트는 init과 last 메소드가 없음.

List().init       // java.lang.UnsupportedOperationException
List().last     // java.util.NoSuchElementException

일정한 시간(constant time)에서 실행되는 head와 tail과 달리 init과 last는 결과를 계산하기 위해 전체 리스트를 횡단함. 가급적 마지막 요소보다는 리스트의 머리를 사용해서 데이터를 조직하는 것이 좋음.

Reversing lists: reverse

리스트의 마지막을 자주 억세스하는 알고리즘의 경우, 리스트를 뒤집어 그 결과로 작업하는 것이 좋음.

abcde.reverse  // List(e, d, c, b, a)

reverse 메소드는 새 리스트는 반환함. 리스트는 불변성을 띠기 때문에 원본 데이터는 변하지 않음

abcde            // List(a, b, c, d, e)

reverse, init, last 연산은 추론 가능한 몇가지 계산 법칙을 만족함.

1) reverse는 자신의 반전임.

xs.reverse.reverse equals  xs

2) reverse는 init은 tail로 last는 head로 돌림. (반전된 요소는 예외)

xs.reverse.init equals xs.tail.reverse
xs.reverse.tail equals xs.init.reverse
xs.reverse.head equals xs.last
xs.reverse.last equals xs.head

반전은 concatenation(:::)으로 구현될 수 있음.

def rev[T](xs: List[T]): List[T] = xs match {
  case List() => xs
  case x :: xs1 => rev(xs1) ::: List(x)
}

위 메소드는 효율이 좋지 못함. rev의 복잡도는 리스트 xs가 길이 n을 가질 때, n번의 rev에 대한 재귀호출이 있으므로 복잡도는 다음과 같음.

n + (n - 1) + … + 1 = (1 + n) * n / 2

즉, rev의 복잡도는 입력 인자의 길이 n을 가지는 2차 방정식임. 선형 복잡도를 지니는 reverse 메소드에 비해 속도가 떨어짐. 섹션4에서 속도를 높이는 방법을 볼 것임.

Prefixes and suffixes: drop, take, and splitAt

drop과 take는 리스트의 prefix나 혹은 suffix를 반환하는tail과 init의 일반적인 형태임.

xs take n – 리스트 xs의 처음 n개의 요소를 반환. n이 리스트 xs의 길이보다 클 경우, 전체 리스트 xs를 반환

xs drop n – 리스트 xs의 처음 n개를 제외한 리스트 요소들을 반환. n이 리스트 xs의 길이보다 작을 경우, 빈 리스트를 반환

splitAt – 주어진 인덱스에서 리스트를 분할, 두 개의 리스트 쌍을 반환. 그러나 리스트를 두 번 횡단하지는 않음

xs splitAt n   equals   (xs take n, xs drop n)

예제

abcde    take 2       // List(a, b)
abcde  drop 2       // List(c, d, e)
abcde  splitAt 2    // (List(a, b), List(c, d, e))

Element selection: apply and incides

apply – 랜덤 요소 선택, array가 아닌 리스트에서는 흔하지 않은 연산.

abcde apply 2     // c 

메소드를 호출할 때 함수 위치에 객체가 나타나는 경우, apply 메소드가 암묵적으로 삽입됨.

abcde(2)       // c

xs(n)은 인덱스 n에 대해 시간에 비례. apply는 drop과 head의 조합으로 정의됨.

xs apply n equals (xs drop n).head

indices – 주어진 리스트의 모든 유효한 인덱스들로 구성된 리스트를 반환함.

abcde.indices  // Range(0, 1, 2, 3, 4)

Flattening a list of lists: flatten

flatten – 리스트의 리스트를 하나로 합침.

List(List(1, 2), List(3), List(), List(4, 5)).flatten  // List(1, 2, 3, 4, 5)
fruit.map(_.toCharArray).flatten    // List(a, p, p, l, e, s, o, r, a, n, g, e, s, p, e, a, r, s)

Zipping lists: zip and unzip

zip – 두 개의 리스트를 취해 한 쌍의 리스트로 구성함.

abcde.indices zip abcde // IndexedSeq((0, a), (1, b), (2, c), (3, d), (4, e))

길이가 다를 경우, 맞지 않는 것은 드랍됨.

val zipped = abcde zip List(1, 2, 3) // List((a, 1), (b, 2), (c, 3))

zipWithIndex – 리스트를 그 인덱스와 zip함

abcde.zipWithIndex // List((a, 0), (b, 1), (c, 2), (d, 3), (e, 4))

튜플의 리스트도 리스트의 튜플로 역변환할 수 있음.

zipped.unzip // (List(a, b, c), List(1, 2, 3))

Displaying lists: toString and mkString

toString – 리스트의 canonical 문자열 표현

xs mkString(pre, sep, post) – 4개의 오퍼랜드를 취함

pre + xs(0) + sep + … + sep + xs(xs.length -1) + post

mkString 메소드는 두 개의 오버로드된 형식이 있음.

첫 번째는 구분자 문자열만 취함

xs mkString seq equals xs mkString("", sep", "")

두 번째는 모든 인자가 생략됨.

xs.mkString equals xs mkString ""

기타 몇 가지 예제

abcde mkString ("[", ",", "]")         // String = [a, b, c, d, e] 
abcde mkString ""                      // String = abcde
abcde mkString                          // String = abcde
abcde mkString ("List(", ", ", ")")      // String = List(a, b, c, d, e)

addString – StringBuilder 객체에 구조화된 문자열을 추가하는 메소드. Java의 StringBuilder가 아님.

val buf = new StringBuilder
abcde addString(buf, "(", ";", ")")        // StringBuilder = (a;b;c;d;e)

Converting lists: iterator, toArray, copyToArray

toArray – 리스트 데이터를 array 데이터로 변경, toList – array 데이터를 리스트 데이터로 변경

val arr = abcde.toArray   // Array(a, b, c, d, e)
arr.toList                // List(a, b, c, d, e)

copyToArray – start 위치부터 array에 리스트 데이터를 복사. 북사 대상 array는 원본 리스트 만큼 충분히 커야함.

val arr2 = new Array[Int](10)      // Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
List(1, 2, 3) copyToArray (arr2, 3)     // Array(0, 0, 0, 1, 2, 3, 0, 0, 0, 0)

iterator – 반복자를 이용해 리스트 요소에 억세스함.

val it = abcde.iterator
it.next      // a
it.next          // b

Example: Merge sort

이상, 예제로 병할 정렬을 구현해보겠음. 병합 정렬 알고리즘은 다음과 같음

리스트가 0개 혹은 1개의 요소를 가지고 있으면 이미 정렬된 거임.
그 이상일 경우, 두 개의 하위 리스트로 분할함.
각각의 하위 리스트는 sort 함수의 재귀호출에 의해 정렬되어 두 개의 정렬된 리스트를 병합(merge) 연산으로 합침.

구현을 일반화시키기 위해 리스트의 타입과 각 요소들을 비교하는 함수는 오픈된 상태로 남겨둠. 궁극의 일반화(Generalization)를 위해 이 두 항목은 매개변수로 전달하는 거임.

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))
  }
}

n이 입력 리스트의 길이일 때, msort의 복잡도는 O(nlog(n)) 임. (※. 일반적인 병합 정렬의 복잡도임. 이하 자세한 설명은 p. 320을 참고 혹은 알고리즘 관련 도서를 참고 바람.)

사용 예)

msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3)) // List(1, 3, 5, 7)

섹션 9.3의 currying을 적용해서 정수형을 정렬하는 함수

val intSort = msort((x: Int, y: Int) => x < y) _

정수형을 역순으로 정렬하는 함수

val reverseIntSort = msort((x: Int, y: Int) => x > y) _

이상 위의 함수들을 이용한 예제

val mixedInts = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)
intSort(mixedInts)
reverseIntSort(mixedInts)

16.7 Higher-order methods on class List

고차함수란 다른 함수를 매개변수로 취하는 함수를 말하는데, 이런 고차 연산자를 이용한 List 클래스의 메소드들을 살펴보겠음.

Mapping over lists: map, flatMap and foreach

xs map f – List[T] 타입의 xs 리스트와 T => U 타입의 함수 f를 오퍼랜드로 취함. xs의 각 리스트 요소에 함수 f를 적용한 리스트를 반환함.

List(1, 2, 3) map (_ + 1)                            // List(2, 3, 4)
  
val words = List("the", "quick", "brown", "fox")
words map (_.length)                             // List(3, 5, 5, 3)
words map (_.toList.reverse.mkString)                // List(eht, kciuq, nworb, xof)

flatMap – map과 비슷. 오른쪽 오퍼랜드로 요소의 리스트를 반환하는 함수를 취함. 모든 함수를 적용한 결과를 단일 리스트로 취합함.

words map (_.toList)
// List(List(t, h, e), List(q, u, i, c, k), List(b, r, o, w, n), List(f, o, x))
  
words flatMap (_.toList)
// List(t, h, e, q, u, i, c, k, b, r, o, w, n, f, o, x)

1 <= j < i < 5인 모든 짝(i, j)의 리스트를 구성하는 예제

List.range(1, 5) flatMap (
  i => List.range(1, i) map (j => (i, j))
)
  
// List((2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3))

for문을 사용한 같은 예제

for (i <- List.range(1, 5); j <- List.range(1, i)) yield (i, j)

foreach가 map과 flatMap과 비슷하나 다른 점은 결과의 리스트를 모으는 것이 아니라 Unit 타입의 결과만 리턴함.

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

Filtering lists: filter, partition, find, takeWhile, dropWhile, and span

xs filter p – List[T] 타입의 xs 리스트와 T => Boolean 타입의 함수 p를 오퍼랜드로 취하고 p(x)가 참인 xs의 모든 요소 x를 반환함.

List(1, 2, 3, 4, 5) filter (_ % 2 == 0)     // List(2, 4)
  
words filter (_.length == 3)              // List(the, fox)

partition 메소드는 filter와 비슷하나 리스트의 쌍을 반환함. 하나는 참, 하나는 거짓인 요소의구성된 각각의 리스트를 반환

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

find 역시 filter와 비슷하나 주어진 술어(predicate)를 만족하는 첫째 요소를 반환

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

xs takeWhile p – p를 만족하는 모든 요소로 구성된 리스트 xs에서 가장 긴 prefix를 취함 xs dropWhile p – p를 만족하는 모든 요소로 구성된 리스트 xs에서 가장 긴 prefix를 버림

List(1, 2, 3, 4, -4, 5) takeWhile (_ > 0) // List(1, 2, 3)
words dropWhile(_ startWith "t")           // List(quick, brown, fox)

span – takeWhile과 dropWhile을 하나로 합침, 그러나 리스트를 두 번 횡단하지 않음.

xs span p equals (xs takeWhile p, xs dropWhile p)

예제

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

Predicates over lists: forall and exists

xs forall p – p를 만족하는 모든 요소를 반환 xs exists p – p를 만족하는 요소가 있으면 true를 반환

def hasZeroRow(m: List[List[Int[) = m exists (row => row forall (_ == 0))
  
hasZeroRow(dia3)    // false

Folding lists: /: and :\

아래의 더하기는

sum(List(a, b, c)) equals 0 + a + b + c

사실 다음과 같은 fold 연산의 인스턴스임.

def sum(xs: List[Int]): Int = (0 /: xs)(_ + _)

아래의 곱하기도

product(List(a, b, c)) equals 1 * a * b * c

다음과 같은 fold 연산의 인스턴스임.

def product(xs: List[Int]): Int = (1 /: xs) (_ * _)

:\ (fold left 라고 발음) 연산은 3개의 오퍼랜드를 취함. 시작값 z, 리스트 xs, 이항 연산 op. fold의 결과는 z가 부가된 리스트의 연속적인 요소 사이에 op가 적용됨.

(z :/ List(a, b, c))(op) equals op(op(op(z, a), b, c)

다른 예

("" /: words) (_ +" "+ _)   //   java.lang.String =  the quick brown fox

공백을 제거하려면

(words.head /: words.tail)   (_ +" "+_)   // java.lang.String = the quick brown

:\(fold right 라고 발음) 연산은 오른쪽으로 기울어진 트리를 만듦.

(List(a, b, c) :\ z)(op) equals op(a, op(b, op(c, z)))

서로 관련된 동작의 경우, fold left와 fold right가 결과는 같지만 효율은 다를 수 있음. 예를 들어 flatten 연산은 fold left나 혹은 fold right로 다음과 같이 구현됨.

def flattenLeft[T](xss: List[List[T]]) = (List[T])() /: xss)(_ ::: _)
  
def flattenRight[T](xss: List[List[T]) = (xss :\ List[T]())(_ :: _)

리스트 연결 xs ::: ys가 첫째 인자 xs에 대해 시간이 비례하기 때문에, flattenRight가 보다 효율적임. flattenLeft의 문제점은 n은 리스트 xss의 길이일 때, flattenLeft(xss)가 xss의 첫째 요소 xss.head를 n-1번 복사하고 있다는 것임. (※. 관련된 Stackoverflow 질문 Performance consideration between /: and :\ operators in Scala)

Scala 타입 추론의 제한으로 인해, 타입 주석을 생략할 경우 오류가 발생함.

def flattenRight[T](xss: List[List[T]]) = (xss :\ List())(_ ::: _)

/:, :\가 직관적이지 않아 보일 경우, List에 정의된 foldLeft와 foldRight를 사용해도 무방함.

Example: List reversal using fold

선형적 효율을 보이는 reverse 메소드의 구현

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

Sorting lists: sortWith

xs sortWith before– 두 개의 요소를 비교하는 before 함수에 의해 리스트 xs의 요소를 정렬

List(1, -3, 4, 2, 6) sortWith (_ < _) // List(-3, 1, 2, 4, 6)
words sortWith (_.length > _.length)  // List(quick, brown, the, fox)

16.8 Methods of list object

Creating lists from their elements: List.apply

리스트 List(1, 2, 3)은 List.apply(1, 2, 3)과 같음 – 요소 1, 2, 3 에 대해서 List의 apply를 호출

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

Creating a range of numbers: List.range

List.range(from, until) – 리스트의 from 에서 시작해서 until까지의 모든 수로 된 새 리스트를 작성. 마지막 until의 요소는 포함되지 않음. 세 번째 매개변수로 step이 있음

List.range(1, 5)     // List(1, 2, 3, 4)
List.range(1, 9, 2)     // List(1, 3, 5, 7)
List.range(9, 1, -3) // List(9, 6, 3)

Creating uniform lists: List.fill

fill – 0 또는 그 이상의 같은 요소로 구성된 리스트를 생성. 매개변수는 2개 – 생성할 리스트의 길이와 반복될 요소

List.fill(5)('a')          // List(a, a, a, a, a)
List.fill(3)("hello")     // List(hello, hello, hello)

2개 이상의 매개변수를 넘기면 다차원 리스트를 구성함

List.fill(2, 3)('b')        // List(List(b, b, b), List(b, b, b))

Tabulating a function: List.tabulate

tabulate – 요소들이 주어진 함수에 의해 계산되는 리스트를 생성. List.fill과 동일한 매개변수를 취함.

val squares = List.tabulate(5)(n => n * n)    // List(0, 1, 4, 9, 16)
val multiplication = List.tabulate(5, 5)(_ * _) // List(List(0, 0, 0, 0, 0), List(0, 1, 2, 3, 4), List(0, 2, 4, 6, 8), List(0, 3, 6, 9, 12), List(0, 4, 8, 12, 16))

Concatenating multiple lists: List.concat

concate – 다수의 리스트 요소들을 합치는 메소드

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

16.9 Processing multiple list together

튜플의 ‘zipped’ 메소드는 여러 리스트에 대해 수행해야할 몇 개의 같은 연산을 그냥 한 리스트로 일반화함.

(List(10, 20), List(3, 4, 5)).zipped.map(_ * _)     // List(30, 80), 3번째 요소는 버려짐.

exists와 forall에 대해 비슷하게 zipped을 하면,

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

16.10 Understanding Scala’s type inference algorithm

sortWith과 msort 사이의 차이점은 비교 함수에서 용인될 수 있는 문법적 형식임. 비교해보자면,

msort((x: Char, y: Char) => x > y)(abcde)        // List(e, d, c, b, a) 
abcde sortWith (_ > _)                            // List(e, d, c, b, a)

두 표현식은 동일하지만, 첫 번째는 명명된 매개변수(named parameter)와 명시적인 타입으로 구성된 비교 함수의 좀 더 긴 형식을 사용하는 반면, 두 번째는 구체적인 형식인 (_ > _)를 사용. 물론, sortWith으로도 첫 번째처럼 긴 형식의 비교 함수를 사용할 수 있음.

그러나 짦은 형식은 msort에서는 사용할 수 없음!

msort(_ > _)(abcde)  // error: missing parameter type for expanded function ((x$1, x$2) => x$1.$greater(x$2)) 

스칼라에서 타입 추론은 flow 기반임. 메소드 m(args)에서 추론자(inferencer)는 메소드 m이 타입을 알고 있는지를 확인함. 이 타입은 인자의 기대되는 타입을 추론하는데 사용됨.

예를 들어, abcde.sortWith(_ > _)에서 abcde는 List[Char] 타입. 따라서, sortWith은 (Char, Char) => Boolean 타입의 인자를 취하는 메소드임을 알 수 있음.

함수 인자의 매개변수 타입을 알고 있기 때문에, 명시적으로 기술할 필요가 없음. 추론자(inferencer)는 (_ > _)는 ((x: Char, y: Char) => x > y)로 확장되어야 함을 추정할 수 있음.

두 번째 msort(_ > _)(abcde)의 경우, msort의 타입은 커리(curry)됨. 다형적(polymorphic) 메소드 타입은 T가 아직 임의의 타입일 때 List[T]에서 List[T]까지 함수의 (T, T) => Boolean 타입을 인자로 취함.

msort 메소드는 그 인자가 적용되기 전에 매개변수 타입 (의 인스턴스)로 초기화되어야 함. msort 인스턴스의 정확한 타입을 알지 못하므로, 자신의 첫 번째 인자 타입을 추론할 수 없음.

이 때, 타입 추론자는 전략을 바꾸어 메소드의 적당한 인스턴스 타입을 결정하기 위해 메소드 인자를 확인함. 주어진 짧은 함수 리터럴 (_ > _)의 타입 확인은 _로 표시된 암묵적 함수 매개변수의 타입에 대한 정보가 없기 때문에 실패함.

한 가지 해법은 msort에 명시적 매개변수 타입을 전달하는 것임.

msort[Char](_ > _)(abcde) // List(e, d, c, b, a)

msort의 정확한 인스턴스 타입을 이제 알고 있으므로, 인자의 타입을 추론할 수 있음.

다른 해법은 msort 메소드를 자신의 매개변수가 스왑되도록 재작성하는 것임.

def msortSwapped[T](xs: List[T])(less: (T, T) => Boolean): List[T] = {
  // msort와 같은 구현, 그러나 인자들이 swap됨.
}

이제 타입 추론은 성공할 것임.

msortSwapped(abcde)(_ > _) // List(e, d, c, b, a)

추론자는 msortSwapped의 매개변수 타입을 결정하기 위해 첫 번째 매개변수 abcde의 알려진 타입을 사용함. msortSwapped의 정확한 타입을 알게 되면, 이어서 두 번째 매개변수인 (_ > _)의 타입을 추론할 수 있음.

추론 계획(inference scheme)은 다음의 라이브러리 설계 원리를 도출함.

비함수 인자와 함수 인자를 취하는 다형성을 지닌 메소드를 설계할 때, 함수 인자는 자신에 의해 커리된 리스트 매개변수의 마지막에 둬야함. (※. 타입 유추가 flow 기반이기 때문. 즉, 첫 번째 명시적인 타입을 지닌 인자인 비함수 인자에 의해 타입 유추를 결정하기 때문임.)

When designing a polymorphic method that takes some non-function arguments and a function argument, place the function argument last in a curried parameter list by its own.

좀 더 복잡한 fold의 경우, 328 페이지의 flattenRight 메소드의 바디처럼 표현식에 명시적인 매개변수 타입이 왜 필요할까?

(xss :\ List[T]()) (_ ::: _)

fold-right의 타입은 두 가지 타입 변수를 가지므로 다형적임.

(xs :\ z)(op)

xs의 타입은 임의의 A 타입의 리스트로, xs: List[A]이고 시작값 z는 다른 타입 ‘B’일 것이며, op 연산은 A 타입과 B 타입 두 개의 인자를 취해 결과로 B 타입을 반환해야 함. 예를 들면 op: (A, B) => B.

z의 타입은 리스트 xs의 타입과 무관하므로, 타입 추론시에 z에 대해 아무런 컨텍스트 정보가 없음.

328 페이지의 잘못된 버전의 flattenRight 살펴보면,

(xss :\ List())(_ ::: _) // 컴파일 안됨

시작값 z는 빈 리스트 List()이고 추가적인 타입 정보가 없으므로 자신의 타입은 List[Nothing]으로 추론됨. 따라서, 추론자는 fold되는 B 타입을 List[Nothing]이라고 추론함. 그러므로, fold의 (_ ::: _)는 아래의 타입으로 기대됨.

(List[T], List[Nothing]) => List[Nothing]

가능한 타입이긴 하지만, 이 연산은 항상 빈 리스트를 두 번째 인자로 취하기 때문에 빈 리스트를 결과로 반환함. 즉, 타입 추론이 너무 이른 시점에 List()에 대해 결정되버림. op의 타입이 보였을 때까지 기다렸어야 함.

커리(curry)된 메소드의 메소드의 타입을 결정하는데 첫 번째 인자에 대해서만 고려하는 규칙이 문제의 근원임. 규칙이 완화되더라도 추론자는 op에 대한 타입을 제시할 수 없음. 따라서, 프로그래머로부터 명시적인 타입 주석으로만 해결될 수 있는 이러지도 저러지도 못하는 시츄에이션임.

16.11 Conclusion

다음 장에서는 콜렉션에 대해 살펴보겠음.

Programming in Scala 16장