CODEWITHSUNDEEP
functionsml
Anthony
Anthony

Reputation: 1

Putting last element of list in the first index "n" times SML

I'm trying to put the last element of a list in the front of the list while keeping the rest of the elements in the same order N times. I can do it once with this function, but I want to add another parameter to the function so that the function in called N times.

Code: 

fun multcshift(L, n) = 
if null L then nil
else multcshift(hd(rev L)::(rev(tl(rev L))));

Thanks

Upvotes: 0

Views: 447

Answers (1)

sshine
sshine

Reputation: 16145

To make the parameter n work, you need recursion. You need a base case at which point the function should no longer call itself, and a recursive case where it does. For this function, a good base case would be n = 0, meaning "shift the last letter in front 0 times", i.e., return L without modification.

fun multcshift(L, n) = 
  if n = 0
    then L
    else multcshift( hd(rev L)::rev(tl(rev L)) , n - 1 )

The running time of this function is terrible: For every n, reverse the list three times!

You could save at least one of those list reversals by not calling rev L twice. E.g.

fun multcshift (L, 0) = L
  | multcshift (L, n) =
    let val revL = rev L
    in multcshift ( hd revL :: rev (tl revL) , n - 1 ) end

Those hd revL and rev (tl revL) seem like useful library functions. The process of applying a function to its own output n times seems like a good library function, too.

(* Return all the elements of a non-empty list except the last one. *)
fun init [] = raise Empty
  | init ([_]) = []
  | init (x::xs) = x::init xs

(* Return the last element of a non-empty list. *)
val last = List.last

(* Shift the last element of a non-empty list to the front of the list *)
fun cshift L = last L :: init L

(* Compose f with itself n times *)
fun iterate f 0 = (fn x => x)
  | iterate f 1 = f
  | iterate f n = f o iterate f (n-1)

fun multcshift (L, n) = iterate cshift n L

But the running time is just as terrible: For every n, call last and init once each. They're both O(|L|) just as rev.

You could overcome that complexity by carrying out multiple shifts at once. If you know you'll shift one element n times, you might as well shift n elements. Shifting n elements is equivalent to removing |L| - n elements from the front of the list and appending them at the back.

But what if you're asked to shift n elements where n > |L|? Then len - n is negative and both List.drop and List.take will fail. You could fix that by concluding that any full shift of |L| elements has no effect on the result and suffice with n (mod |L|). And what if n < 0?

fun multcshift ([], _) = raise Empty
  | multcshift (L, 0) = L
  | multcshift (L, n) =
    let val len = List.length L
    in List.drop (L, len - n mod len) @
       List.take (L, len - n mod len) end

There are quite a few corner cases worth testing:

val test_zero = (multcshift ([1,2,3], 0) = [1,2,3])
val test_empty = (multcshift ([], 5); false) handle Empty => true | _ => false
val test_zero_empty = (multcshift ([], 0); false) handle Empty => true | _ => false
val test_negative = (multcshift ([1,2,3,4], ~1) = [2,3,4,1])
val test_nonempty = (multcshift ([1,2,3,4], 3) = [2,3,4,1])
val test_identity = (multcshift ([1,2,3,4], 4) = [1,2,3,4])
val test_large_n = (multcshift [1,2,3,4], 5) = [4,1,2,3])
val test_larger_n = (multcshift [1,2,3,4], 10) = [3,4,1,2])

Upvotes: 2

Related Questions