1

我正在通过阅读“Yet Another Haskell Tutorial”一书来学习haskell，但在涉及连续传递风格时遇到了一个问题。这本书给出了一个 cps 折叠，如：

cfold’ f z [] = z
cfold’ f z (x:xs) = f x z (\y -> cfold’ f y xs)

并给出测试结果：

CPS> cfold (+) 0 [1,2,3,4]
10
CPS> cfold (:) [] [1,2,3]
[1,2,3]

但是，当我尝试对此进行测试时，我发现有问题，ghci 给出：

*Main> cfold (+) 0 []

<interactive>:8:7:
    Occurs check: cannot construct the infinite type:
      t10 = (t10 -> t10) -> t10
    Expected type: t10 -> t10 -> (t10 -> t10) -> t10
      Actual type: t10 -> t10 -> t10
    In the first argument of `cfold', namely `(+)'
    In the expression: cfold (+) 0 []
    In an equation for `it': it = cfold (+) 0 []

这对我来说很有意义，所以我将 cps 的定义更改为如下内容：

cfold f z [] = z
cfold f z (x:xs) = (\y -> cfold f y xs) (f x z)

它工作正常：

*Main> cfold (+) 0 [1,2,3]
6

所以我的问题来了，这是书中的错误还是我在这里想念的东西？

4

2 回答 2

9

我不认为书中有错误。cfold'书中的函数采用连续传递风格的函数，因此您传递给的函数必须cfold'采用 3 个参数：累加器、当前列表元素和将结果传递给的延续。

(+)只接受两个参数，因为它不是 cps 风格，所以你不能使用 cfold' 函数。要使用 cfold' 对列表的元素求和，您可以编写：

> cfold' (\e acc cont -> cont (acc + e)) 0 [3,2,4]
9

请注意，lambda 接受三个参数：元素、累加器和延续。给定当前计算的结果，延续是一个表示“下一步做什么”的函数。因此，通过每次调用延续，您可以处理下一个元素。

那么，当我不调用延续时，你认为会发生什么？我可以停止以这种方式处理列表，以实现像 takeWhile 这样的东西吗？

> cfold' (\acc e cont -> if e <= 3 then cont (e : acc) else acc) [] [1,2..]
[3,2,1]

在这个例子中，当元素大于 3 时我们不调用延续，所以我们停止处理列表。否则，我们将元素添加到累加器中，这就是列表反向出现的原因。如示例所示，这适用于无限列表。

而且，您还可以编写一个函数，将任何非 cps 样式的 2 参数函数转换为 cps 样式：

toCps2 :: (a -> b -> c) -> (a -> b -> (c -> d) -> d)
toCps2 f = \a b c -> c (f a b)

此函数只是将应用非 cps 函数的结果传递给延续。您可以使用此函数来实现您的 cfold，它采用非 cps 样式的函数来折叠列表：

cfold :: (a -> b -> c) -> b -> [a] -> c
cfold f = cfold' (toCps2 f)

使用此功能，您现在可以使用 (+) 折叠您的列表：

> cfold (+) 0 [3,2,4]
9
于 2013-07-13T11:44:08.440 回答
2

在Yet Another Haskell Tutorial中也是cfold的定义

cfold f z l = cfold' (\x t g -> f x (g t)) z l

此功能cfold正在使用cfold'

在 WinHugs 环境中它工作正常。

于 2013-07-13T11:24:33.097 回答