무료 모나드가있는 스택리스 스칼라

Question

다음 코드는 논문 (R. O. Bjarnason, 무료 모나드가있는 스택리스 스칼라)에서 수정되었습니다.

이 논문의 제목은 제안 된 데이터 구조의 목적을 총체적으로 - 즉, 일정한 스택 공간에서 재귀 적 처리를 허용하고 사용자가 명확한 방식으로 재귀를 표현할 수 있도록하는 것을 가리킨다.

필자의 목표는 오름차순 상수 스택 공간에서 간단한 패턴 일치를 기반으로하는 불변의 트리 (이진 트리) 또는 목록 (n-ary-tree)의 구조적 다시 쓰기를 제공하는 모나 딕 구조를 갖는 것입니다.

sealed trait Free[S[+_], +A]{ 
    private case class FlatMap[S[+_], A, +B](
    a: Free[S, A], 
    f: A => Free[S, B] 
) extends Free[S, B] 

    def map[B](f: A => B): Free[S, B] = this.flatMap((a:A) => Done[S, B](f(a))) 

    def flatMap[B](f: A => Free[S, B]): Free[S, B] = this match { 
    case FlatMap(a, g) => FlatMap(a, (x: Any) => g(x).flatMap(f)) 
    case x => FlatMap(x, f) 
    } 

    @tailrec 
    final def resume(implicit S: Functor[S]): Either[S[Free[S, A]], A] = { 
    this match { 
     case Done(a) => Right(a) 
     case More(k) => Left(k) 
     case FlatMap(a, f) => a match { 
     case Done(a) => f(a).resume 
     case More(k) => Left(S.map(k)((x)=>x.flatMap(f))) 
     case FlatMap(b, g) => b.flatMap((x: Any) => g(x).flatMap(f)).resume 
     } 
    } 
    } 
} 

case class Done[S[+_], +A](a: A) extends Free[S, A] 

case class More[S[+_], +A](k: S[Free[S, A]]) extends Free[S,A] 

trait Functor[F[+_]] { 
    def map[A, B](m: F[A])(f: A => B): F[B] 
} 

type RoseTree[+A] = Free[List, A] 

implicit object listFunctor extends Functor[List] { 
    def map[A, B](a: List[A])(f: A => B) = a.map(f) 
} 
var tree : Free[List, Int]= More(List(More(List(More(List(Done(1), Done(2))), More(List(Done(3), Done(4))))), More(List(More(List(Done(5), Done(6))), More(List(Done(7), Done(8))))))) 

무료를 사용하여 재 작성하는 방법은 무엇입니까?

패턴 일치 자의 후크는 어디에 있습니까? - 오름차순으로 패턴 매처를 각 전체 하위 트리에 노출해야합니다!

for 블록 내에서이 작업을 수행 할 수 있습니까? [. 문제는 편집 된]

Answer 1

업데이트 : 주소 질문 an earlier version 아래의 대답은하지만입니다 대부분 여전히 관련.

---

우선 코드가 그대로 작동하지 않습니다. 모든 것을 불변으로 만들거나 원본 종이에 분산 주석을 넣을 수 있습니다. 단순함을 위해 불변 경로 (전체 예제는 here 참조)를 취할 것이지만,이 문서의 버전이 2.10.2에서 작동 할 것이라는 사실도 확인했습니다.

첫 번째 질문에 먼저 답하십시오. 이진 트리 유형은 BinTree[Int]과 동형입니다. 우리는이를 표시 할 수 있습니다 전에 그러나, 우리는 우리의 쌍 유형에 대한 펑이 필요합니다

def from(tree: T): BinTree[Int] = tree match { 
    case L(i) => Done(i) 
    case F((l, r)) => More[Pair, Int]((from(l), from(r))) 
} 

def to(tree: BinTree[Int]): T = tree.resume match { 
    case Left((l, r)) => F((to(l), to(r))) 
    case Right(i) => L(i) 
} 

:

implicit object pairFunctor extends Functor[Pair] { 
    def map[A, B](a: Pair[A])(f: A => B) = (f(a._1), f(a._2)) 
} 

이제 우리는 우리가 T 다시 BinTree에서 변환해야합니다 resume을 사용할 수 있습니다 의 우리의 동형 및 BinTree의 모나드을 보여 보자

var z = 0 
def f(i: Int): T = if (i > 0) F((f(i - 1), f(i - 1))) else { z = z + 1; L(z) } 
val tree = f(3) 

:

이제 우리는 예를 들어 트리를 정의 할 수 있습니다 그것의 전임자와 후임자가 들어있는 나무와 모든 잎 값을 대체하여 :

val newTree = to(
    from(tree).flatMap(i => More[Pair, Int]((Done(i - 1), Done(i + 1)))) 
) 

을 일부 재 포맷 한 후, 그 결과는 다음과 같이 표시됩니다 등등

F((
    F((
    F((
     F((L(0), L(2))), 
     F((L(1), L(3))) 
    )), 
    F((
     F((L(2), L(4))), 
     F((L(3), L(5))) 
    )), 
    ... 

과, 예상대로.

두 번째 질문 : 장미 나무에 대해 동일한 종류의 작업을 수행하려는 경우 목록을 스트림 (또는 스트림)으로 바꾸십시오. 위에서 설명한대로 펑 터 인스턴스를 제공해야합니다. 나뭇잎이 Done(x)이고 분기가 More(xs) 인 트리가 있습니다.

---

당신의 유형은 일할 수있는 for -comprehension 구문 map이 필요합니다. 이제

def map[B](f: A => B): Free[S, B] = this.flatMap(f andThen Done.apply) 

다음 정확히 newTree 상기와 동일합니다 :

val newTree = to(
    for { 
    i <- from(tree) 
    m <- More[Pair, Int]((Done(i - 1), Done(i + 1))) 
    } yield m 
) 

같은 다행히 당신은 Free의 정의에 다음을 추가 - 그냥 flatMap 및 Done의 측면에서 map을 쓸 수 있습니다 것은 Free[List, _] 장미 나무와 함께 작동합니다.