1

我们有一个列表 like[13,7,8,4]和一个数字N。我们想在该列表的末尾插入数量为“N mod ListSize”的元素（一些零）。假设N = 6，根据列表，ListSize 为 4。所以 6 mod 4 = 2 然后我必须在其中插入 2 个零，如下所示[13,7,8,4,0,0]：

我们如何通过 SML 中的函数来做到这一点？

4

1 回答 1

1

列表末尾的填充是O(n)操作。如果orig是您的原始列表并且zeroes是您要填充的零，则涉及在toorig @ zeroes的每个元素之前添加。origzeroes

组合方法是首先找到零的数量，然后创建这些零，然后附加它们。

fun numberOfZeroes xs n = n mod List.length xs

fun replicate x 0 = []
  | replicate x n = x :: replicate x (n-1)

fun zeroes xs n = replicate 0 (numberOfZeroes xs n)

fun pad xs n = xs @ zeroes xs n

xs您可以通过在附加零的同时计算 的长度来节省一次遍历（与单独的length/不同@）。组合函数可能如下所示：

fun pad xs n =
    let fun pad' (x::xs) count = x :: pad' xs (count + 1)
          | pad' [] count = replicate 0 (count mod n)
    in pad' xs 0 end

然而，这个函数不是尾递归的，所以对于大的xs它可能会耗尽堆栈空间。(replicate两者都不是，但只会产生长度为N的列表。) 要使其以一种或另一种方式进行尾递归，必须遍历列表两次。此外，从不太复杂的功能中构建复杂的功能会降低认知负荷。

最后，您对问题的描述非常好。下次当您对问题有类似的清晰描述时，请尝试编写一个正确实现将通过的测试。例如，您描述的测试是：

val test1 = pad [13,7,8,4] 6 = [13,7,8,4,0,0]

除了一项测试外，还可以添加更多测试，直到您定义了所有极端情况。例如：

val test2 = pad [13,7,8,4] 4 = ?
于 2017-01-31T22:46:28.693 回答