팬 레 터 프로 그래 밍 (6) - 데이터 구조 - List 기초
19434 단어 데이터 구조
1 trait List[+A] {} 2 case class Cons[+A](head: A, tail: List[A]) extends List[A] 3 case object Nil extends List[Nothing]이상 은 A 타 입 요 소 를 불 러 올 수 있 는 List 이 며, 다 중 타 입 (Polymorphic Type) 입 니 다. +A 는 List 가 협 변 (Covariant) 이라는 뜻 으로 애플 이 fruit 의 하위 클래스 (subtype) 라면 List [apple] 는 List [fruit] 의 하위 클래스 라 는 뜻 이다.닐 은 List [Nothing] 을 물 려 받 았 고, Nothing 은 모든 유형의 하위 클래스 다.협 변성 질 을 결합 하면 Nil 은 List [Int], List [String] 로 볼 수 있 습 니 다.
List 의 또 다른 실현 방식:
1 trait List[+A] { 2 def node: Option[(A, List[A])] 3 def isEmpty = node.isEmpty 4 } 5 object List { 6 def empty[A] = new List[A] { def node = None} 7 def cons[A](head: A, tail: List[A]) = new List[A] { def node = Some((head, tail))} 8 }이상 코드 에서 empty, cons 두 가지 방법 으로 List 의 두 상 태 를 실현 할 수 있 습 니 다.
우 리 는 여전히 첫 번 째 실현 방식 을 채택 하여 아래 의 List 데이터 연산 에 관 한 시범 을 진행한다.두 번 째 방식 은 Stream 의 구체 적 인 실현 시범 설명 을 남 겨 두 었 다.
먼저 List 자유 구축 기: List (1, 2, 3) 라 는 형식 으로 List 를 구축 할 수 있 습 니 다.
1 object List { 2 def apply[A](as: A*): List[A] = { 3 if (as.isEmpty) Nil 4 else Cons(as.head,apply(as.tail:_*)) 5 } 6 }설명: 가 변 수량의 입력 파 라미 터 를 처리 하기 위해 귀속 알고리즘 을 사용 했다.apply 의 전송 매개 변수 as 는 배열 Array [A] 입 니 다. 저 희 는 Scala 표준 집합 라 이브 러 리 Array 방법 을 사 용 했 습 니 다: as. head, as. tail.시범 은 다음 과 같다.
1 scala> Array(1,2,3).head 2 res11: Int = 1
3
4 scala> Array(1,2,3).tail 5 res12: Array[Int] = Array(2, 3)apply 방법 을 추가 한 후 List 의 구성 을 시범 합 니 다.
1 val li = List(1,2,3) //> li : ch3.list.List[Int] = Cons(1,Cons(2,Cons(3,Nil)))
2 val ls = List("one","two","three") //> ls : ch3.list.List[String] = Cons(one,Cons(two,Cons(three,Nil)))다음 과 같은 방식 에 비해 쓰기 가 훨씬 간결 하 다.
1 val lInt = Cons(1,Cons(2,Cons(3,Nil))) //> lInt : ch3.list.Cons[Int] = Cons(1,Cons(2,Cons(3,Nil)))다시 한 번 연산 을 시도 합 니 다: List [Int] 의 모든 요소 의 합 을 계산 하 시 겠 습 니까? 아니면 패턴 일치 와 재 귀 방식 으로 쓰 시 겠 습 니까?
1 trait List[+A] { 2 def sum: Int = this match { 3 case Nil => 0
4 case Cons(h: Int,t: List[Int]) => h + t.sum 5 } 6 }우 리 는 sum 의 실현 을 특질 설명 에 넣 으 면 다음 과 같은 간결 한 표현 방식 을 사용 할 수 있다.
1 List(1,2,3) sum //> res0: Int = 6다 중 함수 sum 을 다시 시도 해 보 세 요:
1 def sum[B >: A](z: B)(f: (B,B) => B): B = this match { 2 case Nil => z 3 case Cons(h,t) => f(h, t.sum(z)(f)) 4 }이제 List [Int] 와 List [String] 을 각각 시도 해 볼 수 있 습 니 다.
1 List(1,2,3).sum(0){_ + _} //> res0: Int = 6
2 List("hello",",","World","!").sum(""){_ + _} //> res1: String = hello,World!다음은 List 에서 자주 사용 하 는 함수 입 니 다.
1 trait List[+A] { 2
3 def head: A = this match { 4 case Nil => sys.error("Empty List!") 5 case Cons(h,t) => h 6 } 7 def tail: List[A] = this match { 8 case Nil => sys.error("Empty List!") 9 case Cons(h,t) => t 10 } 11 def take(n: Int): List[A] = n match { 12 case k if(k<0) => sys.error("index < 0 !") 13 case 0 => Nil 14 case _ => this match { 15 case Nil => Nil 16 case Cons(h,t) => Cons(h,t.take(n-1)) 17 } 18 } 19 def takeWhile(f: A => Boolean): List[A] = this match { 20 case Nil => Nil 21 case Cons(h,t) => if(f(h)) Cons(h,t.takeWhile(f)) else Nil 22 } 23 def drop(n: Int): List[A] = n match { 24 case k if(k<0) => sys.error("index < 0 !") 25 case 0 => this
26 case _ => this match { 27 case Nil => Nil 28 case Cons(h,t) => t.drop(n-1) 29 } 30 } 31 def dropWhile(f: A => Boolean): List[A] = this match { 32 case Nil => Nil 33 case Cons(h,t) => if (f(h)) t.dropWhile(f) else this
34 } 35 }이상 의 함수 보기;다 비슷 하지 않 아 요?그것 은 모두 팬 레 터 프로 그래 밍 스타일 이기 때문이다.주로 패턴 매 칭 과 재 귀 알고리즘 으로 이 루어 집 니 다.다음은 사용 시범 이다.
1 List(1,2,3).head //> res0: Int = 1
2 List(1,2,3).tail //> res1: ch3.list.List[Int] = Cons(2,Cons(3,Nil))
3 List(1,2,3).take(2) //> res2: ch3.list.List[Int] = Cons(1,Cons(2,Nil))
4 List(1,2,3).takeWhile(x => x < 3) //> res3: ch3.list.List[Int] = Cons(1,Cons(2,Nil))
5 List(1,2,3) takeWhile {_ < 3} //> res4: ch3.list.List[Int] = Cons(1,Cons(2,Nil))
6 List(1,2,3).drop(2) //> res5: ch3.list.List[Int] = Cons(3,Nil)
7 List(1,2,3).dropWhile(x => x < 3) //> res6: ch3.list.List[Int] = Cons(3,Nil)
8 List(1,2,3) dropWhile {_ < 3} //> res7: ch3.list.List[Int] = Cons(3,Nil)하나의 List 를 다른 List 뒤에 맞 춰 보 세 요.
1 def ++[B >: A](a: List[B]): List[B] = this match { 2 case Nil => a 3 case Cons(h,t) => Cons(h,t.++(a)) 4 }1 ist(1,2) ++ List(3,4) //> res8: ch3.list.List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Nil))))그냥 스칼라 의 간결 한 표현 을 해 보고 싶 었 어 요.
아, 두 개 빠 뜨 렸 어 요.
1 def init: List[A] = this match { 2 case Cons(_,Nil) => Nil 3 case Cons(h,t) => Cons(h,t.init) 4 } 5 def length: Int = this match { 6 case Nil => 0
7 case Cons(h,t) => 1 + t.length 8 }1 List(1,2,3).init //> res9: ch3.list.List[Int] = Cons(1,Cons(2,Nil))
2 List(1,2,3).length //> res10: Int = 3다음은 몇 개의 팬 레 터 데이터 구조 가 통용 되 는 함 수 를 실현 합 니 다.
1 def map[B](f: A => B): List[B] = this match { 2 case Nil => Nil 3 case Cons(h,t) => Cons(f(h),( t map f)) 4 } 5 def flatMap[B]( f: A => List[B]): List[B] = this match { 6 case Nil => Nil 7 case Cons(h,t) => f(h) ++ ( t flatMap f ) 8 } 9 def filter(f: A => Boolean): List[A] = this match { 10 case Nil => Nil 11 case Cons(h,t) => if (f(h)) Cons(h,t.filter(f)) else t.filter(f) 12 }1 List(1,2,3) map {_ + 10} //> res13: ch3.list.List[Int] = Cons(11,Cons(12,Cons(13,Nil)))
2 List(1,2,3) flatMap {x => List(x+10)} //> res14: ch3.list.List[Int] = Cons(11,Cons(12,Cons(13,Nil)))
3 List(1,2,3) filter {_ != 2} //> res15: ch3.list.List[Int] = Cons(1,Cons(3,Nil))이 몇 가지 함 수 는 스칼라 for - comprehension 이 지원 하 는 데이터 구 조 를 실현 할 수 있 도록 여러 가지 실현 방법 이 있 습 니 다.이 몇 가지 함수 가 팬 레 터 프로 그래 밍 에서 의 원리 와 의 미 는 뒤의 Functor, Applicative, Monad 과제 에서 자세히 말 합 니 다.
좋은 웹페이지 즐겨찾기
