Scalaz (23) - 팬 레 터 데이터 구조: Zipper - 커서 포 지 셔 닝

22107 단어
밖 에 모래 먼지 가 북 으로 굴 러 갔 는데 해 가 다 되 었 다 는 것 을 깨 달 았 다. 우 리 는 모두 고향 으로 돌아 가 설 을 쇠 었 는데 나 는 여기 남아 서 지퍼 를 가지 고 놀 았 다.비 뚤 어 지게 생각 하지 마 세 요. 제 가 말 하 는 것 은 바짓가랑이 지퍼 가 아니 라 scalaz Zipper 입 니 다. 팬 레 터 데이터 구조 커서 (cursor) 입 니 다.함수 식 프로 그래 밍 모드 에서 의 집합 은 일반적으로 가 변 적 이지 않 은 (immutable collection) 이다. 우 리 는 FP 프로 그래 밍 과정 에서 가 변 적 이지 않 은 집합 (immutable collection) 데 이 터 를 처리 하 는 방식 이 항상 부족 한 것 같다. 예 를 들 어 집합 에서 좌우 로 점차적으로 이동 하 는 것 은 moveNext, movePrev 등 이다. 집합 중간 에 추가, 업데이트,삭제 기능 이 더욱 미 비 한 것 은 조작 효율 문제 때문이다.가 변 집합 은 선행 조작 (prepend operation) 만 이 신뢰성 있 는 효율 을 얻 을 수 있다. 즉, 첫 번 째 요 소 를 집합 하 는 조작 은 O (1) 에 해당 하 는 속 도 를 얻 을 수 있 고 다른 조작 은 대체적으로 O (n) 속도 이 며 n 은 집합 길이 이다. 즉, 집합 길이 가 증가 함 에 따라 조작 효율 은 배수 로 떨어진다.또 다른 이 유 는 프로 그래 밍 할 때 매우 불편 하 다 는 것 이다. 대부분의 프로그램 이 각종 집합 에 대해 대량의 조작 을 하기 때문에 결국은 프로그램의 복잡 하고 비대 하 며 함수 식 프로 그래 밍 요구 에 부합 되 지 않 는 간단 하고 우아 한 표현 형식 을 초래 할 수 있다.위 와 같은 여러 가지 이유 로 scalaz 는 Zipper typeclass 를 제공 하여 가 변 집합 작업 에 대한 프로 그래 밍 을 도 왔 다 고 생각 합 니 다.Zipper 의 정 의 는 다음 과 같 습 니 다: scalaz / Zipper. scala
final case class Zipper[+A](lefts: Stream[A], focus: A, rights: Stream[A])

이 는 Stream 을 바탕 으로 A 는 기본 유형 이나 고급 유형 에 관 계 없 이 모든 유형 이 될 수 있다.Zipper 의 구 조 는 위 와 같 습 니 다. 현재 초점 창, 왼쪽 데이터 요소, 오른쪽 일련의 지퍼 와 같 기 때문에 Zipper 라 고 부 릅 니 다.아니면 이렇게 보면 좀 더 이미지 가 있 을 것 같 아 요.
final case class Zipper[+A]( lefts: Stream[A], focus: A, rights: Stream[A])

scalaz 는 Zipper 구축 함 수 를 제공 하여 Stream 으로 Zipper 를 직접 생 성 할 수 있 습 니 다.
trait StreamFunctions { ... final def toZipper[A](as: Stream[A]): Option[Zipper[A]] = as match { case Empty   => None case h #:: t => Some(Zipper.zipper(empty, h, t)) } final def zipperEnd[A](as: Stream[A]): Option[Zipper[A]] = as match { case Empty => None case _     => val x = as.reverse Some(Zipper.zipper(x.tail, x.head, empty)) } ...

zipperEnd 정렬 된 Zipper 생 성:
1   Stream(1,2,3).toZipper                          //> res2: Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 1, <rights>))
2   Stream("A","B","C").toZipper                    //> res3: Option[scalaz.Zipper[String]] = Some(Zipper(<lefts>, A, <rights>))
3   Stream(Stream(1,2),Stream(3,4)).toZipper        //> res4: Option[scalaz.Zipper[scala.collection.immutable.Stream[Int]]] = Some(Z 4                                                   //| ipper(<lefts>, Stream(1, ?), <rights>))
5   Stream(1,2,3).zipperEnd                         //> res5: Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 3, <rights>))

scalaz 도 List, NonEmptyList 에 Zipper 구축 함 수 를 제공 합 니 다.
trait ListFunctions { ... final def toZipper[A](as: List[A]): Option[Zipper[A]] = stream.toZipper(as.toStream) final def zipperEnd[A](as: List[A]): Option[Zipper[A]] = stream.zipperEnd(as.toStream) ... final class NonEmptyList[+A] private[scalaz](val head: A, val tail: List[A]) { ... def toZipper: Zipper[A] = zipper(Stream.Empty, head, tail.toStream) def zipperEnd: Zipper[A] = { import Stream._ tail.reverse match { case Nil     => zipper(empty, head, empty) case t :: ts => zipper(ts.toStream :+ head, t, empty) } } ...

스 트림 으로 전환 해서 지퍼 를 만 드 는 거 야.Zipper 자체 의 구축 함 수 는 zipper 입 니 다. NonEmpty List 의 Zipper 생 성 에서 호출 된 적 이 있 습 니 다.
trait ZipperFunctions { def zipper[A](ls: Stream[A], a: A, rs: Stream[A]): Zipper[A] = Zipper(ls, a, rs) }

이 직렬 구조의 구축 함수 로 Zipper 를 만 드 는 것 도 간단 합 니 다.
1 List(1,2,3,4).toZipper                          //> res0: Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 1, <rights>))
2   List(List(1,2),List(2,3)).toZipper              //> res1: Option[scalaz.Zipper[List[Int]]] = Some(Zipper(<lefts>, List(1, 2), <r 3                                                   //| ights>))
4   NonEmptyList("A","C","E").toZipper              //> res2: scalaz.Zipper[String] = Zipper(<lefts>, A, <rights>)
5   NonEmptyList(1,2,3).zipperEnd                   //> res3: scalaz.Zipper[Int] = Zipper(<lefts>, 3, <rights>)
6  

직렬 집합 Zipper 구축 방법 이 있 으 면 Zipper 의 좌우 유동 함 수 를 살 펴 보 겠 습 니 다.
final case class Zipper[+A](lefts: Stream[A], focus: A, rights: Stream[A]) { ... /** * Possibly moves to next element to the right of focus. */ def next: Option[Zipper[A]] = rights match { case Stream.Empty => None case r #:: rs     => Some(zipper(Stream.cons(focus, lefts), r, rs)) } /** * Possibly moves to next element to the right of focus. */ def nextOr[AA >: A](z: => Zipper[AA]): Zipper[AA] = next getOrElse z /** * Possibly moves to the previous element to the left of focus. */ def previous: Option[Zipper[A]] = lefts match { case Stream.Empty => None case l #:: ls     => Some(zipper(ls, l, Stream.cons(focus, rights))) } /** * Possibly moves to previous element to the left of focus. */ def previousOr[AA >: A](z: => Zipper[AA]): Zipper[AA] = previous getOrElse z /** * Moves focus n elements in the zipper, or None if there is no such element. * * @param n number of elements to move (positive is forward, negative is backwards) */ def move(n: Int): Option[Zipper[A]] = { @tailrec def move0(z: Option[Zipper[A]], n: Int): Option[Zipper[A]] =
      if (n > 0 && rights.isEmpty || n < 0 && lefts.isEmpty) None else { if (n == 0) z else if (n > 0) move0(z flatMap ((_: Zipper[A]).next), n - 1) else move0(z flatMap ((_: Zipper[A]).previous), n + 1) } move0(Some(this), n) } /** * Moves focus to the start of the zipper. */ def start: Zipper[A] = { val rights = this.lefts.reverse ++ focus #:: this.rights this.copy(Stream.Empty, rights.head, rights.tail) } /** * Moves focus to the end of the zipper. */ def end: Zipper[A] = { val lefts = this.rights.reverse ++ focus #:: this.lefts this.copy(lefts.tail, lefts.head, Stream.empty) } /** * Moves focus to the nth element of the zipper, or the default if there is no such element. */ def moveOr[AA >: A](n: Int, z: => Zipper[AA]): Zipper[AA] = move(n) getOrElse z ...

start, end, move, next, previous 이동 방식 이 모두 완비 되 었 습 니 다.그리고 위치 함수:
... /** * Moves focus to the nearest element matching the given predicate, preferring the left, * or None if no element matches. */ def findZ(p: A => Boolean): Option[Zipper[A]] =
    if (p(focus)) Some(this) else { val c = this.positions std.stream.interleave(c.lefts, c.rights).find((x => p(x.focus))) } /** * Moves focus to the nearest element matching the given predicate, preferring the left, * or the default if no element matches. */ def findZor[AA >: A](p: A => Boolean, z: => Zipper[AA]): Zipper[AA] = findZ(p) getOrElse z /** * Given a traversal function, find the first element along the traversal that matches a given predicate. */ def findBy[AA >: A](f: Zipper[AA] => Option[Zipper[AA]])(p: AA => Boolean): Option[Zipper[AA]] = { @tailrec def go(zopt: Option[Zipper[AA]]): Option[Zipper[AA]] = { zopt match { case Some(z) => if (p(z.focus)) Some(z) else go(f(z)) case None    => None } } go(f(this)) } /** * Moves focus to the nearest element on the right that matches the given predicate, * or None if there is no such element. */ def findNext(p: A => Boolean): Option[Zipper[A]] = findBy((z: Zipper[A]) => z.next)(p) /** * Moves focus to the previous element on the left that matches the given predicate, * or None if there is no such element. */ def findPrevious(p: A => Boolean): Option[Zipper[A]] = findBy((z: Zipper[A]) => z.previous)(p) ...

조작 함 수 는 다음 과 같다.
... /** * An alias for insertRight */ def insert[AA >: A]: (AA => Zipper[AA]) = insertRight(_: AA) /** * Inserts an element to the left of focus and focuses on the new element. */ def insertLeft[AA >: A](y: AA): Zipper[AA] = zipper(lefts, y, focus #:: rights) /** * Inserts an element to the right of focus and focuses on the new element. */ def insertRight[AA >: A](y: AA): Zipper[AA] = zipper(focus #:: lefts, y, rights) /** * An alias for `deleteRight` */ def delete: Option[Zipper[A]] = deleteRight /** * Deletes the element at focus and moves the focus to the left. If there is no element on the left, * focus is moved to the right. */ def deleteLeft: Option[Zipper[A]] = lefts match { case l #:: ls     => Some(zipper(ls, l, rights)) case Stream.Empty => rights match { case r #:: rs     => Some(zipper(Stream.empty, r, rs)) case Stream.Empty => None } } /** * Deletes the element at focus and moves the focus to the left. If there is no element on the left, * focus is moved to the right. */ def deleteLeftOr[AA >: A](z: => Zipper[AA]): Zipper[AA] = deleteLeft getOrElse z /** * Deletes the element at focus and moves the focus to the right. If there is no element on the right, * focus is moved to the left. */ def deleteRight: Option[Zipper[A]] = rights match { case r #:: rs     => Some(zipper(lefts, r, rs)) case Stream.Empty => lefts match { case l #:: ls     => Some(zipper(ls, l, Stream.empty)) case Stream.Empty => None } } /** * Deletes the element at focus and moves the focus to the right. If there is no element on the right, * focus is moved to the left. */ def deleteRightOr[AA >: A](z: => Zipper[AA]): Zipper[AA] = deleteRight getOrElse z /** * Deletes all elements except the focused element. */ def deleteOthers: Zipper[A] = zipper(Stream.Empty, focus, Stream.Empty) ... /** * Update the focus in this zipper. */ def update[AA >: A](focus: AA) = { this.copy(this.lefts, focus, this.rights) } /** * Apply f to the focus and update with the result. */ def modify[AA >: A](f: A => AA) = this.update(f(this.focus)) ...

insert, modify, delete 도 완비 되 어 있 습 니 다.주의해 야 할 것 은 대부분의 Zipper 의 이동 함수 와 조작 함수 가 Option [Zipper [A] 유형 으로 돌아 가 는 것 입 니 다. 그러면 우 리 는 flatMap 으로 이 동작 들 을 모두 연결 할 수 있 습 니 다.다시 말 하면 우 리 는 for - comprehension 으로 Option 의 context 에서 명령 프로 그래 밍 (imperative programming) 을 실현 할 수 있다.우 리 는 몇 가지 예 를 통 해 Zipper 의 용법 을 시범 할 수 있다.
 1 val zv = for {  2     z <- List(2,8,1,5,4,11).toZipper  3     s1 <- z.next  4     s2 <- s1.modify{_ + 2}.some  5   } yield s2                                      //> zv : Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 10, <rights>))
 6   
 7   zv.get.show          //> res8: scalaz.Cord = Zipper(Stream(2), 10, Stream(1,5,4,11))
 8   zv.get.toList        //> res9: List[Int] = List(2, 10, 1, 5, 4, 11)
 9 ... 10 val zv = for { 11     z <- List(2,8,1,5,4,11).toZipper 12     s1 <- z.next 13     s2 <- s1.modify{_ + 2}.some 14     s3 <- s2.move(1) 15     s4 <- s3.delete 16   } yield s4                                      //> zv : Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 5, <rights>))
17   
18   zv.get.show       //> res8: scalaz.Cord = Zipper(Stream(10,2), 5, Stream(4,11))
19   zv.get.toList     //> res9: List[Int] = List(2, 10, 5, 4, 11)
20 ... 21 val zv = for { 22     z <- List(2,8,1,5,4,11).toZipper 23     s1 <- z.next 24     s2 <- s1.modify{_ + 2}.some 25     s3 <- s2.move(1) 26     s4 <- s3.delete 27     s5 <- s4.findZ {_ === 11} 28     s6 <- if (s5.focus === 12) s5.delete else s2.insert(12).some 29   } yield s6                                      //> zv : Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 12, <rights>))
30   
31   zv.get.show        //> res8: scalaz.Cord = Zipper(Stream(10,2), 12, Stream(1,5,4,11))
32   zv.get.toList      //> res9: List[Int] = List(2, 10, 12, 1, 5, 4, 11)
33 ... 34 val zv = for { 35     z <- List(2,8,1,5,4,11).toZipper 36     s1 <- z.next 37     s2 <- s1.modify{_ + 2}.some 38     s3 <- s2.move(1) 39     s4 <- s3.delete 40     s5 <- s4.findZ {_ === 11} 41     s6 <- if (s5.focus === 12) s5.delete else s2.insert(12).some 42     s7 <- s6.end.delete 43     s8 <- s7.start.some 44   } yield s8                                      //> zv : Option[scalaz.Zipper[Int]] = Some(Zipper(<lefts>, 2, <rights>))
45   
46   zv.get.show         //> res8: scalaz.Cord = Zipper(Stream(), 2, Stream(10,12,1,5,4))
47   zv.get.toList       //> res9: List[Int] = List(2, 10, 12, 1, 5, 4)

나 는 위의 프로그램 에서 for {...} yield 에 명령 을 하나씩 추가 하여 커서 의 현재 초점 과 집합 요소 의 변 화 를 시범 합 니 다.이 절 차 는 명령 절차 라 고 할 수 있다.위 에서 언급 한 효율 과 코드 품질 토론 으로 돌아 가자.우리 가 scalaz 가 Zipper 를 제공 하 는 것 은 집합 작업 프로 그래 밍 을 더욱 간단명료 하고 우아 하 게 하기 위해 서 라 고 말 한 적 이 있 는데 실제 상황 은 어 떻 습 니까?
예 를 들 어 List (1, 4, 7, 9, 5, 6, 10) 와 같은 숫자 가 있 습 니 다. 저 는 첫 번 째 높 은 요 소 를 찾 고 싶 습 니 다. 왼쪽 이 낮 고 오른쪽 이 높 습 니 다. 우리 의 예 에서 요소 9 입 니 다.만약 우리 가 습관 적 인 명령 방식 으로 색인 으로 이 함 수 를 작성 하려 고 한다 면:
def peak(list: List[Int]): Option[Int] = { list.indices.find { index => val x = list(index) index > 0 && index < list.size - 1 && x > list(index - 1) && x > list(index + 1) }.map(list(_)) }

와!이 물건 은 매우 복잡 하고 이해 하기 어 려 울 뿐만 아니 라 효율 도 떨 어 지기 때문에 find 색인 을 반복 해서 사용 하면 속도 가 O (n * n) 로 떨어진다.Array 를 사용 하면 효율 을 O (n) 로 높 일 수 있 지만, 우 리 는 immutable 방식 을 사용 하고 싶 습 니 다.그럼 함수 식 프로 그래 밍 방식 으로 할 까요?
def peak_fp(list: List[Int]): Option[Int] = list match { case x :: y :: z :: tl if y > x && y > z => Some(y) case x :: tl => peak(tl) case Nil => None } 

패턴 매 칭 (pattern matching) 과 재 귀 알고리즘 (recursion) 을 사용 하면 프로그램 이 훨씬 보기 좋 고 효율 도 O (n) 로 높 일 수 있 습 니 다.
그러나 우 리 는 상황 을 좀 더 복잡 하 게 만 들 었 다. 높 은 점 수 를 좀 높 여 라 (+ 1).FP 로 작성 할 지:
def raisePeak(list: List[Int]): Option[List[Int]] = { def rec(head: List[Int], tail: List[Int]): Option[List[Int]] = tail match { case x :: y :: z :: tl if y > x && y > z => Some((x :: head).reverse ::: ((y +1) :: z :: tl)) case x :: tl => rec(x :: head, tl) case Nil => None } rec(List.empty, list) }

코드 가 또 비대 하고 복잡 해 지기 시작 했다.FP 프로 그래 밍 만 으로 는 부족 하고 새로운 데이터 구조 같은 것 으로 도 도움 이 필요 할 것 같다.scalaz 의 Zipper 는 이 장면 에서 도움 이 될 수 있 습 니 다.
def raisePeak_z(list: List[Int]): Option[List[Int]] = { for { zipper <- list.toZipper peak <- zipper.positions.findNext( z => (z.previous, z.next) match { case (Some(p), Some(n)) => p.focus < z.focus && n.focus < z.focus case _ => false }) } yield (peak.focus.modify(_ + 1).toStream.toList) }

Zipper 로 프로그램 을 써 서 많이 표현 하 세 요.여기에 Zipper. positions 를 사 용 했 습 니 다.
/** * A zipper of all positions of the zipper, with focus on the current position. */ def positions: Zipper[Zipper[A]] = { val left = std.stream.unfold(this)(_.previous.map(x => (x, x))) val right = std.stream.unfold(this)(_.next.map(x => (x, x))) zipper(left, this, right) }

positions 함수 반환 유형 은 Zipper [Zipper [A] 입 니 다. findNext 에 맞 게 사용 합 니 다.앞에서 언급 했 듯 이 Zipper 를 사용 하 는 비용 은 약 O (n) 이다.
 
 
 
 
 

좋은 웹페이지 즐겨찾기