Insert an element into a list, to the given indexes, in Haskell

Question

The function has to be like this: insertElemAt :: a -> [Int] -> [a] -> [a].

Examples:

insertElemAt 0 [2,5,9] [1..10] 
    = [1, 0, 2, 3, 0, 4, 5, 6, 0, 7, 8, 9, 10]

insertElemAt 0 [1,2,4,8] [0,1,0,0,1,1,0,1] 
    = [0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1]

I only know beginner Haskell (if with pipeline |, and recursion), but i tried my hardest to solve this, but it never works. This is my most recent attempt:

insertElemAt x [0] ys = ys
insertElemAt x [1,2] ys = x:x:ys
insertElemAt x [] ys = ys
insertElemAt x xs [] = []
insertElemAt x (n:ns) (y:ys) = y:insertElemAt x (n-1:ns) ys  

I also tried something like this, but this just seems to be chaotic, i think the first one is better:

insertElemAt :: a -> [Int] -> [a]-> [a] 
insertElemAt x [0] ys = ys
insertElemAt x [1,2] ys = x:x:ys
insertElemAt x (n:ns) (y:ys) = y:insertElemAt x (map reduc (n:ns)) ys 

reduc (n:ns) = n-1 : reduc ns

Maybe my patterns aren't good? I tried to write them in a lot of ways.

I also have to be able to work with this function and use it in a function called insertElemsAt (:: [(a, Int)] -> [a] -> [a]), which has to be a "general" version of the function above. So i have to be able to give in which position what kind of element i want to insert.

Since I can't do the first one, I'm even more lost with this one. Here is the example. I don't know how I could do this with pipeline if-s and recursion:

insertElemsAt (zip [0,1,1] [2,5,9]) [1..10] 
    = [1, 0, 2, 3, 1, 4, 5, 6, 1, 7, 8, 9, 10]

insertElemsAt (zip [0,1,1,1] [1,2,4,8]) [0,1,0,0,1,1,0,1] 
    = [0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1]

Could someone explain to me how to do this in the most simple way? Thank you in advance for any help!

Answer 1

Assuming that the list of indices is sorted, like @AndyG says, it will likely help if you keep track of the current index. You thus can implement a function like:

insertElemAt :: a -> [Int] -> [a] -> [a]
insertElemAt x = go 0
    where go _ [] ys = ys         -- (1)
          go i ns [] = …          -- (2)
          go i (n:ns) (y:ys) = …  -- (3)

where you need to fill in the … parts.

Here the go is thus a function that will use recursion to insert elements. The base case (1) is where the list of indices where you want to insert elements is exhausted, in that case we can return the list itself.

If the list itself is exhausted, case (2), but there are still items to fill in, you will need to make a list where you repeat x the number of items you still have to insert.

The last case (3) you have to check how the index i compares to the first index where you need to insert an element n. If it is equal, then you will have to insert the element x and make a recursion (where you should call go). If the index is greater than the current one, you yield the element y, and the recurse on the tail of the list and increment the acculator index.

Answer 2

You can start with what you already know:

insertElemAt 0 [
          2,       5,          9] 
      [1,    2, 3,    4, 5, 6,    7, 8, 9, 10] 
    = [1, 0, 2, 3, 0, 4, 5, 6, 0, 7, 8, 9, 10]

This is a perfectly valid definition, which will even produce a correct result, even if for the one very specific case, and diverge everywhere else.

But we can generalize it somewhat, as

insertElemAt _0 [
          2,         5,           9] 
      [1,     2, 3,     4, 5, 6,     7, 8, 9, 10] 
    = [1, _0, 2, 3, _0, 4, 5, 6, _0, 7, 8, 9, 10]

and still some more,

insertElemAt _0 [
          2,         5,           9] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
    = [a, _0, b, c, _0, d, e, f, _0, g, h, i, j ]

and we can add few more special cases which must obviously hold as well, like

insertElemAt _0 [
          2,         5] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
    = [a, _0, b, c, _0, d, e, f,     g, h, i, j ]

and

insertElemAt _0 [
          2] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
    = [a, _0, b, c,     d, e, f,     g, h, i, j ]

and even

insertElemAt _0 [
          ] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
    = [a,     b, c,     d, e, f,     g, h, i, j ]

; and we can generalize this one much further, as

insertElemAt _0 [] xs
    = xs

and it is obvious that

insertElemAt _0 [
          2] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
  =
       a : insertElemAt _0 [
          1]
             [b, c,     d, e, f,     g, h, i, j ]

and

insertElemAt _0 [
          2,         5] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
  =
       a : insertElemAt _0 [
          1,         4]
             [b, c,     d, e, f,     g, h, i, j ]

and in general

insertElemAt _0 (i:is) (x:xs)
    | i > 1  =  x : insertElemAt _0 (minus1 (i:is)) xs

must hold, so why don't we have it as a part of our definition as well; with

-- minus1 is = [i-1 | i <- is]

minus1 []      = _____
minus1 (i:is) = ( ____ - 1) : ______ is

(fill the blanks). And so for the i==1 case,

insertElemAt _0 (i:is) (x:xs)
    | i == 1  =  x : _0 : insertElemAt _0 (minus1 (_____)) xs
  -- or is it
  --             _0 : x : ........   ?

And so you're already halfway there. All that's left to do is add the few edge cases, and you're done.

Now it won't be the most efficient version, because it will repeatedly subtract 1 from the indices list's each member; you can streamline this part by adding one new auxiliary argument which would negate the need to subtract from each element of the indices list, and replace it with just one addition, counting up instead of counting down. To use that additional argument you'd have to define and use an auxiliary, nested function definition.