我打算编辑我的另一篇文章,但这对于它自己来说已经足够大了。
这是使用“类型魔法”的一种方法,但在我看来它有点不理想,因为它需要一个特定于特定数量参数的函数的提升函数(更多下文)。
让我们从定义递归数据类型开始
data RecT a = RecR a
| RecC (a -> RecT a)
因此,RecT 类型的变量可以只是一个包装结果 (RecR),也可以是一个持续递归 (RecC)。
现在,我们如何获取一些东西并将其转换为 Rect a 类型?
价值观很简单:
valRecT x = RecR x
RecR x 显然是 RecT a 类型。
一个接受一个参数的函数,比如 id 呢?
idRecT x = RecC $ \x -> RecR x
RecC 包装了一个函数,该函数接受一个变量并返回类型 RecT a。表达方式
\x -> RecR x
就是这样一个函数,因为我们之前观察到 RecR x 是 RecT a 类型。
更一般地,可以解除任何单参数函数:
lift1RecT :: (a -> a) -> RecT a
lift1RecT fn = RecC $ \a -> RecR $ fn a
我们可以通过在 RecC 中重复包装更深层嵌套的函数调用来概括这一点:
lift2RecT :: (a -> a -> a) -> RecT a
lift2RecT fn = RecC $ \b -> RecC $ \a -> RecR $ fn b a
lift3RecT :: (a -> a -> a -> a) -> RecT a
lift3RecT fn = RecC $ \c -> RecC $ \b -> RecC $ \a -> RecR $ fn c b a
好的,所以我们已经完成了所有这些工作,以将任意数量的参数的函数转换为单一类型,RecT a。我们如何使用它?
我们可以很容易地写出一层函数应用:
reduceRecT :: RecT a -> a -> RecT a
reduceRecT (RecC fn) = fn
reduceRecT _ = undefined
换句话说,reduceRecT 接受一个类型为 RecT a 的参数和另一个类型为 a 的参数,并返回一个新的 RecT a ,它已经减少了一级。
我们还可以将 Rect 内的已完成计算展开到结果中:
unrollRecT :: RecT a -> a
unrollRecT (RecR fn) = fn
unrollRecT _ = undefined
现在我们准备将参数列表应用于函数!
lApply :: [a] -> RecT a -> a
lApply [] fn = unrollRecT fn
lApply (l:ls) fn = lApply ls $ (reduceRecT fn) l
让我们首先考虑基本情况:如果我们完成了计算,我们只需解开结果并返回它。在递归的情况下,我们将参数列表减少一,然后通过将列表的头部应用于减少的 fn 来转换 fn,从而产生一个新的 RecT a。
让我们试一试:
lApply [2,5] $ lift2RecT (**)
> 32.0
那么,这种方式的优缺点呢?嗯,Template Haskell 版本可以做部分列表应用;此处介绍的等递归类型解决方案并非如此(尽管我们原则上可以通过一些丑陋来解决此问题)。类型解决方案还有一个缺点是有更多的样板代码与之关联:我们需要一个 listNRecT 来表示我们想要使用的所有 N。最后,如果我们想应用于混合变量类型的函数,那么将其推广到类似的元组解决方案要容易得多。
当然,另一个有趣的可能性是通过使用 Template Haskell 生成 listNRecT 函数来增强简洁性;这消除了一些样板,但在某种意义上购买了两种实现的缺点。