16.1 리스트 리터럴
| 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() |
: 리스트는 배열과 비슷하지만 변경 불가능하고 구조가 재귀적이다. 배열은 평면적이다. (22장)
16.2 리스트 타입
: 리스트는 동종 원소로 이뤄진다.(= 원소의 타입이 같다)
: 리스트 타입은 공변적이다.(S가 T의 서브타입이면 List[S]도 List[T]의 서브타입이다)
Ex. List[String]은 List[Object]의 서브타입
=> 빈 리스트 타입 List[Nothing]은 모든 T 타입의 List의 서브타입
=> val xs: List[String] = List() 가 가능
16.3 리스트 생성
: 모든 리스트는 Nil과 ::(콘즈)로 리스트를 만든다. List(...)은 Nil과 ::을 확장해주는 래퍼에 불과
Ex. List( 1, 2, 3 )은 1 :: ( 2 :: ( 3 :: Nil ))) 로 생성된다.
: 콜론으로 끝나기 때문에 :: 연산자는 오른쪽 결합 법칙
16.4 리스트 기본 연산
- head : 어떤 리스트의 첫 번째 원소 반환
- tail : 어떤 리스트의 첫 번째 원소를 제외한 나머지 원소로 이뤄진 리스트 반환
- isEmpty : 리스트가 비어 있다면 true 반환
: head와 tail은 비어 있지 않은 리스트에만 유효 => 빈 리스트에 head와 tail을 호출하면 예외 발생
|
" 삽입 정렬 예제 " def isort(xs: List[Int]): List[Int] =
def insert(x: Int, xs: List[Int]): List[Int] = |
16.5 리스트 패턴
|
scala> val List(a, b, c) = fruit
scala> val a :: b :: rest = fruit // 리스트 원소의 개수를 미리 알 수 없다면 |
: 리스트 패턴은 head, tail, isEmpty의 대안
|
" 삽입 정렬 예제 " def isort(xs: List[Int]): List[Int] = xs match { def insert(x: Int, xs: List[Int]): List[Int] = xs match { |
16.6 List 클래스의 1차 메소드
- 1차 메소드 : 어떤 메소드가 함수를 인자로 받지 않는 것
< 두 리스트 연결하기 - ":::" >
: ":::"는 두 인자를 리스트로 받는 리스트 연결 연산, "::"와 마찬가지로 오른쪽 결합 법칙
| scala> List(1, 2) ::: List(3, 4, 5) res0: List[Int] = List(1, 2, 3, 4, 5) |
Ex. 분할 정복 원칙을 통해 ":::" 구현 예제
| def append[T](xs: List[T], ys: List[T]): List[T] = xs match { case List() => ys case x :: xs1 => x :: append(xs1, ys) } |
< 리스트 길이 구하기 : length >
: length는 리스트 끝을 찾기 위해 전체 리스트를 순회 => 리스트 원소 개수만큼 시간 소요 => xs.isEmpty 를 xs.length==0으로 바꾸는 것은 권장 X
< 리스트 양 끝에 접근하기 : init, last >
- init : 마지막 원소를 제외한 모든 원소를 포함한 리스트 반환
- last : 마지막 원소 반환
: init, last 는 빈 리스트에 호출하면 예외
: head와 tail은 상수 시간 복잡도이지만 init와 last는 전체 리스트를 순회해야해 리스트 길이만큼 시간이 걸린다.
< 리스트 뒤집기 : reverse >
|
scala> val abcde = List('a', 'b', 'c', 'd', 'e')
scala> abcde.reverse |
- reverse는 다음 법칙을 만족
1. xs == xs.reverse.reverse
2. reverse는 init을 tail로 바꾸고 last를 head로 바꾼다.
=> xs.reverse.init == xs.tail.reverse
=> xs.reverse.tail == xs.init.reverse
=> xs.reverse.head == xs.last
=> xs.reverse.last == xs.head
- reverse는 ":::"을 사용해 구현할 수 있다.
| def rev[T](xs: List[T]): List[T] = xs match { case List() => xs case x :: xs1 => rev(xs1) ::: List(x) } |
: rev를 n번 재귀 호출, xs ::: ys 는 xs의 크기만큼 시간이 걸린다. => rev 복잡도 : n + (n-1) +... 1 = (n+1)*n/2 => 변경 가능한 연결리스트를 뒤집을 때 선형 복잡도가 드는 것과 비교하면 실망스러운 결과
< 접두사와 접미사 : drop, take, splitAt >
- xs take n 은 xs 리스트 처음부터 n까지 원소 반환
- xs drop n 은 첫 번째에서 n번째까지 원소를 제외한 모든 원소 반환
- xs splitAt n 은 주어진 인덱스 위치에서 리스트를 분할해서 두 리스트가 들어있는 순서쌍 반환 == (xs take n , xs drop n)
|
scala> val abcde = List('a', 'b', 'c', 'd', 'e')
scala> abcde splitAt 2 |
< 원소 선택하기 : apply, indices >
- apply : 인덱스의 원소 선택
|
scala> abcde apply 2 res11: Char = c
scala> abcde(2) |
: 스칼라에서 apply 연산을 거의 사용하지 않는다. xs(n)에서 인덱스 n의 값에 비례해 시간이 걸리기 때문
: xs apply n == (xs drop n).head
- indices : 리스트에서 유효한 모든 인덱스의 리스트를 반환
| scala> abcde.indices res13: scala.collection.immutable.Range= Range(0, 1, 2, 3, 4) |
< 리스트의 리스트를 한 리스트로 반듯하게 만들기 : flatten >
|
scala> List(List(1, 2), List(3), List(), List(4, 5)).flatten
scala> val fruit = List("apples", "oranges", "pears") scala> fruit.map(_.toCharArray).flatten |
: flatten은 리스트의 원소가 모두 리스트인 경우에만 적용 가능
< 두 리스트를 순서쌍으로 묶기 : zip, unzip >
|
scala> val zipped = abcde zip List(1, 2, 3)
scala> zipped.unzip
scala> abcde.zipWithIndex // 각 원소를 인덱스와 함께 순서쌍으로 묶을 때 |
< 리스트 출력하기 : toString, mkString >
- xs mkString ( pre, sep ,post ) => pre + xs(0) + sep + ... + sep + xs + post
: mkString 메소드는 인자 일부가 없는 오버로드한 메소드 2개 존재
=> xs mkString sep == xs mkString ("", sep, "")
=> xs.mkString == xs mkString ""
- addString : 생성한 문자열 결과를 반환하지 않고 StringBuilder 객체에 추가
|
scala> val buf = new StringBuilder |
< 리스트 변환하기 : iterator, toArray, copyToArray >
- xs copyToArray (arr, start) : 리스트 원소를 arr의 start 부터 연속적으로 복사
|
scala> val arr2 = new Array[Int](10)
|
- iterator
|
scala> val it = abcde.iterator scala> it.next
scala> it.next |
Ex. 병합 정렬
|
def msort[T](less: (T, T) => Boolean)
scala> msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
scala> val intSort = msort((x: Int, y: Int) => x < y) _ // 커링을 사용하면 특정 비교 함수로 특화 가능
scala> val mixedInts = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7) |
16.7 List 클래스의 고차 메소드
* 고차 메소드 : 인자로 다른 함수를 받는 함수
< 리스트 매핑 : map, flatmap, foreach >
- xs map f : List[T] 타입인 xs 와 T => U 타입인 f 함수를 받는다. xs의 모든 원소에 함수 f를 적용해서 나온 결과 값 리턴
|
scala> List(1, 2, 3) map (_ + 1)
|
- flatMap : map과 유사하지만 함수 f를 적용해서 나온 모든 리스트를 연결한 단일 리스트를 반환
|
scala> words map (_.toList)
scala> words flatMap (_.toList) |
- foreach는 오른쪽 피연산자로 프로시저(결과 값이 Unit인 함수)를 받는다.
|
scala> var sum = 0 scala> List(1, 2, 3, 4, 5) foreach (sum += _) |
< 리스트 걸러내기 : filter, partition, find, takeWhile, dropWhile, span >
- xs filter p : List[T] 타입 xs와 T => Boolean 타입의 술어 함수 p를 받는다. xs의 원소 중 p(x)가 true인 원소 리스트 리턴
|
scala> List(1, 2, 3, 4, 5) filter (_ % 2 == 0)
|
- partition : filter와 비슷하지만 술어 함수 p가 true인 원소를 포함한 리스트와 false인 원소를 포함한 리스트의 순서쌍 반환
xs partion p == (xs filter p, xs filter (!p(_)))
|
scala> List(1, 2, 3, 4, 5) partition (_ % 2 == 0) |
- find : filter와 비슷하지만 술어 함수 p를 만족하는 첫 번째 원소 반환(true인 원소 x가 존재하면 Some(x), 없으면 None으로 반환)
|
scala> List(1, 2, 3, 4, 5) find (_ % 2 == 0)
|
- xs takeWhile p : 술어 p에 만족하는 가장 긴 접두사 반환
- xs dropWhile p : 술어 p에 만족하는 가장 긴 접두사 제거
|
scala> List(1, 2, 3, -4, 5) takeWhile (_ > 0)
scala> List(1, 2, 3, -4, 5) dropWhile (_ > 0) |
- xs span p == (xs takeWhile p , xs dropWhile p)
| scala> List(1, 2, 3, -4, 5) span (_ > 0) res47: (List[Int], List[Int]) = (List(1, 2, 3),List(-4, 5)) |
< 리스트 전체에 대한 술어 : forall, exists >
- xs forall p : 리스트의 모든 원소가 p 술어 함수를 만족할 때 true 반환
- xs exists p : 리스트의 원소 중에 p 술어 함수를 하나라도 만족할 때 true 반환
|
scala> val diag3 = List( List(1, 0, 0), List(0, 1, 0), List(0, 0, 1) )
scala> def hasZeroRow(m: List[List[Int]]) = m exists (row => row forall (_ == 0))
scala> hasZeroRow(diag3) res48: Boolean = false |
< 리스트 폴드: "/:", ":＼" >
- 왼쪽 폴드 연산 : " ( z /: xs ) (op) " , z는 시작 값, xs는 폴드할 대상 리스트, op는 이항 연산자 의미하고 폴드한 결과는 z를 시작으로 xs의 모든 원소에 대해 op 연산자를 연속으로 적용한 것
Ex. ( z /: List(a,b,c) ) (op) 는 op(op(op(z,a),b),c) 와 같다.
| scala> def sum(xs: List[Int]): Int = (0 /: xs) (_ + _) // sum(List(a,b,c)) 는 0+a+b+c와 같다. sum: (xs: List[Int])Int scala> def product(xs: List[Int]): Int = (1 /: xs) (_ * _) // product(List(a,b,c)) 는 1*a*b*c와 같다. product: (xs: List[Int])Int |
- 오른쪽 폴드 연산 => (List(a,b,c) :＼ z) (op) 는 op(a, op(b, op(c, z))) 와 같다.
- 결합 법칙이 성립하는 연산에 대해 오른쪽 폴드와 왼쪽 폴드는 결과가 동일하지만 효율이 다를 수 있다.
| def flattenLeft[T](xss: List[List[T]]) = (List[T]() /: xss) (_ ::: _) // 스칼라 타입 추론 제약 때문에 리스트 타입을 제대로 추론 못 해 타입 표기 def flattenRight[T](xss: List[List[T]]) = (xss :＼ List[T]()) (_ ::: _) |
: "xs ::: ys" 연산자는 첫 번째 인자 xs에 비례하는 시간이 걸린다. => flattenLeft(xss)가 첫 번째 원소인 리스트 xss.head를 n-1번 복사 => flattenLeft보다 flattenRight가 효율적
- 오른쪽/왼쪽 폴드 연산은 foldLeft, foldRight 메소드로 대신 사용 가능
Ex. 폴드를 사용해 리스트 뒤집기
| def reverseLeft[T](xs: List[T]) = // 위에서 보았던 ":::"로 구현한 reverse 비교해 선형 시간 복잡도 (List[T]() /: xs) {(ys, y) => y :: ys} |
< 리스트 정렬 : sortWith >
- xs sortWith before : xs를 두 원소를 비교할 수 있는 함수 before을 사용해 정렬한다. x before y는 정렬 결과에서 x가 y 앞에 있어야 한다면 true를 반환해야 한다.
|
scala> List(1, -3, 4, 2, 6) sortWith (_ < _) res51: List[Int] = List(-3, 1, 2, 4, 6) |
16.8 List 객체의 메소드
- List.apply : List(1,2,3) == List.apply(1,2,3)
- List.range(from, until) : from부터 until-1까지 모든 정수가 들어간 리스트를 만든다.
- List.range(from, until, seq) : from에서 시작해 seq만큼 간격이 떨어져 있는 수의 리스트를 만든다.
|
scala> List.range(1, 9, 2) res55: List[Int] = List(1, 3, 5, 7)
scala> List.range(9, 1, -3) res56: List[Int] = List(9, 6, 3) |
- List.fill : 같은 원소를 0번 이상 반복한 리스트를 만든다. 첫 번째 인자는 생성할 리스트의 차원, 두 번째 인자는 리스트의 원소
|
scala> List.fill(5)('a') res57: List[Char] = List(a, a, a, a, a)
scala> List.fill(3)("hello") res58: List[String] = List(hello, hello, hello)]
scala> List.fill(2, 3)('b') // 인자를 2개보다 많이 전달하면 다차원 리스트를 생성 res59: List[List[Char]] = List(List(b, b, b), List(b, b, b)) |
- List.tabulate : 제공된 함수로 계산한 원소의 리스트를 생성한다. List.fill과 비슷하고 두 번째 인자에 원소 대신 함수를 가진다.
|
scala> val squares = List.tabulate(5)(n => n * n) squares: List[Int] = List(0, 1, 4, 9, 16)
scala> val multiplication = List.tabulate(5,5)(_ * _) multiplication: List[List[Int]] = 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)) |
- List.concat : 여러 리스트를 연결한다.
|
scala> List.concat(List('a', 'b'), List('c')) res60: List[Char] = List(a, b, c) |
16.9 여러 리스트를 함께 처리하기
- zipped 메소드는 여러 리스트에 공통 연산을 수행한다.
|
scala> (List(10, 20), List(3, 4, 5)).zipped.map(_ * _) res63: List[Int] = List(30, 80)
scala> (List("abc", "de"), List(3, 2)).zipped.forall(_.length == _) res64: Boolean = true
scala> (List("abc", "de"), List(3, 2)).zipped.exists(_.length != _) res65: Boolean = false |
16.10 스칼라의 타입 추론 알고리즘(흐름 기반 타입 추론) 이해
| scala> msort((x: Char, y: Char) => x > y)(abcde) // 함수 파라미터에 이름과 타입 지정 res66: List[Char] = List(e, d, c, b, a) scala> abcde sortWith (_ > _) res67: List[Char] = List(e, d, c, b, a) scala> msort(_ > _)(abcde) // 함수 파라미터에 이름과 타입 지정 X => 타입 추론 실패 :12: error: missing parameter type for expanded function ((x$1, x$2) => x$1.$greater(x$2)) msort(_ > _)(abcde) ^ |
: abcde.sortWith(_>_)에서 abcde 타입은 List[Char] => sortWith가 "(Char,Char) => Boolean" 타입의 인자를 받는 메소드 => 함수 파라미터 타입 지정 X
: msort(_>_)(abcde)는 msort 자체에서 "_>_"의 타입을 알 방법 X => "( T, T ) => Boolean" 타입 추론 실패
* 두 번째 인자인 abcde를 통해서 알 수도 있지만 두 번째 이후의 파라미터 목록은 타입 추론에 사용 X
|
" 추론 실패 문제 해결 " scala> msort[Char](_ > _)(abcde) // msort에 명확하게 타입 파라미터를 전달
def msortSwapped[T](xs: List[T])(less:
scala> msortSwapped(abcde)(_ > _) // 파라미터 위치를 바꾼다. |
=> 함수가 아닌 파라미터와 함수 파라미터를 받는 다형성 메소드를 설계하면다면 함수 인자를 별도의 커링 파라미터 목록으로 맨 마지막으로 넣어라 => 타입 추론 O => 타입 정보를 더 적게 기입하고 함수 리터럴이 더 간결
- fold 연산 타입 추론
| def flattenRight[T](xss: List[List[T]]) = (xss :＼ List[T]()) (_ ::: _) // 타입 파라미터를 넣어야 한다. |
: ( xs :＼ z ) (op) 는 xs A 타입과 z B 타입을 받아서 B 타입의 결과를 반환한다. ( op : (A, B) => B)
: 리스트 xs 타입은 z의 타입과 무관하기 때문에 z에 대한 타입 추론 불가
| def flattenRight[T](xss: List[List[T]]) = (xss :＼ List()) (_ ::: _) // z는 빈 리스트 |
: z는 빈 리스트이기 때문에 List[Nothing] 타입 => " (List[T], List[Nothing]) => List[Nothing] " => 빈 리스트를 반환하기 때문에 유용 X
=> 타입 추론을 너무 일찍(커링 함수를 호출할 때 첫 번째 인자 목록 타입으로 함수 값의 타입을 결정하는 규칙 때문)
=> 규칙을 완화하더라도 op 인자 타입을 명시하지 않았기 때문에 op 타입을 알 수 없다.
=> 타입 표기를 넣어야만 해결 가능(캐치 22 상황 - 규정의 모순으로 인한 진퇴양난의 상황)
'스칼라' 카테고리의 다른 글
| 스칼라 18장 변경 가능한 객체(Programming in Scala, 3rd) (0) | 2019.06.07 |
|---|---|
| 스칼라 17장 컬렉션(Programming in Scala, 3rd) (0) | 2019.06.06 |
| 스칼라 15장 케이스 클래스와 패턴 매치(Programming in Scala, 3rd) (0) | 2019.06.02 |
| 스칼라 14장 단언문과 테스트(Programming in Scala, 3rd) (0) | 2019.06.02 |
| 스칼라 13장 패키지와 임포트(Programming in Scala, 3rd) (0) | 2019.06.01 |