需要帮助了解延续功能

Question

这是一个说明CPS和尾递归的教学示例：

fun sum [] k = k 0
  | sum (x::xs) k = sum xs (fn y=>k(x+y));

我无法理解匿名函数 fn y=>k(x+y) 如何正确地汇总输入列表的元素。

据我了解，匿名函数意味着一个带有一个参数 y 的新函数，其中函数体调用带有参数 y+x 的原始函数 k。

如果我调用 sum [1,2,3,4,5] (fn x=>x);，我得到 15。如果我有 sum [1,2,3,4,5] (fn x=>3x);，答案是 45。因此，sum 函数的用户必须首先了解确切的细节sum 因为只有适当版本的 k 才会产生给定列表的总和。以这种方式让用户提供功能的实际目的是什么？

如果我是 sum 函数的编写者，我无法控制用户为 k 传递的内容。换句话说，我什至如何指定函数将做什么？

Answer 1

The user of the sum function hence would have to first understand the exact gory details of sum as only an appropriate version of k will produce the sum of the given list.

没有。一如既往，阅读文档就足够了，无需查看实现细节。您的 k 是 给定的 列表的确切总和 - 这才是最重要的。您应该将 k 理解为 output parameter (though without mutation); it is basically a callback

If I am the writer of the sum function, I cannot control what the user will pass in for k. In other words, how do I even specify what the function would do precisely?

你不需要关心用户传递了什么。您只需记录该函数的作用：它使用提供的 xs 列表的总和调用提供的 k。 return 的值并不重要。

What is the real-world purpose of having a user supplied function in such a manner?

如果走极端，您不需要 return continuation-passing style 中的任何值 - 您只需将其传递给回调即可。这使得调用堆栈变得多余。从另一个角度来看，每个函数确实以尾调用结束，可以优化掉而不是 returning.

Answer 2

I have problems understanding how [...] would sum up the elements of the input list correctly.

尝试手动评估您的函数：

sum [1,2,3] id
sum [2,3] (fn y1=>id(1+y1))
sum [3] (fn y2=>(fn y1=>id(1+y1))(2+y2))
sum [] (fn y3=>(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+y3))
(fn y3=>(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+y3)) 0
(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+0)
(fn y2=>(fn y1=>id(1+y1))(2+y2)) 3
(fn y1=>id(1+y1))(2+3)
(fn y1=>id(1+y1)) 5
id(1+5)
id(6)
6

因此，正如您所见，此函数在堆内存中构建了一系列最终相互调用的匿名函数。一个普通的递归函数会使用 stack space 作为等价物。

The user of the sum function hence would have to first understand the exact gory details of sum as only an appropriate version of k will produce the sum of the given list. What is the real-world purpose of having a user supplied function in such a manner?

正如 Bergi 所写，用户不需要了解 sum 函数的工作原理，只需要了解它以延续作为参数并在其基本情况下对其进行解析即可。正如 Bergi 还写道，它不必在其基本情况下评估 k。此函数的替代方法是：

fun sum [] k = k
  | sum (x::xs) k = sum xs (fn y=>k(x+y));

此处的一个应用程序以及导出带有回调作为参数和 return 值的 sum 函数的理由是，您可以通过这种方式将函数延迟链接在一起。例如，使用上述函数，您可以对列表的列表求和；

fun sumMany [] k = k
  | sumMany (xs::xss) k = sumMany xss (sum xs k)

你可能会这样评价它

val result = sumMany [[1,2,3],[4,5,6],[7,8,9]] (fn x=>x) 0

需要帮助了解延续功能

Need assistance understanding continuation function

functional-programming

sml

smlnj