Inserting an integer into a list at specific place

Question

I want to make a program insertAt where z is the place in the list, and y is the number being inserted into the list xs. Im new to haskell and this is what I have so far.

insertAt :: Int-> Int-> [Int]-> [Int]
insertAt z y xs
  | z==1 = y:xs

but I'm not sure where to go from there.

I have an elementAt function, where

elementAt v xs
  | v==1 = head xs
  | otherwise = elementAt (v-1) (tail xs)

but I'm not sure how I can fit it in or if I even need to. If possible, I'd like to avoid append.

Answer 1

If this isn't homework: let (ys,zs) = splitAt n xs in ys ++ [new_element] ++ zs

For the rest of this post I'm going to assume you're doing this problem as homework or to teach yourself how to do this kind of thing.

The key to this kind of problem is to break it down into its natural cases. You're processing two pieces of data: the list you're inserting into, and the position in that list. In this case, each piece of data has two natural cases: the list you're procssing can be empty or not, and the number you're processing can be zero or not. So the first step is to write out all four cases:

insertAt 0 val []     = ...
insertAt 0 val (x:xs) = ...
insertAt n val []     = ...
insertAt n val (x:xs) = ...

Now, for each of these four cases, you need to think about what the answer should be given that you're in that case.

For the first two cases, the answer is easy: if you want to insert into the front of a list, just stick the value you're interested in at the beginning, whether the list is empty or not.

The third case demonstrates that there's actually an ambiguity in the question: what happens if you're asked to insert into, say, the third position of a list that's empty? Sounds like an error to me, but you'll have to answer what you want to do in that case for yourself.

The fourth case is most interesting: Suppose you want to insert a value into not-the-first position of a list that's not empty. In this case, remember that you can use recursion to solve smaller instances of your problem. In this case, you can use recursion to solve, for instance, insertAt (n-1) val xs -- that is, the result of inserting your same value into the tail of your input list at the n-1th position. For example, if you were trying to insert 5 into position 3 (the fourth position) of the list [100,200,300], you can use recursion to insert 5 into position 2 (the third position) of the list [200,300], which means the recursive call would produce [200,300,5].

We can just assume that the recursive call will work; our only job now is to convert the answer to that smaller problem into the answer to the original problem we were given. The answer we want in the example is [100,200,300,5] (the result of inserting 5 into position 4 of the list [100,200,300], and what we have is the list [200,300,5]. So how can we get the result we want? Just add back on the first element! (Think about why this is true.)

With that case finished, we've covered all the possible cases for combinations of lists and positions to update. Since our function will work correctly for all possibilities, and our possibilities cover all possible inputs, that means our function will always work correctly. So we're done!

I'll leave it to you to translate these ideas into Haskell since the point of the exercise is for you to learn it, but hopefully that lets you know how to solve the problem.

Answer 2

You could split the list at index z and then concatenate the first part of the list with the element (using ++ [y]) and then with the second part of the list. However, this would create a new list as data is immutable by default. The first element of the list by convention has the index 0 (so adjust z accordingly if you want the meaning of fist elemnt is indexed by 1).

insertAt :: Int -> Int-> [Int] -> [Int] 
insertAt z y xs = as ++ (y:bs)
                  where (as,bs) = splitAt z xs