22장 implementing list

22.1 The List class in principle

• List는 빌트인이 아니다.

• 코드
• scala 패키지에 추상클래스로 정의되어 있다.
• 서브클래스로 :: 과 Nil을 가진다.
• new 로 생성할 수 없다.
• List 타입 파라미터는 covariant

Nil오브젝트

• 빈 리스트
• List[Nothing]을 상속한다.
• List 타입의 모든 인스턴스와 호환(covariant라서)

::클래스

• 비어있지 않은 리스트
• 접두사 ::에 패턴매칭을 지원하는 이름 (x :: xs == ::(x,xs))
• list를 생성하는 head 와 tail 파라미터를 받는다.

메소드 좀 더 소개

• def length:Int 길이 반환
• def drop(n:Int):List[T] head에서 n만큼의 요소를 드롭, tail 반환
• def map[U](f:T=>U):List[U] 함수 f에 맞는 타입U의 새로운 리스트를 반환

  ex) val a = List(1,2,3,4,5,6,7)
  a.map(t=> t+2)
  res5: List[Int] = List(3, 4, 5, 6, 7, 8, 9, 10)
  a.map(t=> t<4)
  res4: List[Boolean] = List(true, true, true, false, false, false, false, false)
  

List생성자

• ::(콘스)와 :::은 특별한 리스트 생성메소드
• 콜론으로 끝나고 right operand(오른쪽부터 시작)
• :: > 폴리모픽 (List는 covariant (lower bound [U >:T]))
• 타입문제를 없애주고 플렉서블한 사용을 가능하게 해준다
• :::(concat)도 폴리모픽

22.2 The ListBuffer class

• 리스트의 접근패턴은 재귀적이다.(not tail recursive)
• 이러한 재귀 호출은 새로운 스택프레임을 생성한다
• 어떻게 바꿀 수 있나?
• 1. 루프사용하기, 루프의 바디는 :::, append할 때마다 길이만큼 시간이 증가
• 2. list buffer를 사용
  • 리스트의 엘리먼트를 축적, toString 으로 버퍼를 리스트로 변환
  • import scala.collection.mutable.ListBuffer 선언 후 사용하면 되능

22.3 The List class in practice

• 22.2 식의 재귀를 사용하면 스택오버플로우 문제가 있다. > List 클래스 구현에서는 재귀를 피하고 루프에서 ListBuffer를 사용한다.
• 여기서 구현한 함수(Listing 22.6)는 var로 파라미터를 받는다. > modify, 접근제한자가 private 이라 package접근만 허용
• ListBuffer 의 private field
  • private var start: List[A] = Nil 버퍼에 저장된 리스트의 모든 엘리먼트를 포인트
  • private var last0: ::[A] = _ 리스트의 마지막 :: 셀을 포인트
  • private var exported: Boolean = false toList를 사용하여 리스트로 바뀐 버퍼
• 리스트버퍼 구현에서 복사는, 리스트버퍼를 리스트로 변환해서 확장할 때만 필요
• 리스트버퍼를 사용하는 대부분의 경우는 요소를 증가시킨 후에 toList를 마지막으로 작업, 복사가 필요없다.

22.4 Functional on the outside

• 외부에서는 순수 함수형이나 내부적으로는 imperative 구현