如何有效遍历递归案例类树 [英] How to efficiently traverse recursive case-class trees

问题描述

我想创建一个宏，该宏生成类似于访问者模式的案例类实例树的递归遍历.生成的代码应针对其类型源自多种基本类型之一的所有字段进行递归.

我想到了一些可以与此类似使用的代码:

 特征A性状B特质C案例D扩展了A {}案例E扩展了C {}案例类F(a:A，b:B，c:Int)扩展了A案例类G(d:C，e:String)扩展了Bval instanceOfA = F(D，G(E，"Foo")，1)//遍历中应包含的预期类型额外类型//vv vvtraverse [A，B，C](handlerForA，handlerForB，handlerForC)(instanceOfA) 

遍历的类型类似于以下内容(我知道这不是有效的语法，但无法提出更好的语法)

  def traverse [T，U ...](handleT:T =>单位，handleU ...:U ... =>单位):T =>单位=宏遍历 

我知道Scala不支持可变参数泛型，但是我不明白为什么不应该有一种通过宏来实现类似目标的方法.但是我还没有找到一种允许将多种类型作为参数传递给def宏的方法.

解决方案

在我看来，经过一番调查后发现，您的问题比乍看之下要复杂一些.我草拟了一个解决方案，其中基于 Monocle :

而不是宏使用DSL.

 导入单片眼镜导入monocle.macros.GenLens案例类Nested [A，B](aToB:Lens [A，B]，handleB:B => Unit){def from [C](cToA:Lens [C，A]):Nested [C，B] = Nested(cToA composeLens aToB，handleB)def nest(nested:Nested [B，_] *):Seq [Nested [A，_]] = this +:nested.map(_.from(aToB))}def traverse [A](handleA:A => Unit)(配置:Nested [A，A] => Seq [Nested [A，_]]):A =>单位=值=>configure(Nested(Lens.id [A]，handleA)).foreach {case Nested(lens，handler)=>处理程序(lens.get(值))} 

但是，当我开始对其进行测试时，我发现了一个问题:

  val t =遍历[F](handlerForA)(_.nest(嵌套(GenLens [F](_.a)，handlerForA)，嵌套(GenLens [F](_.b)，handlerForB)，//如何放置handlerForC?))t(instanceOfA) 

我可以使用handlerForC ...因为您的原始类型不是仅产品类型.A可能有不同的实现，B和C也是如此.

那么，我们可以尝试在考虑副产品的情况下生成一些更复杂的解决方案吗?好吧，就您的确切示例而言，它不是-如果您的类/特征是密封的，并且所有(直接)实现都必须在同一文件中实现，则编译器只能派生已知的直接子类.

但是，假设您将 A ， B 和 C 密封了.在这种情况下，我将以某种方式尝试使用Prism，以便仅在可能的情况下才进入内部(或使用模式匹配或任何其他等效解决方案).但这使DSL变得复杂-我想为什么决定首先查看宏的原因.

因此，让我们重新考虑问题.

您必须编写的代码将是:

• 考虑从产品类型中提取值
• 考虑到副产品类型上的分支
• 为每种(副产品)类型使用提供的处理程序
• 最大限度地减少编写的代码量

这个要求听起来很难实现.现在，我在考虑是否可以通过使用递归方案更快地实现目标，如果您创建了一个公共父级对于所有特征，将所有类提升"到 Id ，然后编写一个遍历函数和一个应用处理程序的遍历函数.

当然，所有这些都可以使用def宏以一种或另一种方式实现，但是问题是现在将要求以它们现在的方式，要确保它不会做不好的事情是非常困难的，因为我们对输出有非常严格的要求(即使每个嵌套的案例都嵌套，也要找到它们)，而对输入的要求则非常宽松(最小上限为 Any / AnyRef ，层次结构未密封).我不确定只要您不想更改任何假设或要求，运行时反射是否不是实现目标的简单方法.

I want to create a macro that generates a recursive traversal of a tree of case class instances similar to the visitor pattern. The generated code should recurse for all fields whose type is derived from one of multiple base types.

I thought about some code that could be used similar to this:

trait A
trait B
trait C

case object D extends A { }
case object E extends C { }
case class F (a: A, b: B, c: Int) extends A
case class G (d: C, e: String) extends B
val instanceOfA = F (D, G (E, "Foo"), 1)

// expected type   extra types that should be included in traversal
//       vv        vv
traverse[A,        B, C] (handlerForA, handlerForB, handlerForC) (instanceOfA)

The type of traverse would be something like the following (I know this isn't valid syntax but couldn't come up with any better):

def traverse[T, U...] (handleT : T => Unit, handleU... : U... => Unit) : T => Unit = macro traverseImpl

I know that Scala can't support variadic generics but I don't see why there shouldn't be a way to achieve something like this with macros. But I haven't found a way that allows to pass multiple types as arguments to a def macro.

解决方案

After some investigation is appears to me that your problem is slightly more complicated than it seems on the first sight. I drafted a solution where instead of macros I used DSL based on Monocle:

import monocle.Lens
import monocle.macros.GenLens

case class Nested[A, B](aToB: Lens[A, B], handleB: B => Unit) {

  def from[C](cToA: Lens[C, A]): Nested[C, B] = Nested(cToA composeLens aToB, handleB)

  def nest(nested: Nested[B, _]*): Seq[Nested[A, _]] = this +: nested.map(_.from(aToB))
}

def traverse[A](handleA: A => Unit)(configure: Nested[A, A] => Seq[Nested[A, _]]): A => Unit =
  value => configure(Nested(Lens.id[A], handleA)).foreach { case Nested(lens, handler) =>
    handler(lens.get(value))
  }

However, as soon as I started testing it I figured out an issue:

val t = traverse[F](handlerForA)(_.nest(
  Nested(GenLens[F](_.a), handlerForA),
  Nested(GenLens[F](_.b), handlerForB),
  // how to put handlerForC?
))

t(instanceOfA)

I was usable to use handlerForC... because your original types were not product types-only. A might have different implementations, B and C as well.

So, could we try to generate some more complex solution where coproducts are taken into account? Well, with your exact example not - compiler is only able to derive known direct subclasses if your class/trait is sealed and all (direct) implementations have to be implemented in the same file.

But let's say you made A, B and C sealed. In such case I would somehow try to use Prism, in order to step inside only when possible (or use pattern matching or any other equivalent solution). But that complicates the DSL - the reason I guess why do decided to look at the macros in the first place.

So, lets rethink the issue anew.

Code that you would have to write would:

• take into account extracting values from products types
• take into account branching on coproduct types
• make use of provided handlers for each (coproduct) type
• minimize the amount of code written

This requirements sounds difficult to achieve. Right now I am thinking if you could achieve your goal faster by using recursive schemes if you created a common parent for all traits, "lifted" all your classes to Id and then writing one traversing function and one which applies handlers.

Of course all of that could be implemented one way or the other using def macros, but the thing is will requirements in the way they are now I would be extremely difficult to make sure that it won't do something bad, as we have pretty strict requirements for the output (for each handled cases find them even if they are nested) while very relaxed requirements on the input (least upper bound is Any/AnyRef, hierarchies are not sealed). I am not sure if runtime reflection wouldn't be easier way to achieve your goals as long as you don't want to change any assumption or requirements.

这篇关于如何有效遍历递归案例类树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！