Scala 编译时递归？
由于我昨天发布的有关 Scala 中元组的问题得到了一些有用的答案，因此我一直在研究 Scala HLists。我想从该问题中重新哈希一个 C++ 示例来问另一个问题：
在 C++ 中，可以使用模板专门化来实现编译时递归终止。我经常对 boost 元组进行此操作，就像 Scala/Haskell HList 一样，它是通过多次组合通用“cons”类型来构造的，每个相关类型一次，并以 null_type 终止。因此，
boost::tuple<int, std::string, float>
在底层实现为：
cons<int, cons<std::string, cons<float, null_type> > >
然后，我们可以编写一对在编译时在此结构上递归的函数，当第二个更专业的函数与最终的 cons 类型匹配时终止。下面显示了一个计算元素数量的简单示例：
template<typename T1, typename T2>
void countTupleElements( boost::tuples::cons<T1, T2>& tupleRec, int index, const std::vector<std::string>& vals )
{
return 1 + countTupleElements( tupleRec.tail );
}
template<typename T>
void countTupleElements( boost::tuples::cons<T, boost::tuples::null_type>& tupleRec, int index, const std::vector<std::string>& vals )
{
return 1;
}
至关重要的是，此模式通常用于您想要对每种元组元素类型执行不同操作的情况（我的示例中未说明）： 在 C++ 编译时递归中至关重要，因为一旦代码运行，类型信息就会丢失，无法用于所有有用的目的。
我的问题是，Scala HList 是否可能有类似的情况，例如，
val example = 1 :: 2.0 :: "Hello" :: "World" :: HNil
我知道在 JVM 上运行的 Scala 具有反射，因此大概可以使用运行时递归以及使用清单和模式匹配的函数来实现。但我有兴趣知道是否可以使用编译时递归来执行类似于 C++ 示例的操作？
As a result of some helpful answers to a question I posted yesterday about tuples in Scala, I've been looking at Scala HLists. I'd like to re-hash a C++ example from that question to ask another:
In C++ one can implement compile-time recursion terminated using template specialization. I've often done this operating on boost tuples which, like Scala/Haskell HLists are constructed by composing the generic 'cons' type multiple times, once for each relevant type and terminating with null_type. So this:
boost::tuple<int, std::string, float>
is implemented under the hood as:
cons<int, cons<std::string, cons<float, null_type> > >
We can then write a pair of functions that recurse at compile-time over this structure, terminating when the second, more-specialized function matches the final cons type. A simple example, counting the number of elements is shown below:
template<typename T1, typename T2>
void countTupleElements( boost::tuples::cons<T1, T2>& tupleRec, int index, const std::vector<std::string>& vals )
{
return 1 + countTupleElements( tupleRec.tail );
}
template<typename T>
void countTupleElements( boost::tuples::cons<T, boost::tuples::null_type>& tupleRec, int index, const std::vector<std::string>& vals )
{
return 1;
}
Crucially this pattern is often used in circumstances where you want to do something different for each of the various tuple element types (not illustrated in my example): in C++ compile-time recursion is essential as once code is running, the type information is lost for all useful purposes.
My question is, is something similar possible with a Scala HList, e.g.
val example = 1 :: 2.0 :: "Hello" :: "World" :: HNil
I'm aware that Scala, running on the JVM, has reflection - and so presumably this could be implemented using run-time recursion with a function using manifests and pattern matching. But I'm interested in knowing if it's possible to do something similar to the C++ example, using compile-time recursion?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的，可以使用隐式参数来实现编译时递归。请参阅：
http://apocalisp.wordpress.com/ 2010/06/08/type-level-programming-in-scala/
http://jnordenberg.blogspot.com/2008/08/hlist-in -scala.html
Yes, it's possible to implement compile time recursion using implicit parameters. See:
http://apocalisp.wordpress.com/2010/06/08/type-level-programming-in-scala/
http://jnordenberg.blogspot.com/2008/08/hlist-in-scala.html
Joshua Suereth 的新书 Scala in Depth 中有一个很好的例子。第 7.4 节是“使用类型系统的条件执行”，它介绍了 HList 构造以及如何使用编译时递归来实现可以访问 HList 的特定元素的 IndexedView 类型。这用于实现 AtIndex 类型，该类型用于在编译时检索各个值。
There is an excellent example of this in the new book Scala in Depth by Joshua Suereth. Section 7.4 is "Conditional execution using the type system" and it introduces the HList construct and how you can use compile time recursion to implement an IndexedView type that can access a specific element of the HList. This is used to implement an AtIndex type which is used to retrieve individual values at compile time.
是的，你可以。请参阅我的博客文章，了解如何实现 SKI 演算。我还写过关于 循环展开和条件编译。最后的解决方案这个小谜题展示了本质如何实现编译时递归的一种方法。
Yes you can. See my blog post about how to implement the SKI calculus in Scala's type system for the most general case. I have also written about the more specific case of loop unrolling and conditional compilation. Finally the solution to this little puzzle shows the essence of one way how compile time recursion can be implemented.