Вставить элемент в список, по заданным индексам в Haskell

Question

Функция должна быть такой: insertElemAt :: a -> [Int] -> [a] -> [a].

примеры:

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]

Я знаю только новичка haskell (если с конвейером и рекурсией), но я изо всех сил пытался решить эту проблему, но это никогда не работает. Это моя самая последняя попытка:

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  

Я тоже пробовал что-то подобное, но кажется, что это хаотично c, я думаю, что первая лучше:

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

Может быть, мои шаблоны не хороши? Я пытался написать их многими способами. Я также должен иметь возможность работать с этой функцией и использовать ее в функции с именем insertElemsAt (:: [(a, Int)] -> [a] -> [a]), которая должна быть «общей» версией функции выше. Поэтому я должен быть в состоянии указать, в какую позицию какой элемент я хочу вставить. Так как я не могу сделать первый, я еще больше потерян с этим. Вот пример. Я не знаю, как я мог бы сделать это с помощью if-s и рекурсии в конвейере:

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]

Может кто-нибудь объяснить мне, как это сделать самым простым способом? Спасибо в Advnace за любую помощь!

Answer 1

Предполагая, что список индексов отсортирован, как @ AndyG говорит , это, вероятно, поможет, если вы будете отслеживать текущий индекс. Таким образом, вы можете реализовать такую ​​функцию, как:

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)

, где вам необходимо заполнить … части.

Здесь go, таким образом, является функцией, которая будет использовать рекурсию для вставки элементы. Базовый случай (1) - это когда список индексов, куда вы хотите вставить элементы, исчерпан, в этом случае мы можем вернуть сам список.

Если сам список исчерпан, case (2), но Есть еще пункты для заполнения, вам нужно будет составить список, в котором вы повторяете x количество элементов, которые вам еще нужно вставить.

В последнем случае (3) вы должны проверить, как индекс i сравнивается с первым индексом, в который нужно вставить элемент n. Если он равен, то вам нужно будет вставить элемент x и сделать рекурсию (где вы должны вызвать go). Если индекс больше текущего, вы получите элемент y, рекурс в конце списка и увеличите индекс счета.