We have a list like [13,7,8,4] and a number N. We want to insert elements (some zeroes) at the end of that list with the number of N mod ListSize. Suppose that N = 6 and according to the list, ListSize is 4.
6 mod 4 = 2. So, we have to insert 2 zeroes at the end of list like [13,7,8,4,0,0].
How can we do this by a function in SML?
Padding at the end of a list is a O(n) operation. If orig is your original list and zeroes is the zeroes you're padding, orig @ zeroes involves prepending every single element of orig to zeroes.
The compositional approach would be to first find the number of zeroes, then create those zeroes, and then append them.
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
You could save one traversal by counting the length of xs at the same time as you are appending the zeroes (unlike separate length/@). A combined function might look like this:
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
This function, however, isn't tail-recursive, so for large xs it might run out of stack space. (replicate isn't either, but will only produce lists of length N.) To make it tail-recursive, one way or the other, one must traverse the list twice. Also, building complex functions out of less complex functions decreases cognitive load.
Lastly, your description of the problem was very fine. The next time you have a similarly clear description of a problem, try and write a test that a correct implementation will pass. E.g. the test you described was:
val test1 = pad [13,7,8,4] 6 = [13,7,8,4,0,0]
Besides one test, add more until you've defined all the corner cases. For example:
val test2 = pad [13,7,8,4] 4 = ?