int列表的累计和

Question

我实现了以下累计和功能：

fun cumsum_reverse (xs: int list) = 
  if null xs then [0]
  else
    let val tl_cumsum = cumsum_reverse (tl xs)
    in
      hd xs + hd tl_cumsum :: tl_cumsum
    end

fun reverse (first: int list, second: int list) =
  if null first
  then
    second
  else
    reverse (tl first, hd first :: second)

fun cumsum (xs: int list) = 
  tl(reverse(cumsum_reverse(reverse(xs, [])), []))

测试用例：

val test = cumsum[1,4,20] = [1,5,25]

有什么方法可以只用一个函数来实现吗？

Answer 1

当然，这是我想仍然使用多个函数的一种方式，但它只是一个帮手，可以保持累加和，并从0开始递归。

然而，递归循环完全发生在辅助函数中，该函数被命名为相同以故意隐藏第一个。

fun cumsum (xs : int list) =
  let fun cumsum (x::xs, sum) = let val foo = x + sum in foo::cumsum(xs, foo) end
        | cumsum ([], _) = []
  in cumsum (xs, 0) end

Answer 2

我会根据通用 scanl 函数来定义它。它类似于 foldl 但会生成一个中间结果列表。它的工作原理与累积和非常相似，但使用 + 运算符和默认元素参数化。它在标准库中不可用，但它也可能是。

fun scanl _ _ [] = []
  | scanl f y0 (x::xs) =
    let val y1 = f (x, y0)
    in y1 :: scanl f y1 xs
    end

然后：

val cumsum = scanl op+ 0

Is there any way to implement this using one function only?

这取决于你"one function only"的意思。

只有一个功能吗？ cumsum 只接受一个列表作为输入，您需要一个额外的参数来跟踪累计和。由于累加结果的函数不能直接cumsum，所以需要两个函数。所以你的意思是"one named function besides cumsum"？那么scanl或者matt的内部辅助函数就可以解决这个问题。

如果您只能使用标准库函数定义 cumsum：

val cumsum = tl o rev o foldl (fn (x, y::ys) => x + y :: y :: ys) [0]

然后 cumsum 成为您声明的唯一函数。

如果您只能使用单个标准库函数定义 cumsum，我会选择 foldl:

val cumsum = (fn (_::xs) => xs)  (* tl *)
           o foldl op:: []       (* rev *)
           o foldl (fn (x, y::ys) => x + y :: y :: ys) [0]

然后 cumsum 成为您声明的唯一函数，并且您只使用了一个命名的标准库函数来完成它。（如果它不是标准库函数，您必须声明它，然后您将声明两个函数。）

但这有点傻了。 :-)

int列表的累计和

Cumulative sum of int list

recursion

functional-programming

sml

smlnj