用零填充列表末尾
Pad end of list with zeroes
我们有一个列表 [13,7,8,4]
和一个数字 N。我们想在该列表的末尾插入元素(一些零),数量为 "N mod ListSize"。假设 N = 6 并且根据列表,ListSize 为 4。所以 6 mod 4 = 2 然后我必须在其中插入 2 个零,如下所示:[13,7,8,4,0,0]
.
我们如何通过 SML 中的函数来做到这一点?
列表末尾的填充是一个 O(n) 操作。如果 orig
是您的原始列表,而 zeroes
是您要填充的零,则 orig @ zeroes
涉及将 orig
的每个元素添加到 zeroes
.
组合方法是首先找到零的数量,然后创建这些零,然后追加它们。
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
但是,此函数不是 tail-recursive,因此对于大型 xs
,它可能 运行 出栈 space。 (replicate
也不是,但只会生成长度为 N 的列表。)要使其成为 tail-recursive,不管怎样,必须遍历列出两次。此外,用不太复杂的函数构建复杂的函数可以减少认知负担。
最后,你对问题的描述很好。下次您对问题有类似清晰的描述时,请尝试编写一个正确的实现将通过的测试。例如。您描述的测试是:
val test1 = pad [13,7,8,4] 6 = [13,7,8,4,0,0]
除了一个测试之外,添加更多测试,直到您定义了所有极端情况。例如:
val test2 = pad [13,7,8,4] 4 = ?
我们有一个列表 [13,7,8,4]
和一个数字 N。我们想在该列表的末尾插入元素(一些零),数量为 "N mod ListSize"。假设 N = 6 并且根据列表,ListSize 为 4。所以 6 mod 4 = 2 然后我必须在其中插入 2 个零,如下所示:[13,7,8,4,0,0]
.
我们如何通过 SML 中的函数来做到这一点?
列表末尾的填充是一个 O(n) 操作。如果 orig
是您的原始列表,而 zeroes
是您要填充的零,则 orig @ zeroes
涉及将 orig
的每个元素添加到 zeroes
.
组合方法是首先找到零的数量,然后创建这些零,然后追加它们。
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
但是,此函数不是 tail-recursive,因此对于大型 xs
,它可能 运行 出栈 space。 (replicate
也不是,但只会生成长度为 N 的列表。)要使其成为 tail-recursive,不管怎样,必须遍历列出两次。此外,用不太复杂的函数构建复杂的函数可以减少认知负担。
最后,你对问题的描述很好。下次您对问题有类似清晰的描述时,请尝试编写一个正确的实现将通过的测试。例如。您描述的测试是:
val test1 = pad [13,7,8,4] 6 = [13,7,8,4,0,0]
除了一个测试之外,添加更多测试,直到您定义了所有极端情况。例如:
val test2 = pad [13,7,8,4] 4 = ?