22장 implementing list - codeport/scala GitHub Wiki

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할 때마다 길이만큼 시간이 증가
    1. 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 구현