New to SML / NJ. Making a custom insert function

Question

Define a function that, given a list L, an object x, and a positive integer k, returns a copy of L with x inserted at the k-th position. For example, if L is [a1, a2, a3] and k=2, then [a1, x, a2, a3] is returned. If the length of L is less than k, insert at the end. For this kind of problems, you are supposed not to use, for example, the length function. Think about how the function computes the length. No 'if-then-else' or any auxiliary function.

I've figured out how to make a function to find the length of a list

fun mylength ([]) = 0
| mylength (x::xs) = 1+ mylength(xs)

But, as the questions states, I can't use this as an auxiliary function in the insert function. Also, i'm lost as to how to go about the insert function? Any help or guidance would be appreciated!

Answer 1

Here's how to do this. Each recursive call you pass to the function tail of the list and (k - 1) - position of the new element in the tail of the list. When the list is empty, you construct a single-element list (which was given to you); when k is 0, you append your element to what's left from the list. On the way back, you append all heads of the list that you unwrapped before.

fun kinsert [] x k = [x]
  | kinsert ls x 0 = x::ls
  | kinsert (l::ls) x k = l::(kinsert ls x (k - 1))

I used a 0-indexed list; if you want 1-indexed, just replace 0 with 1.

As you can see, it's almost the same as your mylength function. The difference is that there are two base cases for recursion and your operation on the way back is not +, but ::.

Edit

You can call it like this

kinsert [1,2,3,4,5,6] 10 3;

It has 3 arguments; unlike your length function, it does not wrap arguments in a tuple.

Answer 2

Here's how I'd approach it. The following assumes that the list item starts from zero.

fun mylength (lst,obj,pos) =
    case (lst,obj,pos) of
        ([],ob,po)=>[ob]
          | (xs::ys,ob,0) => ob::lst
          | (xs::ys,ob,po) => xs::mylength(ys,obj,pos-1)