Scala编译时递归？

Question

作为昨天我发布的有关Scala元组的问题的一些有用答案的结果，我一直在研究Scala HLists。我想重新讨论一个来自该问题的C++示例以提出另一个问题：

在C++中，可以使用模板特化实现编译时递归终止。我经常在boost元组上执行此操作，就像Scala/Haskell HLists一样，通过多次组合通用的“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++示例一样使用编译时递归来实现类似的功能？

- Alex Wilson

---

我不确定这里在问什么。但是考虑到你的问题的一般趋势，我想知道你是否看过关于Scala类型系统中的Church数和SKI演算的博客？ - Daniel C. Sobral

谢谢Daniel。你提供的各种建议非常有帮助。我也一直在ScalaQuery源代码中寻找灵感。 - Alex Wilson

你能否添加一个更有趣的案例示例，其中“您希望针对各种元组元素类型执行不同操作”的情况？ - Miles Sabin

Answer 1

是的，使用隐式参数可以实现编译时递归。请参阅以下链接：
http://apocalisp.wordpress.com/2010/06/08/type-level-programming-in-scala/
http://jnordenberg.blogspot.com/2008/08/hlist-in-scala.html

- Jesper Nordenberg

Answer 2

在 Joshua Suereth 的新书《Scala in Depth》中有一个很好的例子。第7.4节是“使用类型系统进行条件执行”，它介绍了 HList 构造和如何使用编译时递归来实现 IndexedView 类型，该类型可以访问 HList 的特定元素。这用于实现 AtIndex 类型，该类型用于在编译时检索单个值。

- iain

Answer 3

是的，你可以。请看我的博客文章，了解如何在Scala类型系统中实现SKI演算以获得最一般的情况。我还写过关于循环展开和条件编译更具体情况的文章。最后，这个小谜题的解决方案展示了如何实现编译时递归的本质。

- michid