SML：prefixSum 使用 addToEach 方法

Question

我正在努力解决这个问题，因为我不确定如何递归地实现它（我可以强制执行）。

列表 l 的前缀和是列表 s，其中 s 的第 i 个索引元素是 l 的前 i + 1 个元素的总和。

我必须使用 addToEach 函数，我写的如下：

fun addToEach(number : int, nil : int list) : int list = nil
    | addToEach(number : int, x::y : int list) =
        (x + number)::addToEach(number, y);

我想做的是遍历列表 l，假设我在索引 j 处，将索引 j 处的数字添加到列表 s 中的所有元素 0 - (j-1)。不过，不太确定如何递归执行此操作。

感谢您的帮助！

Answer 1

将给定索引处的数字添加到列表的其余部分（索引 j+1,j+2,... 而不是 0,...,j-1）的要点：

fun prefixSum [] = []
|   prefixSum (x::xs) = x::addToEach(x, prefixSum xs);

这里有一个不用 addToEach 的方法，它使用尾递归辅助函数：

fun prefixSum' (sums, []) = sums
|   prefixSum' ([], x::xs) = prefixSum' ([x],xs)
|   prefixSum' (y::ys, x::xs) = prefixSum' ((x+y)::y::ys,xs);

例如，prefixSum' [2,3,4,5] = [14,9,5,2]——这是向后的（当您使用尾递归函数构建列表时的常见问题）。所以——只需在主函数中反转它：

fun prefixSum xs = rev (prefixSum'([],xs));

SML：prefixSum 使用 addToEach 方法

SML: prefixSum using addToEach method

functional-programming

sml